From one decision to many
Basic Paxos lets a set of nodes agree on one value despite failures, using two phases: a prepare phase to claim leadership for a proposal number, and an accept phase to commit a value. Running full Paxos for every log entry would be wasteful.
Multi Paxos extends this to agree on a sequence of values, one per log slot, which is what state machine replication needs.
The key optimization
The insight is that the prepare phase establishes a stable leader. Once a node wins prepare, it can skip the prepare phase for future slots and run only the accept phase, as long as no other node challenges it.
- The first round elects a distinguished leader.
- That leader proposes values for many slots using just one round trip each.
- If the leader fails, another node runs prepare to take over.
This collapses steady state agreement to roughly one round trip per entry, matching the efficiency of a single leader while keeping consensus safety.
Key idea
Multi Paxos amortizes the prepare phase by keeping a stable leader, so each log entry usually needs only a single accept round.