Distributed consensus, replication, and fault tolerance / personal lessonsLesson 10 of 17
Lesson browserDistributed consensus, replication, and fault tolerance lessonsPrevious: Raft log repair and commitmentNext: Safe reads, leases, and fencing
Distributed systems · Lesson 10

Paxos and preserving an earlier decision

Derive prepare, promises, and value adoption for one consensus slot.

By the end: Explain why a higher ballot cannot simply replace a previously chosen value.

Separate ballot numbers from values

Basic Paxos chooses one value for one slot. Proposers try to get values chosen; acceptors record promises and accepted proposals; learners discover the result. These roles may live on the same machines. A proposal has a unique, ordered ballot number and a value. An acceptor accepting a proposal is not the same as a quorum choosing it.

A value is chosen when a quorum accepts the same proposal under the protocol. A proposer can crash before learning that this happened. Later proposers must preserve the value even if nobody previously announced it. This is the same knowledge problem seen in replication: a decision’s existence does not require that the client has received a reply.

A chosen value can outlive every announcement

Treat a slot as a question with one irrevocable answer, such as which command occupies position 17. Different commands can be proposed for that question, but after a value is chosen, every later successful proposal for that slot must carry that value. A chosen command can still produce an application rejection. Choosing Reserve(12, Bo) does not promise Bo the seat. It promises agreement on running that command, whose deterministic result might be that Ada already owns the seat. Paxos agreement concerns the command, not whether its requested business action succeeds.

For a separate paper case, use three acceptors A, B, and C, with a majority of two. A proposer completes preparation at ballot 10 with A and B reporting no earlier acceptances. It then sends proposal (10, x). A and B durably accept it, while C receives nothing. At that point x is chosen. Now lose both acceptance replies and crash the proposer. No learner has enough delivered evidence to announce success, yet the decision already exists. Announcing a decision is an information transfer about an established fact, not the act that creates that fact. A replacement must preserve x even if every client reports only a timeout.

Compare a second execution where only A accepts (10, x), while B and C receive nothing. The first proposer again crashes. Here the stated evidence does not establish that x was chosen. Nevertheless, a replacement hearing from A and C cannot distinguish this execution from one where B accepted x and its reply disappeared. A must report its acceptance. The replacement cannot discard that report merely because it has heard only one copy. Its observations cover a quorum, not every acceptor and every delayed message in the execution.

Keep accepted, chosen, and learned as separate labels on your paper. Accepted describes one acceptor's durable state. Chosen describes a quorum fact. Learned describes a participant obtaining sufficient evidence of that fact under its learning procedure. Once chosen, the slot's answer cannot change, although later ballots may choose the same answer again. An acceptor may replace its highest accepted proposal with a later one according to the rules. That local replacement does not erase the earlier decision or authorize a different chosen value.

Ballot uniqueness prevents another ambiguity. Two different proposers must not issue different values under the same ballot for the same slot. A conceptual way to order attempts is a pair containing a durable increasing counter and a unique proposer identity, compared by counter and then identity. This is an explanatory numbering scheme, not a complete implementation prescription. Restart must not cause ballot reuse. A clock reading alone is insufficient because clocks can coincide or move backward. Neither a larger ballot nor a distinct proposer identity implies that its proposed application value deserves priority.

Prepare constrains the future and reveals the past

A proposer selects a ballot higher than those it has observed and sends Prepare. An acceptor promises not to accept proposals with lower ballot numbers and reports its highest previously accepted proposal, if any. Promises and accepted proposals must survive the covered crashes. A response is not just a vote of confidence; it constrains what the acceptor may do next.

After promises from a majority, the proposer must adopt the value in the highest-numbered accepted proposal among those responses. Only if none report an accepted proposal can it choose its own value freely. It then sends Accept for its ballot and selected value. Acceptors accept if doing so does not violate a higher promise. A majority of accepts chooses the value. Ballot numbers order attempts for this slot; they are not log positions or wall times.

Promises close an older proposer's remaining options

Each acceptor needs two kinds of protocol memory for this slot. Its promised ballot is a lower bound on future ballots it may accept. Its highest accepted proposal records a ballot and value that may carry a past decision forward. These records answer different questions. An acceptor can have promised ballot 14 while its highest accepted proposal remains (10, x). The promise does not claim that ballot 14 has supplied a value, and it does not delete x. A Prepare response must expose the relevant accepted proposal as well as establish the promise.

