Multi-Paxos and Leader-Based Optimization

By the end of this lesson, you will be able to...

• Explain why a replicated log needs many Paxos decisions rather than one.

• Trace how a new Multi-Paxos leader recovers accepted evidence before using the fast path.

• Identify why stable leadership improves latency without turning leadership into a safety proof.

Idea in one sentence: Multi-Paxos pays the expensive prepare phase when leadership changes, then uses the resulting promises to choose new log slots with only the accept phase while that leadership remains stable.

Core Insight

A metadata service must record an ordered stream of commands: create a namespace, move a shard, revoke a lease. A single-decree Paxos instance can choose one command safely. The service needs the same protection for slot 41, then 42, then 43—and it needs replicas to apply those slots in the same order.

The obvious construction is safe: run full Paxos independently for every slot. For each command, a proposer sends prepare, collects promises and accepted history, then sends accept. The problem is that a healthy leader would repeat the same leadership contest before every append, even though the same majority has already promised to reject lower ballots.

Multi-Paxos does not remove the hard part. It moves it off the healthy hot path. A leader first runs Phase 1 with a ballot for a collection of log instances, discovers any values that old attempts already accepted, and repairs those slots. For slots with no inherited value, it can then issue new commands directly in Phase 2 under that ballot.

The key correction is subtle: “the leader can append freely” is true only for slots whose Phase 1 evidence leaves their value unconstrained. Leadership is an efficiently reused safety context, not permission to rewrite a log.

The Situation: One Choice Becomes an Ordered History

Use five acceptors, A1 through A5. Any three form a quorum. The service treats each log position as a separate single-decree Paxos instance:

slot 41 -> one chosen command
slot 42 -> one chosen command
slot 43 -> one chosen command

The log order matters. Suppose 41 creates /teams/search, 42 assigns its owner, and 43 grants a worker a lease. Applying 43 before a missing 42 can give replicas different state transitions, even if every individual slot is chosen safely. The primary goal here is still one value per slot; deterministic ordered application comes later in the track.

The teaching example holds membership fixed. Reconfiguration changes which sets intersect and deserves its own later lesson.

The Initial Model: Prepare Every Slot Forever

We might first use the single-decree recipe for each append:

slot 41: prepare -> majority promises -> accept -> majority accepts
slot 42: prepare -> majority promises -> accept -> majority accepts
slot 43: prepare -> majority promises -> accept -> majority accepts

This works. It is also wasteful in a stable period. If L already prepared ballot 17 with a quorum, those acceptors have promised not to accept lower ballots. Starting a fresh prepare for every empty next slot repeats coordination work instead of using the established ballot.

The tempting optimization is too aggressive: “Once L is leader, it can put any command in every slot.” That breaks whenever a prior leader accepted a value in a slot before failing. A value need not have been learned by every replica—or even chosen—to constrain the new leader's Phase 2 proposal.

The stronger model is: establish a higher ballot, recover the accepted evidence for each relevant slot, and only then use that ballot's Phase 2 path for new unconstrained slots.

The Mechanism: A Ballot Spans Many Slots

Plain meaning: Establish one safe leadership attempt, inspect the old work it may need to finish, then avoid repeating that establishment for each new command.

In this scenario: L prepares ballot 17 with a majority. The acceptors promise ballot 17 and report any accepted proposal they hold for the log slots under consideration. For a slot with an accepted value in the replies, L must carry that value forward. For an empty slot, L may select the next client command.

Technical name: This is Multi-Paxos: many Paxos instances share a stable leader and ballot context. Its ordinary fast path is Phase 2 for new slots; Phase 1 returns when leadership changes or the ballot loses authority.

1. A new leader prepares and recovers history

After a leader failure or a competing higher ballot, L chooses a ballot above those it knows and contacts a quorum:

L -> A2, A3, A4: prepare(17, slots 42 and onward)

The exact wire format varies by implementation. The safety job does not: a successful Phase 1 response means the acceptor promises not to accept lower ballots and reports prior accepted evidence for the relevant instances. Lamport's state-machine description shows one proposal number used across many instances; acceptors need detailed replies only where an earlier Phase 2 message exists.

For each slot, L now applies the same selection rule from the previous lesson:

