Paxos — The Original Consensus Algorithm

The agreement problem Paxos solves

Fix the model first, because Paxos is only interesting relative to it. A fixed set of processes exchange messages. Any process may crash and later restart; it keeps whatever it wrote to stable storage and nothing else. Messages may be arbitrarily delayed, reordered, dropped, or duplicated, but they are not forged or altered — these are crash faults, not Byzantine ones, which is why Paxos needs a bare majority rather than the two-thirds a Byzantine protocol demands. There is no bound on message delay and no synchronised clock, so a process that has not answered is indistinguishable from a process that is merely slow.

Consensus in this setting means three properties at once. Validity: the value eventually settled on must be one that some proposer actually put forward, not something the protocol invented. Agreement: at most one value is ever settled on, and no two processes ever come to believe in different ones. Termination: eventually some value is settled on and the interested parties find out.

The Fischer-Lynch-Paterson result of 1985 proves you cannot have all three. In a fully asynchronous system where even a single process may crash, no deterministic protocol guarantees both agreement and termination; there is always an adversarial schedule that keeps the decision one message away forever. This is a statement about the model, not a weakness in any particular algorithm.

Paxos responds by refusing to trade safety. Validity and agreement hold in every execution: arbitrary delays, a partitioned network, processes restarting, any number of proposers racing. Termination is the conditional part — it needs a stretch of time long enough for one proposer to finish both phases without a competitor interrupting it, which is the partial-synchrony assumption every production deployment buys with timeouts and leader leases. Paxos never returns a wrong answer; under contention it returns no answer.

Proposers, acceptors and learners

Paxos names three roles. They are logical, not physical: a five-node cluster normally runs all three on every node, and the separation exists so the argument can talk about them independently.

A proposer takes a value — typically a client request — and tries to get it settled. Any number of proposers may run at once, and this is the part worth internalising early: correctness never depends on there being only one. Concurrent proposers cost throughput, never consistency.

An acceptor is the only role that holds durable state, and that state is the collective memory of the system. Each acceptor keeps exactly three fields, all of which must be written to stable storage before it replies to anything:

promised — the highest ballot number for which it has issued a promise. acceptedBallot and acceptedValue — the ballot and value of the highest-numbered proposal it has actually accepted. Those are two different pieces of state, and collapsing them into one is the most common implementation error in the whole algorithm. An acceptor can have promised at ballot 12 while its last accepted proposal is still the one from ballot 7.

A learner watches for accepted messages and concludes a value is settled once it has seen the same proposal from a majority. The subtlety is that "chosen" is not a flag any node sets. It is a predicate over the global state, true the instant a majority of acceptors happen to hold the same accepted proposal — possibly at a moment when no process in the system knows it yet, because the acknowledgements are still in flight. Chosen and learned are different events, and the gap between them is real.

The two phases in full

A single instance of Paxos settles exactly one value. It runs as two round trips between a proposer and a majority of acceptors: prepare / promise, then accept / accepted. Every message carries a ballot number, and every acceptor decision is a comparison against the two ballots it remembers.

ACCEPTOR STATE  (durable; fsync before every reply)
  promised       : ballot     # highest ballot promised     init -inf
  acceptedBallot : ballot     # ballot of last acceptance   init -inf
  acceptedValue  : value      # value  of last acceptance   init null

PHASE 1a   proposer -> acceptors           prepare(b)

PHASE 1b   acceptor, on prepare(b):
             if b > promised:
                 promised = b                        # durable
                 reply promise(b, acceptedBallot, acceptedValue)
             else:
                 reply nack(promised)

PHASE 2a   proposer, after promises from ANY majority Q:
             R = { replies in Q whose acceptedValue is not null }
             if R is empty:
                 v = my own value                    # free choice
             else:
                 v = acceptedValue of the reply in R with the
                     LARGEST acceptedBallot
                     # not the newest reply to arrive
                     # not the most frequent value in Q
             send accept(b, v) to acceptors

PHASE 2b   acceptor, on accept(b, v):
             if b >= promised:
                 promised       = b                  # durable
                 acceptedBallot = b
                 acceptedValue  = v
                 reply accepted(b, v)
             else:
                 reply nack(promised)

CHOSEN     the instant some majority holds the same accepted (b, v)

Two details in that listing repay attention. Phase 2b tests b >= promised, not b > promised: an acceptor that promised at ballot b must still accept a proposal at b, otherwise the proposer it just promised could never finish. And phase 2b writes promised as well, so an acceptor that receives an accept without a preceding prepare — which happens constantly in Multi-Paxos — still ratchets its ballot forward.

The proposer's own bookkeeping is thin by comparison and need not be durable at all, with one exception covered below: the ballot counter.

Why the prepare phase exists at all