Consider a fresh paper execution with all acceptors initially empty. Proposer P prepares ballot 20 at A and B, receives durable promises reporting no accepted proposal, and selects x. Before its Accept messages arrive, proposer Q prepares ballot 21 at B and C. Both again report no acceptance. Q may select y. B now rejects P's delayed ballot-20 Accept because it promised 21. Even if A accepts x at 20, P cannot obtain a majority from A alone. Q can have B and C accept y at 21 without conflicting with an already chosen x.

Change only the message order. P gets A and B to accept x before Q's Prepare reaches B. Q's ballot-21 preparation now receives B's report of (20, x). Q must select x, even if it wanted y. These two executions explain the two jobs of preparation. It discovers relevant earlier acceptances, and its promises prevent lower ballots from acquiring new acceptances at the responding acceptors. A report with no acceptance is useful only together with that future restriction. A snapshot of old state without a promise would leave older attempts free to complete afterward.

For another case, suppose a majority of responses contains accepted (7, x) and accepted (9, y). The preparation rule selects y, not the value reported by the fastest response or the value most often reported. These records need not mean x was previously chosen. If x had been chosen, the protocol's earlier adoption obligations would have forced later accepted proposals to preserve x. The general safety argument uses that obligation repeatedly across ballots. It is not a vote tally among application values. The highest accepted ballot identifies the proposal whose history the new attempt must continue.

Persistence is part of each step, not later housekeeping. If B replies to Prepare 21 before its promise is durable, crashes, and restarts remembering only promise 20, it may accept P's delayed request. That violates the restriction Q relied on. Similarly, forgetting an accepted value can make a later proposer incorrectly conclude that no prior value needs preservation. Assume non-malicious acceptors and storage that retains acknowledged protocol records across the covered crashes. The majority argument does not protect arbitrary disk loss or an acceptor that deliberately reports false state. The table below isolates value adoption under those assumptions.

Work through the model

AcceptorAccepted before prepare 5Response to prepare 5
A(4,x)Unreachable
B(4,x)Promise 5; report (4,x)
CNonePromise 5; report none
B+C form a majority. The proposer must carry x into ballot 5, even without contacting A.

Read the table as evidence rather than a tally

In the displayed table, A is unreachable, not empty. B and C are enough to finish preparation because two of the three acceptors form a majority. B reports (4, x), and C reports no accepted proposal. The proposer therefore sends (5, x), rather than choosing an application value from C's empty history. Writing x beside the next ballot on paper makes the distinction explicit. The attempt number advances from 4 to 5 while the value stays x. This table presents evidence states, not an interactive message scheduler.

Do not infer from the displayed responses alone that ballot 5 has chosen anything. Preparation has constrained acceptors and selected a permissible value, but acceptance is another phase. Suppose B and C promise 5 and the proposer sends Accept(5, x). B accepts, while C has already promised 6 to a competitor and rejects 5. The ballot-5 proposer has one acceptance, not a majority. Its successful preparation did not reserve uninterrupted access to those acceptors. Higher ballots can prevent completion without invalidating the preparation evidence that selected x.

Continue this separate case by letting ballot 6 prepare successfully with A and C. Its reports might reveal an earlier acceptance at A, or none at C. Apply the adoption rule to the actual reports, rather than automatically copying the last proposer's intention. An intention that never reached an acceptor is not accepted evidence. If x was already chosen at some ballot, the complete protocol rules ensure this later preparation cannot permit a different value. If x was never chosen, a later attempt may sometimes choose another value. Safety protects decisions, not every unsuccessful proposal.

A useful guided comparison is to make two columns headed before promise and after promise. In the first column, have B accept ballot 4 before reporting to ballot 5. Its report must contain that acceptance. In the second, have B promise 5 before the ballot-4 Accept arrives. It must reject the old Accept. These are the exhaustive relative orders at that acceptor if each operation updates its protocol state atomically. There is no allowed third case in which B promises 5, reports no earlier acceptance, and then helps ballot 4 choose a conflicting value.

The shared acceptor provides protection because it enforces both sides of that comparison. Intersection arithmetic alone merely identifies B. It says nothing about whether B's response is truthful, durable, or consistent with later behavior. The safety explanation assumes those properties for nonfaulty acceptors. Delays and lost replies can leave proposers uncertain, but they must not make a correct acceptor retract its promise. This is how the protocol tolerates missing communication without treating a timeout as permission to choose a new value.

Why adoption is necessary

