Paxos Explained: The Algorithm Behind Most Consensus Systems

Chubby, the lock service at the base of Google’s coordination stack, has run Paxos in production since the mid-2000s. Spanner replicates every one of its shard groups with it. And when Raft arrived, it introduced itself by what it was not: the understandable alternative to a protocol everyone respected and few claimed to fully understand. Consensus research since has largely positioned itself for or against Paxos, which is what “the algorithm behind most consensus systems” means in practice, not that everyone runs the 1989 paper verbatim, but that almost everyone runs something descended from it.

The problem it solves was defined in distributed consensus: a cluster of crash-prone nodes on an unreliable network must agree on one value. Its place against Raft, ZAB, and the byzantine family was staked in consensus algorithms. This deep dive covers the paxos algorithm itself, and, because the paper is a proof rather than a system, the parts every implementation adds around it. It assumes the substrate of partial failure and unreliable networks without re-deriving it, and borrows the quorum arithmetic rather than repeating it.

The Paxos algorithm is a consensus protocol for agreeing on a single value, published by Leslie Lamport as “The Part-Time Parliament” (1998) and restated plainly as “Paxos Made Simple” (2001). Nodes exchange numbered ballots: any majority of acceptors can make a decision, any two majorities overlap, and the protocol’s one iron rule is that once a value is chosen, no later ballot can displace it.

Why Paxos is the way it is

Part of understanding Paxos is understanding its strange publication history, because the history explains the shape of the algorithm. Lamport’s original paper presented the protocol as archaeology: the tale of a Greek island parliament whose legislators were part-time, whose messengers were unreliable, and in which no one stayed in the room long enough to matter. The joke buried a serious protocol, but reviewers could not reliably dig past the fiction, and the paper sat effectively unread for years. In 2001 Lamport published “Paxos Made Simple,” which observed that the protocol in plain English is almost embarrassingly simple; the difficulty had been the presentation, not the idea.

The design philosophy is visible in that story. Paxos is a proof substrate, not a system. It specifies agreement on one value, with crash failures, on an asynchronous network, and stops there. There is no leader, no log, no client API, no membership change, no snapshot mechanism, because none of those are needed to prove the core claim: safety holds unconditionally; progress holds when the network cooperates. That split is the FLP-shaped compromise; no protocol can promise both termination and agreement on a fully asynchronous network that can crash one node, so Paxos promises agreement always and progress under the conditions real networks meet most of the time.

The gap between proof and product is not hypothetical. When Google described building Chubby on Paxos, the report “Paxos Made Live” (2007) spent most of its length on engineering the algorithm does not mention: making protocol state survive disk failures, catching up slow replicas, changing membership without downtime, and confirming in testing that the parts the paper waves at are where the bugs live. The algorithm is a page; the system around it is thousands of lines. What follows covers the page first, then the gaps.

The problem Paxos solves

Strip the story away and the setting is the one from distributed consensus: N nodes must agree on exactly one value, any node can crash and recover at any moment, messages can be delayed, reordered, or lost forever, and there is no shared clock to break ties. Agreement means all non-faulty nodes eventually learn the same value; validity means the value was actually proposed by someone; termination means it happens in finite time, and that last clause is the one no algorithm can promise on a truly asynchronous network, per FLP.

Paxos commits to the crash model, not the byzantine one: nodes fail by stopping, not by lying. A node that crashes and recovers is expected to remember what it promised; that durability requirement is load-bearing, and an implementation that replies before the fsync is quietly broken. Byzantine agreement needs a different protocol family with a different quorum cost, covered with PBFT in consensus algorithms.

One structural idea is worth restating, because everything in Paxos reduces to it: any majority of nodes can act for the cluster, and any two majorities share at least one node. With five nodes, any three overlap any other three. Paxos never needs everyone’s vote; it needs majorities, and it arranges the protocol so the shared node between two majorities carries the history forward.

The paxos roles: proposers, acceptors, and learners

Paxos divides the world into three roles:

• Proposers champion values and drive the protocol. A proposer that wants the cluster to decide v runs ballots until v (or some earlier-chosen value) is decided.
• Acceptors are the memory of the protocol. They answer ballots, and their recorded promises are what make a chosen value permanent. Only a majority of acceptors matters; the rest can be down.
• Learners find out what was decided and carry it onward; serving reads, applying it to a state machine, telling clients.

Three details about the roles trip up readers of the paper. First, they are logical, not physical: in a real deployment one machine usually plays all three, and the interesting production question is how many machines play proposer at once. Second, the asymmetry is deliberate; acceptors are passive and stateful, proposers are active, learners are pure downstream. Third, ballot numbers are per-proposer: each numbers its own ballots in a space it can never share by mistake (node ID in the low bits is the classic construction), so numbers from different proposers are comparable without coordination.

