Oh My Learning

Consensus and Agreement (Paxos/Raft Foundations)

distributed-systems/10 staff drafted · 20 min read

Distributed Systems, 3rd ed. (van Steen & Tanenbaum), Chapter 8

Prerequisites distributed-systems/06 distributed-systems/07 distributed-systems/09 ddia/13

Consensus and Agreement (Paxos/Raft Foundations)#

TL;DR#

Consensus asks a set of processes to agree on a single value despite failures and network unreliability, and the FLP impossibility result proves this cannot be solved with a guaranteed time bound in a fully asynchronous system with even one crash failure - which is why every practical consensus protocol (Paxos, Raft) sacrifices liveness guarantees (it might not terminate in pathological conditions) rather than safety guarantees (it never agrees on two different values). Paxos solves this with proposers, acceptors, and learners negotiating over numbered proposals; Raft achieves the same safety property with a more understandable structure built around leader election and a replicated log. This is the staff-level anchor lesson of the subject because operating consensus-backed systems in production - leader changes, split-brain risk, quorum sizing - is where the theory meets real operational consequences.

The idea#

Many of the mechanisms earlier in this subject - electing a coordinator (Lesson 07), replicating data consistently (Lesson 08), tolerating failures without silent corruption (Lesson 09) - all reduce, at their core, to the same underlying problem: can a group of processes agree on one value, even when some of them might fail and messages might be delayed or lost? This is the consensus problem, and it is one of the most studied (and most consequential) problems in distributed computing, because so much else is built on top of it: leader election is a form of consensus ("agree on who the leader is"), replicated state machines need consensus on the order of operations, and distributed locks need consensus on who holds the lock.

