Understanding Paxos
Paxos is the foundational consensus algorithm. Invented by Leslie Lamport in 1989, it's proven correct and used (in various forms) in many production systems.
It's also famously difficult to understand. Let's fix that.
The Setup
The Goal
Multiple nodes want to agree on a single value. Some nodes might crash. Messages might be delayed or lost. But once a value is chosen, it must never change.
Three Roles
Proposes values to be chosen
Votes on proposals, stores decisions
Learns the chosen value
A single node can play multiple roles. In practice, every node is often a proposer, acceptor, and learner simultaneously.
The Two Phases
Phase 1: Prepare
The proposer asks acceptors: "Has anyone already accepted a value?"
Proposer Acceptors
| [A1] [A2] [A3]
|--- Prepare(n=1) ------->| | |
|--- Prepare(n=1) ------------>| |
|--- Prepare(n=1) ---------------->|
| | | |
|<-- Promise(n=1) ---------| | |
|<-- Promise(n=1) --------------| |
|<-- Promise(n=1) ------------------|Prepare Message
Proposer sends Prepare(n) where n is a unique proposal number.
Promise Response
Acceptor promises not to accept proposals with numbers less than n. If it already accepted a value, it tells the proposer.
Phase 2: Accept
If a quorum of acceptors promised, the proposer sends the actual value.
Proposer Acceptors
| [A1] [A2] [A3]
|--- Accept(n=1, v="X") -->| | |
|--- Accept(n=1, v="X") ------->| |
|--- Accept(n=1, v="X") ----------->|
| | | |
|<-- Accepted(n=1) --------| | |
|<-- Accepted(n=1) -------------| |
|<-- Accepted(n=1) -----------------|
|
| Value "X" is chosen!Key Rule
If during Phase 1 an acceptor reports it already accepted a value, the proposer must propose that value. This preserves decisions that were already made.
The Complete Protocol
class Proposer:
def propose(self, value):
# Generate unique proposal number
n = self.next_proposal_number()
# Phase 1: Prepare
promises = []
for acceptor in self.acceptors:
response = acceptor.prepare(n)
if response.promised:
promises.append(response)
if len(promises) < self.quorum:
return False # Failed to get quorum
# Check if any acceptor already accepted a value
highest_accepted = max(
(p for p in promises if p.accepted_value),
key=lambda p: p.accepted_number,
default=None
)
# Must use previously accepted value if exists
if highest_accepted:
value = highest_accepted.accepted_value
# Phase 2: Accept
accepts = []
for acceptor in self.acceptors:
response = acceptor.accept(n, value)
if response.accepted:
accepts.append(response)
if len(accepts) >= self.quorum:
return value # Consensus reached!
return False
class Acceptor:
def __init__(self):
self.promised_number = 0
self.accepted_number = 0
self.accepted_value = None
def prepare(self, n):
if n > self.promised_number:
self.promised_number = n
return Promise(
promised=True,
accepted_number=self.accepted_number,
accepted_value=self.accepted_value
)
return Promise(promised=False)
def accept(self, n, value):
if n >= self.promised_number:
self.promised_number = n
self.accepted_number = n
self.accepted_value = value
return Accepted(accepted=True)
return Accepted(accepted=False)Why Two Phases?
Without Phase 1, two proposers could conflict:
Without Prepare Phase (Broken)
Proposer P1: Accept(v="A") → Acceptors [1,2]
Proposer P2: Accept(v="B") → Acceptors [2,3]
Acceptor 2 receives both! Which wins?
Different acceptors have different values = Broken!With Prepare Phase (Correct)
P1: Prepare(n=1) → Gets promises from [1,2]
P2: Prepare(n=2) → Gets promises from [2,3]
Acceptor 2 tells P2: "I promised n=1"
P2 must use higher n, or discover P1's value
Ordering prevents conflicts!Handling Failures
As long as a quorum responds, consensus proceeds. Crashed acceptor can recover and learn the decision.
Another proposer can take over with a higher proposal number. The protocol continues.
Proposer times out and retries with a higher proposal number. Eventually succeeds.
The Dueling Proposers Problem
What if two proposers keep interrupting each other?
Livelock Scenario
P1: Prepare(n=1) → Promises
P2: Prepare(n=2) → Promises (invalidates n=1)
P1: Accept(n=1) → Rejected!
P1: Prepare(n=3) → Promises (invalidates n=2)
P2: Accept(n=2) → Rejected!
... forever ...Multi-Paxos: The Practical Version
Basic Paxos decides one value. Multi-Paxos decides a sequence of values (a log):
Multi-Paxos Optimization
- Elect a stable leader
- Leader skips Phase 1 for subsequent proposals
- Only Phase 2 needed (one round-trip!)
- If leader fails, elect new leader (back to Phase 1)
Log position: [1] [2] [3] [4] [5]
Values: "A" "B" "C" "D" "E"
↑ ↑ ↑ ↑ ↑
Paxos instance for each positionWhy Is Paxos Hard?
The Paper
Lamport's original paper uses a Greek parliament metaphor that confuses more than it helps.
Many Variants
Multi-Paxos, Fast Paxos, Cheap Paxos, Egalitarian Paxos... each with subtle differences.
Edge Cases
Handling leadership changes, log gaps, and reconfiguration requires careful implementation.
"The Paxos algorithm, when presented in plain English, is very simple."
The community disagrees. This is why Raft was invented.
Real-World Paxos
Google's distributed lock service uses Paxos. Powers everything from GFS to Bigtable to Spanner.
Uses a Paxos-like protocol called Zab. Powers coordination for Kafka, Hadoop, and many distributed systems.
Key Takeaways
- Two phases - Prepare (discover) and Accept (propose)
- Proposal numbers - Order proposals to prevent conflicts
- Preserve decisions - If a value was accepted, use it
- Multi-Paxos - Practical version with stable leader
Next up: Raft Made Simple - A more understandable consensus algorithm.