What the role list does not include is the role production systems reach for first: a leader. Paxos has no leader; any proposer may run a ballot at any time, and the protocol stays safe when they all do. How that freedom turns into livelock, and how real systems collapse the proposer set to one distinguished node, is covered below, and is exactly the move that turns single-decree Paxos into Raft-style Multi-Paxos.

How a ballot runs: prepare and accept

A ballot is one attempt to choose a value, numbered with a number from the proposer’s private space. It has two phases, each a majority exchange, and both are needed to see why the protocol is safe. The full run:

1. A proposer picks a ballot number n larger than any it has seen and sends PREPARE(n) to a majority of acceptors.
2. An acceptor receiving PREPARE(n) checks its record. If n is higher than every ballot it has promised before, it promises that nothing numbered below n will be accepted from now on, and replies PROMISE, including the highest-numbered proposal it has already accepted, if any.
3. If the proposer collects promises from a majority, it picks a value. If any acceptor reported an accepted proposal, the proposer must re-propose that value, the one from the highest-numbered accepted proposal reported. Only if nobody reported anything may it choose its own value.
4. The proposer sends ACCEPT(n, value) to a majority of acceptors.
5. Each acceptor accepts the proposal (durably records it) unless it has since promised a higher ballot, and replies ACCEPTED(n, value).
6. Once a majority of acceptors has accepted a value at ballot n, that value is chosen. Learners are notified, and the ballot is done.

Now run the crash clock through those steps, because the design tolerates failure everywhere. A proposer that dies after step 1 leaves nothing behind, its promises die with its ballot, and the next proposer simply starts a higher one. An acceptor that dies shrinks the pool; the ballot completes with any majority of the survivors. A proposer that dies between steps 3 and 4 strands no one: acceptors stay free to promise higher ballots, and step 3’s re-propose rule guarantees that whatever was half-decided survives into the next attempt. Even two proposers running overlapping ballots cannot corrupt the outcome; the next ballot has to pass through step 3, where the acceptors’ recorded history wins.

What the protocol never tolerates is losing the majority itself. With five acceptors, three down means no ballot completes, not because messages fail, but because there is no majority left to promise or accept. Safety is untouched; the cluster simply stops deciding until enough acceptors return. That is Paxos’s whole temperament: it would rather halt than disagree, which is the consensus trade-off taken to its extreme.

Paxos made simple: the safety argument

“Paxos made simple” is a fair description of the proof, which is one observation repeated three times. Walk the worst case: a value v has been chosen, accepted by a majority of acceptors at ballot 5. Later, a new proposer runs ballot 7 and would prefer to choose its own value w. To reach its own ACCEPT, it must first collect promises from a majority of acceptors. Any majority it asks overlaps the majority that accepted v in at least one node, so at least one acceptor reports: “I have already accepted v at ballot 5.” The proposer is then bound by step 3 of the protocol; it must re-propose v, not w. Ballot 7 accepts v again, and every ballot after it does the same. Once a value is chosen, every later ballot re-chooses it.

The other case closes the loop. If v had not been chosen (if its acceptance never reached a majority) then a new ballot may find no accepted proposal, or only scattered ones, and is free to choose a new value. No harm done: nothing was ever chosen, so nothing was ever owed to anyone. The protocol’s entire safety argument reduces to the majority-overlap fact from earlier, which is why the quorum arithmetic of distributed consensus is worth internalizing: Paxos is the quorum intersection rule with ballot numbers attached.

Notice what the proof does not contain: any promise that a ballot ever completes. Two proposers can interleave forever (each new PREPARE invalidating the other’s in-flight ACCEPT) while the protocol stays perfectly safe and makes no progress at all. That livelock is not a theoretical footnote; it is the reason the algorithm, as published, is a building block rather than a service.

Dueling proposers and livelock

Picture it: proposer A sends PREPARE(10) and collects promises. Before its ACCEPTs land, proposer B sends PREPARE(11), which invalidates every acceptor’s promise to 10. A’s ACCEPTs bounce; B collects its own promises; A rebounds with PREPARE(12), invalidating B’s in turn, and so on, indefinitely. Every step is legal, every step is safe, and nothing is ever chosen. The paper acknowledges the hazard and prescribes the obvious cure: eventually, elect one distinguished proposer and let it run. With a single active proposer, every ballot completes unless the proposer itself dies.

The cure is where election, leases, and failure detection enter, none of which Paxos provides, and all of which deployments must add. The dependency runs in both directions: consensus-based systems elect their leader with quorum machinery (covered from the election side in leader election), and the election is often itself a Paxos decision; a value whose content is a node ID. The recursion is finite and the systems built on it are stable; the point is that “run Paxos” in production always means “run Paxos plus a leader management protocol.”

Raft’s answer was to stop treating the leader as an add-on and make it the center of the protocol: one strong leader per term, elected by majority vote, with the term number fencing off stale leaders by construction. At this altitude, Raft is Multi-Paxos reorganized for understandability, and the head-to-head comparison of the families lives in consensus algorithms.

From single decree to Multi-Paxos

