The goal
Paxos lets a group of nodes agree on a single value even if some crash or messages are delayed. It is the classic foundation of consensus, valued for its proven safety.
The roles
- Proposers suggest values.
- Acceptors vote on proposals and form the quorum.
- Learners discover the chosen value.
The two phases
Each proposal carries a unique increasing number.
- Prepare the proposer sends a number to acceptors. Each acceptor promises not to accept anything lower and returns any value it already accepted.
- Accept if a majority promised, the proposer sends an accept request. If acceptors saw a prior accepted value they must reuse the highest numbered one.
A value is chosen when a majority accept it.
Why the reuse rule matters
Forcing a proposer to adopt the highest previously accepted value is what makes Paxos safe. Once a value could have been chosen, every later proposal carries it forward, so the system never decides two different values.
The catch
Plain Paxos agrees on one value. Real systems run Multi Paxos to chain many decisions and add a stable leader to avoid dueling proposers that stall progress.
Key idea
Paxos guarantees a single agreed value by making proposers carry forward any previously accepted value through a two phase majority vote.