Course contentsShow
← Computer Science
Lesson 2681 of 2,87259. Consensus and ReplicationFree lesson

Multi-Paxos: Optimizing for Multiple Decisions

Learning how Multi-Paxos reduces message overhead by electing a stable leader for a sequence of consensus instances.

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:

  1. Leader Election: One proposer successfully completes Phase 1 (prepare/promise) with a high proposal number
  2. 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)
  3. 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.