Lesson 27 · Consensus · Module 3
Paxos, One Value at a Time
Lesson 26 left you with a machine that cannot be trusted to decide anything: no clock, no reliable delivery, no way to tell a slow node from a dead one. Paxos does not repeal any of that. It writes down a small set of refusals — things an acceptor will not do, things a proposer may not propose — and the refusals turn out to be enough to make two different values impossible.
The win in this lesson: you will be able to explain why Paxos stays safe even while two proposers fight each other to a standstill, and why that same fight can stop the algorithm making progress without ever making it wrong.
1. The problem: one value, agreed, despite everything
Lamport states the job in two sentences and then spends the rest of the paper refusing to let anything violate them:
"Assume a collection of processes that can propose values. A consensus algorithm ensures that a single one among the proposed values is chosen. If no value is proposed, then no value should be chosen. […] The safety requirements for consensus are: Only a value that has been proposed may be chosen, Only a single value is chosen, and A process never learns that a value has been chosen unless it actually has been."
Leslie Lamport, Paxos Made Simple (2001), §2.1 The Problem
Notice what is not on that list. Nothing promises a decision arrives. Nothing promises it arrives quickly. Every requirement is of the form this must never happen. That split — safety as an absolute, liveness as a hope — is the whole shape of the algorithm, and it is the direct answer to Lesson 26's impossibility result: you cannot have both guaranteed, so Paxos gives up the one you can survive losing.
Paxos is always safe and eventually live. A round that stalls costs you a decision you have to wait for. A round that decided twice would cost you the system. Every rule below exists to buy the first risk with the second.
2. Three roles, and why there are three
Lamport separates proposers (who suggest values), acceptors (who vote and remember), and learners (who find out what was decided). One process usually plays all three; the separation is for reasoning, not deployment.
| Role | Does | Must remember, durably | Refuses to |
|---|---|---|---|
| Proposer | Picks a proposal number, runs both phases, may propose a value | The highest number it has ever used | Propose its own value once an acceptor has reported a different accepted one |
| Acceptor | Answers prepare requests, accepts or ignores accept requests | Highest prepare answered; highest proposal accepted, with its value | Accept anything numbered below a promise it has already given |
| Learner | Discovers that a majority accepted the same proposal | Nothing required for safety | Report a value as chosen on fewer than a majority of acceptances |
The acceptors are the only durable state in the protocol. "Stable storage, preserved during failures, is used to maintain the information that the acceptor must remember" (Lamport, §2.5 The Implementation). An acceptor that forgets its promises after a restart is not a slow acceptor; it is a lying one, and the safety argument collapses.
3. Why a majority, and nothing smaller
One acceptor would be a consensus algorithm — until it died. Many acceptors need a rule for what counts as enough, and Lamport picks it for exactly one reason:
"How large is large enough? To ensure that only a single value is chosen, we can let a large enough set consist of any majority of the agents. Because any two majorities have at least one acceptor in common, this works if an acceptor can accept at most one value."
Lamport, Paxos Made Simple, §2.2 Choosing a Value
You have already bought this argument once. Lesson 05's dial set R + W greater than N so that a read set and a write set could not miss each other. Kleppmann states the general form, and the majority case:
"In general, a quorum is a minimum set of nodes that must respond to some request for it to be successful. […] A common choice of quorum in distributed systems is a majority quorum, which is any subset of nodes that comprises strictly more than half of the nodes. […] Majority quorums have the property that any two quorums always have at least one element in common."
Martin Kleppmann, Distributed Systems lecture notes, §5.2 Quorums
4. Phase 1 — prepare and promise
A proposer that simply broadcast its value would have no way of knowing whether an earlier value had already been chosen somewhere behind its back. Asking is not enough: an acceptor could accept something a millisecond after answering. So the proposer does not ask about the past alone — it also forecloses the future.
"Learning about proposals already accepted is easy enough; predicting future acceptances is hard. Instead of trying to predict the future, the proposer controls it by extracting a promise that there won't be any such acceptances."
Lamport, Paxos Made Simple, §2.2 Choosing a Value
Phase 1, in Lamport's words, with the elisions marked:
"Phase 1. (a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors. (b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted."
Lamport, Paxos Made Simple, §2.2 Choosing a Value (words broken across the PDF's line breaks are rejoined)
A promise is a refusal about the future, and the report of an accepted proposal is a confession about the past. The proposer needs both from a majority before it is allowed to say anything at all.
5. Phase 2 — accept and accepted
Now the proposer may propose — but often not what it wanted to propose:
"Phase 2. (a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals. (b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n."
Lamport, Paxos Made Simple, §2.2 Choosing a Value
| Phase | Proposer sends | Acceptor answers | What the phase guarantees |
|---|---|---|---|
| 1 · prepare / promise | prepare(n) to a majority |
Promise to refuse everything below n, plus its highest accepted proposal |
Nothing older can still be chosen behind the proposer's back, and anything already chosen is now visible to it |
| 2 · accept / accepted | accept(n, v) where v is forced by phase 1 if anything was reported |
Accepts, unless it has since promised a higher number | If a majority accepts, the value is chosen — and by construction it is the same value as any earlier choice |
6. The one rule: adopt the highest, or propose nothing of your own
Everything above is plumbing. This is the lesson. A proposer whose quorum reported an accepted proposal must propose that value — the one attached to the highest proposal number it heard — and is forbidden from proposing its own. A proposer told nothing may pick freely.
Run the induction once and you have the safety proof. Suppose proposal number m with value v was chosen: a majority accepted it. Any later proposal, numbered n greater than m, must first hear from a majority — and two majorities share an acceptor. That acceptor accepted (m, v), so it reports it, so the later proposer proposes v too. Every proposal above m therefore carries v, so every proposal that can be chosen after m is v again. One value, forever, no matter how many proposers there are.
Paxos never rolls back a decision, because it never lets a second decision be proposed. Safety lives entirely in phase 1: by the time a proposer is permitted to speak in phase 2, the value it is allowed to say has already been determined by what it heard.
7. Duelling proposers: how it stalls without breaking
The same rule that makes Paxos safe is what makes it possible to livelock. A prepare request with a higher number invalidates a pending round — and there is nothing stopping two proposers from doing that to each other forever.
"It's easy to construct a scenario in which two proposers each keep issuing a sequence of proposals with increasing numbers, none of which are ever chosen."
Lamport, Paxos Made Simple, §2.4 Progress
Lamport's fix is not a cleverer protocol. It is to stop the duel by convention:
"To guarantee progress, a distinguished proposer must be selected as the only one to try issuing proposals. […] The famous result of Fischer, Lynch, and Patterson [1] implies that a reliable algorithm for electing a proposer must use either randomness or real time—for example, by using timeouts. However, safety is ensured regardless of the success or failure of the election."
Lamport, Paxos Made Simple, §2.4 Progress (words broken across the PDF's line breaks are rejoined)
Read the last sentence twice. Leader election is allowed to be wrong. It may elect nobody, or two people. Neither outcome can produce two values, because the election is not part of the safety argument at all — it is a performance optimisation bolted onto an algorithm that was already correct without it. As Lamport puts it in §3: "Election of a single leader is needed only to ensure progress."
Back in §2.2, Lamport also explains why an acceptor is allowed to be rude: "An acceptor can ignore any request without compromising safety." Dropping messages costs time. It never costs correctness. That asymmetry is why Paxos survives a network that loses, duplicates and delays anything it likes.
8. Residual risk
Liveness is your problem, not Paxos's. The paper hands you safety and hands liveness back. In practice that means timeouts, randomised backoff and a leader — and a badly tuned timeout turns a healthy cluster into a duel. A cluster that keeps electing and deposing leaders will stay correct while getting nothing done, and your monitoring must be able to tell that state from a healthy one.
Durability is load-bearing in a way that is easy to under-build. An acceptor must flush its promise before replying. A deployment that keeps acceptor state in memory, or on a disk that lies about flushes, has an algorithm that is provably safe and an implementation that is not.
Proposal numbers must never collide. Two proposers using the same number break the induction outright, because "highest-numbered" stops being well defined. The standard fix is to draw numbers from disjoint sets — a per-proposer suffix — and to persist the highest number used, which means proposer identity becomes configuration you have to get right at deployment time.
One value is rarely what you want. Everything here decides a single value, once. A real system wants an ordered log of commands, which is many instances of this algorithm running in sequence, plus leader handover, plus filling gaps with no-ops, plus reconfiguration. That machinery is where most real Paxos bugs live — not in the two phases above, which is precisely why the next lesson looks at a protocol designed to make the log, and not the single decision, the thing you reason about.
9. Check yourself
10. Back to your world
You almost certainly run Paxos already, inside something else: a configuration store, a lock service, a database's metadata layer, a leader-election library. Find it, and find the two numbers it exposes — the quorum size and the election timeout. The first is the safety knob and you should never be tempted to lower it below a majority. The second is the liveness knob, and it is the one that will actually page you.
Then ask the question this lesson was really about: when that system is unavailable, is it unavailable because it is stalled, or because it has decided something you disagree with? It is always the first. Knowing that is the difference between waiting calmly and restarting things until the invariant breaks.