Classic Paxos agrees on one value. But real systems—replicated logs, state machines, databases—need to agree on a continuous stream of values. Running full Paxos per value means two round trips of messages (Prepare/Promise, then Accept/Accepted) for every single decision. At 10ms cross-datacenter latency, that's 40ms per operation before you even touch disk. Multi-Paxos fixes this by recognizing a simple truth: if the same node keeps proposing, you don't need to re-run the Prepare phase every time.

The core insight: The Prepare phase exists to establish a proposer as the authority for a ballot number. Once a proposer wins Prepare for ballot b, it can use that same ballot for all future slots in the log until someone else runs a higher-ballot Prepare. So Multi-Paxos elects a stable leader, and that leader skips Prepare on every subsequent proposal—reducing the steady-state cost from 2 round trips to 1 round trip per decision.

How it works in practice:

• A node runs Prepare once for a ballot number, covering all log slots from position N onward.
• Acceptors promise not to accept lower-ballot proposals for any slot ≥ N.
• The leader now issues Accept messages directly for each new slot—no Prepare needed.
• If the leader dies, a new leader runs Prepare with a higher ballot and takes over.

Real-world example: Google's Chubby lock service uses Multi-Paxos. A single master handles all writes; replicas accept its proposals directly. When the master fails, a new election runs the expensive Prepare phase, but during normal operation—which is 99%+ of the time—every write is a single round trip. Spanner's Paxos groups work the same way: one leader per shard amortizes consensus across millions of transactions.

The rule of thumb: Multi-Paxos cuts steady-state message complexity from 4n messages per decision (Prepare+Promise+Accept+Accepted across n acceptors) to 2n messages (Accept+Accepted only). At a 5-node cluster with 10ms RTT, that's the difference between 40ms and 20ms per commit—a 2× throughput ceiling improvement, before batching.

The catch: Multi-Paxos requires a stable leader, which means you need a failure detector, leader election, and lease management. Split-brain scenarios where two nodes both think they're leader are handled by ballot ordering—the higher ballot wins, and the loser's in-flight proposals get rejected. But if leadership churns constantly, you pay Prepare costs repeatedly, and performance collapses toward single-decree Paxos.