Suppose ballot 4 with x was accepted by A and B in a three-acceptor system. A new proposer obtains ballot-5 promises from B and C. B’s report carries x into the new attempt even if C knows nothing about it. With concurrent attempts, adopting the highest accepted ballot is essential; the general proof shows that this rule preserves any already-chosen value through intervening ballots. An isolated accepted value may also need adoption when the proposer cannot rule out that it was chosen elsewhere.

Multi-Paxos applies consensus across a sequence of slots and can amortize preparation under a stable leader. Raft instead organizes the explanation around terms, leader election, and a replicated log with an election freshness restriction. Do not equate Raft’s log-term comparison with choosing an arbitrary highest Paxos ballot across all log slots. Both protect earlier decisions through durable restrictions and intersecting quorums, but their exact rules differ. Competing proposers can keep preempting one another; a stable leader helps progress without being a new safety axiom.

Repeated slots need progress and application rules

A replicated service needs more than one slot because it executes a sequence of commands. Slot 17 and slot 18 ask different consensus questions. Choosing x for slot 17 does not require choosing x for slot 18. A state machine normally applies the decided sequence in slot order. If slot 18 is known while slot 17 remains unresolved locally, application must wait for the missing prefix or use another explicitly justified mechanism. Executing whichever decision arrives first would let replicas run different command orders even though each individual slot is safe.

Ballots and slots therefore form separate coordinates. A stable proposer may use one leadership ballot while driving acceptance for many slots, but each slot retains its own accepted value information. Preparation for a multi-slot protocol must account for the relevant unresolved slots and earlier acceptances. Basic single-slot reasoning explains why value adoption matters; it does not specify log compaction, recovery, hole filling, membership changes, or a production Multi-Paxos implementation. Treating a single maximum ballot anywhere in a log as the answer for every slot would confuse separate decisions.

Safety also does not guarantee that a particular proposer finishes. P can prepare 30, then Q prepares 31 before P collects accepts. P retries at 32, and Q repeats at 33. Each acceptor can obey every promise while both proposers keep losing the opportunity to finish. A stable leader reduces this competition. Progress still requires enough reachable acceptors and a communication period in which the leader can complete the necessary phases. Increasing ballot numbers is a reaction to interference, not a proof that interference must eventually stop.

For a guided failure comparison, keep acceptors A and B reachable and C silent. With one effective proposer and functioning durable storage, A and B can supply the two responses required at each phase. Now isolate A from both B and C. A can retain its records, but cannot decide new values alone. This loss of progress does not revoke an earlier chosen value. The restriction is consistent with the earlier impossibility lesson: deterministic safety under arbitrary delays does not imply termination in every asynchronous execution. A temporary stable majority is a progress assumption, not evidence that absent machines have died.

Finally, a chosen command and a delivered client result remain separate service events. Two retries can occupy two different slots unless the application recognizes that they name the same intended operation. Even after a learner knows a slot's value, the state machine may need to apply preceding slots before calculating its result. The next lesson examines a related knowledge problem for reads: a server needs evidence that it still has authority and that its applied state includes the necessary committed prefix. Consensus on writes does not grant every replica perpetual permission to answer current reads.

Exercises

Can the new proposer use its own value?

A proposer wants y. Its majority of Prepare responses includes accepted (8,x) and accepted (6,y). Which value must it send in Accept at ballot 9?

Hint

Select by highest accepted ballot among the responses, not by preference or response count.

Worked answer
Reported ballotValueAdopt?
8xYes
6yNo, lower accepted ballot
The new proposal is (9,x), not (9,y).

It must propose x at ballot 9. Ballot 8 is the highest reported accepted ballot. The proposer cannot safely infer that x was never chosen by other acceptors it did not hear from. A higher attempt number does not authorize changing an already chosen slot.

A late Accept arrives

An acceptor promised ballot 12, then receives an Accept request at ballot 11. Should it accept because the value seems harmless?

Hint

A promise constrains later behavior independently of application meaning.

Worked answer
Persistent promiseIncoming ballotResult
1211Reject
1212Eligible under the normal accept rule
Accepted does not yet mean chosen; a quorum is still needed.

No. It must reject the lower ballot. The safety argument uses that persistent restriction to prevent an older proposer from creating a conflicting decision after a newer quorum has prepared. Application-level plausibility is not a substitute for the protocol rule.

Sources and further reading

The explanations and worked answers above stand alone. These references provide the original algorithms, assumptions, and deeper proofs; they are not required downloads.

Lesson browserDistributed consensus, replication, and fault tolerance lessonsPrevious: Raft log repair and commitmentNext: Safe reads, leases, and fencing