Everything above decides one value. A replicated log needs a sequence of them (decree 1, decree 2, decree 3) so the naive build runs one full Paxos instance per log entry: two phases, two round trips, every time. Multi-Paxos is the observation that almost all of that cost is redundant. If the same distinguished proposer stays in charge, phase 1 does not need to repeat: one PREPARE, accepted by a majority, establishes a leader whose ballot number covers every subsequent entry, and the log then advances with single-phase ACCEPTs; the same shape as any leader-based log protocol, which is precisely the shape Raft later made canonical.

The remaining work is the gap the paper waves at and “Paxos Made Live” itemizes. Log entries can have holes (ballot 3 accepted while ballot 2 stalls) and implementations renumber, truncate, or re-propose around them. State grows without bound, so snapshots and log truncation arrive, with learners catching up from snapshots rather than full history. Membership changes while the cluster runs, which the basic protocol cannot express, so deployments bolt on configuration epochs. None of these pieces is intellectually hard alone; together they are why a one-page algorithm becomes a ten-thousand-line system, and why teams that skip the engineering discover in production that they implemented the proof but not the service.

The lineage runs straight from here. Chubby’s coordinators, Spanner’s shard groups, and most proprietary consensus cores are Multi-Paxos with the gaps filled in house; Raft took the same substrate and reorganized it around an elected leader, explicit log matching, and a safety argument a maintainer can hold in mind. The differences between the families are cataloged in consensus algorithms, and Raft’s version is covered in its own deep dive. Choosing between them today is mostly a choice of which engineering team already solved which gaps: a mature Multi-Paxos library is battle-tested and opaque; Raft implementations are auditable by a single engineer, which was the point.

Common mistakes

• Shipping the proof as the product. Single-decree Paxos with no leader, no log, and no snapshot is a demonstration, not a service. The gaps are the system.
• Letting every node propose. Multiple active proposers are safe and livelock-prone. Production collapses the proposer set to one distinguished node and re-elects it on failure, the livelock cure from above.
• Replying before the disk. An acceptor’s promise is only as durable as the fsync behind it. Answering from memory is the classic silent bug: correct until the crash that proves otherwise.
• Colliding ballot numbers. Two proposers numbering ballots from the same space will eventually race with identical numbers and interleave wrongly. Disjoint per-proposer ranges (node ID in the low bits) cost nothing and eliminate the class.
• Testing only the happy path. Paxos bugs live in the interleavings: proposers dying between phases, acceptors recovering with stale disks, majorities shrinking to the wire. Crash injection between every step is the only test suite it respects.

FAQ

Is Paxos still used in production, or has Raft replaced it?
Both live. Systems built before Raft (Chubby, Spanner) still run Paxos families, and large new systems still choose Multi-Paxos variants when they want the battle-tested core or already employ engineers who have solved its gaps. Raft owns most greenfield consensus since 2014, because implementations a single engineer can audit are worth more than elegance points. The trade-offs are laid out in consensus algorithms.

Why was Paxos considered so hard to understand?
Partly presentation: the original paper’s archaeological joke actively obscured the protocol, and the plain restatement in “Paxos Made Simple” reads far easier. But partly substance: the paper proves safety for one ballot and leaves the systems work (leaders, logs, snapshots, membership) as folklore. Understanding production Paxos always meant reading three or four papers plus a codebase, which is exactly the burden Raft was designed to remove.

Does Paxos guarantee my value gets chosen?
No, and no protocol can promise that in full generality. Paxos guarantees that a chosen value stays chosen and that all learners learn the same one. Termination requires partial synchrony: bounded message delays and fewer than a majority of failures. On a fully asynchronous network the FLP result rules out guaranteed termination, so “safety always, progress usually” is the ceiling, not a gap.

What is the difference between Paxos and Multi-Paxos?
Paxos agrees on one value, running both phases per decision. Multi-Paxos agrees on a sequence (a log) and reuses one successful phase 1 so a stable leader commits subsequent entries in a single round. Multi-Paxos is not a different algorithm; it is Paxos plus a leader optimization plus the log machinery, which is why nearly every production deployment is Multi-Paxos of some flavor rather than single-decree.

How is Paxos related to Raft?
Raft is in the Multi-Paxos family: one leader elected by majority, log entries committed by majority acceptance, safety from quorum intersection. What Raft changed is organization; explicit leader management, log matching rules, and safety stated in terms a maintainer can verify. The family comparison, including ZAB and PBFT, lives in consensus algorithms; Raft itself is covered in its own article.

Related articles

• Next read: leader election, consensus’s most common application: how clusters pick their coordinator, and the split-brain risk that follows.
• consensus algorithms, the comparison this article kept deferring: Paxos, Raft, ZAB, and byzantine fault tolerance, side by side.
• the Raft consensus algorithm: the understandable descendant, covered with the same depth.
• distributed consensus: the problem Paxos solves, the quorum arithmetic underneath it, and FLP.
• what is a distributed system?, the pillar hub for this cluster: every article, one page.