Paxos
Paxos is the consensus algorithm. Published by Leslie Lamport in 1989 (circulated as a manuscript; finally published in 1998), it was the dominant solution to distributed consensus for 20+ years. Google Chubby, Apache Zookeeper (ZAB is Paxos-derived), and Google Spanner all build on Paxos or direct derivatives.
Correction
ZooKeeper does not run Paxos. ZAB (ZooKeeper Atomic Broadcast) is its own protocol. It shares the core ideas of Paxos (epochs that play the role of ballots, majority quorums, a recovery phase before a new leader may broadcast), but its authors describe it as a different protocol designed for primary-backup systems, and it gives ordering guarantees per primary that plain Multi-Paxos does not. "Paxos-family" is fair; "Paxos-derived" overstates it. See ZAB.
Understanding Paxos matters not because you'll implement it (use Raft instead), but because it reveals why consensus is hard and what the minimum requirements for solving it are.
How this page fits
This is the overview of Paxos: what problem it solves, how the two phases work, a worked example with competing proposers, why it is safe, why it can stall, how it grows into a replicated log (Multi-Paxos), how membership changes, and how it compares to Raft. For the full treatment, which covers the formal safety proof, the acceptor state machine, a TLA+ sketch, Flexible Paxos and EPaxos in depth, read Paxos Made Simple. Related pages:
| If you want... | Read |
|---|---|
| The impossibility result Paxos has to live with | FLP Impossibility |
| The timing and failure assumptions spelled out | System Models |
| How a consensus log becomes a replicated service | Replicated State Machines |
| The algorithm most people actually deploy | Raft Full Walkthrough |
| A sibling protocol from the same era | Viewstamped Replication |
| Leaders, leases and stale leaders | Leader Election, Leases and Fencing |
The Problem
Multiple nodes must agree on a single value. Requirements:
- Safety — at most one value is ever chosen
- Liveness — some value is eventually chosen (assuming enough nodes are up)
- Validity — only a proposed value can be chosen
This is consensus — and FLP proves it's impossible in a fully asynchronous system. Paxos sidesteps FLP by assuming partial synchrony (messages eventually arrive).
Correction
"Messages eventually arrive" is not partial synchrony; it is the ordinary asynchronous model, and FLP holds there. The precise statement is: Paxos is always safe, even in a fully asynchronous network, and it is live only when the system behaves synchronously for long enough (after some unknown "global stabilization time", message delays and processing times stay under a bound, so a single proposer can finish a round without being interrupted). Paxos does not beat FLP. It gives up guaranteed termination and keeps safety unconditionally, which is exactly the trade FLP allows.
A fourth property is often stated alongside the three above:
- Learnability / agreement — if a value is chosen, every correct learner can eventually find out which value it was, and no two learners learn different values.
The interesting part is not any one of these properties. It is getting all of them while nodes crash and restart, messages are lost, duplicated, reordered and delayed by arbitrary amounts, and nobody can tell a slow node from a dead one.
The model Paxos assumes
| Assumption | Paxos's position |
|---|---|
| Failures | Crash-recovery: nodes stop, and may later restart with their stable storage intact |
| Byzantine behaviour | Not tolerated: nodes do not lie or corrupt messages (see Byzantine Fault Tolerance for that) |
| Network | Asynchronous: messages can be lost, delayed, duplicated, reordered, but not forged |
| Clocks | Not needed for safety at all. Only timeouts, for liveness |
| Fault tolerance | With acceptors, tolerates simultaneous failures |
| Storage | Each acceptor must durably record its promise and its accepted proposal before replying |
That last row is the one implementers forget. The whole safety argument rests on acceptors remembering what they promised. An acceptor that restarts with an empty disk is not a "recovered node"; it is a new node wearing the old one's name, and it can break safety (see Failure modes).
Why the obvious approaches fail
It helps to see why simpler protocols do not work, because every rule in Paxos exists to close one of these holes.
| Naive protocol | What breaks |
|---|---|
| One fixed coordinator decides | Coordinator crashes, and nobody can decide. Not fault tolerant. |
| Acceptors accept the first value they see, majority wins | Three acceptors, three proposers each reach one acceptor first: a three-way split and no majority, forever. |
| Acceptors accept every value, latest wins | Value A reaches a majority and is "chosen", then value B overwrites it on a majority. Two values chosen over time, which violates safety. |
| Use timestamps to order proposals | Clocks drift and skew; two proposers can produce the same or inverted timestamps. Safety now depends on clock accuracy. |
| Wait for every node to agree | One crashed node blocks everything. This is basically two-phase commit, and it blocks the same way (see Distributed Transactions). |
Paxos's answer combines three ideas: numbered proposals so newer attempts can supersede older ones, majority quorums so any two decisions share a witness, and a rule that forces new proposals to carry forward any value that might already have been chosen.
Roles
Every node can play any or all roles simultaneously.
| Role | Responsibility |
|---|---|
| Proposer | Proposes a value; drives the protocol forward |
| Acceptor | Votes on proposals; remembers what it has accepted |
| Learner | Learns the chosen value once consensus is reached |
In practice: every node is a proposer, acceptor, and learner. One node is typically the distinguished proposer (leader) to avoid dueling proposers.
The roles separate concerns cleanly:
- Acceptors are the memory of the system. They are the only role whose state matters for safety. The number of acceptors determines fault tolerance: 3 acceptors tolerate 1 failure, 5 tolerate 2.
- Proposers are stateless drivers apart from the ballot counter. Any number of them can exist, and any of them can crash at any time without harming safety. A crashed proposer just leaves a round unfinished, and another proposer can pick it up.
- Learners are observers. They do nothing but count
Acceptedmessages. In a replicated database, the learners are the replicas that apply the chosen command to their state machine.
Proposal numbers (ballots)
Every proposal carries a number, often called a ballot. Two properties are required:
- Totally ordered. Any two ballots can be compared.
- Unique across proposers. Two different proposers must never use the same ballot. If they did, two acceptors could accept different values under "the same" proposal and the safety argument collapses.
The standard construction is a pair (round, proposer_id) compared lexicographically, or the equivalent integer:
def next_ballot(highest_seen_round: int, my_id: int, num_proposers: int) -> int:
# Unique per proposer (different residues mod num_proposers) and higher than anything seen.
round_ = highest_seen_round + 1
return round_ * num_proposers + my_id
The proposer must also persist the highest round it has used, or a restarted proposer might reuse a ballot it already sent with a different value.
Quorums
A quorum is any majority of acceptors: out of . The single property Paxos needs from quorums is that any two of them intersect. Majorities have this property, and so do other quorum systems (grids, weighted votes). Flexible Paxos showed that only Phase 1 quorums need to intersect Phase 2 quorums, which is a weaker requirement.
| Acceptors | Quorum size | Failures tolerated |
|---|---|---|
| 3 | 2 | 1 |
| 4 | 3 | 1 (the 4th node adds cost, not tolerance) |
| 5 | 3 | 2 |
| 7 | 4 | 3 |
That is why consensus clusters are almost always odd-sized.
Single-Decree Paxos (The Classic)
Reaches agreement on one value, one time. Two phases:
Phase 1: Prepare / Promise
Proposer → Acceptors: Prepare(n)
Acceptors → Proposer: Promise(n, accepted_value_if_any)
- Proposer chooses a proposal number
n(must be unique and higher than any it's used before) - Sends
Prepare(n)to a majority of acceptors - Each acceptor that receives
Prepare(n):- If
n> any promise it has already made: promises not to accept any proposal numbered <n, responds with the highest-numbered proposal it has already accepted (if any) - Otherwise: ignores or rejects
- If
sequenceDiagram
participant P as Proposer
participant A1 as Acceptor A1
participant A2 as Acceptor A2
participant A3 as Acceptor A3
P->>A1: Prepare(n=5)
P->>A2: Prepare(n=5)
P->>A3: Prepare(n=5)
Note over A1: promised was 0, so promise 5, nothing accepted
A1-->>P: Promise(5, none)
Note over A2: promised was 3, accepted (3, X)
A2-->>P: Promise(5, accepted 3 with X)
Note over A3: already promised 7, so reject
A3-->>P: Nack(promised 7)
Note over P: 2 of 3 promises is a majority. Highest accepted is (3, X), so the value must be X
Phase 1 does two jobs at once. It locks out older ballots (every acceptor that promises n will refuse anything lower from now on), and it discovers the past (the proposer learns whether some value may already have been chosen). A Nack that carries the acceptor's promised ballot is an optimisation, not part of the core algorithm; it lets the proposer skip straight to a higher ballot instead of waiting for a timeout.
Phase 2: Accept / Accepted
Proposer → Acceptors: Accept(n, v)
Acceptors → Proposer: Accepted(n, v)
-
If proposer receives promises from a majority:
- If any acceptor returned an already-accepted value, the proposer must use the value with the highest proposal number
- Otherwise, proposer can use its own value
v
-
Proposer sends
Accept(n, v)to a majority -
Each acceptor that receives
Accept(n, v):- If it hasn't promised to ignore proposals <
n: accepts and sendsAccepted(n, v)to learner(s) - Otherwise: ignores
- If it hasn't promised to ignore proposals <
-
When a learner hears
Accepted(n, v)from a majority: valuevis chosen
Correction
Step 6 is worded ambiguously above. The precise rule: an acceptor accepts Accept(n, v) unless it has already promised a ballot greater than n. Having promised exactly n (the normal case) is fine. Accepting also raises its promised ballot to n if it was lower.
sequenceDiagram
participant P as Proposer
participant A1 as Acceptor A1
participant A2 as Acceptor A2
participant A3 as Acceptor A3
participant L as Learner
P->>A1: Accept(n=5, X)
P->>A2: Accept(n=5, X)
P->>A3: Accept(n=5, X)
Note over A1: promised 5, so accept and persist (5, X)
A1->>L: Accepted(5, X)
Note over A2: promised 5, so accept and persist (5, X)
A2->>L: Accepted(5, X)
Note over A3: promised 7, which is higher, so ignore
Note over L: 2 of 3 acceptors accepted (5, X), so X is chosen
L-->>P: X chosen
What each acceptor stores
| Field | Meaning | Updated on |
|---|---|---|
promised_n | Highest ballot this acceptor has promised | Prepare with a higher ballot, or Accept with a higher ballot |
accepted_n | Ballot of the last proposal accepted | Accept |
accepted_v | Value of the last proposal accepted | Accept |
Three fields, all durable. An acceptor never needs to remember older accepted proposals, only the most recent one, because a newer accepted proposal is always at least as constrained as the older ones.
A runnable model
The following is a complete single-decree Paxos in about 40 lines of Python, without networking, so the rules are visible. The reach argument simulates a proposer that can only talk to some acceptors.
from dataclasses import dataclass
from typing import Optional
@dataclass
class Acceptor:
promised: int = -1 # highest ballot promised
accepted_n: int = -1 # ballot of the accepted proposal, -1 = none
accepted_v: Optional[str] = None
alive: bool = True
def prepare(self, n: int):
if not self.alive or n <= self.promised:
return None # reject (a real acceptor would send a NACK)
self.promised = n # must be durable BEFORE replying
return (self.accepted_n, self.accepted_v)
def accept(self, n: int, v: str) -> bool:
if not self.alive or n < self.promised:
return False
self.promised = n
self.accepted_n, self.accepted_v = n, v # durable before replying
return True
def propose(acceptors, n, my_value, reach=None):
"""One round of single-decree Paxos. `reach` = indices this proposer can talk to."""
reach = range(len(acceptors)) if reach is None else reach
majority = len(acceptors) // 2 + 1
# Phase 1: Prepare / Promise
promises = [p for i in reach if (p := acceptors[i].prepare(n)) is not None]
if len(promises) < majority:
return None # retry later with a higher ballot
# The value-selection rule: adopt the highest-ballot accepted value, if any
prior_n, prior_v = max(promises, key=lambda p: p[0])
value = prior_v if prior_n >= 0 else my_value
# Phase 2: Accept / Accepted
acks = sum(acceptors[i].accept(n, value) for i in reach)
return value if acks >= majority else None
if __name__ == "__main__":
a = [Acceptor() for _ in range(5)]
# P1 reaches A0..A2: "red" is chosen
assert propose(a, n=11, my_value="red", reach=[0, 1, 2]) == "red"
# P2 uses a higher ballot and a different majority, overlapping only at A2
assert propose(a, n=12, my_value="blue", reach=[2, 3, 4]) == "red" # forced to adopt
# A stale proposer with an old ballot gets nowhere
assert propose(a, n=11, my_value="green") is None
# Even with two acceptors down, a majority (3 of 5) still decides, and it is still red
a[0].alive = a[1].alive = False
assert propose(a, n=21, my_value="green") == "red"
print("all safety checks passed")
Notice the second assertion. Proposer P2 wanted blue, but because its quorum overlapped the quorum that chose red, it was forced to propose red. That one line, value = prior_v if prior_n >= 0 else my_value, is the heart of Paxos.
Worked Example: Two Competing Proposers
The example in Paxos Made Simple walks through a clean round. This one is messier on purpose: two proposers, five acceptors, a delayed message and a crash. We run it twice with one difference, to show the two ways Paxos resolves a race.
Setup: acceptors A1 to A5 (quorum is 3). Proposer P1 uses ballot 11 and wants value X. Proposer P2 uses ballot 12 and wants value Y. Ballot 12 beats ballot 11.
Run A: the earlier value never reached a quorum
sequenceDiagram
participant P1 as P1 (ballot 11)
participant A1
participant A2
participant A3
participant A4
participant A5
participant P2 as P2 (ballot 12)
P1->>A1: Prepare(11)
P1->>A2: Prepare(11)
P1->>A3: Prepare(11)
A1-->>P1: Promise(11, none)
A2-->>P1: Promise(11, none)
A3-->>P1: Promise(11, none)
P1->>A1: Accept(11, X)
P1->>A2: Accept(11, X)
Note over P1,A3: Accept(11, X) to A3 is delayed in the network. P1 then crashes
P2->>A3: Prepare(12)
P2->>A4: Prepare(12)
P2->>A5: Prepare(12)
A3-->>P2: Promise(12, none)
A4-->>P2: Promise(12, none)
A5-->>P2: Promise(12, none)
Note over A3: the delayed Accept(11, X) finally arrives. Promised 12, so reject
P2->>A3: Accept(12, Y)
P2->>A4: Accept(12, Y)
P2->>A5: Accept(12, Y)
Note over A3,A5: three acceptors hold (12, Y). Y is chosen
Acceptor state after each step:
| Step | A1 | A2 | A3 | A4 | A5 | Chosen? |
|---|---|---|---|---|---|---|
| P1 Prepare(11) to A1–A3 | p11 | p11 | p11 | – | – | no |
| P1 Accept(11, X) reaches A1, A2 | p11 (11,X) | p11 (11,X) | p11 | – | – | no, only 2 of 5 |
| P2 Prepare(12) to A3–A5 | p11 (11,X) | p11 (11,X) | p12 | p12 | p12 | no |
| Late Accept(11, X) at A3 | unchanged | unchanged | rejected | – | – | no |
| P2 Accept(12, Y) to A3–A5 | p11 (11,X) | p11 (11,X) | p12 (12,Y) | p12 (12,Y) | p12 (12,Y) | Y |
(p11 means "promised 11"; (11,X) means "accepted value X at ballot 11".)
Now P1 restarts and tries again with ballot 21, reaching A1, A2, A3. It gets back (11,X), (11,X) and (12,Y). The highest ballot is 12, so P1 must propose Y. Two acceptors still hold X, which looks alarming, but X was never chosen and can never be chosen now: any future quorum overlaps A3–A5, so any future proposer will see (12,Y) or something newer carrying Y.
Lesson: acceptors can hold a value that is not and never will be chosen. "Accepted somewhere" is not "chosen". Only a quorum accepting the same ballot makes a value chosen.
Run B: the new quorum sees the earlier value
Same as Run A, except P2's Prepare goes to A2, A4, A5 instead of A3, A4, A5.
| Step | A1 | A2 | A3 | A4 | A5 | Chosen? |
|---|---|---|---|---|---|---|
| P1 Accept(11, X) reaches A1, A2 | p11 (11,X) | p11 (11,X) | p11 | – | – | no |
| P2 Prepare(12) to A2, A4, A5 | p11 (11,X) | p12 (11,X) | p11 | p12 | p12 | no |
A2's promise carries (11, X). P2 must now propose X, not Y, even though X has not been chosen and P2 cannot know whether it was. P2 sends Accept(12, X) to A2, A4, A5, they accept, and X is chosen at ballot 12. Then the delayed Accept(11, X) reaches A3; A3 has only promised 11, so it accepts it too, which is harmless because it is the same value.
Lesson: the value-selection rule is conservative. A proposer cannot tell "accepted by a minority" apart from "accepted by a majority I can't see", so whenever it sees any accepted value it has to assume that value might be chosen and carry it forward. Paxos sometimes chooses a value that a crashed proposer only half-proposed. That is correct behaviour, not a bug: validity only requires that the chosen value was proposed by someone.
What the two runs have in common
In both runs, P1 and P2 reached different conclusions about what they wanted, but the protocol produced exactly one chosen value, and every later round agrees with it. Which value won depended on timing and on which acceptors each proposer happened to contact. Paxos does not promise that the "first" or the "best" value wins. It only promises that one value wins, permanently.
Why It Works
The magic is in the constraint: if a value has already been chosen, no future round can choose a different value.
Here's why: If v was chosen in round n, that means a majority Q1 accepted it. Any future proposer in round m > n must get promises from a majority Q2. Since any two majorities overlap (quorum intersection), at least one node in Q2 was also in Q1. That node will report (n, v) in its promise, forcing the new proposer to propose v again.
Round n: Majority Q1 accepts (n, v) → v is chosen
Round m: New proposer contacts majority Q2
Q1 ∩ Q2 ≠ ∅ → at least one node reports (n, v)
Proposer must use v → safety preserved ✓
Tightening the argument
The sketch above has a gap that is worth closing, because closing it explains why the proposer picks the highest-numbered accepted value and not just any accepted value.
The overlapping node might not report (n, v). Between round n and round m, it may have accepted a proposal from some round k with n < k < m, and it will report that instead. So the real invariant is stronger:
Invariant. If value
vis chosen at ballotn, then every proposal with a ballot higher thannthat any acceptor ever accepts also carries valuev.
Proof sketch, by induction on ballots above n:
- Take the first ballot
m > nwhose Phase 2 runs. Its proposer collected promises from a quorumQ2that overlapsQ1(the quorum that accepted(n, v)). - The overlapping acceptor accepted
(n, v)before promisingm(if it had promisedmfirst, it would have refused ballotn < m). So its promise reports something with ballot at leastn. - Every accepted proposal with ballot between
nandmcarriesv(induction hypothesis, and here there are none, sincemis the first). - So the highest-ballot proposal reported in
Q2has ballot at leastn, and carriesv. The proposer must pick it. Ballotmcarriesv. - Repeat for the next ballot, using the fact that all ballots in between already carry
v.
Step 2 is where the promise matters, and step 4 is where highest matters. If the proposer picked an arbitrary reported value, it could pick a stale value from a ballot below n, and the invariant would break. The full proof, with each invariant spelled out, is in Paxos Made Simple: Formal Safety Proof.
Each rule and the failure it prevents
| Rule | Remove it and... |
|---|---|
| Ballots are unique per proposer | Two proposers both run "ballot 7" with different values, and two acceptors each accept a different (7, ·). Learners cannot tell them apart. |
| Acceptors refuse ballots below their promise | An old proposer's slow Accept lands after a new proposer read the acceptor's state, so the new proposer's view of "the past" is already out of date. |
| Promise is durable before replying | Acceptor promises, crashes, restarts with no memory, and accepts an older ballot it had promised to refuse. |
| Proposer adopts the highest accepted value | New proposer pushes its own value over a value that was already chosen. Two values chosen. |
| Quorums intersect | Two disjoint groups choose two different values during a partition. |
| A value is chosen only when a quorum accepts the same ballot | Counting "acceptors that hold X" across different ballots can declare a value chosen when it wasn't, as in Run A, where two acceptors still hold X. |
Safety does not depend on timing
None of the rules above mention clocks, timeouts or message delays. Messages can be arbitrarily late, duplicated or reordered (a duplicated Accept is idempotent, a delayed one is either still valid or gets rejected) and safety still holds. That is the property that makes Paxos worth its complexity: the worst a bad network can do is stop progress, never produce a wrong answer.
Learning the Chosen Value
Learners have to find out that a quorum accepted the same ballot. There are a few ways to arrange that:
| Approach | Messages | Latency | Notes |
|---|---|---|---|
Every acceptor sends Accepted to every learner | Lowest | Good for small clusters | |
| Acceptors tell the proposer, which tells learners | One extra hop | Common: the leader is the natural place to count | |
| Acceptors tell one distinguished learner | One extra hop | Single point of delay, not of safety |
A learner that missed the messages (it was down, or messages were lost) can always ask, or simply run a Paxos round itself: Phase 1 will reveal the chosen value, and Phase 2 re-proposing it is harmless. That property ("asking is just proposing") is one reason Paxos composes nicely into larger systems.
The Dueling Proposers Problem
What if two proposers compete simultaneously?
Proposer A: Prepare(n=1) → accepted
Proposer B: Prepare(n=2) → accepted (invalidates A's promise)
Proposer A: Accept(n=1, vA) → rejected (promised n≥2)
Proposer A: Prepare(n=3) → accepted (invalidates B's promise)
Proposer B: Accept(n=2, vB) → rejected
...forever
(In this trace, "accepted" on a Prepare line means "a majority promised". Acceptors promise on Prepare and accept only on Accept.)
Two proposers can livelock, each invalidating the other's promises. Paxos can live-lock indefinitely — it violates liveness.
sequenceDiagram
participant PA as Proposer A
participant Q as Acceptor majority
participant PB as Proposer B
PA->>Q: Prepare(1)
Q-->>PA: Promise(1)
PB->>Q: Prepare(2)
Q-->>PB: Promise(2)
PA->>Q: Accept(1, vA)
Q-->>PA: Nack, promised 2
PA->>Q: Prepare(3)
Q-->>PA: Promise(3)
PB->>Q: Accept(2, vB)
Q-->>PB: Nack, promised 3
PB->>Q: Prepare(4)
Q-->>PB: Promise(4)
Note over PA,PB: neither Accept ever lands. Safe, but nothing is ever chosen
This is not a bug in Paxos; it is FLP showing through. In an asynchronous system no deterministic protocol can guarantee both safety and termination with even one possible crash, and Paxos picks safety. Dueling proposers are the concrete execution that keeps it from terminating. See FLP Impossibility for why this cannot be designed away, only made unlikely.
Solution: Elect a distinguished proposer (leader). Only the leader runs Phase 1. If the leader fails, elect a new one. This is the same approach Raft formalizes.
Making the livelock unlikely
Electing a leader itself requires something like consensus, so in practice systems combine several techniques:
| Technique | How it helps | Cost |
|---|---|---|
| Randomized backoff before retrying with a higher ballot | Desynchronises the duellers, so one of them finishes both phases first | Adds latency after every conflict |
| Leader via failure detector (lowest-id live node, or a lease) | Usually only one node thinks it is the leader, so usually only one proposer runs | Two leaders can briefly coexist, which is safe but slow |
| Leader leases | A proposer holds a time-bounded right to propose; others wait for it to expire | Depends on bounded clock drift for liveness (and for lease-based reads, safety) |
| Forwarding | Non-leaders forward client requests to the leader instead of proposing | One extra hop for clients connected to followers |
| Nack with the promised ballot | Losers jump straight to a higher ballot instead of probing | Fewer wasted rounds, but no guarantee |
The leader does not have to be unique for Paxos to stay correct. Two nodes that both think they are leader is a performance problem in Paxos, not a correctness problem, because ballots decide which one wins at the acceptors. Contrast that with systems where leadership is used to authorise side effects outside the protocol (writing to a shared disk, calling an external API): there, two leaders can corrupt data, and you need fencing tokens.
The timeout values that drive election and backoff are covered in Timeouts, Retries and Backoff, and the theory of "suspecting" a leader in Failure Detectors.
Multi-Paxos
Single-decree Paxos agrees on one value. Real systems need a replicated log — an ordered sequence of commands. Multi-Paxos runs Paxos instances for each log slot.
Optimization: Phase 1 is expensive (two round trips). If the same leader runs consecutive instances, Phase 1 can be skipped for subsequent slots (the leader's promises from the first round cover all future rounds until it steps down).
Correction
Phase 1 costs one round trip (Prepare out, Promise back); a full single-decree round with both phases costs two. The optimisation is that a stable leader pays Phase 1 once and then commits each new slot with a single Phase 2 round trip.
First log entry: Phase1 + Phase2 (two round trips)
Subsequent entries: Phase2 only (one round trip)
This is how Google Chubby and ZooKeeper achieve decent performance despite the theoretical overhead.
(Chubby does run Multi-Paxos. ZooKeeper gets the same "pay recovery once, then one round trip per write" shape from ZAB, which is a separate protocol; see the correction at the top of the page.)
How a leader takes over every slot at once
The trick is that one Prepare can cover all slots from some index onward. A new leader with ballot b:
- Sends
Prepare(b, from_slot=k)wherekis the first slot it does not know to be chosen. - Each acceptor promises
bfor every slot≥ kand replies with every proposal it has accepted at slots≥ k. - For each slot where some acceptor reported an accepted value, the leader must re-propose the highest-ballot value (the single-decree rule, slot by slot).
- For each slot below the highest reported slot where nobody reported anything, the leader proposes a no-op to fill the gap.
- From then on, every new client command goes to the next free slot with Phase 2 only.
sequenceDiagram
participant C as Client
participant L as Leader (ballot 8)
participant F1 as Acceptor F1
participant F2 as Acceptor F2
Note over L,F2: Once, on becoming leader
L->>F1: Prepare(8, slots from 40)
L->>F2: Prepare(8, slots from 40)
F1-->>L: Promise(8), accepted slot 41 = (5, SET y)
F2-->>L: Promise(8), nothing at 40 or later
Note over L: slot 41 must be re-proposed as SET y. Slot 40 is a gap, fill with no-op
L->>F1: Accept(8, slot 40, no-op) and Accept(8, slot 41, SET y)
L->>F2: Accept(8, slot 40, no-op) and Accept(8, slot 41, SET y)
F1-->>L: Accepted
F2-->>L: Accepted
Note over L,F2: Steady state, one round trip per command
C->>L: SET x = 3
L->>F1: Accept(8, slot 42, SET x = 3)
L->>F2: Accept(8, slot 42, SET x = 3)
F1-->>L: Accepted(8, 42)
Note over L: leader plus F1 is a majority of 3. Slot 42 chosen
L-->>C: OK
L->>F2: Commit up to slot 42 (piggybacked on next message)
Gaps, ordering and execution
Multi-Paxos lets a leader have many slots in flight at once, and slots can be chosen out of order: slot 43 might be chosen before slot 42 if messages for 42 were lost. That is allowed, but the state machine must still execute in slot order. A replica applies slot 42 only once slots 1 to 41 are chosen and applied.
| Situation | What happens |
|---|---|
| Slot chosen, earlier slot not yet chosen | Replica buffers it; does not execute yet |
| Old leader died with slot 40 half-proposed | New leader's Phase 1 finds it (if any acceptor in the quorum saw it) and re-proposes it, or fills with a no-op |
| Same client command proposed in two slots (client retried after leader change) | Both get chosen. The state machine must deduplicate, usually by client id and request sequence number |
| Replica far behind | Fetches chosen values from peers, or installs a snapshot, then continues |
This is one of the real differences from Raft. Raft forbids holes: a follower only appends an entry if it matches the previous one, so logs are always contiguous prefixes. Multi-Paxos permits holes and has the new leader patch them up.
Reads in Multi-Paxos
A leader cannot simply answer reads from its local state, because it might have been deposed without knowing it and a newer leader may have committed writes. Options:
| Read strategy | Guarantee | Cost |
|---|---|---|
| Put the read through the log as a command | Linearizable | A full consensus round per read |
| Leader confirms it is still leader with a round of heartbeats to a majority, then reads | Linearizable | One round trip, no disk write |
| Leader lease: acceptors promise not to support another leader for T seconds | Linearizable if clock drift is bounded | No round trip; safety now depends on clocks |
| Read from any replica | Possibly stale | Free |
Google's "Paxos Made Live" paper (Chandra, Griesemer and Redstone, 2007) describes Chubby using master leases for exactly this reason: so the master can serve reads locally. The lease is the place where a clock assumption sneaks into an otherwise clock-free protocol. More on that trade-off in Leases and Fencing.
Batching and pipelining
| Optimisation | Effect |
|---|---|
| Batching: many client commands in one slot | Amortises the round trip and the fsync across many commands |
| Pipelining: send Accept for slot 43 before 42 is chosen | Keeps the network busy, so throughput is no longer bounded by one RTT per command |
| Group commit at acceptors | One fsync for many accepted slots |
| Thrifty: send Accept to exactly a quorum, not to everyone | Less bandwidth, but one slow acceptor stalls a round until a retry |
With these, a well-built Multi-Paxos group handles tens of thousands of small writes per second or more in a single data centre; the bottleneck is usually the leader's CPU, network bandwidth, or disk fsync rate, not the protocol.
Reconfiguration: Changing the Set of Acceptors
Machines die and are replaced. A long-lived Paxos group has to change membership without stopping and, more importantly, without ever having two quorums that don't overlap. Lamport's original paper only sketched this, and it is one of the places where real implementations diverge most.
The danger
Suppose you go from 3 acceptors {A, B, C} to 5 acceptors {A, B, C, D, E} by just switching everybody's config file.
flowchart LR
subgraph Old["Old config: A, B, C (quorum 2)"]
A["A"]
B["B"]
end
subgraph New["New config: A to E (quorum 3)"]
C["C"]
D["D"]
E["E"]
end
A --- B
C --- D
D --- E
If A and B have not yet switched while C, D and E have, then {A, B} is a quorum of the old config and {C, D, E} is a quorum of the new one, and they share no member. Two leaders could choose two different values for the same slot. Every reconfiguration scheme exists to prevent that window.
Approaches
| Approach | Idea | Used / described by |
|---|---|---|
| Config in the log, with an α window | The membership change is itself a command in slot i. It takes effect at slot i + α. The leader may only have α slots in flight. | Lamport's original "Part-Time Parliament" and "Paxos Made Simple" |
| Stop-and-restart (stop sign) | Choose a special "stop" command. Nothing after it is chosen in the old config. A new Paxos instance with the new members starts from that state. | Stoppable Paxos (Lamport, Malkhi and Zhou, 2008) |
| Vertical Paxos | Configuration is managed by an external master (itself replicated). Each ballot is tied to a configuration, and a new config's leader reads the old config's state before proceeding. | Vertical Paxos (Lamport, Malkhi and Zhou, 2009) |
| Joint consensus | During the change, decisions need a majority of the old config and a majority of the new one. | Raft paper |
| One server at a time | Adding or removing a single member always leaves old and new majorities overlapping. | Raft dissertation, etcd |
The α window in practice
With the "config in the log" approach, if slot 100 contains reconfig({A,B,C,D,E}) and α is 3, then slots 101 to 102 still use the old config and slot 103 onward uses the new one. The leader cannot propose slot 103 until it knows slot 100 is chosen, because until then it doesn't know which acceptors slot 103 should go to. So α bounds the pipeline: a large α allows more concurrency but delays every reconfiguration; α = 1 serialises everything.
Operational rules that apply to every approach
- Change one thing at a time. Replace a dead node by first adding the new one, letting it catch up, then removing the old one. Swapping both in one step multiplies the risk.
- Never remove a majority at once. A 5-node group losing 3 members in one reconfiguration loses the ability to confirm the change itself.
- A new acceptor must not vote until it has the state. "Paxos Made Live" describes Google's choice to bring a replica with a wiped or corrupted disk back as a non-voting participant until it has caught up, for this reason.
- Removed nodes must be told they are removed, or they will time out, start elections with higher ballots, and disrupt the live group. (Raft adds a "pre-vote" phase to stop exactly this.)
Paxos vs Raft
| Paxos | Raft | |
|---|---|---|
| Log replication | Multi-Paxos (add-on) | Built-in |
| Leader election | External mechanism | Built-in, well-specified |
| Log matching | Possible gaps, complex reconciliation | Strict ordering, no gaps |
| Understandability | Notoriously difficult | Designed for understandability |
| Implementation | Hard to get right | Hard but much better-specified |
| Performance | Comparable | Comparable |
Lamport himself called Paxos hard to understand and implement correctly. A 2014 Stanford paper showed that even engineers who thought they understood Paxos often implemented it incorrectly. Raft was designed explicitly to be easier to understand — and it succeeded.
Correction
Both claims in the paragraph above are misattributed. Lamport has consistently said the opposite: "Paxos Made Simple" (2001) opens by stating that the algorithm, explained plainly, is very simple. The complaint that it is hard to implement comes most famously from Google's "Paxos Made Live" (2007), which describes the large gap between the paper and a production system. The 2014 Stanford paper is the Raft paper (Ongaro and Ousterhout, "In Search of an Understandable Consensus Algorithm"). Its user study had students learn both algorithms and take a quiz on each; students scored better on Raft. It measured understanding, not implementation bugs.
Use Raft for new implementations. Use Paxos knowledge to understand ZooKeeper, Chubby, and Spanner internals.
They are closer than the table suggests
Howard and Mortier's 2020 paper "Paxos vs Raft: Have we reached consensus on distributed consensus?" put both algorithms into the same notation and concluded that they are strikingly similar, and that the main difference is how a leader is elected and what it has to do afterwards. The terms map almost one to one:
| Paxos | Raft | Role in the protocol |
|---|---|---|
| Ballot / proposal number | Term | Orders leadership attempts. Higher wins |
Prepare(b) | RequestVote(term) | Ask a majority to back a new leader |
Promise | Vote granted | Commit not to support older leaders |
Accept(b, slot, v) | AppendEntries(term, index, entry) | Leader replicates a log entry |
Accepted | AppendEntries success | Follower stored the entry |
| Chosen | Committed | A majority stored it under the current leader |
| Distinguished proposer | Leader | The node that drives progress |
| No-op to fill a gap | No-op entry at the start of a term | Lets a new leader commit earlier entries |
The real difference: who can become leader
| Multi-Paxos | Raft | |
|---|---|---|
| Who can win | Any node with a high enough ballot | Only a candidate whose log is at least as up-to-date as a majority's |
| After winning | Leader learns missing values from Phase 1 replies and re-proposes them | Leader already has every committed entry. It just overwrites conflicting follower entries |
| Data flow | Values can flow to the new leader | Entries only ever flow from leader to followers |
| Log shape | Holes allowed | Contiguous prefix always |
Raft's election restriction is what makes it simpler to reason about: the leader's log is the truth, full stop. The price is that a node with a stale log cannot become leader even if it is the only one that can reach a majority quickly, and election may take an extra round. Paxos's approach is more flexible and the leader can be any node, but the leader-change path is where most Paxos implementation bugs live.
Variants
Byzantine Paxos (BFT Paxos): Handles Byzantine (malicious) failures, not just crash-stop. Requires 3f+1 nodes to tolerate f failures. Used in blockchain and high-security systems.
Fast Paxos: Allows clients to send values directly to acceptors in the common case, reducing latency by one round trip. Falls back to classic Paxos on conflict.
Cheap Paxos: Reduces the number of full participants needed for fault tolerance using auxiliary replicas.
Flexible Paxos (FPaxos): Generalizes quorum requirements — Phase 1 and Phase 2 quorums don't both need to be majorities, as long as they overlap. Enables latency/fault-tolerance trade-offs.
EPaxos (Egalitarian Paxos): No designated leader. Any replica can commit a command; commands that don't conflict commit in one round trip, and conflicting ones need an extra round to agree on dependencies. Good for geo-distributed groups where each region would rather not send every write to a distant leader. Covered in detail in Paxos Made Simple: EPaxos.
| Variant | Problem it targets | Key change | Cost |
|---|---|---|---|
| Multi-Paxos | One value is not a log | Stable leader, Phase 1 once for all slots | Leader is a bottleneck and a single point of slowness |
| Fast Paxos | Client to leader to acceptors is an extra hop | Clients write directly to acceptors | Larger quorums (about 3/4 of acceptors), slower recovery on collision |
| Cheap Paxos | Full replicas are expensive | Auxiliary acceptors used only during failures | Slower failover |
| Flexible Paxos | Majorities in both phases are more than needed | Only Phase 1 and Phase 2 quorums must intersect | Smaller Phase 2 quorum means larger Phase 1 quorum |
| EPaxos | Single leader adds WAN latency | Leaderless, dependency tracking | Much harder to implement correctly; conflicts cost extra |
| Mencius | Leader load | Round-robin slot ownership | Slowest replica affects everyone |
| Byzantine Paxos | Nodes may lie | Larger quorums, authenticated messages | nodes and much more messaging |
Real-World Usage
Google Chubby: Distributed lock service. Uses Multi-Paxos for its replicated log. Powers Bigtable tablet server election and GFS master election.
(More precisely, per the Chubby paper: GFS uses Chubby to appoint its master, and Bigtable uses it to elect its master, to let the master discover tablet servers, and to let clients find the master.)
Apache Zookeeper (ZAB): ZooKeeper Atomic Broadcast is a Paxos variant optimized for primary-backup replication. Powers Kafka's controller election, HBase master election, and countless other systems.
(As noted at the top of the page, ZAB is better described as a sibling of Paxos than a variant of it. Also, newer Kafka versions replace ZooKeeper with KRaft, Kafka's own Raft-based controller quorum; Kafka 4.0 removed ZooKeeper mode entirely.)
Google Spanner: Uses Paxos groups for each tablet (data shard). Combines Paxos with TrueTime (GPS/atomic clock-based) to achieve external consistency across globally distributed data.
etcd: Uses Raft (Paxos successor), but understanding Paxos explains why etcd is designed the way it is.
Google Megastore: Replicates each "entity group" across data centres with Paxos, and was one of the first published systems to run Paxos across a wide area for every write. Spanner later built on its lessons.
Apache Cassandra lightweight transactions: INSERT ... IF NOT EXISTS and UPDATE ... IF col = x run a Paxos round among the replicas of that partition. It is single-decree style, per partition, with no long-lived leader, which is why these operations cost several round trips (prepare/promise, read, propose/accept, commit) and are much slower than ordinary Cassandra writes.
| System | What Paxos decides | Scope |
|---|---|---|
| Chubby | Every write to the lock service's database | One cell (typically 5 replicas) |
| Spanner | Every write to a shard; a Paxos leader also manages locks for transactions | One Paxos group per split, many groups per database |
| Megastore | Every write to an entity group | One group per entity group, across data centres |
| Cassandra LWT | One conditional update | One partition's replica set |
The Paxos Complexity Problem
Lamport's original paper described Paxos as a solution to the consensus problem. What it didn't describe was:
- How to handle leader election
- How to handle log gaps and holes
- How to handle leader changes mid-stream
- How to perform log compaction
- How to handle Byzantine failures
Each of these requires additional algorithms. Real Paxos implementations are 10-20x more complex than the algorithm itself. This is why Raft, which addresses all of these in a single coherent design, became the practical consensus algorithm of choice.
Correction
Raft addresses the first four items (election, log consistency, leader change, snapshots) but not Byzantine failures; like Paxos it assumes crash-recovery nodes that don't lie. Handling Byzantine failures needs a different class of protocols such as PBFT. Also, "10–20x" is a rough rule of thumb, not a measured figure; the point, which "Paxos Made Live" makes at length, is that the core algorithm is a small fraction of a production implementation.
The things "Paxos Made Live" reported having to build or handle on top of the algorithm give a good sense of the gap:
| Concern | Why the paper doesn't cover it |
|---|---|
| Disk corruption | The model assumes stable storage is reliable. Real disks lose and corrupt data, so a replica must detect it and rejoin carefully |
| Master leases | Needed for fast local reads, and they bring clocks back into the picture |
| Snapshots and log truncation | The log grows forever otherwise; the snapshot must be consistent with the log position |
| Group membership | See the reconfiguration section above |
| Testing | They built a fault-injection framework and still found bugs; the protocol's corner cases are rare in normal operation |
Failure Modes and How Implementations Handle Them
| Failure | What happens | Mitigation |
|---|---|---|
| Acceptor crash, disk intact | Stops voting. Group continues while a majority is up | Restart; it resumes with its durable promise and accepted value |
| Acceptor amnesia (restarts with lost or rolled-back state) | Can accept a ballot it promised to refuse. Can cause two values to be chosen | fsync before replying, detect lost state (e.g. a marker file or epoch), rejoin as a non-voter until caught up |
| Leader crash mid-round | Slots in flight may be partly accepted | New leader's Phase 1 finds them and re-proposes, or fills gaps with no-ops |
| Network partition | Minority side cannot complete either phase. Majority side elects a leader and continues | Nothing to do for safety. Clients on the minority side see timeouts |
| Two leaders | Both run rounds. The higher ballot wins at the acceptors; the other gets Nacks | Safe. Fix with leases or better failure detection for performance |
| Duplicate client command after leader change | Same command chosen in two slots | Client id plus sequence number, deduplicated by the state machine |
| Ballot reuse after proposer restart | Same ballot, different value, can break safety | Persist the highest ballot used, or derive ballots from a durable counter |
| Slow acceptor | If it's in every quorum the leader uses, everything slows | Send to all acceptors and use the first majority that answers |
| Clock jump with lease-based reads | Old leader thinks its lease is still valid and serves stale reads | Conservative lease durations, monotonic clocks, bounded drift assumptions |
Real numbers
| Quantity | Typical magnitude |
|---|---|
| Commit latency, single data centre, Multi-Paxos steady state | One RTT to the nearest quorum (well under a millisecond on a good network) plus an fsync (from tens of microseconds on NVMe with a power-loss-protected cache to several milliseconds on cheaper disks) |
| Commit latency, quorum spread across regions | One RTT to the second-nearest region for a 3-region group, i.e. tens of milliseconds, often more |
| Messages per command, steady state | About (Accept to each acceptor, Accepted back) |
| Messages per command, full two-phase round | About |
| Durable writes per command | One per acceptor in the quorum, amortised by batching and group commit |
| Failover time | Dominated by the leader timeout, typically hundreds of milliseconds to a few seconds |
The fault-tolerance math is simple: . Every extra pair of acceptors buys one more tolerated failure and costs more latency (a bigger quorum means waiting for a slower member) and more bandwidth at the leader.
War Story (illustrative)
A team ran a homegrown Multi-Paxos configuration store on five containers. To speed up a slow benchmark, someone moved the acceptor state from a persistent volume to the container's local filesystem, which was wiped on restart. For months nothing happened, because restarts were rare and one at a time.
Then a node pool upgrade restarted three acceptors within a minute. Each came back with no promises and no accepted values. A leader with an older ballot, which had been partitioned briefly, sent its pending Accept for slot 912 to the three amnesiac acceptors. Having no record of any promise, they accepted. Slot 912 had already been chosen with a different value under the newer ballot on the old incarnations of those same nodes. Two replicas applied one command, three applied the other, and the config store served two different versions of a routing table.
The fix was a one-line deployment change back to persistent storage, plus a startup check: an acceptor that finds no state file, but whose node id is already a configured member, refuses to vote until an operator or the reconfiguration protocol re-adds it. The lesson is the one the algorithm states plainly: an acceptor's memory is the protocol. Faster without it means wrong.
Summary
Paxos proves that consensus is achievable despite failures. It does so with elegant minimalism: two phases, three roles, one quorum intersection invariant. Everything else in distributed consensus theory is either a simplification (Raft), an extension (Multi-Paxos), or a generalization (Flexible Paxos) of this core idea.
| Property | Guarantee |
|---|---|
| Safety | Only one value ever chosen |
| Liveness | Progress if a majority of acceptors are reachable (no dueling proposers) |
| Fault tolerance | Tolerates f failures with 2f+1 acceptors |
| Message complexity | O(n) per round (n = number of acceptors) |
The ideas to carry away:
- Numbered proposals let newer attempts override abandoned ones without coordination.
- Promises stop old proposals from landing after a new proposer has read the state.
- Adopting the highest accepted value is what carries a possibly-chosen value forward.
- Quorum intersection guarantees the new proposer will see it.
- Durable acceptor state is a correctness requirement, not a performance knob.
- Liveness needs a leader and timing, which is exactly where FLP says something must give.
Interview Questions
1. What are the two phases of Paxos, and what does each one achieve?
Phase 1 (Prepare/Promise) reserves a ballot number at a majority, so those acceptors will refuse older ballots, and it reports any previously accepted value so the proposer can carry it forward. Phase 2 (Accept/Accepted) asks the majority to accept a specific value under that ballot. A value is chosen once a majority accepts the same ballot.
2. Why must the proposer pick the value with the highest ballot among the promises, and not its own value or any reported value?
Because the highest-ballot reported value is the only one that might have been chosen, or that carries forward a chosen value. Quorum intersection ensures that if some value was chosen at ballot n, every quorum includes an acceptor that accepted ballot n or a later ballot carrying the same value. Picking a lower-ballot value could resurrect something that was superseded, and picking your own value could overwrite a chosen one.
3. Can two different values ever both be accepted by some acceptors? Is that a safety violation?
Yes, they can, and no, it isn't. In the worked example above, two acceptors hold X at ballot 11 while three hold Y at ballot 12. Safety concerns chosen values, and only Y reached a quorum at one ballot. X can never be chosen afterwards, because every future quorum will see Y's higher ballot.
4. How does Paxos relate to FLP? Does Paxos violate it?
No. FLP says no deterministic protocol in an asynchronous system can guarantee safety and termination with even one crash. Paxos keeps safety in every execution and gives up guaranteed termination: dueling proposers can keep it from deciding forever. It terminates in practice once the network behaves synchronously long enough for one leader to finish a round.
5. What happens if an acceptor loses its disk and restarts empty?
It may accept a proposal with a ballot it had promised to refuse, or forget a value it accepted that was part of a chosen quorum. If enough acceptors do this, a different value can be chosen for the same instance. Real systems must detect lost state and bring such a node back as a non-voter (or through reconfiguration) until it has rebuilt state from the others.
6. Why is Multi-Paxos faster than running single-decree Paxos per slot?
A stable leader runs Phase 1 once, covering every future slot. After that, each command needs only Phase 2: one round trip to a majority plus a durable write. Batching and pipelining let it amortise even that over many commands.
7. Two nodes both believe they are the Multi-Paxos leader. What breaks?
Nothing safety-wise inside Paxos. The acceptors have promised the higher ballot, so the lower-ballot leader's Accepts are rejected and it eventually learns it was deposed. Throughput drops while they fight. What can break is anything outside the protocol that trusts "I am leader", like lease-based local reads or side effects on external systems, which is why leases need bounded clock drift and external writes need fencing tokens.
8. How would you add a node to a 3-node Paxos group safely?
Bring the new node up as a learner, let it catch up on the log or a snapshot, then commit a reconfiguration command through the log (or use one-server-at-a-time changes, or joint consensus), so there is never a moment when an old-config majority and a new-config majority can both decide independently. Never just edit config files on all nodes at once.
9. What are the main differences between Multi-Paxos and Raft?
They are mostly the same algorithm in different terms (ballot and term, Prepare and RequestVote, Accept and AppendEntries). The differences: Raft only lets a candidate with an up-to-date log become leader, so data only flows from leader to followers, and Raft logs never have holes. Multi-Paxos lets any node become leader and has it learn and re-propose missing values, and it allows slots to be chosen out of order. Raft also specifies membership changes and snapshots as part of the algorithm.
10. Why do consensus clusters use 3 or 5 nodes and not 4 or 6?
Quorum is a majority. With 4 nodes the quorum is 3, so you still only tolerate 1 failure, the same as 3 nodes, while paying for an extra member in every quorum. 6 nodes tolerate 2 failures, the same as 5. Odd sizes give the most fault tolerance per node.
11. In a Flexible Paxos deployment with 10 acceptors, if the Phase 2 quorum is 3, what must the Phase 1 quorum be?
Phase 1 and Phase 2 quorums must intersect: , so . Steady-state writes only wait for 3 acceptors, which is fast, but leader election needs 8 of 10, so the group can only change leaders if no more than 2 acceptors are down.
Further Reading
- Leslie Lamport, "The Part-Time Parliament" (ACM TOCS, 1998) and "Paxos Made Simple" (2001)
- Tushar Chandra, Robert Griesemer, Joshua Redstone, "Paxos Made Live: An Engineering Perspective" (PODC 2007)
- Diego Ongaro, John Ousterhout, "In Search of an Understandable Consensus Algorithm" (USENIX ATC 2014)
- Heidi Howard, Richard Mortier, "Paxos vs Raft: Have we reached consensus on distributed consensus?" (PaPoC 2020)
- Heidi Howard, Dahlia Malkhi, Alexander Spiegelman, "Flexible Paxos: Quorum intersection revisited" (2016)
- Leslie Lamport, Dahlia Malkhi, Lidong Zhou, "Vertical Paxos and Primary-Backup Replication" (PODC 2009)
- Next: Paxos Made Simple for the formal proof and the variants in depth, then Raft Full Walkthrough