Catalog My learning Blog
Raft and Paxos Explained: Consensus, ZooKeeper and etcd · Phase 2 · Lesson 6 · 10 min read

Paxos Explained: Proposers, Acceptors, Learners

On this page
  1. Learning Objective
  2. Concept Explanation
  3. Worked Example: A Competing Proposer Forced to Adopt an Existing Value
  4. Real-World Examples
  5. Review Questions & Answers

Learning Objective

Walk through both phases of single-decree Paxos, explain precisely which rule preserves safety when proposals compete, describe how Multi-Paxos amortises the protocol across a stream of commands, and account for why Paxos earned its reputation as difficult to implement correctly.

Concept Explanation

Paxos is the foundational consensus algorithm, published by Leslie Lamport as "The Part-Time Parliament" in 1998 after a famously difficult submission history, and later restated in the much shorter "Paxos Made Simple" in 2001. It defines three roles: proposers, which suggest values; acceptors, which vote and constitute the fault-tolerant memory of the system; and learners, which find out what was chosen. In a real deployment a single process plays all three roles at once, so the roles are best understood as three separate jobs rather than three separate machines.

The protocol runs in two phases, each a round trip to a majority of acceptors. In phase one, a proposer picks a proposal number n that is globally unique and higher than any it has used before, and sends Prepare(n) to a majority. An acceptor receiving Prepare(n) checks whether n exceeds every proposal number it has already promised to. If so, it replies with a Promise never to accept any proposal numbered lower than n, and critically, it includes the highest-numbered proposal it has already accepted, if any. If n is not higher, it simply ignores or rejects the message. In phase two, the proposer that collected promises from a majority sends Accept(n, v) to those acceptors, and an acceptor accepts unless it has since promised to a higher number. Once a majority has accepted (n, v), the value v is chosen, permanently, and learners can be told.

The entire safety of Paxos rests on one rule inside phase two that is easy to read past. The proposer does not get to send its own value freely. If any promise it received reported a previously accepted proposal, the proposer must propose the value from the highest-numbered such proposal, discarding its own. Only if every promise reported nothing accepted may it propose the value it actually wanted. This rule is what makes it impossible to choose two different values. Suppose some value was already chosen, meaning a majority accepted it. Any later proposer must gather promises from a majority, and any two majorities intersect, so at least one promise will report that accepted value, forcing the new proposer to re-propose the same thing. A chosen value therefore propagates forward through every subsequent round rather than being overwritten, and this is the exact point where the quorum intersection property from earlier in this course does its real work.

Paxos is always safe and is not always live, which is FLP appearing on schedule. Two proposers can duel indefinitely: proposer X completes phase one with number 5, proposer Y completes phase one with number 6 before X reaches phase two, X's Accept(5) is now rejected so X retries with number 7, which invalidates Y's pending Accept(6), and the cycle repeats. Nothing unsafe ever happens and nothing is ever decided. The standard remedy is to elect a distinguished proposer, a leader, so that in the common case only one proposer is active. Notice what this means structurally: to make Paxos live you need leader election, and leader election is itself a consensus problem, so the leader is treated as a performance optimisation that may be wrong without endangering safety rather than as something that must be correct.

Single-decree Paxos decides one value, which is not a system. Multi-Paxos is the standard extension: run a separate logical Paxos instance for each position in a replicated log, and exploit the fact that a stable leader can run phase one once for an entire range of future log positions rather than once per position. After that single setup round, committing each new command costs only phase two, which is one round trip from the leader to a majority. Steady-state Multi-Paxos is therefore about as cheap as Raft, and the resemblance is not coincidental: a Multi-Paxos deployment with a stable distinguished proposer and a log is structurally the same design Raft later specified explicitly. The difficulty is that Lamport described the single-decree core precisely and left the log, the leader, the membership changes, and the snapshotting as exercises, so every implementer made their own choices and no two Multi-Paxos implementations agree in detail.

StepMessageSender LogicReceiver Logic
1a PreparePrepare(n)Pick n unique and higher than any n used before; send to a majorityPromise only if n exceeds every number promised so far
1b PromisePromise(n, highestAccepted)Collect promises from a majority before continuingReport the highest-numbered proposal already accepted, if any
2a AcceptAccept(n, v)v MUST be the value from the highest-numbered reported acceptance; only if none, use your ownAccept unless a higher number has since been promised
2b AcceptedAccepted(n, v)A majority of these means v is chosen, permanentlyNotify learners that v is chosen

Worked Example: A Competing Proposer Forced to Adopt an Existing Value

The phase-two value rule is the whole safety argument, so it is worth tracing a round where a proposer arrives with its own preferred value and is compelled by the protocol to abandon it.

Code
# 5 acceptors: A1..A5. Majority = 3.
# Proposer P wants to choose "blue". Proposer Q wants to choose "green".

# --- P runs a round and gets partway ---
P -> A1,A2,A3 : Prepare(n=10)
A1,A2,A3      : promise(10, accepted=none)      # nothing accepted yet
P -> A1,A2,A3 : Accept(n=10, v="blue")
A1,A2         : accepted(10,"blue")
A3            : (message lost in the network)

# Only 2 of 5 have accepted. "blue" is NOT chosen - no majority yet.
# P crashes here and never returns. Nobody knows whether blue was chosen.

