Consensus: Raft & Paxos

Many distributed systems need exactly one thing to be true: a set of independent, failure-prone machines must agree on a single value — who the leader is, what the next entry in the log is, what the current config says. This is the consensus problem, and it is the beating heart of etcd, ZooKeeper, Spanner, Kafka’s controller, and the control plane of nearly every platform you’ll touch. It sounds trivial (“just take a vote”) and is, in fact, one of the deepest results in computer science. This page builds it from why it’s hard up to how Raft and Paxos actually work.

Why agreement is hard

On one machine, agreement is free: there’s one decider. Distribute it, and two demons appear.

First, nodes fail — they crash mid-decision, leaving others unsure whether a value was chosen. Second, the network is unreliable: messages drop, delay, and reorder, so a silent node is indistinguishable from a dead one (the same ambiguity from the overview). A correct consensus algorithm must guarantee, despite all this:

• Agreement — no two nodes decide different values.
• Validity — the decided value was actually proposed by someone (no inventing values).
• Termination — every non-failing node eventually decides.

The FLP impossibility result

Fischer, Lynch, and Paterson proved in 1985 that in a fully asynchronous network (no bound on message delay), no deterministic algorithm can guarantee all three properties if even one node may crash — you cannot tell “crashed” from “slow,” so you can be forced to wait forever. Real systems escape this not by breaking the proof but by sidestepping it: they use timeouts (a partial synchrony assumption) to make progress, accepting that they might occasionally stall and retry rather than violate agreement. Consensus algorithms never sacrifice safety; they only ever gamble on liveness.

The key tool: quorums (majority)

The mechanism that makes consensus possible is the quorum — requiring agreement from a majority of nodes (more than half). Majorities have one magical property:

Any two majorities of the same set must overlap in at least one node.

5-node cluster. A majority is 3.

   Majority X: {A, B, C}        Majority Y: {C, D, E}
                    └──── overlap at C ────┘

  C "remembers" what X decided and tells Y. No two majorities
  can decide conflicting things, because some node is in BOTH.

That overlap is how the system avoids two different decisions: any new majority is guaranteed to include at least one node that witnessed the previous one. It’s also why clusters are sized odd — 3, 5, 7. A 5-node cluster tolerates 2 failures (3 remain to form a majority); a 6-node cluster also only tolerates 2 (you still need 4 for majority of 6), so the sixth node buys you nothing but cost. The general rule: to tolerate f failures you need 2f + 1 nodes.

Raft: consensus you can actually understand

Paxos came first and is correct, but notoriously hard to follow. Raft (Ongaro & Ousterhout, 2014) was designed explicitly for understandability, and it now underlies etcd, Consul, and TiKV. It decomposes consensus into three digestible pieces.

1. Leader election

Raft elects a single leader; all writes flow through it, which sidesteps the chaos of everyone proposing at once. Time is divided into numbered terms (a logical clock — see Time, Clocks & Ordering). Each node is a follower, candidate, or leader.

Follower hears nothing from a leader for a random timeout
        │  (randomness prevents everyone timing out at once)
        ▼
Becomes CANDIDATE → increments term → requests votes from all nodes
        │
        ├─ wins a MAJORITY of votes ──────────────► becomes LEADER
        ├─ hears from a leader with ≥ its term ────► steps back to FOLLOWER
        └─ split vote (no majority) ───────────────► new term, try again

A node votes for at most one candidate per term, and only for a candidate whose log is at least as up-to-date as its own. Combined with the majority requirement, this guarantees at most one leader per term — the overlap property again.

2. Log replication

The leader appends each client command to its log and replicates it to followers via AppendEntries messages. An entry is committed once a majority have stored it — at which point it’s safe to apply, because any future leader is guaranteed (by the up-to-date-log voting rule) to already contain every committed entry. The followers’ logs converge to match the leader’s, in order.

3. Safety

The two rules above interlock to give Raft its core guarantee: if any node has applied an entry at a given log index, no other node will ever apply a different entry at that index. One log, one truth, replicated.

Why a leader makes consensus tractable

Leaderless agreement (every node proposing freely) is possible but turbulent — competing proposals can stall each other indefinitely. Funneling all writes through one leader turns the hard “agree on an order” problem into the easy “copy the leader’s log” problem, and reduces the only truly contentious moment to electing the leader. The cost: the leader is a throughput bottleneck and a single point of focus whose failure triggers an election pause (typically a sub-second blip).

Paxos, at a high level

Paxos (Lamport, 1998) solves the same problem with a different shape. A proposer runs a two-phase protocol against a quorum of acceptors:

1. Prepare — the proposer picks a monotonically increasing proposal number n and asks acceptors to promise not to accept anything numbered below n. If a majority promise (and report any value they’ve already accepted), the proposer proceeds.
2. Accept — the proposer asks the majority to accept value v at number n. If a value was already reported in phase 1, the proposer is obligated to reuse it — this is the rule that preserves agreement across rounds.

