The question this answers
How do Paxos, Multi-Paxos, Zab and Viewstamped Replication differ from Raft — and does the difference change anything I do?
Every protocol in this family provides the same safety envelope: at most one value decided per instance or index, decisions never revoked, and no committed entry lost across leadership change — all under asynchrony, arbitrary message loss and up to f crash failures in a 2f+1 cluster. They differ in decomposition, in leadership model, and in the cost of a leadership change, never in what they guarantee.
Everything below is bought to hold this sentence. "Strongly consistent" with no scope attached is a slogan, not a guarantee — read what it actually covers, and what it explicitly does not.
The same as in Raft, because the constraint is the network rather than the algorithm: a node knows what it has persisted and what has arrived. In Paxos this is felt more sharply — an acceptor that has accepted a value does not know whether that value was *chosen*, since chosen-ness is a property of a majority that no single acceptor observes. Learning that a value was chosen requires a separate round of asking, which is why Paxos has a "learner" role at all.
A node knows its own state and the messages that arrived. Everything else is inference from evidence that was already stale. "B has not replied in five seconds" is knowledge; "B is down" is a decision — and usually the bug.
What Paxos established
Lamport’s Paxos answered the question the field needed answered: consensus is achievable in an asynchronous system with crash failures, safely, without ever risking two different decisions. Not "usually", not "with good clocks" — always, under any message loss or delay. Everything since is a refinement of that result.
The shape is two phases run by a proposer. Phase 1 (prepare): the proposer picks a ballot number higher than any it knows of and asks a majority of acceptors to promise not to accept anything numbered lower; each acceptor that promises reports back the highest-numbered value it has already accepted. Phase 2 (accept): if any acceptor reported a value, the proposer *must* propose that value rather than its own; otherwise it may propose freely. It then asks the majority to accept.
The obligation in phase 2 is the entire safety mechanism, and it is worth stating plainly: a proposer inherits any value that might already have been chosen. Because the phase-1 majority overlaps any earlier accepting majority, a chosen value is always visible to a later proposer, so no later round can decide differently. That is the same quorum-intersection argument Raft uses in its vote rule, arrived at from the other direction.
We stop there deliberately. Deriving Paxos fully — the induction over ballot numbers, the acceptor invariants — is a worthwhile exercise and is not what this lesson is for.
From one decision to a log: Multi-Paxos
Basic Paxos decides one value. A replicated log needs a decision per index, and running two full phases per entry costs two round trips per operation, which is unaffordable.
Multi-Paxos observes that phase 1 is about establishing the right to propose, and that right does not need re-establishing for every index. Run phase 1 once for *all* future indexes, and the proposer becomes a stable leader that can commit each subsequent entry in a single phase-2 round trip. The result is operationally the same shape as Raft: a stable leader, one round trip per entry, and an expensive changeover.
The convergence is not an accident. Once you decide a leader is worth having, every protocol in this family ends up in the same place — the interesting differences are all about what happens when the leader changes.
How the family differs
The clearest way to compare them is by what a new leader must do before it can serve, and by whether logs are allowed to have holes.
Raft’s distinguishing choices are that the log is contiguous — no gaps, ever — and that entries flow only from leader to follower, never the reverse. Both restrictions cost some flexibility and buy a great deal of comprehensibility: they are why leader change in Raft needs no separate protocol phase, only the ordinary consistency check.
Multi-Paxos permits gaps: index 12 can be chosen while 11 is still undecided, which allows more parallelism and means a new leader must run a recovery round to fill in what it does not know. Viewstamped Replication is closest to Raft in spirit but makes the view change an explicit phase with explicit state transfer. Zab, which powers ZooKeeper, is built around primary-order broadcast and a recovery phase that synchronises followers to the new leader’s history before serving.
| Protocol | Log shape | On leader change | Where you meet it |
|---|---|---|---|
| Basic Paxosprotocol | One decision, no log | Every round re-establishes the right to propose | Building blocks; rarely used directly |
| Multi-Paxostypical | Gaps allowed | Recovery round per uncertain index | Chubby, Spanner, many in-house systems |
| Rafttypical | Strictly contiguous | Ordinary consistency check; no special phase | etcd, Consul, TiKV, CockroachDB, Kafka KRaft |
| Viewstamped Replicationtypical | Contiguous | Explicit view change with state transfer | Influential; descendants in several systems |
| Zabtypical | Contiguous, primary order | Explicit recovery phase syncing followers | ZooKeeper |
What is genuinely different: EPaxos and leaderless variants
One branch of the family does change the operational picture. Leaderless variants such as EPaxos have no distinguished leader; any replica may commit a command, and commands that do not conflict (do not touch the same keys) commit in one round trip without any global ordering. Only conflicting commands need an extra round to agree on their relative order.
The appeal is real — no leader bottleneck, no election stalls, and a client can talk to its nearest replica, which matters enormously across regions. The cost is that conflict detection must be exact, the recovery paths are considerably harder to reason about, and implementations are far less battle-tested. This is the one place where "which protocol" is a genuine architectural decision rather than an implementation detail.
It is also the protocol-level expression of a theme that runs through the Coordination module: if operations do not conflict, they do not need to be ordered relative to each other. EPaxos builds that observation into consensus itself.
What this should change about your decisions
For almost every team, the answer to "which consensus protocol?" is "the one inside the system you already chose", and that is the correct answer. You will consume Raft through etcd, Zab through ZooKeeper, or Multi-Paxos through a database, and you will never implement any of them.
What is worth carrying is the shared envelope. Every one of these protocols needs a majority, gives up liveness rather than safety, and cannot protect effects outside its own log. If a vendor claims consensus with better availability under partition, they have either changed the guarantee or changed the failure model — and either way the right question is which one, not which protocol.
Do not implement one yourself. The published algorithms are correct; the implementations are where the bugs live, and the bugs are in membership change, log compaction, snapshot install and restart recovery — none of which appear in the papers’ core sections.
Key points
- Paxos proved consensus is achievable safely under asynchrony with crash failures; everything since refines that result.
- Its safety hinges on one rule: a new proposer must adopt any value that might already have been chosen.
- Multi-Paxos amortises phase 1 across all indexes, producing the same stable-leader shape as Raft.
- Raft’s distinguishing choices are a contiguous log and one-directional entry flow — comprehensibility bought with flexibility.
- Zab and Viewstamped Replication make leader change an explicit phase; Raft folds it into the ordinary consistency check.
- Leaderless variants like EPaxos remove the leader bottleneck for non-conflicting commands, at a real cost in complexity.
- All of them share the same envelope: majority required, liveness surrendered first, no protection outside the log.
The chain, answered
Every field here is required, which is why no lesson in this domain can recommend a design without naming what an operator sees when it fails, what survives the partition, what repairs it afterwards, and the simpler thing to consider first.
- • Paxos phase 1: a proposer picks a ballot higher than any it knows and asks a majority of acceptors to promise to ignore lower ballots.
- • Each promising acceptor returns the highest-numbered value it has already accepted, if any.
- • Paxos phase 2: the proposer must propose the highest-numbered reported value; only if none was reported may it propose its own.
- • A value accepted by a majority is chosen; learners discover this by observing a majority of accepts.
- • Multi-Paxos runs phase 1 once for all indexes, so the stable leader needs only phase 2 per entry.
- • Zab and VR replace the implicit changeover with an explicit recovery or view-change phase that synchronises followers before serving.
- • Duelling proposers: two proposers repeatedly outbid each other in phase 1 and neither reaches phase 2 — the Paxos analogue of a vote split.
- • A learner never observes a majority of accepts and so never learns a value that was in fact chosen.
- • Gaps in a Multi-Paxos log leave indexes whose state a new leader must recover before it can serve.
- • Recovery or view-change logic diverges from the paper in an edge case, producing a rare and catastrophic bug.
- • Membership change is implemented ad hoc, allowing two non-overlapping majorities to exist at once.
- • Duelling proposers: the operator sees ballot numbers climbing on two nodes, no decisions committed, and a cluster that is healthy by every liveness check. The fix is leader election or randomised backoff, not more capacity.
- • Stuck log gap in Multi-Paxos: the operator sees a new leader unable to serve because index 8,412 is undecided; commit progresses everywhere else and the apply pipeline is blocked behind the hole.
- • Slow leader change in Zab/VR: the operator sees a multi-second outage on every failover as followers synchronise history — correct behaviour, but visible in the SLO in a way Raft’s handover often is not.
- • Home-grown implementation loses data on restart: the operator sees committed entries missing after a full-cluster power loss, because recovery-after-restart was implemented from an informal reading of the paper.
- • Version-skew during upgrade: two implementations of the same protocol disagree on a membership-change encoding. The operator sees a cluster that forms two configurations and refuses to converge.
- • All variants need a majority per decision; that cost is invariant across the family.
- • The steady-state cost differs only by round trips per entry: two for basic Paxos, one for any stable-leader variant.
- • Leaderless variants pay one round trip for non-conflicting commands and two for conflicting ones — a workload-dependent cost rather than a fixed one.
- • Safety is identical across the family: no two conflicting decisions, no committed entry lost.
- • Liveness differs in character — Paxos can livelock through duelling proposers; leader-based variants can livelock through election storms.
- • Every one of them stops on loss of majority rather than diverging.
- • Detect: whatever the protocol, the signal is the same — decisions per second at zero while processes are healthy.
- • Contain: ensure exactly one node is trying to lead or propose at a time; most livelocks in this family are contention between would-be leaders.
- • Recover: restore majority connectivity and let the protocol’s own recovery phase run.
- • Reconcile: undecided indexes are resolved by the recovery round (Paxos) or by the consistency check (Raft); neither needs an operator.
- • Verify: converged view/term/epoch across members and identical applied state — the checks are protocol-independent.
- • Decisions or commits per second — the one metric that means the same thing in every protocol.
- • Ballot/term/epoch/view number per member and its rate of change.
- • Count of undecided indexes below the apply point, for gap-permitting protocols.
- • Leader-change duration, measured client-side as the write-unavailability window.
- • When evaluating a system: knowing the family lets you ask what happens on leader change rather than accepting "it uses consensus" as an answer.
- • When a cross-region design keeps hitting the leader bottleneck and a leaderless variant is genuinely worth investigating.
- • When reading incident reports or papers about a system you depend on.
- • As a basis for building your own: the papers are correct and the implementations are where correctness is lost.
- • As a selection criterion for ordinary systems, where operational maturity of the implementation matters far more than the protocol on the label.
- • Use a mature implementation rather than a protocol: etcd, ZooKeeper or Consul give you the guarantee without the bugs. See Coordination Services: The Primitives, Not the Product.
- • Avoid consensus for the operation entirely where the invariant permits — see Coordination Avoidance: Restructuring the Problem Instead of Paying for It and Do You Actually Need Consensus?.
- • Use a database that already embeds consensus, so replication and failover are the vendor’s problem rather than yours.
- • For Byzantine settings, an entirely different family (PBFT and successors) with
3f+1members and much higher message complexity — see Byzantine Failures, and Why You Probably Do Not Assume Them.
What people believe, and what is true
Raft is safer than Paxos.
They provide the same safety guarantees. Raft is easier to implement correctly, which makes real deployments safer — a property of implementations, not of the algorithms.
Paxos is obsolete.
Multi-Paxos runs inside some of the largest production systems in existence. It is less taught, not less used.
A leaderless protocol removes the coordination cost.
It removes the leader bottleneck. Every command still needs a majority, and conflicting commands still need an extra round.
Choosing the protocol is an important architectural decision.
For nearly everyone it is determined by the system chosen, and implementation maturity dominates protocol choice. The exception is a genuinely leaderless design.
Go deeper
Only the levels this lesson can honestly fill — a missing level is a claim nobody had.
Overview
Paxos proved consensus is possible under asynchrony; Raft made it teachable. They guarantee the same things. The practical differences are in what a new leader must do before it can serve.
Practical
Consume consensus from a mature implementation rather than writing one. When comparing systems, ask what happens on leader change, whether the log permits gaps, and how membership change is performed — those are where the real differences and the real bugs live.
Advanced
The unifying idea is quorum intersection used twice: once to guarantee a chosen value is visible to any later proposer, and once to guarantee a later proposer adopts it. Paxos does this per instance with ballot numbers and a mandatory adopt-the-highest rule; Raft does it once per term by refusing votes to candidates with incomplete logs. Same argument, different placement — and Raft’s placement is why it needs no recovery round at all.
Apply it
- 🔧 Explain the adopt-the-highest-accepted-value rule in phase 2 and construct the divergence that occurs without it.
- 🔧 Compare Raft leader change with Zab recovery in terms of the client-visible unavailability window.
- 💬 What does Paxos guarantee, and what is the rule that makes it safe?
- 💬 How does Multi-Paxos differ from basic Paxos, and why does the difference matter in production?
- 💬 Name a design decision Raft makes that Paxos does not, and say what it buys.
- 💬 Would you implement a consensus protocol in-house? Defend your answer.