Key Question
Who are the actors in Paxos, and what does each do?
Deep Dive
Paxos defines three roles. A single server typically plays all three simultaneously.
Proposer: The active role. A proposer initiates the consensus process by sending proposals to acceptors. It picks a proposal number (unique, monotonically increasing) and asks acceptors to vote. If a proposer’s proposal is rejected, it picks a higher number and tries again. Multiple proposers can exist, but proposers should back off to let one succeed.
Acceptor: The memory of the system. Acceptors receive proposals, vote on them, and remember their votes. Each acceptor stores two pieces of state:
max_promise: The highest proposal number it has promised to accept (or nothing if none).accepted_valueandaccepted_proposal: The highest-numbered proposal it has actually voted for.
Acceptors must be persistent — if an acceptor crashes and loses its max_promise, it might promise a lower number than it already accepted, violating safety. This is the one place where Paxos requires durable storage.
Learner: The passive role. Learners collect accept messages from acceptors and learn the decided value. Learners don’t participate in the protocol — they just observe. In practice, every node is usually also a learner so they know the final decision.
Proposer
/ | \
Prepare/ | \Accept
/ | \
Acceptor 1 --- Acceptor 2 --- Acceptor 3
\ | /
\ | /
Learned: value is decided!
Learner(s)Nodes can play multiple roles. In a 3-node Paxos deployment:
- Node 1: proposer + acceptor + learner
- Node 2: proposer + acceptor + learner
- Node 3: proposer + acceptor + learner
This is the standard deployment pattern. The roles are logical, not physical.
Check Your Understanding
- What two pieces of state must an acceptor persist to disk?
- Why must acceptors be persistent, but proposers don’t need to be?
- If a learner crashes and restarts, how does it learn the decided value?
The “So What?”
Paxos roles map to real components. In Google’s Chubby lock service, each server is simultaneously a proposer, acceptor, and learner. Understanding the role separation helps you reason about what each node must remember (acceptors persist promises and votes) and what can be ephemeral (proposers can restart fresh). This role separation is what makes Paxos composable — you can add learners without affecting the protocol’s safety.
✏️ 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.