Key Question

How does a proposer claim the right to propose a value?

Deep Dive

Phase 1 establishes a “lock” on the system. Before a proposer can suggest a value, it must first ensure that no earlier proposal could later succeed with a different value. It does this by asking acceptors to promise they’ll reject older proposals.

Phase 1a (Prepare): The proposer picks a unique, monotonically increasing proposal number n (e.g., sequence numbers like 1, 2, 3…). It sends Prepare(n) to all acceptors. The number must be higher than any number the proposer has used before.

Phase 1b (Promise): Each acceptor receives Prepare(n). The acceptor checks: have I already promised to a proposal with number ≥ n? If so, it ignores this Prepare (it’s stale). If n is higher than any promise it’s made, the acceptor:

1. Promises never to accept any proposal with number < n.
2. If the acceptor has already accepted some proposal (value v, number k), it includes (k, v) in the response.
3. Sends Promise(n, k, v) back, or Promise(n, null) if nothing accepted.

Concrete example with 3 acceptors:

Proposer P sends Prepare(5) to A1, A2, A3.

Acceptor states before:
  A1: max_promise=2, accepted=(2, "X")
  A2: max_promise=0, accepted=none
  A3: max_promise=0, accepted=none

A1 receives Prepare(5): 5 > 2, so A1 promises.
  Responds: Promise(5, accepted=(2, "X"))
  New state: max_promise=5

A2 receives Prepare(5): 5 > 0, so A2 promises.
  Responds: Promise(5, none)
  New state: max_promise=5

A3 receives Prepare(5): 5 > 0, so A3 promises.
  Responds: Promise(5, none)
  New state: max_promise=5

Proposer receives 3/3 promises. Phase 1 complete!

If an acceptor responds Promise(5, accepted=(2, "X")), it’s saying: “I already accepted proposal 2 with value X. I won’t accept anything below 5, but you should know about my previous acceptance.”

A proposer needs a majority of promises to proceed — with 3 acceptors, that’s 2 promises (including its own if the proposer is also an acceptor).

Check Your Understanding

1. A proposer sends Prepare(10) to 5 acceptors and gets 3 promises. Can it proceed? What if it only gets 2?
2. What does an acceptor do if it receives Prepare(7) but has already promised to proposal 10?
3. Why must proposal numbers be unique across all proposers? What happens if two proposers both use number 5?

The “So What?”

Phase 1 establishes a “lock” on the system — once a majority has promised to number n, no older proposal can succeed. This is Paxos’s safety guarantee. If you have promises from a majority, you know that any previously accepted value is included in one of those promises, and no new proposal with a lower number can be accepted anywhere.

✏️ 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?