Basic Paxos decides a single value; Multi-Paxos chains it to agree on a log of values (and, in practice, elects a stable leader to skip phase 1 on the common path — converging on the same leader-based shape as Raft). Raft and Multi-Paxos are, under the hood, close cousins; Raft just packages the moving parts so humans can hold them in their heads.

What it powers — and what it costs

Consensus is the foundation that lets a cluster behave like a single linearizable machine for the data that must never disagree: etcd (Kubernetes’ brain), ZooKeeper (HBase coordination — and Kafka’s, until Raft-based KRaft replaced it in Kafka 4.0), Spanner, CockroachDB, distributed locks, and leader election itself (next page: Leader Election & Coordination). What does it buy us? A trustworthy single source of truth that survives a minority of failures. What does it cost? Every committed decision requires a majority round-trip — so writes are slower than a single node, the cluster halts if it can’t reach a majority (it chooses CP), and you pay for 2f + 1 machines to tolerate f failures. That price is exactly why you run consensus only for the small, critical core of state, and keep the bulk of your data on cheaper, weaker stores.

Under the hood — even reads need a quorum

It’s tempting to think only writes need consensus and a leader can answer reads from memory for free. It can’t — not safely. A leader that’s been partitioned away may not yet know it’s been deposed; a newer leader could have committed writes it hasn’t seen, making its “current” value stale. Serving that read would break linearizability. Raft systems close this with one of two mechanisms: a leader lease (serve reads only within a time-bounded lease, assuming bounded clock drift), or ReadIndex — before answering, the leader confirms with a majority that it’s still the leader and records the latest commit index, then waits for its state machine to reach that index. etcd uses ReadIndex by default. The cost is the lesson: a strongly-consistent read is not free, it’s a quorum round-trip in disguise — the PACELC latency tax, paid even on reads.

The architect’s lens

Consensus is expensive enough that where you run it is the real decision — interrogate it with the five questions:

• Why does it exist? Because many systems need exactly one thing true: a set of failure-prone machines must agree on a single value — who’s leader, the next log entry, the current config — and consensus is the only correct way to do that despite crashes and an unreliable network.
• What problem does it solve? It turns a cluster into a single linearizable source of truth that survives a minority of failures, guaranteeing agreement, validity, and termination through the overlap of majority quorums.
• What are the trade-offs? Every committed decision needs a majority round-trip, so writes are slower than a single node; you pay for 2f + 1 machines to tolerate f failures; the cluster halts if it can’t reach a majority (it deliberately chooses CP); and even strongly-consistent reads cost a quorum round-trip (leader lease or ReadIndex).
• When should I avoid it? For the bulk of your data. Run consensus only for the small, critical core (leader identity, locks, config); using it for high-throughput, partition-survivable data (shopping carts, timelines) squanders its cost — keep that on cheaper, weaker, AP stores.
• What breaks if I remove it? Without agreement, crashes and the crashed-vs-slow ambiguity let nodes decide different values — split-brain, two leaders, conflicting log entries — and the single source of truth everything depends on (etcd is Kubernetes’ brain) forks into two.

Check your understanding

1. State the three properties any consensus algorithm must satisfy, and explain why FLP says you can’t guarantee all three in a fully asynchronous network.
2. Why must any two majority quorums overlap, and how does that single fact prevent two conflicting decisions?
3. Why does a 6-node cluster tolerate no more failures than a 5-node one? Give the 2f + 1 reasoning.
4. In Raft, what two rules together guarantee at most one leader per term, and why is randomized election timeout important?
5. In Paxos, why is a proposer sometimes forced to reuse a value reported during the prepare phase rather than proposing its own?

Show answers

1. The three properties are agreement (no two nodes decide different values), validity (the decided value was actually proposed), and termination (every non-failing node eventually decides). FLP proved that in a fully asynchronous network you can’t guarantee all three if even one node may crash, because you cannot distinguish “crashed” from “slow” and so may be forced to wait forever. Real systems sidestep this with timeouts (partial synchrony) — they gamble on liveness but never on safety.
2. Any two majorities of the same set must share at least one node, because two subsets each larger than half can’t be disjoint. That single overlapping node remembers the previous decision and carries it into the next majority, so no two majorities can ever decide conflicting things.
3. A majority of 6 is 4, while a majority of 5 is 3 — both leave only enough room to lose 2 nodes. The general rule is 2f + 1 nodes to tolerate f failures, so the sixth node buys nothing but cost; clusters are sized odd (3, 5, 7) for exactly this reason.
4. A node votes for at most one candidate per term, and only for a candidate whose log is at least as up-to-date as its own; combined with the majority requirement, that yields at most one leader per term (the overlap property again). Randomized election timeouts matter because they prevent everyone from timing out and becoming candidates simultaneously, which would cause repeated split votes.
5. If a value was already reported during prepare, the proposer is obligated to reuse it rather than propose its own. This is the rule that preserves agreement across rounds: a value that may already have been chosen must not be overwritten by a later proposer with a higher number.