On this page

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 withFLP Impossibility
The timing and failure assumptions spelled outSystem Models
How a consensus log becomes a replicated serviceReplicated State Machines
The algorithm most people actually deployRaft Full Walkthrough
A sibling protocol from the same eraViewstamped Replication
Leaders, leases and stale leadersLeader 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

AssumptionPaxos's position
FailuresCrash-recovery: nodes stop, and may later restart with their stable storage intact
Byzantine behaviourNot tolerated: nodes do not lie or corrupt messages (see Byzantine Fault Tolerance for that)
NetworkAsynchronous: messages can be lost, delayed, duplicated, reordered, but not forged
ClocksNot needed for safety at all. Only timeouts, for liveness
Fault toleranceWith acceptors, tolerates simultaneous failures
StorageEach 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 protocolWhat breaks
One fixed coordinator decidesCoordinator crashes, and nobody can decide. Not fault tolerant.
Acceptors accept the first value they see, majority winsThree acceptors, three proposers each reach one acceptor first: a three-way split and no majority, forever.
Acceptors accept every value, latest winsValue 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 proposalsClocks drift and skew; two proposers can produce the same or inverted timestamps. Safety now depends on clock accuracy.
Wait for every node to agreeOne 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.

RoleResponsibility
ProposerProposes a value; drives the protocol forward
AcceptorVotes on proposals; remembers what it has accepted
LearnerLearns 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 Accepted messages. 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:

  1. Totally ordered. Any two ballots can be compared.
  2. 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 sizeFailures tolerated
321
431 (the 4th node adds cost, not tolerance)
532
743

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)
  1. Proposer chooses a proposal number n (must be unique and higher than any it's used before)
  2. Sends Prepare(n) to a majority of acceptors
  3. 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
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)
  1. 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
  2. Proposer sends Accept(n, v) to a majority

  3. Each acceptor that receives Accept(n, v):

    • If it hasn't promised to ignore proposals < n: accepts and sends Accepted(n, v) to learner(s)
    • Otherwise: ignores
  4. When a learner hears Accepted(n, v) from a majority: value v is 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

FieldMeaningUpdated on
promised_nHighest ballot this acceptor has promisedPrepare with a higher ballot, or Accept with a higher ballot
accepted_nBallot of the last proposal acceptedAccept
accepted_vValue of the last proposal acceptedAccept

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:

StepA1A2A3A4A5Chosen?
P1 Prepare(11) to A1–A3p11p11p11––no
P1 Accept(11, X) reaches A1, A2p11 (11,X)p11 (11,X)p11––no, only 2 of 5
P2 Prepare(12) to A3–A5p11 (11,X)p11 (11,X)p12p12p12no
Late Accept(11, X) at A3unchangedunchangedrejected––no
P2 Accept(12, Y) to A3–A5p11 (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.

StepA1A2A3A4A5Chosen?
P1 Accept(11, X) reaches A1, A2p11 (11,X)p11 (11,X)p11––no
P2 Prepare(12) to A2, A4, A5p11 (11,X)p12 (11,X)p11p12p12no

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 v is chosen at ballot n, then every proposal with a ballot higher than n that any acceptor ever accepts also carries value v.

Proof sketch, by induction on ballots above n:

  1. Take the first ballot m > n whose Phase 2 runs. Its proposer collected promises from a quorum Q2 that overlaps Q1 (the quorum that accepted (n, v)).
  2. The overlapping acceptor accepted (n, v) before promising m (if it had promised m first, it would have refused ballot n < m). So its promise reports something with ballot at least n.
  3. Every accepted proposal with ballot between n and m carries v (induction hypothesis, and here there are none, since m is the first).
  4. So the highest-ballot proposal reported in Q2 has ballot at least n, and carries v. The proposer must pick it. Ballot m carries v.
  5. 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

RuleRemove it and...
Ballots are unique per proposerTwo 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 promiseAn 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 replyingAcceptor promises, crashes, restarts with no memory, and accepts an older ballot it had promised to refuse.
Proposer adopts the highest accepted valueNew proposer pushes its own value over a value that was already chosen. Two values chosen.
Quorums intersectTwo disjoint groups choose two different values during a partition.
A value is chosen only when a quorum accepts the same ballotCounting "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:

ApproachMessagesLatencyNotes
Every acceptor sends Accepted to every learnerLowestGood for small clusters
Acceptors tell the proposer, which tells learnersOne extra hopCommon: the leader is the natural place to count
Acceptors tell one distinguished learnerOne extra hopSingle 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:

TechniqueHow it helpsCost
Randomized backoff before retrying with a higher ballotDesynchronises the duellers, so one of them finishes both phases firstAdds 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 runsTwo leaders can briefly coexist, which is safe but slow
Leader leasesA proposer holds a time-bounded right to propose; others wait for it to expireDepends on bounded clock drift for liveness (and for lease-based reads, safety)
ForwardingNon-leaders forward client requests to the leader instead of proposingOne extra hop for clients connected to followers
Nack with the promised ballotLosers jump straight to a higher ballot instead of probingFewer 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:

  1. Sends Prepare(b, from_slot=k) where k is the first slot it does not know to be chosen.
  2. Each acceptor promises b for every slot ≥ k and replies with every proposal it has accepted at slots ≥ k.
  3. 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).
  4. For each slot below the highest reported slot where nobody reported anything, the leader proposes a no-op to fill the gap.
  5. 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.

