Multi-Paxos & leader election

Same 3 acceptors as before, but now deciding 5 log slots in a row. Plain Paxos pays for prepare/promise every time; Multi-Paxos, with a stable leader, only pays once.

Once a leader has run Phase 1 (prepare/promise) successfully and no other proposer has interfered, every acceptor has already promised to accept that leader's numbers. The leader can skip straight to Phase 2 (accept/accepted) for every subsequent decision — right up until something disrupts its leadership.

Counting message-hops per round trip (prepare, promise, accept, accepted = 4 for a full round; accept, accepted = 2 for an accept-only round):

• $k$ — the number of log slots (decisions) being made.
• $M_{\text{plain}}(k)$ — total messages if every decision re-runs both phases.
• $M_{\text{multi}}(k)$ — total messages with one stable leader skipping Phase 1 after the first decision.

1. Only the first decision pays full price

   Decision 1 still needs a full round (4 messages) to establish the leader's numbers are trusted.

2. Every decision after that is cheaper

   Decisions 2 through $k$ only need the accept/accepted round trip — 2 messages each.

Slide $k$ up. The gap between the two bars is the savings — it grows by 2 messages for every extra decision, because Multi-Paxos never repeats the prepare phase as long as the leader stays the same.

$k = 5$ decisions, one stable leader throughout:

1. Plain Paxos

   $M_{\text{plain}}(5) = 4 \times 5 = 20 \text{ messages}$

2. Multi-Paxos

   $M_{\text{multi}}(5) = 4 + 2(5-1) = 4 + 8 = 12 \text{ messages}$

3. Savings

   $20 - 12 = 8 \text{ messages saved}$