This is the article the entire series has been building toward — the actual mechanics of Paxos, walked through carefully enough that the "Paxos is hard" reputation (article 5.1) shouldn't survive contact with it. Two phases — Prepare/Promise and Accept/Accepted — built entirely from tools this series has already handed you: proposal numbers that behave like a cross between article 3.2's log terms and article 2.2's Lamport clocks, and a safety argument that's just article 3.3's majority-overlap proof applied with one extra twist. By the end, you'll be able to trace, step by step, exactly why Paxos can never choose two different values, even when multiple proposers compete simultaneously and messages arrive in the worst possible order.
Proposal numbers: the ordering mechanism
Every proposal a proposer sends carries a proposal number — a value that must be (a) unique to that proposer (commonly built as (counter, proposer_id), exactly the tie-breaking trick from article 2.2's Lamport clocks) and (b) higher than any number that proposer has used before. Proposal numbers are compared purely by counter first, proposer ID as tiebreaker — they carry no relationship to real time (echoing article 2.1's entire argument against trusting physical clocks) and no relationship to the actual value being proposed. Their only job is to create a strict, unambiguous ordering that acceptors can use to reject stale proposals — which is precisely what the two phases below do with them.
Phase 1: Prepare / Promise
A proposer that wants to get a value chosen doesn't jump straight to proposing it — first, it sends a Prepare(n) message (just the proposal number, no value yet) to a majority of acceptors, asking, in effect, "will you promise to ignore any future proposal numbered lower than n?"
Each acceptor, on receiving Prepare(n), checks: is n higher than any proposal number it has already promised to honor? If yes, it replies Promise(n, accepted_proposal) — a promise to never again accept any proposal numbered lower than n, plus — this is the single most important detail in the entire protocol — the highest-numbered proposal it has already accepted, if any, including that proposal's actual value. If n is not higher than something already promised, the acceptor simply ignores or rejects the request (safety is preserved either way; the proposer just doesn't get a promise it can use).
Phase 2: Accept / Accepted
If the proposer receives Promise responses from a majority of acceptors (article 3.3's mechanism, doing its work again here), it moves to Phase 2. Here's the critical rule that makes the whole algorithm safe, worth reading twice: the proposer must propose the value from the highest-numbered already-accepted proposal it saw in any of the promises it received — not its own preferred value — if any promise reported an already-accepted value at all. Only if every promise reported no previously-accepted value is the proposer free to propose its own original value.
The proposer then sends Accept(n, v) (the proposal number and the value determined by the rule above) to the same majority. Each acceptor accepts it — replying Accepted(n, v) — unless it has, in the meantime, promised a higher-numbered proposal to some other proposer (which can happen if a competing proposer's Prepare arrived in between). If a value is accepted by a majority of acceptors, that value is chosen — the algorithm's terminal, safety-critical event.
PHASE 1 (Prepare/Promise)
Proposer -> majority of Acceptors: PREPARE(n)
Acceptor -> Proposer: PROMISE(n, <highest accepted proposal, if any>)
(or ignore, if n is not high enough)
PHASE 2 (Accept/Accepted)
Proposer picks value v:
- the value from the highest-numbered accepted proposal seen in any promise, if any
- otherwise, its own original value
Proposer -> majority of Acceptors: ACCEPT(n, v)
Acceptor -> Proposer: ACCEPTED(n, v)
(unless it has since promised a higher n)
If a majority ACCEPTED(n, v) -> v is CHOSEN.
A worked example: two competing proposers
Five acceptors (A1-A5). Proposer P1 sends Prepare(1), wants to propose "X". Before P1 finishes Phase 2, Proposer P2 sends Prepare(2) (a higher number), wanting to propose "Y". Walk through exactly what happens and why the result is always safe:
| Step | Event | Result |
|---|---|---|
| 1 | P1 sends Prepare(1) to A1-A3 (a majority of 5) | A1, A2, A3 promise(1, none) — no prior accepted value |
| 2 | P1 sends Accept(1, "X") to A1-A3 | A1 accepts (1,"X") before P2's prepare arrives; A2, A3 haven't processed yet |
| 3 | P2 sends Prepare(2) to A2-A4 (a different majority) | A2 promises(2, none) — hasn't seen P1's accept yet; A3 promises(2, (1,"X")) — HAS seen P1's accept; A4 promises(2, none) |
| 4 | P2 collects promises from A2, A3, A4 — a majority | Per the Phase 2 rule: A3's promise reported an already-accepted value ("X" at proposal 1) — P2 MUST now propose "X", not its own "Y" |
| 5 | P2 sends Accept(2, "X") — not "Y" — to A2-A4 | All accept. "X" is chosen by a second, independent majority. |
Fig 1 — The overlap node (A3) is the physical mechanism that transmits "a value was already accepted" from one majority to the next, guaranteeing safety.
The safety argument, generalized
The worked example shows one trace; the general argument (this is the essence of the formal proof in Lamport's papers) generalizes it: suppose value v is chosen via some majority M1 at proposal number n. Any later proposer using a higher number n' must, to complete its own Phase 1, get promises from some majority M2. By article 3.3's overlap proof, M1 and M2 share at least one acceptor — call it a. Because a was part of M1, it accepted (n, v). When a responds to the later Phase 1 Prepare(n'), it must report the highest proposal it has accepted — which is (n, v) or something even later that itself must (by induction, tracing the same argument backward) also carry value v. Either way, the new proposer is forced, by the Phase 2 rule, to propose v again — the chosen value can never change, no matter how many further proposal rounds happen. This is a proof by induction over proposal numbers, and it's the rigorous version of exactly what the worked example demonstrated concretely.
Where liveness can still stall (and why that's OK)
Notice what the safety argument above never required: that any particular proposer's Phase 2 actually succeeds. Two competing proposers can, in principle, keep leapfrogging each other with ever-higher Prepare messages, each invalidating the other's in-progress Accept phase before it completes — a real liveness risk (this is, not coincidentally, essentially the same "dueling proposers" shape as FLP's bivalence-preservation adversary from article 2.5, and it's exactly why plain single-decree Paxos, run repeatedly by multiple competing proposers with no coordination, can theoretically stall forever). Per article 4.1's safety/liveness framework, this is acceptable — safety is never at risk in this scenario, only liveness, and liveness is already understood to be conditional (article 2.5's escape hatches). The practical fix, used by essentially every real deployment: have only one proposer active at a time via leader election (article 4.2) — which is exactly what Multi-Paxos (article 5.3, next) formalizes as a first-class part of the protocol rather than an afterthought.
FAQ
What happens if a proposer's Prepare only reaches a minority of acceptors?
It simply fails to gather a majority promise and cannot proceed to Phase 2 with any guarantee — this is a normal, expected outcome under network trouble (article 1.1), not a special error case. The proposer retries, typically with a higher proposal number, once conditions improve.
Can an acceptor ever change its mind about an already-accepted value?
Not for a given proposal number, but it can accept a different value at a higher proposal number if it hasn't yet promised not to (i.e., no competing Prepare with an even higher number reached it first) — this flexibility is exactly what the worked example's step 3 (A3 already having accepted "X" but still able to promise for P2's higher number 2) relies on, and it's precisely bounded by the safety argument above so it can never cause two different values to be chosen.
Do acceptors need to persist their promises and accepted values durably?
Yes — this is a critical, easy-to-overlook implementation detail. If an acceptor crashes and restarts having forgotten what it previously promised or accepted, it could violate safety by promising something it already broke a promise on. Real implementations durably write promises and accepted values to disk before responding, directly analogous to article 3.2's log-durability requirements.
Is the "propose the highest-numbered already-accepted value" rule the single most important line in the whole algorithm?
Essentially yes — it's fair to say this one rule is where Paxos's entire safety guarantee lives. Every other mechanism (proposal numbers, majority quorums, the promise/accept message flow) exists to set up the conditions under which this one rule can be correctly applied. Understanding why this specific rule is necessary (the worked example above) is the single highest-leverage thing to internalize about Paxos.
Takeaways
- Proposal numbers provide a strict, real-time-independent ordering (built like article 2.2's Lamport-clock tie-breaking) that acceptors use to reject stale proposals.
- Phase 1 (Prepare/Promise): a proposer asks a majority to promise ignoring lower-numbered proposals, and collects any already-accepted value those acceptors know about.
- Phase 2 (Accept/Accepted): the proposer must propose the highest-numbered already-accepted value it learned about in Phase 1, if any exists — only proposing its own original value if no acceptor reported one.
- The safety proof is article 3.3's majority-overlap guarantee doing real work: any two majorities share an acceptor, and that shared acceptor is the physical mechanism that forces every later proposal onto the same, already-chosen value.
- Liveness can stall under dueling proposers (a real, acceptable-per-article-4.1 risk) — the practical fix is restricting to one active proposer via leader election, formalized next in Multi-Paxos.
References & further reading
- Lamport — Paxos Made Simple (2001) — the primary source for this article's protocol description.
- De Prisco, Lampson & Lynch — Revisiting the Paxos Algorithm (1997) — an early, rigorous formal treatment of Paxos's safety and liveness properties.
- cvam.sight — Consensus 3.3: Quorums and Majority Voting — the overlap proof this article's safety argument directly applies.
- cvam.sight — Consensus 5.1: Paxos, History and the Problem — the problem statement this article's protocol satisfies.