Formally, a consensus protocol must satisfy three properties: - Agreement - no two correct processes decide on different values. - Validity - the value decided must have actually been proposed by some process (you can't just agree on an arbitrary value nobody suggested). - Termination - every correct process eventually decides some value.

The famous, sobering result in this area - the FLP impossibility result (Fischer, Lynch, Paterson, 1985) - proves that no deterministic consensus protocol can guarantee all three properties in a fully asynchronous system where even a single process might crash. This isn't a statement about clever engineering not having found the right algorithm yet; it's a mathematical proof that no such algorithm can exist under those exact assumptions. Understanding why this is true, and how real systems route around it, is the intellectual core of this lesson.

How it works#

1. Why consensus is impossible in general (FLP, explained intuitively)#

The FLP result assumes a fully asynchronous system: there is no bound on message delay and no bound on how long a process takes to respond - a message could take one millisecond or one thousand years, and you have no way to tell, mid-wait, which it will be. Combine that with the possibility of even a single crash failure, and here's the intuitive core of the impossibility argument:

Imagine a consensus protocol reaches a point where the group's collective decision hinges on one more message from one more process - call it process P. If P is slow (but not crashed), the protocol must eventually wait for P's message and proceed once it arrives. But because the system is asynchronous, no other process can ever distinguish "P is just very slow" from "P has crashed and will never respond" (this is precisely Lesson 01's crash-vs-slow ambiguity, now shown to have a formal, unavoidable consequence). If the protocol times out and proceeds without P (to guarantee termination), it risks reaching a different decision than it would have if P's message had arrived just before the timeout - risking the Agreement property being violated in some run. If the protocol always waits for P no matter how long (to guarantee it never decides wrongly), it risks never terminating if P really has crashed - violating Termination. FLP proves, rigorously, that you cannot always have it both ways: in an asynchronous system, any protocol that guarantees Agreement and Validity in every possible execution must, in at least some execution, fail to Terminate.

The practical takeaway is not "consensus is impossible, give up." It's that real systems achieve consensus by relaxing one of FLP's assumptions in a way that's acceptable in practice: - Assume partial synchrony - the network is asynchronous most of the time but eventually behaves synchronously long enough (bounded message delay, for some unknown-but-eventually-true period) for progress to happen. Both Paxos and Raft rely on this in practice: they remain safe (never violate Agreement) even during fully asynchronous, chaotic periods, but only make progress (Terminate) once the network settles into behaving predictably for long enough. - Use randomization - some consensus protocols use randomized timeouts (Raft's randomized election timers, discussed below) specifically to avoid the deterministic worst-case scenarios FLP's proof constructs, making non-termination a probability-zero-in-practice event rather than a guaranteed impossibility.

This is why every practical consensus protocol is correctly described as: safe always, live only eventually (under sufficiently good network conditions). That single sentence is the resolution of FLP that every staff engineer operating a Raft- or Paxos-backed system needs to internalize - it's the reason a consensus cluster can appear to "hang" (no progress) during a bad network partition without that being a bug; it's the protocol correctly refusing to risk an unsafe decision rather than guessing.

2. Paxos: the original, foundational protocol#

Paxos (Leslie Lamport, 1989/1998) solves consensus for a single value using three logical roles (a real process can play more than one role simultaneously): - Proposers - propose values for the group to agree on. - Acceptors - vote on proposals; a value is chosen once a majority of acceptors accept it. - Learners - learn what value was ultimately chosen (often just the proposers/acceptors themselves, or external observers).

Paxos proceeds in two phases, using proposal numbers (unique, increasing, and totally ordered - often (sequence_number, proposer_id) pairs to break ties) to establish precedence between competing proposals:

Phase 1 (Prepare/Promise). A proposer picks a proposal number n (higher than any it has used before) and sends PREPARE(n) to a majority of acceptors. Each acceptor that receives PREPARE(n) with n greater than any proposal number it has already promised to responds with PROMISE(n), promising never to accept any proposal numbered less than n again - and critically, if the acceptor has already accepted some earlier proposal, it includes that proposal's number and value in its promise reply.

Phase 2 (Propose/Accept). If the proposer receives promises from a majority of acceptors, it sends ACCEPT(n, v) - where v is either the value from the highest-numbered proposal reported by any acceptor in their promises (if any were reported - this is the crucial safety mechanism, explained below), or the proposer's own preferred value if no acceptor reported a previously-accepted value. Each acceptor that receives ACCEPT(n, v) accepts it (and tells learners) unless it has since promised a higher-numbered proposal in the meantime.

Why this is safe even with concurrent, competing proposers. The subtle, crucial insight is Phase 2's rule: a new proposer must adopt the value of any already-accepted proposal reported by a majority-overlapping acceptor set, rather than pushing its own preferred value. Because any two majorities of acceptors always overlap by at least one acceptor (a mathematical property of majorities over the same set), if a value was already chosen (accepted by a majority) in an earlier round, any later proposer's Phase 1 PREPARE must reach at least one acceptor that already accepted that value - and that acceptor's promise reply reveals it, forcing the later proposer to propose that same value rather than a conflicting one. This is the mechanism that guarantees Agreement even when multiple proposers race concurrently.

Worked example: a Paxos round with a competing proposer. Five acceptors (A1-A5). Proposer X sends PREPARE(1) to a majority (A1, A2, A3); all three promise (none has seen a higher number, none has accepted anything yet). X sends ACCEPT(1, "blue") to A1, A2, A3; all three accept - "blue" is now chosen (accepted by a majority). Suppose, concurrently, before learning of X's success, proposer Y sends PREPARE(2) to a different majority (A3, A4, A5). A3 - which already accepted (1, "blue") - replies PROMISE(2) but includes "I already accepted (1, blue)" in its response. A4 and A5 (having accepted nothing) reply with plain promises. Y, seeing that A3 reported an already-accepted value, is now forced by the protocol's rule to propose that same value in Phase 2: it sends ACCEPT(2, "blue") - not ACCEPT(2, "red") even if "red" was Y's own original preference - because A3's report revealed a majority had already chosen "blue." The overlap between X's majority {A1,A2,A3} and Y's majority {A3,A4,A5} (their common member, A3) is exactly what carried the already-chosen value forward and prevented Y from causing disagreement. This overlap-forces-agreement mechanism is the single most important thing to understand about why Paxos is safe.

Multi-Paxos. Running the full two-phase protocol for every single value (e.g., every entry in a replicated log) is expensive. Multi-Paxos optimizes this by electing a stable leader (via a Paxos round establishing "leadership" itself) that can skip Phase 1 for subsequent proposals as long as it remains the recognized leader - reducing the common case to a single round trip (just Phase 2) per log entry, only falling back to full two-phase negotiation when leadership changes.

3. Raft: consensus designed for understandability#

Raft (Diego Ongaro and John Ousterhout, 2014) was explicitly designed to achieve the same safety guarantees as Multi-Paxos while being dramatically easier to understand and implement correctly - a real, stated design goal, not an incidental benefit - by decomposing the problem into three clearly separated subproblems: leader election, log replication, and safety.

Leader election. Every Raft node is in one of three states: Follower, Candidate, or Leader, and time is divided into terms (monotonically increasing integers, each term having at most one leader). A follower that doesn't hear from a leader within a randomized election timeout (deliberately randomized, typically 150-300ms with jitter, specifically to avoid multiple followers becoming candidates simultaneously and splitting votes repeatedly - a direct, pragmatic answer to FLP's liveness challenge) transitions to Candidate, increments the term, votes for itself, and requests votes from every other node. A node grants its vote to at most one candidate per term (whichever asks first, with some additional log-freshness checks explained below), and a candidate that receives votes from a majority becomes the leader for that term, immediately sending heartbeats to establish authority and reset everyone's election timers.

