Single-decree Paxos (5.2) decides one value. A real replicated log (article 3.2) needs to decide a whole sequence — the entire point of article 4.3's SMR/log/atomic-broadcast equivalence. The naive approach — run a completely independent instance of single-decree Paxos for every log position — works correctly but pays Phase 1's full round-trip cost for every single entry, an unacceptable tax at any real throughput. Multi-Paxos is the practical optimization: elect a stable leader once, let it skip Phase 1 for every subsequent entry, and only fall back to a full Phase 1 when leadership actually changes. This single optimization is what turns Paxos from an elegant proof into the algorithm that actually powers production systems (Chubby, Spanner, and others covered in Phase 9).
The naive cost: full Paxos per log entry
Running independent single-decree Paxos instances for every log index works — article 4.3 already showed this reduction is formally valid — but look at the cost per entry: Phase 1 (Prepare/Promise) round-trip, then Phase 2 (Accept/Accepted) round-trip, for every single value. That's two full network round-trips to a majority for every write, when — as the worked example in article 5.2 showed — Phase 1's entire purpose is discovering whether some other proposer might have already gotten a conflicting value accepted. If the same proposer keeps winning every round, asking that question over and over is pure, wasted overhead.
The key insight: Phase 1 can cover a whole range at once
Here's the optimization, stated precisely: a proposer's Phase 1 Prepare(n) doesn't have to reference a specific log index at all — it can ask, in effect, "promise to ignore any proposal numbered below n, for every log index from here forward." If a majority of acceptors grant this broader promise, the proposer has effectively "reserved" the right to skip Phase 1 for every future index, as long as it keeps using the same proposal number n — it only needs to run Phase 2 (Accept/Accepted) for each new value, which is a single round-trip instead of two.
This proposer that's "reserved" the leadership role is, of course, exactly what article 4.2 called the elected leader — Multi-Paxos formalizes leader election as a specific, first-class use of Phase 1, rather than treating election and log-appending as separate mechanisms. A stable leader, once it has completed one Phase 1 covering "all future indices," can accept new client writes with just one round-trip (Phase 2 only) for as long as it remains leader.
Fig 1 — Amortizing Phase 1's cost across an entire stream of writes is Multi-Paxos's single defining optimization.
When the full Phase 1 is still required
The optimization only holds as long as the same proposer keeps winning — the moment leadership changes (the old leader is suspected dead, per article 2.4/4.2's election machinery, and a new proposer takes over), the new leader must run a genuine Phase 1 before it can safely append anything, for exactly the reason article 5.2's safety proof requires: it needs to discover whether any prior leader might have already gotten a value accepted at some log index it doesn't yet know about (mirroring article 3.2's log-divergence-and-repair discussion directly). This is precisely why leadership changes in Multi-Paxos-family systems have a brief, real cost — one Phase 1 round-trip to re-establish the new leader's "reservation" — before normal fast-path appends resume.
Handling gaps: out-of-order acceptance
A real-world wrinkle worth naming: because Phase 2 messages for different log indices can be sent and acknowledged somewhat independently (especially with network reordering, article 1.1's "Lie #1"), an acceptor might receive and accept index 49 before index 48 arrives — creating a temporary gap in its local log. Multi-Paxos implementations handle this with an explicit "no-op" filling mechanism: if a leader change occurs and the new leader's Phase 1 discovers a gap (some index below the highest known accepted index that nobody reports an accepted value for), it's safe to fill that gap with an explicit no-op entry — because if no acceptor in the responding majority has an accepted value there, article 5.2's Phase 2 rule confirms nothing could have been chosen at that index, so filling it with a placeholder that changes nothing is provably safe.
FAQ
Does Multi-Paxos require a completely different safety proof from single-decree Paxos?
No — this is one of the cleanest illustrations of article 4.3's equivalence in practice. Multi-Paxos's safety rests entirely on running (an optimized version of) single-decree Paxos independently at each log index; the per-index safety guarantee from article 5.2's proof applies unchanged. The optimization only touches the message-count/latency cost, never the safety argument.
Can multiple leaders coexist temporarily in Multi-Paxos, and is that unsafe?
It can happen briefly (e.g., a network hiccup causes a majority to elect a new leader while the old one hasn't yet realized it's been replaced — directly echoing article 3.4's stale-leader discussion) but it's never unsafe, only potentially wasteful — competing proposers can, at worst, cause the liveness stall discussed in article 5.2, never a safety violation, because the underlying single-decree safety proof holds regardless of how many proposers are active.
Why don't acceptors need to durably store a separate promise per log index if Phase 1 is unified?
They typically store one "highest promised proposal number" that applies across all indices (since a unified Phase 1 covers all of them at once), plus per-index accepted values as entries actually get appended — a modest, practical simplification of the bookkeeping compared to running fully independent per-index state.
Is Multi-Paxos a different algorithm from Paxos, or an optimization of it?
It's best understood as an optimization/practical-deployment-pattern layered on top of the same core single-decree algorithm, not a separate algorithm with its own independent safety proof — which is exactly why this article's safety-argument FAQ above reduces cleanly back to article 5.2. Some later algorithms in Phase 7 (Flexible Paxos, in particular) optimize Multi-Paxos further in ways that do require new, extended safety arguments — a genuine, more substantial departure covered when that article arrives.
Takeaways
- Running fully independent single-decree Paxos per log index is correct but expensive — two round-trips (Phase 1 + Phase 2) per entry.
- Multi-Paxos's optimization: one Phase 1 can "reserve" a proposal number across all future log indices at once, letting a stable leader append new entries with just Phase 2 — a single round-trip — for as long as it remains leader.
- This makes leader election (article 4.2) a first-class, built-in part of the protocol rather than a separate mechanism — the leader is whichever proposer's Phase 1 reservation is currently valid.
- A leadership change requires paying Phase 1's cost again once, to safely discover any values a prior leader might have already gotten accepted — directly mirroring article 3.2's log-repair discussion.
- Out-of-order acceptance can create log gaps, safely filled with no-op entries once a new leader's Phase 1 confirms nothing was actually chosen there.
- This "elect once, append cheaply many times" structure is identical in shape to Raft's design (5.5-5.6, next) — Multi-Paxos and Raft solve the practical replicated-log problem the same way, differing mainly in presentation and some mechanism details.
References & further reading
- Lamport — Paxos Made Simple (2001) — Section 3 covers the Multi-Paxos extension directly.
- Chandra, Griesemer & Redstone — Paxos Made Live: An Engineering Perspective (2007) — Google's Chubby team on the real-world engineering gap between the algorithm and a production Multi-Paxos system.
- cvam.sight — Consensus 5.2: Single-Decree Paxos — the per-index safety proof Multi-Paxos relies on unchanged.
- cvam.sight — Consensus 4.3: Atomic Broadcast — the equivalence this article's "correct but expensive" framing depends on.