MultiPaxos

Multi-Paxos is a family of consensus protocols designed to enable replicated state machines to agree on a sequence of values, i.e., a log, rather than a single value. It extends the Paxos protocol by optimizing for multiple consecutive decisions, typically by presenting a stable leader that can drive many consensus instances with reduced overhead. The core goal remains safety: the system never decides conflicting values, and once a value is chosen for a log slot, it remains fixed.

In Multi-Paxos, common roles are proposer, acceptor, and learner. During an initial leader election, a proposer uses a prepare/promise exchange (phase 1) and an accept phase (phase 2) to secure a ballot number. Once a leader has established authority, it can propose values for successive slots using the same ballot without repeating phase 1, a technique known as locking in a leader. Each decision is tied to a slot in a log; previously decided slots cannot be altered.

Safety in Multi-Paxos hinges on majority quorums: a value chosen for a slot must have been accepted by a majority of acceptors. If a new leader is elected, it may need to perform a phase 1 to learn the current log state and ensure it preserves previously chosen values. Progress requires a majority of acceptors to be functioning and reachable.

Typical deployments assume asynchronous networks with possible crashes; Multi-Paxos tolerates up to f failures with N = 2f+1 acceptors. Optimizations include batching and pipelining to increase throughput, while maintaining safety guarantees. The protocol is widely used for replicated state machines in distributed systems and forms the basis for many consensus implementations, often tailored to specific performance and failure model requirements.