The agreement problem
Basic Paxos lets a set of unreliable nodes agree on a single value even when some crash and messages arrive late, get reordered, or vanish. It never agrees on two different values, which is the property that makes it trustworthy.
Roles and the two phases
Nodes act as proposers, acceptors, and learners. A value is chosen when a majority of acceptors accept it. Agreement runs in two rounds, each tagged with a globally unique, increasing proposal number.
- Prepare phase: a proposer picks a number n and sends prepare n to acceptors. An acceptor that has not promised a higher number replies with a promise, plus any value it already accepted.
- Accept phase: if a majority promise, the proposer sends accept with value v. Crucially, if any acceptor reported a previously accepted value, the proposer must reuse the value tied to the highest such number.
Why it is safe
That reuse rule is the heart of safety. Once a value is chosen by a majority, any later proposer with a higher number will see it during prepare and be forced to propose the same value. Two majorities always intersect, so the chosen value cannot be lost or contradicted.
Key idea
Basic Paxos chooses one value safely by requiring majority quorums and forcing proposers to adopt any already accepted value.