SituationWhat happens
Slot chosen, earlier slot not yet chosenReplica buffers it; does not execute yet
Old leader died with slot 40 half-proposedNew 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 behindFetches 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 strategyGuaranteeCost
Put the read through the log as a commandLinearizableA full consensus round per read
Leader confirms it is still leader with a round of heartbeats to a majority, then readsLinearizableOne round trip, no disk write
Leader lease: acceptors promise not to support another leader for T secondsLinearizable if clock drift is boundedNo round trip; safety now depends on clocks
Read from any replicaPossibly staleFree

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

OptimisationEffect
Batching: many client commands in one slotAmortises the round trip and the fsync across many commands
Pipelining: send Accept for slot 43 before 42 is chosenKeeps the network busy, so throughput is no longer bounded by one RTT per command
Group commit at acceptorsOne fsync for many accepted slots
Thrifty: send Accept to exactly a quorum, not to everyoneLess 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

ApproachIdeaUsed / described by
Config in the log, with an α windowThe 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 PaxosConfiguration 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 consensusDuring the change, decisions need a majority of the old config and a majority of the new one.Raft paper
One server at a timeAdding 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

PaxosRaft
Log replicationMulti-Paxos (add-on)Built-in
Leader electionExternal mechanismBuilt-in, well-specified
Log matchingPossible gaps, complex reconciliationStrict ordering, no gaps
UnderstandabilityNotoriously difficultDesigned for understandability
ImplementationHard to get rightHard but much better-specified
PerformanceComparableComparable

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:

PaxosRaftRole in the protocol
Ballot / proposal numberTermOrders leadership attempts. Higher wins
Prepare(b)RequestVote(term)Ask a majority to back a new leader
PromiseVote grantedCommit not to support older leaders
Accept(b, slot, v)AppendEntries(term, index, entry)Leader replicates a log entry
AcceptedAppendEntries successFollower stored the entry
ChosenCommittedA majority stored it under the current leader
Distinguished proposerLeaderThe node that drives progress
No-op to fill a gapNo-op entry at the start of a termLets a new leader commit earlier entries

The real difference: who can become leader

Multi-PaxosRaft
Who can winAny node with a high enough ballotOnly a candidate whose log is at least as up-to-date as a majority's
After winningLeader learns missing values from Phase 1 replies and re-proposes themLeader already has every committed entry. It just overwrites conflicting follower entries
Data flowValues can flow to the new leaderEntries only ever flow from leader to followers
Log shapeHoles allowedContiguous 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.

