Paxos, Raft, and the Shape of Consensus

Symptom

Your database has two nodes that both believe they are the primary.

Each has been accepting writes. Each has a coherent log. Neither has crashed. The old primary was declared dead by a health check that timed out during a GC pause, a new one was elected, and then the old one woke up still holding what it thinks is a valid lease. You now have two divergent histories of the same data and no principled way to merge them, because both contain acknowledged writes that customers were told had succeeded.

The other version of this failure is quieter. You run two-phase commit across two services. The coordinator sends PREPARE, both participants vote yes and take locks, and then the coordinator’s machine dies. The participants are now holding locks on rows they cannot release, because releasing them might violate atomicity and holding them blocks everything behind them. They will wait forever. There is no timeout that is safe.

Both failures are the same failure. Something had to be decided, and the decision was made by a component that could fail at exactly the wrong moment.

Statement

FLP (T062) says deterministic asynchronous consensus with one crash fault is impossible. Real systems run consensus every day. The resolution is precise, and it is the whole design pattern:

Practical consensus protocols guarantee safety unconditionally and liveness only during periods of synchrony. They never decide two different values, under any scheduling; they may fail to decide at all while the network misbehaves.

FLP is not violated because FLP forbids a protocol that always terminates. These protocols do not always terminate. They merely always terminate in practice, because the adversary that defeats them is a network that stays pathological forever, and real networks recover.

Argument

Paxos, in the only form worth memorizing. A proposer picks a ballot number $b$, higher than any it has used.

Phase 1 (prepare). Send $b$ to all acceptors. An acceptor that has not seen a higher ballot promises never to accept anything below $b$, and returns the highest-numbered value it has already accepted, if any.

Phase 2 (accept). On hearing from a majority, the proposer must propose the value returned with the highest ballot number, if any was returned; only if none was returned may it propose its own. It sends $(b, v)$; acceptors that have kept their promise accept.

The entire safety argument is in that italicized clause. It is the reason Paxos is correct and the reason it is confusing.

Why it is safe. Suppose value $v$ is chosen at ballot $b$, meaning a majority accepted $(b, v)$. Consider the smallest ballot $b’ > b$ at which any value $v’$ is accepted. The proposer of $b’$ collected promises from a majority. Two majorities intersect (T065), so at least one acceptor in that set had already accepted $(b, v)$ and reported it. The proposer was therefore obliged to propose $v$, so $v’ = v$. Induct upward and no ballot above $b$ can carry a different value. $\blacksquare$

The proof uses exactly two ingredients: quorum intersection, and the rule that a proposer adopts what it finds. Everything else in a Paxos implementation is performance.

Why it may not terminate. Two proposers can alternate. $P_1$ prepares at ballot 5, $P_2$ prepares at 6 invalidating it, $P_1$ retries at 7 invalidating $P_2$, forever. This is exactly the FLP scenario made concrete: no safety violation, no progress. Multi-Paxos fixes it by electing a distinguished proposer and skipping Phase 1 for subsequent entries, which turns steady-state commit into a single round trip. Leader election is a heuristic, and it has to be, because a correct one would violate FLP.

Raft is the same algorithm with the state space cut down. It makes three restrictions that are not required for safety but are required for comprehensibility:

• Strong leader. Log entries flow only leader to follower. Paxos allows any proposer to propose any slot, so a Paxos log can have holes; Raft’s cannot.
• Election restriction. A candidate cannot win unless its log is at least as up to date as a majority’s. This front-loads the “adopt the highest-numbered value” rule into the election, so the new leader is by construction the one that needs no catch-up. This is the single change that makes Raft feel simpler, and it is a restriction rather than a discovery.
• Terms as logical clocks. A monotonically increasing term number serves as ballot number, election epoch, and staleness detector at once.

Ongaro and Ousterhout then did what no other consensus paper did: they taught both to students and measured. Raft scored significantly higher on a quiz after equal instruction time. Whether or not you weight that evidence heavily, treating understandability as a stated design goal is why Raft is what new systems implement.