Log replication. Once elected, the leader is the only node that accepts new writes from clients. Each write is appended to the leader's log and replicated to followers via AppendEntries RPCs; once a majority of nodes have durably stored an entry, the leader considers it committed and applies it to its own state machine, informing followers (via subsequent AppendEntries calls) that the entry is now safe to apply too. This is exactly the same majority-quorum idea as Paxos's acceptor majorities, just organized around a stable leader and an ordered log rather than independent per-value negotiation.

Safety: the election restriction. Raft's cleverest safety mechanism prevents a node with a stale, incomplete log from ever becoming leader (which would risk it overwriting already-committed entries that a more up-to-date node has, violating Agreement): during voting, a node refuses to grant its vote to a candidate whose log is less up-to-date than its own (compared by the term and index of the last log entry). Combined with the "committed = replicated to a majority" rule, this guarantees that any future leader is guaranteed to already have every previously committed entry in its log - because to win a majority vote, a candidate must get votes from at least one node that participated in every previous committed majority (the same overlapping-majorities argument as Paxos), and that node will have refused to vote for a candidate missing entries it already has.

Worked example: a leader change under Raft. A 5-node cluster (N1-N5) has N1 as leader in term 3, having committed log entries up to index 10 (replicated to at least N1, N2, N3 - a majority). N1 crashes. N2, N4, and N5 each independently time out at slightly different (randomized) moments; N2 times out first, becomes a Candidate for term 4, and requests votes. N3 checks: N2's log (up to index 10, matching what N3 has) is at least as up-to-date as N3's own - N3 grants its vote. N4 and N5, whose logs are behind (say, only up to index 8, having missed recent replication before N1 crashed), also check N2's request: since N2's log (index 10) is more up-to-date than their own (index 8), they too grant their votes - Raft's rule is about not voting for a candidate whose log is behind the voter's, and here N2's log is ahead of or equal to every voter's, so all votes are valid. N2 collects a majority (itself, N3, and at least one more) and becomes leader for term 4, with the guarantee - by construction - that it holds every entry that was ever committed under N1's term 3 leadership. If instead N4 (the node with the stale, index-8 log) had tried to become a candidate first, N2 and N3 (holding the more up-to-date index-10 log) would have refused to vote for it, precisely preventing the exact split-brain risk of a stale leader overwriting or losing already-committed data.

4. Why quorums must be a majority, and the split-brain risk#

Both Paxos and Raft require majority quorums (floor(N/2) + 1 out of N nodes) specifically because any two majorities of the same set of N nodes are mathematically guaranteed to overlap by at least one node - this overlap is what carries forward already-decided/committed values across leadership or proposal changes, as shown in both worked examples above. A quorum requirement smaller than a majority would not guarantee overlap, and could allow two disjoint groups to each independently believe they have "enough" votes to decide different, conflicting values - a genuine split-brain scenario where the safety guarantee (Agreement) is violated.

