The roles
Paxos, by Leslie Lamport, reaches consensus on a single value using three roles, often played by the same machines:
- Proposers suggest values
- Acceptors vote and form the quorum
- Learners find out the chosen value
The two phases
A proposer drives a numbered round:
- Phase one prepare the proposer picks a unique proposal number n and asks acceptors to promise not to accept anything lower; acceptors reply with any value they already accepted
- Phase two accept if a majority promised, the proposer asks them to accept its value, but it must reuse the highest numbered value any acceptor already reported
Why it is safe
Because any two majorities overlap in at least one acceptor, once a value is chosen no later round can choose a different one. The promise step ensures a new proposer learns and preserves an already chosen value.
The pain points
- Bare Paxos decides one value; you need Multi Paxos for a log
- Dueling proposers can stall progress, so practical systems elect a stable leader
- The paper is famously hard to read, which motivated Raft
Key idea
Paxos uses prepare and accept phases over majority quorums, and overlapping majorities plus the promise rule guarantee that once a value is chosen it can never change.