VariantProblem it targetsKey changeCost
Multi-PaxosOne value is not a logStable leader, Phase 1 once for all slotsLeader is a bottleneck and a single point of slowness
Fast PaxosClient to leader to acceptors is an extra hopClients write directly to acceptorsLarger quorums (about 3/4 of acceptors), slower recovery on collision
Cheap PaxosFull replicas are expensiveAuxiliary acceptors used only during failuresSlower failover
Flexible PaxosMajorities in both phases are more than neededOnly Phase 1 and Phase 2 quorums must intersectSmaller Phase 2 quorum means larger Phase 1 quorum
EPaxosSingle leader adds WAN latencyLeaderless, dependency trackingMuch harder to implement correctly; conflicts cost extra
MenciusLeader loadRound-robin slot ownershipSlowest replica affects everyone
Byzantine PaxosNodes may lieLarger 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.

SystemWhat Paxos decidesScope
ChubbyEvery write to the lock service's databaseOne cell (typically 5 replicas)
SpannerEvery write to a shard; a Paxos leader also manages locks for transactionsOne Paxos group per split, many groups per database
MegastoreEvery write to an entity groupOne group per entity group, across data centres
Cassandra LWTOne conditional updateOne 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:

ConcernWhy the paper doesn't cover it
Disk corruptionThe model assumes stable storage is reliable. Real disks lose and corrupt data, so a replica must detect it and rejoin carefully
Master leasesNeeded for fast local reads, and they bring clocks back into the picture
Snapshots and log truncationThe log grows forever otherwise; the snapshot must be consistent with the log position
Group membershipSee the reconfiguration section above
TestingThey 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

FailureWhat happensMitigation
Acceptor crash, disk intactStops voting. Group continues while a majority is upRestart; 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 chosenfsync before replying, detect lost state (e.g. a marker file or epoch), rejoin as a non-voter until caught up
Leader crash mid-roundSlots in flight may be partly acceptedNew leader's Phase 1 finds them and re-proposes, or fills gaps with no-ops
Network partitionMinority side cannot complete either phase. Majority side elects a leader and continuesNothing to do for safety. Clients on the minority side see timeouts
Two leadersBoth run rounds. The higher ballot wins at the acceptors; the other gets NacksSafe. Fix with leases or better failure detection for performance
Duplicate client command after leader changeSame command chosen in two slotsClient id plus sequence number, deduplicated by the state machine
Ballot reuse after proposer restartSame ballot, different value, can break safetyPersist the highest ballot used, or derive ballots from a durable counter
Slow acceptorIf it's in every quorum the leader uses, everything slowsSend to all acceptors and use the first majority that answers
Clock jump with lease-based readsOld leader thinks its lease is still valid and serves stale readsConservative lease durations, monotonic clocks, bounded drift assumptions

Real numbers

QuantityTypical magnitude
Commit latency, single data centre, Multi-Paxos steady stateOne 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 regionsOne RTT to the second-nearest region for a 3-region group, i.e. tens of milliseconds, often more
Messages per command, steady stateAbout (Accept to each acceptor, Accepted back)
Messages per command, full two-phase roundAbout
Durable writes per commandOne per acceptor in the quorum, amortised by batching and group commit
Failover timeDominated 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.

PropertyGuarantee
SafetyOnly one value ever chosen
LivenessProgress if a majority of acceptors are reachable (no dueling proposers)
Fault toleranceTolerates f failures with 2f+1 acceptors
Message complexityO(n) per round (n = number of acceptors)

The ideas to carry away:

  1. Numbered proposals let newer attempts override abandoned ones without coordination.
  2. Promises stop old proposals from landing after a new proposer has read the state.
  3. Adopting the highest accepted value is what carries a possibly-chosen value forward.
  4. Quorum intersection guarantees the new proposer will see it.
  5. Durable acceptor state is a correctness requirement, not a performance knob.
  6. 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