Start with the protocol you would write if nobody warned you. A proposer sends its value to every acceptor; each acceptor accepts the first value it receives and remembers it; a value is settled once a majority holds it. This is broken in an obvious way and a non-obvious way. Obviously, two proposers can each capture a fraction of the acceptors so that neither reaches a majority, and since acceptors never change their minds, the instance is wedged forever. Non-obviously, the moment you let acceptors change their minds so the system can make progress, you have created the possibility of two different values each reaching a majority at different times.

The prepare phase is the fix, and it does two jobs, not one. The first is fencing: an acceptor that has promised at ballot b will reject any accept carrying a lower ballot, which retires half-finished older proposals permanently rather than leaving them to complete at an awkward moment. The second is discovery: the promise replies carry each acceptor's last accepted proposal, so the phase is simultaneously a read of whatever value might already have been settled.

Discovery is only useful with the right selection rule, and the rule is precise: adopt the value carried by the highest accepted ballot among the promise replies. Not the value in the reply that arrived last. Not the value most of the replies agree on. Not the proposer's own value, unless every single reply in the quorum reports no acceptance at all — only then is the proposer free.

The induction that makes it work

Suppose value v became settled at ballot b: some majority M accepted the proposal (b, v). Now take the next ballot b' greater than b that manages to reach phase 2, whose proposer gathered promises from some majority M'. Because both are majorities of the same acceptor set, M and M' cannot be disjoint; some acceptor a is in both.