This has a direct, practical consequence for cluster sizing: a 5-node Raft/Paxos cluster tolerates 2 node failures (quorum of 3 still reachable) and remains available; if 3 of 5 nodes are unreachable (e.g., a network partition splitting the cluster 2-vs-3), only the side with 3 nodes (the majority side) can make progress - the minority side of 2 nodes correctly refuses to elect a leader or commit anything, because doing so could create a second, conflicting decision-maker. This is not a bug or a missed optimization; it is FLP's safety-over-liveness trade-off made concrete: the minority partition sacrifices availability (it stops making progress) specifically to guarantee it never diverges from the majority side's decisions. Even-numbered cluster sizes are a common operational mistake: a 4-node cluster requires a majority of 3, tolerating only 1 failure - the same fault tolerance as a 3-node cluster (which also tolerates 1 failure, requiring a majority of 2), but with an extra node's worth of operational and resource cost for no additional resilience. This is exactly why production Raft/Paxos deployments almost always use odd cluster sizes (3, 5, 7).

5. Operational nuance at staff level: evolution over time#

Running a consensus-backed system in production surfaces second-order concerns beyond the core algorithm: - Leader changes cause latency spikes, not silent transparency - every leader election pauses write availability for at least one election timeout (typically hundreds of milliseconds), and a cluster experiencing frequent, unnecessary leader churn (e.g., from overly aggressive timeout tuning, or from a genuinely flaky network) will show up as periodic latency spikes and occasional brief unavailability windows in production dashboards - this is a direct, observable cost of the safety-over-liveness trade-off, not a defect. - Cluster membership changes (adding/removing nodes) are themselves a consensus problem - naively swapping the voting membership (e.g., replacing a 5-node cluster's node set all at once) can create a window where two disjoint majorities exist simultaneously under old and new configurations, a genuine split-brain risk during reconfiguration itself. Raft addresses this with a joint-consensus (or, in a common simplification, single-node-change-at-a-time) approach, changing membership one node at a time so old and new majorities are guaranteed to overlap throughout the transition. - Quorum sizing is a capacity-planning decision with a real ceiling - adding more nodes to a consensus cluster does not increase write throughput (every write still needs majority agreement, and more nodes means more replication traffic per write, not less); it only increases fault tolerance and, often, read capacity (if reads can be served from any up-to-date follower). Staff-level system design recognizes that consensus clusters do not horizontally scale writes the way stateless services do - if write throughput needs to scale, the answer is partitioning/sharding data across multiple independent consensus groups, not growing one group's node count.

Pros#

  • Provides the strongest practical safety guarantee (Agreement) achievable in a system with crash failures and network unreliability - the foundation that strongly consistent replicated systems, distributed locks, and leader election are built on.
  • Paxos is proven, foundational, and highly optimizable (Multi-Paxos reduces the common case to one round trip).
  • Raft achieves the same safety with a dramatically more understandable structure, making correct implementation and operational reasoning much more tractable - a major reason it has become the default choice (etcd, Consul, CockroachDB, and many others) over classical Paxos in new systems.

Cons#

  • Consensus protocols pay a real latency cost - every committed write requires a majority round trip, meaning consensus-backed systems are inherently slower than an unreplicated single node or an eventually consistent alternative.
  • Availability is explicitly sacrificed during network partitions that split the cluster into a minority side - by design, not by accident, the minority stops making progress rather than risk unsafe divergence.
  • Does not scale write throughput horizontally by adding nodes - more nodes mean more fault tolerance, not more write capacity; scaling writes requires partitioning into multiple independent consensus groups.
  • Operational subtlety (membership changes, timeout tuning, monitoring leader-election frequency) requires real expertise; a naively-run consensus cluster can suffer avoidable churn and latency spikes.

Alternatives#

  • Eventually consistent / leaderless quorum systems (Lesson 08) - avoid consensus's coordination cost entirely by accepting weaker guarantees (conflicts resolved via vector clocks or last-writer-wins rather than prevented via agreement) - the right choice when the application can tolerate temporary divergence.
  • Byzantine fault-tolerant consensus (PBFT and blockchain-style protocols) - solve a strictly harder version of consensus (Lesson 09's Byzantine failure model) at the cost of requiring 3f+1 nodes and more message rounds, appropriate only when nodes cannot be assumed to fail merely by crashing (e.g., multi-party systems with no shared trust anchor).
  • Chain replication and other non-quorum strong-consistency schemes - achieve strong consistency by replicating writes through an ordered chain of nodes rather than a quorum vote, trading some latency/throughput characteristics differently than Paxos/Raft; used in some specialized high-throughput storage systems.

When to use it#

  • Use consensus (Paxos/Raft, typically via a mature implementation like etcd, ZooKeeper, or a database's built-in Raft layer) whenever you need a strongly consistent, highly available source of truth that must survive individual node failures without ever disagreeing with itself - distributed locks, leader election for other services, cluster configuration/metadata, and any replicated log that downstream state depends on.
  • Reach for it specifically when the cost of two nodes disagreeing (split-brain) is unacceptable - financial systems, coordination services, configuration that must be globally consistent.

When NOT to use it#

  • Don't use consensus for data or operations that can tolerate eventual consistency and don't need strict agreement - you'll pay real latency and availability cost for a guarantee the application doesn't need (Lesson 08's eventual/causal consistency models are cheaper and often sufficient).
  • Don't try to scale write throughput by adding more nodes to a single consensus group - it doesn't work that way; partition into multiple consensus groups instead if write throughput, not fault tolerance, is the bottleneck.
  • Don't use an even-numbered cluster size - it adds cost without adding fault tolerance versus the next-smaller odd size, and slightly increases the chance of an unresolvable tie during elections in some edge cases.
  • Don't build a custom consensus implementation from scratch for a production system - the subtlety of getting safety exactly right (as the Paxos and Raft worked examples show) is exactly the kind of thing where "it works in testing" hides serious bugs; use a mature, battle-tested implementation.

Key takeaways / mental model#

Consensus is provably impossible to solve with a guaranteed time bound in a fully asynchronous network with even one failure (FLP) - every real protocol responds by guaranteeing safety (Agreement) always, and liveness (Termination) only once the network behaves well enough for long enough. Paxos achieves safety through the overlapping-majorities trick: any new proposal must build on whatever a majority has already accepted, because any two majorities are guaranteed to share at least one member who knows about it. Raft achieves the identical safety property with a much more approachable structure - a single elected leader driving a replicated log, with an election rule that guarantees a new leader always already holds every previously committed entry. Quorums must be a strict majority for the overlap guarantee to hold, which is why cluster sizing, minority-partition unavailability, and no-write-scaling-by-adding-nodes are not implementation quirks but direct, load-bearing consequences of the mathematics underneath.

Self-check questions#

  1. State the FLP impossibility result precisely (what system model, what failure assumption, what's proven impossible), and explain intuitively why an asynchronous network makes "wait for a possibly-crashed process" and "guarantee timely termination" fundamentally incompatible.
  2. Walk through a scenario (like the worked example in this lesson) where two Paxos proposers propose concurrently, and explain exactly which mechanism forces them to converge on the same value rather than causing disagreement.
  3. Explain Raft's election-safety rule (a candidate's log must be at least as up-to-date as the voter's). What specific bad outcome does this rule prevent, and how does it connect to the overlapping-majority argument from Paxos?
  4. A team wants to grow their 5-node Raft cluster to 6 nodes for "more fault tolerance." What's wrong with this reasoning, and what would you recommend instead?
  5. During a network partition splitting a 5-node consensus cluster into groups of 2 and 3, the 2-node minority side stops accepting writes entirely, even though both of its nodes are healthy and reachable to each other. Explain why this is correct behavior rather than a bug, referencing the safety-over-liveness trade-off.

References#

  • Distributed Systems, 3rd ed. (van Steen & Tanenbaum), Chapter 8: Fault Tolerance (consensus/agreement sections)
  • M. Fischer, N. Lynch, M. Paterson, "Impossibility of Distributed Consensus with One Faulty Process" (1985)
  • Leslie Lamport, "The Part-Time Parliament" (Paxos, 1998) and "Paxos Made Simple" (2001)
  • Diego Ongaro and John Ousterhout, "In Search of an Understandable Consensus Algorithm (Raft)" (2014)
  • ddia/13 (Consistency and Consensus) - practical treatment of the same territory
  • distributed-systems.net (free companion site for the source book)