Where 2PC fits, and why it is not this. Two-phase commit has the same shape, prepare then commit, and one fatal difference: the commit decision rests on a single coordinator. When the coordinator fails after prepare, participants are stuck, because the outcome is knowable only to the dead node. 2PC is blocking, and the blocking is inherent rather than an implementation flaw. Three-phase commit adds a round to make the pending decision recoverable, and trades the blocking window for incorrectness under network partition, which is usually a worse deal.

The fix is to replicate the decision itself. Modern systems run 2PC where the coordinator’s state is itself a Paxos group, so a coordinator failure is a leader election rather than a stall. Spanner does exactly this, and it is why Spanner can offer cross-shard transactions without a blocking window: every participant leader is a Paxos group, and so is the coordinator.

What it costs. Steady-state Multi-Paxos or Raft commits in one round trip to a majority, so latency is the median replica’s round trip, not the slowest. With five replicas the third-fastest response commits. A leader failure costs an election timeout, typically 150 to 300 ms randomized to avoid split votes, plus a round of log reconciliation. That is the price of the FLP escape hatch, paid only when the leader dies.

Forbids

A consensus protocol that always terminates. Any implementation claiming to is either assuming synchrony without saying so, or is not solving consensus.

Safe unilateral timeout in 2PC. A prepared participant that cannot reach the coordinator cannot correctly abort or commit on its own. Any code that does is choosing to be wrong occasionally, which may be acceptable, but should be a documented decision rather than a timeout constant.

Split brain in a correctly implemented majority protocol. Two leaders in the same term cannot both collect majority support. If you observe split brain you have a bug, a misconfiguration, or a system that is not actually running a majority protocol, and the third case is more common than the first two.

Consensus with an even number of replicas being better than odd. Four replicas tolerate one failure, exactly as three do, at higher cost and higher latency for the majority.

Does not forbid

It does not forbid fast reads. A common misreading is that every read must run consensus. Leases let a leader serve reads locally without a round trip, as long as the lease is shorter than the election timeout. etcd, Consul, and Spanner all do this, and it is the difference between a 1 ms and a 5 ms read.

It does not forbid cross-datacenter consensus. It makes it expensive, not impossible. Spanner runs Paxos across continents and pays 50 to 100 ms of commit latency for it, and for the workloads that need global transactions that is the correct trade.

It does not mean you must implement it yourself. This is the misreading that causes the most damage. Consensus implementations are notoriously subtle; the Raft authors’ own TLA+ specification found bugs in implementations that passed extensive test suites. etcd, ZooKeeper, Consul, and FoundationDB exist so you do not have to, and using one of them as a coordination service while your own system stays stateless is nearly always the right architecture.

It does not forbid systems that skip consensus entirely. Most data does not need it. Dynamo-style quorums (T065) give read-your-writes at lower cost, and CRDTs (T067) avoid coordination altogether for the operations that permit it. Consensus is for the small set of decisions that must be unique: who is the leader, what is the cluster membership, which of two conflicting writes wins.

It does not say Paxos and Raft differ in what they guarantee. They provide the same safety and the same liveness conditions. The difference is entirely in the shape of the state space and therefore in the difficulty of implementing and debugging them, which is an engineering property rather than a theoretical one.

Boundary

• Crash faults only. Both assume nodes fail by stopping. A lying node breaks them, and needs $3f+1$ (T063) and a different protocol family.
• Liveness needs a stable leader. Repeated leader churn under a flapping network can starve progress indefinitely, and this is FLP arriving on schedule. Randomized election timeouts reduce the probability, and cannot eliminate it.
• Membership changes are the hard part. Naive reconfiguration can produce two disjoint majorities across the old and new sets. Both protocols specify joint-consensus or single-server-change procedures, and this is where real implementations most often go wrong.
• Durability assumptions. Safety relies on acceptors remembering their promises across restarts. A node that loses its persistent state and rejoins as if fresh can break agreement, which is why fsync before acknowledging is not optional and why some deployments have discovered this the expensive way.

The shape to carry away: consensus buys you a single, agreed, totally ordered sequence of decisions, at the cost of one majority round trip per decision and an availability gap whenever the leader dies. Use it for the decisions that must be unique, and route everything else around it.

Read next