Multi-Paxos and the Paxos Family

From one value to a log

Running Basic Paxos independently for every log slot would cost two round trips per command. Multi-Paxos observes that phase 1 does not depend on the value, so a stable leader can run phase 1 once for all future slots with a single high ballot. After that, each new command needs only phase 2: one round trip to a majority. If the leader fails, another node runs phase 1 with a higher ballot, learns any values already accepted in unfinished slots, and fills holes (often with no-op entries) before serving new requests. Lamport's papers left many engineering details open (leader election, membership changes, log compaction), which is why implementations differ and why Paxos earned its reputation as hard to implement. Well-known relatives include Fast Paxos (fewer message delays when there is no conflict), EPaxos (leaderless, commutative commands) and Flexible Paxos, which shows phase-1 and phase-2 quorums only need to intersect each other, not all be majorities.

Paxos vs Raft in one breath

Raft is closely related to Multi-Paxos with a strong leader, but it fixes the design choices Paxos leaves open: logs have no holes, only up-to-date nodes can become leader, and entries flow only from leader to followers. That specificity is why it is easier to teach and to implement correctly.

A standing chairperson

A committee could re-elect a chair before each agenda item (Basic Paxos per slot), or elect one chair for the whole meeting who then simply calls each vote (Multi-Paxos). Only when the chair leaves does the committee run a fresh election.

Quick check: What does a stable Multi-Paxos leader skip for each new log entry?

• Phase 2 (accept)
• Writing entries to disk
• Phase 1 (prepare/promise)
• Waiting for a majority of acceptors