# --- Q starts a round with its own preferred value ---
Q -> A3,A4,A5 : Prepare(n=11)
A3            : promise(11, accepted=none)
A4            : promise(11, accepted=none)
A5            : promise(11, accepted=none)
# Q's majority happened to MISS A1 and A2. Q may safely propose "green":
# no promise reported any acceptance, which means no value could have
# reached a majority - because a majority would have had to include at
# least one of A3,A4,A5.
Q -> A3,A4,A5 : Accept(n=11, v="green")   -> "green" is chosen.

# --- Now replay with P having reached a MAJORITY first ---
P -> A1,A2,A3 : Accept(n=10, v="blue")
A1,A2,A3      : accepted(10,"blue")       -> "blue" IS chosen (3 of 5)

Q -> A3,A4,A5 : Prepare(n=11)
A3            : promise(11, accepted=(10,"blue"))   # the intersection!
A4,A5         : promise(11, accepted=none)

# Q wanted "green". The rule forbids it. Q must propose the value from
# the highest-numbered reported acceptance, which is (10,"blue").
Q -> A3,A4,A5 : Accept(n=11, v="blue")    # NOT "green"

# Safety by construction: Q's majority {A3,A4,A5} and P's majority
# {A1,A2,A3} must share a node (A3), and that node carries the memory of
# what was chosen. There is no schedule in which Q can miss it.
A single-decree Paxos round drawn as two phases across five acceptors: prepare and promise establishing a proposal number and surfacing any prior acceptance, then accept and accepted choosing the value, with the quorum intersection shown as the node that forces a later proposer to adopt an already-chosen value.
A single-decree Paxos round drawn as two phases across five acceptors: prepare and promise establishing a proposal number and surfacing any prior acceptance, then accept and accepted choosing the value, with the quorum intersection shown as the node that forces a later proposer to adopt an already-chosen value.

Real-World Examples

  • Google built Chubby, the lock and small-file service underpinning GFS, Bigtable, and much of Google's internal infrastructure, on Multi-Paxos, and the resulting 2007 paper "Paxos Made Live" by Chandra, Griesemer, and Redstone is the canonical account of the gap between the published algorithm and a working system. The authors report that the algorithm as described covered only a fraction of what a production implementation needed, and that they had to design their own solutions for disk corruption, group membership changes, snapshotting, and master leases, none of which the papers specified.
  • Google Spanner runs a Paxos group per data split, with a long-lived leader holding a time-based lease so that in the steady state a write costs a single phase-two round trip to a majority of replicas rather than the full two-phase protocol. This is Multi-Paxos in its intended form, and the design shows why the distinction between single-decree Paxos and a leader-driven log-based deployment matters so much in practice: the expensive phase-one round is amortised across every command the leader commits during its term.
Key TakeawaysThe safety of Paxos is not spread evenly across the protocol - it is concentrated in one rule: a proposer in phase two must adopt the value from the highest-numbered acceptance reported in its promises, and may use its own value only when no promise reports any acceptance. Combined with quorum intersection, that single rule makes it impossible for two different values to be chosen, regardless of message loss, reordering, or how many proposers compete.

Review Questions & Answers

If any promise reports a previously accepted proposal, that value might already have been chosen by a majority, and a chosen value must never be superseded. The proposer therefore adopts the value from the highest-numbered reported acceptance. If proposers could always propose their own value, two proposers could each reach a majority with different values at different times and both would be chosen, directly violating agreement. The rule turns a later round into a mechanism that propagates an earlier decision forward rather than one that can overwrite it.

A value is chosen only when a majority of acceptors have accepted it. A later proposer must collect promises from a majority before it may send any Accept message. Two majorities of the same acceptor set always share at least one member, so at least one acceptor in the new proposer's promise quorum accepted the chosen value and will report it in its promise. There is no possible message schedule in which the new proposer collects a valid majority of promises while missing every acceptor that holds the chosen value, which is why the guarantee is structural rather than probabilistic.

It is not a bug but the expected consequence of FLP: Paxos guarantees safety unconditionally and cannot guarantee termination in an asynchronous system. Each proposer's new, higher prepare invalidates the other's pending accept, so the two can alternate indefinitely without anything unsafe occurring and without anything being decided. The standard mitigation is to elect a distinguished proposer so that only one proposer is normally active, often with randomised backoff before retrying. Because a wrong leader costs only liveness, the leader election itself is permitted to be imperfect, which is what keeps the design from being circular.

Multi-Paxos lets a stable leader run phase one once for an entire range of future log positions rather than once per position, so each subsequent command costs only the phase-two round trip to a majority. It is safe because phase one exists to establish that the proposer holds the highest proposal number and to surface any prior acceptances; a leader that has done this for a range of positions retains that standing until some other proposer prepares with a higher number, at which point the leader's accepts start being rejected and it learns it has been displaced. Safety never depended on running phase one per position, only on the ordering guarantees the proposal number provides.

Lamport specified the single-decree core precisely but left everything a real system needs - the log structure, leader election, cluster membership changes, snapshotting, client interaction, and failure handling - unspecified, so each implementer invented their own approach and the resulting systems shared only the core. "Paxos Made Live" documents exactly this, reporting that the published algorithm covered a fraction of what Chubby required. Raft was designed as a direct response: it specifies the leader, the log, the election rules, membership changes, and snapshotting as a single prescriptive protocol, so two independent implementations are far more likely to agree and to be verifiable against the same specification.