From one value to a log
Basic Paxos chooses one value. Real systems need an ordered log of commands so replicas execute the same state machine. Multi Paxos runs one logical Paxos instance per log slot, so slot 1, slot 2, and so on each settle on a command.
Cutting the prepare cost
Running a full two phase Paxos for every slot is wasteful. Multi Paxos elects a stable leader that runs the prepare phase once for an entire range of future slots. While that leader is uncontested, each new command needs only the accept phase, collapsing a normal commit to a single round trip to a majority.
- Leader sends one prepare covering all future slots.
- For each command it sends only accept messages.
- A competing proposer forces a new, higher numbered prepare, demoting the old leader.
Failure and recovery
If the leader crashes, a new node prepares with a higher proposal number and learns any partially accepted slots, filling gaps with no operation commands so the log stays contiguous. Replicas apply committed slots in order.
Key idea
Multi Paxos amortizes the prepare phase under a stable leader so each command commits in one accept round trip across an ordered log.