Multi-Paxos for Log Replication
You'll learn how Paxos extends from agreeing on a single value to agreeing on an ordered sequence of values, enabling replicated state machines.
From Single-Value to Sequence Agreement
Basic Paxos solves consensus for one value. But most distributed systems need agreement on a sequence of operations—think of a replicated database log or a distributed key-value store. Running independent Paxos instances for every log entry would be prohibitively expensive: each would require separate prepare and accept phases.
Multi-Paxos optimizes this by reusing the prepare phase across multiple values. Once a proposer becomes the leader (through a successful prepare with the highest proposal number), it can skip the prepare phase for subsequent log entries. It directly issues accept requests for new values, dramatically reducing message overhead.
How It Works
- Leader election: A proposer sends prepare(n) once and becomes the stable leader for proposal number
n - Log positions: Each consensus decision corresponds to a numbered slot in the replicated log (slot 1, slot 2, etc.)
- Streamlined accepts: The leader sends accept requests for new log entries without repeating prepare, as long as it remains unchallenged
- Preemption handling: If a higher-numbered prepare arrives, the current leader steps down, and the protocol reverts to full Paxos
Building Replicated State Machines
Each node applies committed log entries in order to its local state machine. Because Multi-Paxos guarantees all nodes agree on the same sequence of values in the same order, all replicas converge to identical states—achieving strong consistency across the distributed system.
This is the foundation for systems like Chubby, Spanner's transaction coordinators, and many replicated databases.
Key Takeaway:
Multi-Paxos extends single-value Paxos to efficiently replicate an ordered log by electing a stable leader who skips repeated prepare phases, enabling strongly consistent replicated state machines.