Multi-Paxos: Optimizing for Multiple Decisions
What you'll learn: How Multi-Paxos dramatically reduces message overhead by electing a stable leader to coordinate multiple consensus rounds efficiently.
The Problem with Basic Paxos
In basic Paxos, every single consensus decision requires a full two-phase protocol: prepare/promise (Phase 1) and accept/accepted (Phase 2). If you need to reach consensus on a sequence of values—like ordering a stream of client requests in a replicated state machine—running separate Paxos instances for each decision becomes prohibitively expensive. Each decision would require at least 4 message delays and numerous network round trips.
Multi-Paxos: The Leader Optimization
Multi-Paxos recognizes that if one proposer consistently wins Phase 1, we can reuse that leadership across multiple consensus instances. Here's how:
- Leader Election: One proposer successfully completes Phase 1 (prepare/promise) with a high proposal number
- Phase 1 Skipping: As long as no failures occur, this leader can skip Phase 1 for subsequent decisions and jump straight to Phase 2 (accept/accepted)
- Sequence of Decisions: The same leader coordinates consensus for instance 1, 2, 3, and so on, sending only accept requests
Think of it like this: instead of electing a class president for every single decision, you elect one president who makes multiple decisions during their term. They only need re-election if they fail or are challenged.
Efficiency Gains
With a stable leader, each consensus decision requires just one round trip (accept/accepted) instead of two. Message complexity drops from 2n phases to 1n for normal operation. The leader only re-runs Phase 1 if it suspects another proposer may have attempted to take over.
Key Takeaway: Multi-Paxos transforms Paxos from a single-shot consensus algorithm into an efficient replicated log by electing a stable leader who coordinates multiple sequential decisions, dramatically reducing message overhead from two phases to one per decision.