Paxos

Paxos is a family of consensus algorithms designed to allow a collection of unreliable processes to agree on a single value, even in the presence of failures and message delays. Developed by Leslie Lamport, the original Paxos protocol was described in 1998 as a solution to reaching agreement in asynchronous networks. The core guarantee is safety: no two different values can be chosen for the same consensus instance, so long as a majority of participants cooperate.

In typical descriptions, participants assume three roles: proposers, acceptors, and learners. A basic Paxos run proceeds in two phases. In the prepare phase, a proposer sends a prepare request with a proposal number N to a majority of acceptors. Each acceptor promises not to accept proposals with numbers less than N and may return the highest-numbered proposal it has already accepted. If the proposer receives promises from a majority, it proceeds to the accept phase.

During the accept phase, the proposer sends an accept request containing N and a value V. An acceptor accepts the request unless it has already promised a higher-numbered proposal. If a majority of acceptors accepts the value, the value is chosen and can be learned by all learners. Once chosen, future proposals must adopt the chosen value. Paxos typically models a single instance of consensus per slot or sequence, with multiple independent instances used to agree on a sequence of values.

Paxos is robust to crashes but its liveness depends on network conditions and leadership behavior. Variants such as Multi-Paxos optimize by electing a stable leader to reduce repeated prepare phases, while other variants aim to reduce message rounds under specific conditions. Paxos has influenced many distributed systems and coordination services, including implementations used in large-scale databases and cloud platforms.