Paxos Made Moderately Complex
đź“ś Abstract
For anybody who has ever tried to implement it, Paxos is by no means a simple protocol, even though it is based on relatively simple invariants. This paper provides imperative pseudo-code for the full Paxos (or Multi-Paxos) protocol without shying away from discussing various implementation details. The initial description avoids optimizations that complicate comprehension. Next we discuss liveness, and list various optimizations that make the protocol practical.
✨ Summary
Summary
The paper presents an operational description of Multi-Paxos for replicated state machines in an asynchronous message-passing environment with crash failures. It decomposes the protocol into replicas, leaders, scouts, commanders, and acceptors, and explains their behavior with imperative pseudocode.
Replicas assign client commands to numbered log slots and execute commands only after a decision has been learned for the corresponding slot. The safety argument is organized around invariants: a slot cannot have two different decided commands; replicas execute decided commands in slot order; replicas’ application states therefore remain equivalent; and replica progress does not move backward.
Acceptors provide durable logical memory for consensus. Ballot numbers impose an ordering on competing attempts, while majority intersection prevents a later ballot from selecting a value inconsistent with an earlier chosen value. Leaders use scouts to establish a ballot and recover previously accepted proposals, then use commanders to obtain acceptance for proposals. The central inductive argument is that leaders must preserve previously chosen values when moving to higher ballots; this ensures that no slot receives conflicting decisions.
The paper distinguishes safety from liveness. Safety can hold despite failures and indefinitely delayed messages, but unrestricted asynchrony permits competing leaders to repeatedly preempt one another. Progress therefore requires additional practical assumptions, such as bounded clock drift and eventual message-delay bounds, together with failure detection or adaptive timeouts that allow one leader to remain effective long enough to complete decisions.
The initial presentation is intentionally impractical. The paper then discusses reducing acceptor state and phase-one messages, garbage collection, co-locating protocol roles, optimizing read-only commands, using leases, persisting state, and recovering from failures. These techniques connect the abstract protocol to implementable replicated services.
Influence and Subsequent Use
The manuscript’s role-oriented pseudocode and invariant-based explanation have been used as teaching and implementation material. The DSLabs distributed-systems laboratory explicitly recommends the paper when teaching Paxos-based state-machine replication, and subsequent student and open-source projects report implementing Multi-Paxos by following its architecture and protocol roles. (ellismichael.com)
A later research paper, Moderately Complex Paxos Made Simple, directly builds on the protocol variant described here. It develops higher-level executable specifications for Multi-Paxos, reconfiguration, preemption, state reduction, and failure detection, and uses TLA+ to machine-check safety properties. (arxiv.org)
The expanded journal version appeared in ACM Computing Surveys in 2015, with Robbert van Renesse and Deniz Altinbuken as authors. It formalized a reconfigurable Multi-Paxos presentation and supplied additional variants and implementation guidance. (doi.org)