Topic: This implementation runs independent Paxos per slot; compare with a Multi-Paxos leader-lease optimization that skips Phase 1 for a stable leader

Date: 2026-05-29

Time: 14:23

Independent Paxos Per Slot vs. Multi-Paxos Leader Lease

What This Implementation Does

The Total Order Broadcast in total-order-broadcast/totalorderbroadcast.py runs a fresh single-decree Paxos instance for every slot in the log. Each ConsensusInstance (line 4) is standalone: it tracks its own promised ballot, acceptedproposal, and acceptedvalue with no awareness of any other slot.

When a node wants to broadcast a message, startproposal (line 167) always begins at Phase 1 (Prepare). It creates a new proposal number, initializes a fresh promises dict, and sends prepare messages to every node — including itself:


# line 167-191
def _start_proposal(self, slot, value, outgoing):
    prop_num = self._make_proposal_number(0)  # always starts at round 0
    self._proposals[slot] = {
        'round': 0,
        'phase': 'prepare',     # <-- always begins here
        ...
    }
    for nid in self.all_ids:
        outgoing.append({'type': 'prepare', ...})

This means every single slot pays the full two-round-trip cost: Prepare → Promise → Accept → Accepted. For N messages, that's 2N round trips of consensus protocol messages.

What Multi-Paxos With Leader Lease Would Do Differently

In Multi-Paxos, a stable leader runs Phase 1 once and then reuses the resulting ballot number across all subsequent slots. The optimization works like this:

1. A leader is elected (via Phase 1 or a separate election mechanism) and receives promises from a majority for some ballot b.

2. For every new slot, the leader skips directly to Phase 2 (Accept) using ballot b. Acceptors already promised not to accept anything below b, so the Accept is safe without re-preparing.

3. A lease timer prevents other nodes from starting competing Phase 1 rounds while the leader is alive, avoiding unnecessary ballot conflicts.

The cost drops from 2 round trips per slot to 1 round trip per slot in the steady state — a 50% reduction in latency.

Where You Can See the Cost in This Code

Look at findproposalslot (line 155) and tick (line 119). Every pending message triggers startproposal, which unconditionally enters the 'prepare' phase. There is no concept of "I already hold promises from a majority, so I can skip ahead." The proposals dict (line 82) tracks per-slot state, but nothing carries over between slots.

The proposal number construction at line 107 also reveals the per-slot independence:


def _make_proposal_number(self, round_num):
    return round_num * self.num_nodes + self.node_id

Each slot starts at round_num=0. A Multi-Paxos leader would instead use a single monotonically increasing ballot that persists across slots.

Contrast With the Raft Implementation in This Repo

The Raft implementation in raft-consensus/raft.py is essentially Multi-Paxos with leader lease under a different name. Once a node becomes leader (becomeleader, line 87), it never re-runs an election for each log entry. It simply appends entries to its log (client_request, line 148) and replicates them via AppendEntries — which is Phase 2 only. The election timeout / heartbeat mechanism (lines 42-46, 161-163) acts as the lease: followers won't start a new election as long as they receive heartbeats.

| Aspect | This TOB (per-slot Paxos) | Multi-Paxos / Raft |

|---|---|---|

| Phase 1 frequency | Every slot | Once per leader term |

| Steady-state round trips | 2 per slot | 1 per slot |

| Leader concept | None — any node proposes | Explicit stable leader |

| Conflict handling | Competing proposals bump rounds | Leader monopolizes appends |

| Implementation complexity | Lower | Higher (lease management, leader failover) |

Why Per-Slot Paxos Still Matters

The per-slot approach is simpler and correct by construction — each slot is an isolated consensus problem. It's a clearer teaching tool because it shows the full Paxos protocol for every decision. Multi-Paxos is a performance optimization that introduces coupling between slots (the leader's ballot spans all of them), which complicates reasoning about leader failure, ballot recovery, and exactly when a new leader must re-run Phase 1 for in-flight slots.

Topics to Explore

Beliefs