highest accepted value reported for this slot
  -> carry that value forward

no accepted value reported by the preparing quorum for this slot
  -> choose a new client command for that slot

This rule is per slot. Finding an accepted command at slot 42 does not force that command into slot 43; it constrains only its own Paxos instance.

2. The leader uses Phase 2 for the recovered and new slots

Once L has established ballot 17, it sends accepts under that same ballot:

L -> quorum: accept(17, slot 42, recovered value)
L -> quorum: accept(17, slot 43, new client command)

Each slot becomes chosen only when a majority accepts the same proposal for that slot. The leader can often pipeline several Phase 2 requests; it need not wait for slot 42 to be learned before sending a proposal for slot 43. But replicas must not pretend that an out-of-order learned suffix is an already applicable history. A gap still matters to application.

3. The fast path lasts only while the ballot does

If the leader can continue communicating with a majority and no higher ballot preempts it, later slots can use only the Phase 2 exchange:

client command -> L assigns next free slot -> accept(17, slot, command) -> majority acceptance

That is the latency win. It is not a weaker quorum rule; every chosen slot still has majority acceptance. The removed work is the repeated preparation, not the evidence that makes a value chosen.

Worked Trace: Recover One Slot, Then Append Two More

The following state and timing are illustrative. The previous leader failed while slot 41 was known chosen, 42 had an accepted but not yet chosen command, and 43 was empty.

slot 41: create /teams/search             chosen already
slot 42: set owner = node-6               accepted by A2 and A3 only
slot 43: no accepted value

A2 and A3 alone are not a majority of five, so slot 42 is not chosen. Still, a new leader cannot replace it casually: its accepted evidence must be carried forward if it appears in the Phase 1 quorum.

Starting state

Step 1: L establishes ballot 17

L prepares A2,A3,A4, a majority. They persist a promise not to accept lower ballots and return their accepted state. For slot 42, L sees set owner = node-6 from A2 and A3. For slot 43, nobody reports an accepted value.

Why is one accepting report enough to constrain L? The leader does not need to prove that slot 42 was previously chosen. It needs to preserve values that its preparing quorum says may be safety-relevant. That conservative rule is what makes later leadership compatible with any hidden majority evidence.

Step 2: the leader completes the recovered slot

L sends accept(17, slot 42, set owner = node-6) to A2,A3,A4. All three accept. Slot 42 is now chosen by a majority, even though the leader did not choose its content from a new client request.

recovery result:
  slot 41 = create /teams/search          chosen
  slot 42 = set owner = node-6            chosen

Step 3: the same ballot drives the steady path

For slots 43 and 44, Phase 1 found no accepted values. L may assign the two new client commands and send Phase 2 requests under ballot 17:

accept(17, slot 43, grant lease to worker-12)
accept(17, slot 44, set quota = 20)

If a majority accepts each request, both slots are chosen. The leader did not re-run prepare for each one because ballot 17 already establishes the relevant promise context. A learner can now apply the contiguous sequence 41 through 44.

So far: Multi-Paxos earns its fast path by doing the recovery work once per leadership period. The leader first preserves old accepted evidence; only empty slots become places for new commands.

When the Fast Path Ends

Suppose another proposer successfully prepares ballot 18 with a quorum. The 17 promises no longer guarantee that L can obtain accepts. An accept(17, ...) request reaching an acceptor that promised 18 is rejected or ignored. L must stop treating its ballot as active authority.

That is not a safety failure. It is the protocol exposing its boundary: a leader may continue the fast path only while it has a ballot that a reachable quorum will honor. The new proposer must repeat the recovery step before it can safely move the log forward.

The same boundary appears operationally when a leader process pauses, a network partition splits communication, disks make replication slow, or timeout policy starts multiple candidates. Useful signals include rising prepare counts, higher-ballot rejections, leader changes, and time spent waiting for quorum acknowledgments. These are progress and performance signals, not evidence that two values were chosen for a slot.

Trade-offs and Limits

The trade-off is clear. Multi-Paxos improves steady-state append latency and throughput by amortizing Phase 1 across many slots. It costs more recovery logic: a new leader must locate accepted values, fill or preserve gaps safely, and make its ballot durable before it relies on it. It also makes leader stability materially important to performance.

