Paxos Made Simple
A plain-language derivation of the Paxos consensus algorithm: proposers, acceptors, and learners, and the two-phase protocol that lets a majority agree on a single value even when messages are lost and nodes crash. The safety argument is built up one requirement at a time.
Key ideas
- A majority quorum guarantees that any two decisions overlap
- Proposal numbers order attempts so later proposals respect earlier chosen values
- Liveness needs a distinguished proposer; safety never does
Why read it now
Consensus is the foundation of every coordination service and replicated log. Read this before Raft so you can see what Raft was simplifying.
Question to keep in mind
What exactly does phase one promise, and why is that promise enough to prevent two different values from being chosen?