The idea: many machines, one value, no leader needed
Several servers must agree on one value: who holds a lock, which command goes into slot 7 of a log, which node is the primary. Servers crash and messages get lost, but once a value is chosen it must never change. Paxos (Leslie Lamport) does this with three roles. Proposers suggest values, acceptors vote on them, and learners find out what was chosen. A value is chosen when a majority of acceptors accepted it in the same proposal. With 3 acceptors a majority is 2, so one may fail.
| On the page | Meaning |
|---|---|
| P1, P2 | proposers; P1 wants X, P2 wants Y; blue is everything of P1, orange everything of P2 |
| A1, A2, A3 | acceptors; each shows the highest n it promised and the proposal n:v it accepted last (both kept on disk) |
| L | the learner; it counts Accepted messages per n and shows the chosen value |
| boxes in flight | messages; each one appears at its sender in one step and reaches its receiver in the next; red = Nack, grey with ✗ = lost (sent to a node that is down) |
| t | the clock: one tick per wave of messages |
Proposal numbers
Every proposal has a number n, and no two proposers may use the same one. The page uses
n = round·10 + id: P1 uses 11, 21, 31, and P2 uses 12, 22, 32. A higher n always wins over a lower one.
When a proposer finds out about a higher number, its next round is higher still.
The two phases
Phase 1, Prepare / Promise. The proposer sends Prepare(n) to the acceptors. An acceptor
that has not promised anything higher promises n: from now on it ignores proposals numbered below n. Its
Promise(n, n_a:v_a) also reports the last proposal it accepted (or –).
Phase 2, Accept / Accepted. With Promises from a majority, the proposer picks a value. If any Promise
reported an accepted proposal, it must take the value with the highest n_a. Only if none did may
it use its own value. It sends Accept(n, v). An acceptor accepts unless it has promised a higher n, and tells the
learner Accepted(n, v). A majority of Accepted for the same n means v is chosen (Demo 1).
| An acceptor gets | If | It does |
|---|---|---|
Prepare(n) | n > promised | promised = n; answers Promise(n, n_a:v_a) |
Prepare(n) | n ≤ promised | answers Nack(promised) (or stays silent) |
Accept(n, v) | n ≥ promised | promised = n, accepted = (n, v); sends Accepted(n, v) |
Accept(n, v) | n < promised | answers Nack(promised) (Demo 6) |
Why only one value can be chosen
Any two majorities of the same acceptors share at least one acceptor. Suppose X was chosen with n = 11: a majority accepted 11:X. A later proposer with n = 12 needs Promises from a majority too, and that majority contains at least one acceptor that accepted 11:X. Its Promise reports 11:X, so the new proposer has to propose X again (Demo 2). The same holds for every later n, so the chosen value never changes.
Accepted is not chosen
If a proposer crashes in the middle of phase 2, a value may be accepted by only some acceptors. In Demo 3 only A1 accepted X before P1 crashed. P2's majority included A1, A1 reported 11:X, and P2 finished the job for X. In Demo 4 P2's majority was A2 and A3, which knew nothing about X, so Y was chosen. That is still safe: X was accepted by one acceptor, never by a majority, so it was never chosen. A1 keeps 11:X, but any later proposer will hear of 12:Y with a higher number and pick Y.
Crashes and lost messages
An acceptor writes its promise and its accepted proposal to disk before it answers. After a restart it must still keep its promises, or two values could be chosen. With 3 acceptors, Paxos keeps working while any 2 are up. With only 1 up it stops: no majority, so no decision at all (Demo 5). It never decides with a minority. A crashed proposer simply stops, and any other proposer can take over by running phase 1 with a higher n.
Dueling proposers
Paxos is always safe, but it is not guaranteed to finish. In Demo 7 P1's Prepare(21) arrives just before P2's Accept(12), so the acceptors reject it. Then P2's Prepare(32) arrives before P1's Accept(21), and so on. Each proposer keeps pre-empting the other and nothing is ever chosen. This is a livelock. The fix is to let only one distinguished proposer (a leader) propose, or to wait a random time before retrying.
Multi-Paxos and Raft
A replicated log needs one decision per slot. Multi-Paxos runs one Paxos instance per slot with a stable leader. The leader runs phase 1 once, for all future slots, and then needs only phase 2 per command: one round trip. A new leader runs phase 1 again and adopts any values it hears of. Raft is built the same way, but spells out leader election and log repair, which papers on Paxos leave open.
| Single-decree Paxos | Multi-Paxos | Raft | |
|---|---|---|---|
| decides | one value | one value per log slot | a log of entries |
| who proposes | anyone | usually a stable leader | only the leader of the term |
| round trips per value | 2 (Prepare, Accept) | 1 while the leader is stable | 1 (AppendEntries) |
| numbers | proposal number n | ballot number | term |
| a new leader | (no leader) | adopts the highest accepted value per slot | must already have every committed entry (election rule) |
| livelock | possible | avoided by the leader | avoided by random election timeouts |
For what a majority store does when the network splits, see The CAP Theorem: CP vs AP. Chubby (Google's lock service), Spanner and Megastore use Paxos; etcd, Consul and CockroachDB use Raft.
MySQL Group Replication orders every commit through XCom, a Paxos variant: see MySQL Group Replication.
See also Raft vs Multi-Paxos: Multi-Paxos with a leader next to Raft, including a leader crash and duelling proposers.
FLP says no deterministic algorithm can always finish over an asynchronous network, which is why Paxos keeps safety always and uses timeouts only to retry; see Two Generals and FLP.
What the page leaves out
Several learners and how they hear of the result (directly from the acceptors or through a leader), leader election for Multi-Paxos, log slots, changing the set of acceptors, Fast Paxos and Flexible Paxos (phase 1 and phase 2 quorums of different sizes), and disk writes. Simplifications: one action is a whole round trip, so messages are never delayed past the next action; acceptors answer a refused message with a Nack (real Paxos may stay silent); a down node drops messages instead of receiving them late; the proposer sends Accept to every acceptor, not only the ones that promised.