Key Question
How does a proposer turn promises into a committed value?
Deep Dive
Phase 1 guarantees safety. Phase 2 drives the system toward a decision.
Phase 2a (Accept): After receiving promises from a majority, the proposer must choose the value to propose. The rule is:
- If ANY promise included a previously accepted value
(k, v), choose the valuevfrom the highest-numbered previous proposal. - If NO promise included a previous acceptance, the proposer is free to choose its own value.
The proposer sends Accept(n, v) to all acceptors, where n is the proposal number from Phase 1 and v is the chosen value.
Phase 2b (Accepted): Each acceptor receives Accept(n, v). If the acceptor hasn’t promised to any proposal with number > n, it accepts: records accepted_proposal=n and accepted_value=v, and sends Accepted(n, v) back. If it has promised a higher number, it ignores or rejects the Accept.
Full worked example:
Phase 1: Proposer sent Prepare(5)
A1 promised: included accepted=(2, "X")
A2 promised: no previous value
A3 promised: no previous value
Phase 2: Proposer selects value
Highest-numbered previous value: (2, "X")
So proposer must propose value "X" (not its own value!)
Proposer sends Accept(5, "X") to all
Acceptor responses:
A1: max_promise=5 == 5, so accepts. Sends Accepted(5, "X")
A2: max_promise=5 == 5, so accepts. Sends Accepted(5, "X")
A3: max_promise=5 == 5, so accepts. Sends Accepted(5, "X")
A value is decided when a majority accepts the same (n, v).
Here: 3/3 accepted (5, "X") — value "X" is decided.Why the “highest-numbered previous value” rule exists: Suppose two proposers P1 and P2 run concurrently. P1 gets promises with number 5, but P2 gets promises with number 6 and proposes value “Y”. If an acceptor was in both majorities (promised to both 5 and 6), that acceptor’s highest-numbered accepted value would be “Y”. When P1’s Accept(5) arrives, the acceptor rejects it because it promised 6. But if P1 gets promises from a different majority that includes an acceptor that accepted 6, P1 must propose “Y” — not its own value. This ensures that once a value is chosen, all future proposals carry the same value.
P1: Prepare(5) --> promises from A1, A2, A3
P2: Prepare(6) --> promises from A2, A3 (A1 missed)
P2: Accept(6, "Y") accepted by A2, A3.
(Now A2 and A3 have accepted value "Y")
P1: Accept(5) arrives at A2...
But A2 max_promise=6, so A2 REJECTS Accept(5)
P1 must restart with higher number, and carry "Y"Check Your Understanding
- What value must a proposer use if it received promises including a previously accepted value (3, “foo”)? What if no previous values were returned?
- A proposer sends Accept(7, “X”) to all acceptors. One acceptor has max_promise=5, another has max_promise=10. Which one accepts?
- Why does the rule about using the highest-numbered previous value prevent two competing proposals from deciding different values?
The “So What?”
The rule “use the value from the highest-numbered promise” is what guarantees safety across multiple proposers. It ensures that once a value is decided, all future proposals carry the same value — even if the proposer originally wanted a different value. This is Paxos’s invariant: once a value is chosen, it stays chosen.
✏️ Exercises
Paxos: Exercises
Exercise 1: Majority Decision
A proposer sends Prepare(5) to 3 acceptors and gets promises from 2 of them. What happens next? What if the proposer only gets 1 promise?
Exercise 2: Prior Acceptance
What does an acceptor include in its Promise if it already accepted value X under proposal number 3, and now receives Prepare(7)?
Exercise 3: Multi-Paxos
In Multi-Paxos, when must Phase 1 be repeated? Describe the exact scenario.
Exercise 4: Livelock
What prevents two proposers from “livelocking” each other — where P1 sends Prepare(5), P2 sends Prepare(6), P1 retries with Prepare(7), P2 retries with Prepare(8), ad infinitum?
👁️ View Solutions
Paxos: Solutions
Exercise 1
With 2 promises out of 3, the proposer has a majority and can proceed to Phase 2. It sends Accept(5, value) to all acceptors, where value is determined by the highest-numbered prior acceptance (if any) from the promises.
With only 1 promise out of 3, the proposer does NOT have a majority and cannot proceed to Phase 2. It must wait, pick a higher proposal number, and retry Phase 1.
Exercise 2
The acceptor includes its accepted state in the Promise. Since it accepted value X under proposal 3, the response is:
Promise(7, accepted_proposal=3, accepted_value=X)
This tells the proposer: “I promise not to accept anything below 7. By the way, I previously accepted X under proposal 3. Use this value if no higher-numbered acceptance exists.”
Exercise 3
Phase 1 must be repeated when:
- The current leader crashes or becomes unreachable (detected via timeout).
- A new leader must be elected to take over.
The new leader sends Prepare with a higher ballot number to all acceptors. Acceptors respond with all their accepted values (for all log positions), allowing the new leader to fill in gaps and continue where the old leader left off.
Phase 1 is NOT needed between individual log entries while the leader is stable — that’s the core Multi-Paxos optimization.
Exercise 4
Two practical mechanisms prevent livelock:
- Backoff: In practice, proposers use randomized backoff when their proposals fail. After a failed attempt, a proposer waits a random delay before retrying, giving the other proposer time to complete.
- Leader election: Real systems elect a single leader. Only the leader acts as proposer for most operations. Other proposers defer to the leader. This eliminates concurrent proposals in normal operation.
Without these mechanisms, basic Paxos can livelock — two aggressive proposers can keep outbidding each other forever. This is why practical Paxos implementations always have leader election.