Now the ordering argument, which is the piece that usually goes missing. Did a report (b, v) in its promise? It must have. If a had answered prepare(b') first, it would have set promised = b', and its subsequent test of b >= promised would have rejected accept(b, v) — contradicting the fact that a is in M. So a accepted (b, v) before it answered the prepare, and its promise reply necessarily carries an acceptedBallot of at least b. If it is exactly b, the value is v. If it is higher, then by induction over ballots strictly between b and b', that value is also v. Either way the maximum accepted ballot in the whole quorum reports v, and the selection rule leaves the proposer of b' no choice but to propose v again. Every subsequent ballot inherits the same obligation. At most one value is ever settled, and that is the entire safety property.

Notice that neither ingredient works alone. Quorum overlap without the selection rule lets a later ballot cheerfully overwrite a settled value. The selection rule without the fencing promise lets an older, slower proposal complete afterwards and settle something different. Paxos is safe because the two are combined in one round trip.

The consequence nobody likes

A proposer that adopts a value has no way to tell whether that value was actually settled. It may be faithfully re-proposing something exactly one acceptor accepted and no majority ever held. Adopting it anyway is conservative and costs nothing, because the guarantee is only that at most one value is ever settled — not that the settled one is the one anybody wanted. From the client's side this is visible and needs handling: if you submit a value and a competing proposer's ballot wins, your value is not settled, and the correct response is an explicit failure and a retry, never an optimistic success.

Quorum intersection and the 2F+1 arithmetic

The overlap step above is doing more work than its one line suggests. With N = 2F+1 acceptors, a quorum is any F+1 of them, and the cluster tolerates F crashes. Two such subsets cannot avoid each other: (F+1) + (F+1) = 2F+2, one more than the population, so at least one acceptor belongs to both. That single counting fact is the load-bearing beam under every safety argument in this article, and under Raft's election rules too.

It also explains why consensus clusters are sized with odd numbers. Four acceptors tolerate exactly one failure, the same as three, while requiring three acknowledgements per decision instead of two — strictly worse on latency for no gain in fault tolerance. Going from three to five buys a second tolerated failure and costs a third acknowledgement.

The latency consequence is worth stating plainly: a decision completes when the (F+1)-th fastest acceptor has durably acknowledged, so a single slow disk or a straggling replica does not stall the cluster. What does stall it is a straggler plus a failure, which is why capacity planning for consensus should assume the slowest quorum member, not the average one. Note also that this majority-quorum discipline is a different animal from the tunable R + W > N quorums of Dynamo-style stores, which intersect reads with writes rather than writes with writes and do not decide a single order.

Ballot numbers - unique, monotonic and durable

Ballot numbers (Lamport calls them proposal numbers) need three properties, and each one has a specific failure attached to violating it.

Totally ordered. Any two ballots must be comparable, so acceptors can decide which of two proposals is newer without ambiguity.

Unique per proposer. The usual construction is the pair (counter, nodeId) compared lexicographically, so two proposers incrementing to the same counter still produce distinct ballots. Disjoint stripes — proposer i uses only ballots congruent to i modulo N — work equally well and waste numbers, which is free. If two proposers ever issue the same ballot with different values, the acceptor's b >= promised test admits both, a majority can accept each, and you have two settled values at one ballot. This is the sharpest safety bug the algorithm has, and it is caused entirely by sloppy number allocation.

Monotonic across restarts. The counter must be durable, written before the ballot is used, not merely held in memory. A proposer that reboots and resumes from a stale counter can reissue a ballot it already spent, with a different value attached — the uniqueness bug again, arriving by way of amnesia. Implementations normally fsync the counter alongside the acceptor state and, on restart, jump it forward by a margin rather than resuming exactly where they think they left off.

One useful optimisation falls out of the nack path: a rejected proposer is told the acceptor's current promised value, so it can jump straight above that instead of climbing one ballot at a time into a fight it keeps losing.

Dueling proposers and the distinguished proposer

Trace the pathological schedule. Proposer P1 completes prepare(5) against a majority. Before its accept(5, v1) lands, P2 issues prepare(6); the acceptors promise, and P1's accept is now rejected everywhere. P1 notices, picks ballot 7, and prepares again — which invalidates P2's pending accept(6, v2). P2 moves to ballot 8. Neither ever completes phase 2, and nothing is ever settled.

Nothing unsafe has happened here. No value was settled twice; no acceptor's state is inconsistent; the instance is simply empty. This is a pure liveness failure, and it is precisely the corner FLP proved you cannot close with a deterministic protocol in an asynchronous network. Any fix has to import a timing assumption from outside the algorithm.

The fixes, in ascending order of usefulness: randomised backoff before retrying a lost ballot, which turns a deterministic duel into one with a probabilistic winner; the nack feedback described above, which stops a proposer wasting rounds climbing slowly; and the real answer, which is to designate one proposer and route all client traffic through it. Everyone else stands down unless they suspect it has died, and suspicion is driven by a timeout or a lease. Electing that proposer is itself a distributed problem, but crucially it does not have to be solved perfectly: two simultaneous Paxos leaders make the cluster slow, never wrong. That is a genuine structural difference from Raft, where the single leader per term is load-bearing for the algorithm itself.

Multi-Paxos - one prepare, many accepts

Real systems do not want one value; they want an ordered sequence of commands. The construction is to run one independent instance of the algorithm per log position, usually called a slot. Done naively that is two round trips per command, which is roughly twice what a primary-backup system with majority acknowledgement costs, and nobody would pay it.

The optimisation that makes Paxos practical is the observation that phase 1 is per-ballot, not per-slot. A proposer running prepare(b) can scope it to every slot from some index onward rather than to one instance; acceptors reply once with everything they have accepted at or beyond that index. Having done that, and for as long as no higher ballot appears anywhere in the cluster, the proposer may run phase 2 alone for each new command. Steady state is therefore one round trip — two message delays from the leader to a majority and back — which is the same cost as unreplicated primary-backup with a durable quorum acknowledgement. This is what every production system means when it says it "uses Paxos"; nobody runs the two-phase form per command.

Two further properties come with it. The leader can pipeline, keeping many slots in flight at once, and because each slot is an independent instance, slot 9 may become settled before slot 8 does. Execution still respects the prefix, but commitment does not have to, and that decoupling is worth real throughput on a high-latency link.

Takeover is where the full algorithm reappears. A new leader picks a ballot above anything it has seen and runs phase 1 across the tail of the log. For every slot where the promise quorum reports an accepted proposal, it is bound by the selection rule and must re-propose that value. For the rest it is free.

The replicated log - slots, holes and no-ops

What sits on top of the log is a deterministic state machine: identical starting state, identical command sequence, identical resulting state on every replica. Consensus supplies the sequence and nothing else, which is why the general primitive is total order broadcast and why state-machine replication is the standard way to turn an agreement protocol into a usable service.

Execution is strictly sequential. Slot k may only be applied once slot k-1 has been. A slot that is not settled therefore blocks every slot behind it, however many of those are settled already.

Holes appear routinely. A leader proposes slots 6, 7 and 8 concurrently, then crashes; 7 and 8 reached a majority and 6 did not. The new leader's phase 1 asks its quorum about slot 6 and every reply reports no acceptance — which, by the same overlap argument, is proof that no value was ever settled there, since a settled value would have shown up. The new leader is free to choose, and what it chooses is a no-op: a command the state machine deliberately ignores. Settling a no-op at slot 6 unblocks 7 and 8.

The tempting shortcut — just skip slot 6 — is wrong, because skipping is not agreement. A replica that was partitioned away might later learn a real value at slot 6 from a straggling message, and two replicas would then disagree about the command sequence. The hole has to be closed by settling something in it.

One client-facing consequence: a command can become settled at a slot without the client ever seeing the response, because the leader may crash between commit and reply. Clients therefore retry, and the state machine needs a deduplication key per client request, otherwise the retry is applied a second time and your "consistent" system has double-charged somebody.

Reconfiguration is the genuinely hard part

Changing the set of acceptors attacks the one fact every safety argument rests on. Quorums of the old configuration and quorums of the new configuration need not intersect at all. Swap a three-node membership for a different three-node membership by editing config files and restarting, and two disjoint majorities can each settle a different value at the same slot — the failure is not subtle, it is total.

The Paxos-native answer is elegant: put the configuration in the log and let the state machine own it. The membership governing instance i is whatever the state machine says after applying instance i - alpha, for a fixed pipeline depth alpha. Every replica derives the same configuration for the same slot because they apply the same log, so there is never disagreement about who the acceptors are. The parameter alpha is the price: it is exactly the number of instances the leader may have in flight, because instance i cannot be proposed until i - alpha is settled. With alpha = 1 you get correct reconfiguration and no pipelining whatsoever; with alpha = 100 you get pipelining and a membership change that takes effect 100 slots later than you issued it.

The operational wrinkle is the new member. A freshly added acceptor starts with empty state, which means it can honestly report "I have accepted nothing" for slots where a value was settled by the old configuration. Let enough such members vote and you have manufactured a quorum with amnesia. Real systems either ship it a snapshot and the log tail before it is allowed to vote, or admit it as a non-voting learner and promote it only once it has caught up.

Raft's answer to the same problem is joint consensus: a transitional configuration whose quorums require a majority of the old set and a majority of the new one simultaneously, so overlap is preserved through the transition; the simpler variant restricts changes to one server at a time, where old and new majorities necessarily share a member by counting. Either way, reconfiguration is where most consensus incidents actually originate — replacing a failed node, restoring a member from a stale backup, or removing two nodes in quick succession from a five-node cluster.

Paxos against Raft, honestly

Raft is best understood as Multi-Paxos with restrictions chosen so the result can be explained, and its authors were explicit that understandability was the design goal rather than a side effect. Two restrictions carry most of the weight.

The first is the strong leader. Entries flow from leader to follower only, and a leader never overwrites or reorders its own log. Compare that with a Paxos proposer, which may be forced by the selection rule to drop its own value and re-propose someone else's. A Raft leader is never in that position, and removing it removes the single most confusing step in the algorithm.

The second is the election restriction. A Raft voter refuses a candidate whose log is less up to date than its own, comparing last term first and then last index. The consequence is that a winning candidate already holds every committed entry, so it never has to fetch a value from its voters. This is not a different idea from Paxos — it is the same information gathered at a different moment. Paxos discovers already-settled values in the promise replies of phase 1; Raft moves that discovery into the vote itself. The work is identical; only its position in the protocol changed. Raft's log replication and its election mechanics are covered separately.

The cost of the strong leader is that Raft logs have no holes, a divergent follower tail gets truncated, and commitment is strictly in order. That is much easier to reason about and it gives up the out-of-order commitment that Multi-Paxos permits.

Scored fairly, for a single-datacenter replicated log with a stable leader, Raft and Multi-Paxos have the same message count, the same commit latency and the same fault tolerance. Raft's win is entirely in implementability: a specification precise enough to test an implementation against, and a shape enough engineers can review. That is not a small win. Google's own write-up of building Chubby on Paxos is essentially a catalogue of the distance between a correct algorithm and a correct program — disk corruption, master leases, membership, and the test infrastructure needed to trust any of it.

Where Paxos variants still win

Paxos is a family rather than a single algorithm, and the family reaches regimes Raft's shape excludes.

Flexible Paxos observes that the two quorums never need to intersect with others of their own kind — only phase-1 quorums with phase-2 quorums. The requirement is therefore just |Q1| + |Q2| > N, and neither has to be a majority. With five acceptors you can commit against two of them in the steady state and pay for it with a four-acceptor phase 1 whenever the leader changes: cheaper commits, a more expensive and less resilient takeover. The result applies to Raft's quorums as well, which is what makes it more than a curiosity.

Fast Paxos lets clients send values straight to the acceptors, removing one message delay from the common path. The price is that fast quorums are strictly larger than classic majorities, and two clients proposing different values concurrently collide, which forces a recovery round through the leader. It pays off when contention is genuinely rare and the extra acknowledgements are cheap.

EPaxos abandons the designated leader entirely. Any replica commits the commands it receives; commands that do not interfere — touching disjoint keys — commit in a single round trip, while interfering commands acquire dependencies and need a second. The wins are real in the wide area, where routing everything through one leader means a cross-continent hop for half the clients, and there is no leader-failover stall because there is no leader to fail. The complexity did not vanish, it moved: you now maintain a dependency graph and execute it in a consistent order.

As for where classical Paxos actually runs, the canonical deployments are Google's Chubby lock service, the per-group replication underneath Spanner, and Megastore's cross-datacenter entity groups. ZooKeeper's ZAB is frequently miscatalogued here; it is Paxos-like in spirit and is a distinct primary-order broadcast protocol, not Paxos.