Consensus — Paxos and Raft

Imagine you have five bank servers. A customer deposits $100. Every server must agree on that fact. Not one server. Not a majority. Every server. Because if server 3 misses the memo and later becomes the "source of truth" after a failover, your $100 vanishes.

This is the consensus problem. It sounds trivial. It is one of the hardest problems in computer science. Leslie Lamport proved in 1985 (the FLP impossibility result) that no deterministic protocol can guarantee consensus in a fully asynchronous network with even one node failure. The problem is provably unsolvable. And yet, every production distributed system solves it every day — by making pragmatic assumptions the theorists didn't.

The two families of algorithms that make it work are Paxos (Lamport, 1998) and Raft (Ongaro & Ousterhout, 2014). Paxos came first, is more general, and is famously incomprehensible. Raft was designed explicitly to be understandable and has since become the default choice inside etcd, Consul, CockroachDB, TiKV, MongoDB (v4+), and Kafka (since 2.8's KRaft mode). This page is mostly about Raft — with a Paxos comparison at the end.

The core insight — one leader, majority quorum

Raft's big idea: elect one leader, funnel every write through it, and consider a write "committed" the moment a majority (⌊N/2⌋+1) of nodes have written it to their log. If the leader dies, hold an election among the survivors and pick a new one. Then the new leader keeps going.

The clever part isn't the leader idea — that's obvious. The clever part is how you ensure the new leader always has every committed entry. Raft's election rule guarantees that a candidate can't become leader unless it has at least as much of the log as any node that could form a quorum — because those nodes will refuse to vote for it otherwise. That refusal is the entire safety proof.

Three node states — Follower, Candidate, Leader

Every node in a Raft cluster is in exactly one of three states at any time:

• Follower — the default state. Listens for heartbeats from the leader. Applies commands the leader tells it to. Never initiates anything.
• Candidate — a follower that hasn't heard from the leader in ~150-300ms (the "election timeout"). Bumps the term counter, votes for itself, and asks every other node to vote.
• Leader — a candidate that got votes from a majority. Sends heartbeats every ~50ms so followers don't time out. Serves every read/write. Replicates every write to followers.

The Raft election — animated

Watch a 5-node cluster. The leader dies. One follower's election timeout fires first (randomized, 150-300ms). It becomes a candidate, bumps the term, requests votes. If it wins a majority (3 of 5), it becomes leader and starts sending heartbeats. Total wall-clock: ~200-500ms in the happy path.

Two subtle safety mechanisms make this work. First, each term has at most one leader — because to win, you need a majority, and any two majorities of the same cluster must overlap in at least one node, and that node can only vote once per term. Second, randomized election timeouts prevent split votes: if timeouts were fixed (say, exactly 150ms), all followers would time out simultaneously, all become candidates, all vote for themselves, and no one wins. Ongaro found that randomization in [150ms, 300ms] converges in 1-2 election rounds >99% of the time.

Log replication — how a write actually commits

Once the leader is elected, writes work like this: the client sends a command to the leader. The leader appends the command to its own log (uncommitted). It sends AppendEntries RPCs to every follower with that entry. When a majority (including the leader itself) has written the entry to their log, the leader marks it committed — meaning it will never be undone — and applies it to its state machine (executes the command). Followers apply the entry the next time they see a commitIndex advance in the leader's heartbeat.

The key insight: the write is durable the moment a majority has it in their log, not when everyone does. If 2 of 5 servers crash right after the write commits, the entry still survives on 3 nodes — a majority — so any future leader will have it.

Why odd numbers — the quorum arithmetic

Raft clusters are almost always odd-sized: 3, 5, or 7. Why? Because N=2f+1 tolerates f failures — you need a strict majority to make progress, and a strict majority of an even cluster is the same as of an odd cluster with one fewer node.

A cluster of 4 tolerates the same failure count (1) as a cluster of 3, but requires quorum 3 instead of 2 — so it's less available (needs 3 nodes reachable instead of 2) at the same cost of tolerating just 1 failure. Adding an even node never helps. This is why every production Raft cluster is 3, 5, or 7.

Split brain — the failure Raft prevents

Suppose the network partitions your 5-node cluster into a group of 3 and a group of 2. The group of 2 has the old leader — but it has lost majority. It can't commit any writes because it can't get 3 ACKs from a 2-node partition. Meanwhile the group of 3 elects a new leader (they still have majority) and continues serving writes.

When the partition heals, the old leader (in the minority) sees a term higher than its own coming from the new leader's heartbeat — and immediately steps down to follower. Any writes it accepted during the partition (which were never committed because they never got quorum) are silently rolled back from its log. This is Raft's split-brain safety: at most one leader per term, and the minority partition simply can't commit anything.

Paxos vs Raft — the family tree

Paxos was invented by Lamport in the late 1980s (published 1998). Its safety proof is airtight. Its explanation is famously confusing — Lamport wrote the paper as a story about a fictional Greek parliament and the community spent 20 years arguing about what it meant. Google's Chubby, Google Spanner, and Yahoo ZooKeeper all use Paxos variants. Raft came out of Stanford in 2014 with the explicit goal of doing the same thing more clearly. Today, most new systems pick Raft.

Applied in real systems — the deep dive

Every entry below is a real production system built on consensus. Each one made distinct choices about which family (Paxos vs Raft), how to handle multi-region, and how the leader interacts with the client protocol. Click any card for the full deep dive.

Key takeaways

• Consensus is provably impossible in the fully asynchronous model (FLP 1985) — but every practical algorithm uses timeouts to route around this and works in practice.
• Raft = elected leader + majority quorum + monotonic terms + randomized election timeouts. Those four ingredients cover safety, liveness, and split-brain protection.
• Cluster size is always N = 2f+1. Even-sized clusters are strictly worse: same failure tolerance, worse availability.
• Committed means "majority has it in log" — not "every node has it." The write survives even if the minority crashes, because any future leader is elected from a majority which by pigeonhole includes at least one node with the committed entry.
• Election completes in 1-2 randomized-timeout intervals — typically 200-500ms in production. This bounds your write-availability window during a leader failure.
• Every modern distributed database that offers strong consistency (Spanner, CockroachDB, TiDB, YugabyteDB, MongoDB v4+) uses either Raft or a Paxos variant. There is no third family.
• Paxos vs Raft is a pedagogical distinction more than a performance one — both achieve the same safety and similar latency. New systems overwhelmingly pick Raft because it's teachable.

References

• Fischer, Lynch, Paterson (1985) — "Impossibility of Distributed Consensus with One Faulty Process." JACM. The famous FLP result.
• Lamport (1998) — "The Part-Time Parliament." ACM TOCS. The original Paxos paper. Notoriously hard to read.
• Lamport (2001) — "Paxos Made Simple." The follow-up that admitted the first paper was confusing.
• Ongaro & Ousterhout (2014) — "In Search of an Understandable Consensus Algorithm." USENIX ATC 2014. The Raft paper.
• Ongaro (2014) — "Consensus: Bridging Theory and Practice." Stanford PhD thesis, 280 pages.
• Burrows (2006) — "The Chubby Lock Service for Loosely-Coupled Distributed Systems." OSDI 2006.
• raft.github.io — Ongaro's interactive Raft visualization. The gold standard.