This is a good fit when a replicated service has a mostly stable leader and an ordered write stream. It becomes risky when leader churn is frequent enough that the system spends most of its time in preparation rather than Phase 2. No choice of timeout turns a slow node into a definitely failed node; timeouts help pick a new attempt for progress, while the Paxos evidence rules protect safety.

Multi-Paxos does not by itself define every product-level choice: client acknowledgement semantics, deterministic application, membership changes, snapshots, and read consistency still need separate rules. It only gives the log's repeated agreement mechanism a usable common case.

Common Confusions

Confusion: “Multi-Paxos eliminates Phase 1.”

Why it is tempting: The normal append trace can show only accepts and acknowledgements.

Better model: Phase 1 is amortized, not deleted. It is needed after a leader change or when a higher ballot preempts the old leader.

Confusion: “A stable leader can choose any value in every slot.”

Why it is tempting: The leader owns the normal append path.

Better model: It may choose a new value only for a slot whose prepare evidence is empty. A reported accepted value for that slot must be carried forward.

Confusion: “A chosen slot is immediately safe to apply anywhere.”

Why it is tempting: The slot has majority evidence.

Better model: A replica needs the chosen commands in log order to apply a deterministic state machine safely. Later slots can be learned before an earlier gap is repaired.

Check Your Understanding

Check: During Phase 1 at ballot 30, a new leader learns that slot 52 has accepted value X, while slots 53 and 54 have no accepted values in the quorum replies. Which values may it send in Phase 2?

Think first, then reveal.

Answer: It must send X for slot 52. It may choose new client commands for 53 and 54. The restriction is per slot, not a rule that makes every later slot repeat X.

Check: A leader at ballot 30 receives a rejection that reports ballot 31. Can it safely keep treating Phase 2 at ballot 30 as its fast path?

Think first, then reveal.

Answer: No. The higher ballot is evidence that some acceptor has promised a newer attempt. The old leader must stop relying on ballot 30; a proposer at the newer ballot must recover the relevant accepted history before continuing.

Practice: Trace a Short Leader Change

Five acceptors use quorums of three. Old leader L1 accepted remove node-9 for slot 80 at A1,A2, then failed. New leader L2 prepares ballot 41 with A2,A3,A4. Its replies show remove node-9 at A2 for slot 80, no accepted value for slot 81, and no accepted value for slot 82.

What Phase 2 proposals should L2 send if the next two client commands are create /ops and set quota = 50? Explain what must happen before replicas apply slot 81.

Model answer: L2 must first propose remove node-9 at slot 80, because the Phase 1 quorum reported that accepted value. It may propose create /ops at 81 and set quota = 50 at 82, all under ballot 41. Each slot still needs majority acceptance. Replicas apply slot 81 only after the contiguous prefix includes a chosen slot 80; a later chosen slot does not skip a missing earlier decision.

Connections

The previous lesson provided the single-decree rule: a later ballot learns accepted history from an overlapping quorum and carries it forward. Multi-Paxos repeats that rule per log slot, then amortizes Phase 1 during stable leadership.

The next lesson, Raft, makes the leader-shaped control path explicit through terms, elections, and roles. It is not “Paxos with better safety”; it is another crash-fault consensus design organized to make leader authority easier to inspect.

Resources

• [PAPER] Paxos Made Simple — Focus: read the state-machine implementation and its recovery of accepted log instances before the Phase 2 steady path.
• [PAPER] Paxos Made Moderately Complex — Focus: inspect an implementation-oriented vocabulary for ballots, slots, and leader recovery.
• [PAPER] In Search of an Understandable Consensus Algorithm — Focus: compare Multi-Paxos's leader-shaped steady state with Raft's explicit leadership design.

Key Takeaways

• A replicated log is many Paxos decisions, one protected value per slot, plus ordered application.
• Multi-Paxos first uses Phase 1 to establish a ballot and recover accepted slot values; it then uses Phase 2 for new unconstrained slots.
• The fast path preserves the same quorum safety requirement as single-decree Paxos; it only avoids repeated preparation while leadership is stable.
• A higher ballot, an unreachable majority, or leader churn ends the fast path without permitting conflicting chosen values.
• The cost of better steady-state latency is recovery complexity and dependence on stable leadership for progress.