In computer science, Paxos is a family of protocols for solving consensus in a network of unreliable or fallible processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communications may experience failures.
Consensus protocols are the basis for the state machine replication approach to distributed computing, as suggested by Leslie Lamport and surveyed by Fred Schneider. State machine replication is a technique for converting an algorithm into a fault-tolerant, distributed implementation. Ad-hoc techniques may leave important cases of failures unresolved. The principled approach proposed by Lamport et al. ensures all cases are handled safely.
The Paxos protocol was first submitted in 1989 and named after a fictional legislative consensus system used on the Paxos island in Greece, where Lamport wrote that the parliament had to function "even though legislators continually wandered in and out of the parliamentary Chamber". It was later published as a journal article in 1998.
The Paxos family of protocols includes a spectrum of trade-offs between the number of processors, number of message delays before learning the agreed value, the activity level of individual participants, number of messages sent, and types of failures. Although no deterministic fault-tolerant consensus protocol can guarantee progress in an asynchronous network (a result proved in a paper by Fischer, Lynch and Paterson), Paxos guarantees safety (consistency), and the conditions that could prevent it from making progress are difficult to provoke.
Paxos is usually used where durability is required (for example, to replicate a file or a database), in which the amount of durable state could be large. The protocol attempts to make progress even during periods when some bounded number of replicas are unresponsive. There is also a mechanism to drop a permanently failed replica or to add a new replica.
History In 1988, Lynch, Dwork and Stockmeyer had demonstrated the solvability of consensus in a broad family of "partially synchronous" systems. Paxos has similarities to a protocol used for agreement in "viewstamped replication", first published by Oki and Liskov in 1988, in the context of distributed transactions. Paxos offered an elegant formalism and included one of the earliest proofs of safety for a fault-tolerant distributed consensus protocol.
Reconfigurable state machines have ties to prior work on reliable group multicast protocols that support dynamic group membership e.g. Birman's work in 1985 and 1987 on the virtually synchronous gbcast protocol. gbcast is uncommon in supporting durability and addressing partitioning failures. Most reliable multicast protocols do not have these properties which are required for implementations of the state machine replication model. This point is discussed in a paper by Lamport, Malkhi and Zhou.
Paxos protocols are members of a theoretical class of solutions to a problem formalized as uniform agreement with crash failures. Lower bounds for this problem have been proved by Keidar and Shraer. Derecho, a C++ software library for cloud-scale state machine replication, offers a Paxos protocol that has been integrated with self-managed virtually synchronous membership. This protocol matches the Keidar and Shraer optimality bounds and maps efficiently to modern remote DMA (RDMA) datacenter hardware. It uses TCP if RDMA is not available.
Assumptions
In order to simplify the presentation of Paxos, the following assumptions and definitions are made explicit. Techniques to broaden the applicability are known in the literature, and are not covered in this article.
Processors
Processors operate at arbitrary speed. Processors may experience failures. Processors with stable storage may re-join the protocol after failures (following a crash-recovery failure model). Processors do not collude, lie, or otherwise attempt to subvert the protocol. (That is, Byzantine failures don't occur. See Byzantine Paxos for a solution that tolerates failures that arise from arbitrary/malicious behavior of the processes.)
Network
Processors can send messages to any other processor. Messages are sent asynchronously and may take arbitrarily long to deliver. Messages may be lost, reordered, or duplicated. Messages are delivered without corruption. (That is, Byzantine failures don't occur. See Byzantine Paxos for a solution that tolerates corrupted messages that arise from arbitrary/malicious behavior of the messaging channels.)
Number of processors
In general, a consensus algorithm can make progress using processors, despite the simultaneous failure of any processors: in other words, the number of non-faulty processes must be strictly greater than the number of faulty processes. However, using reconfiguration, a protocol may be employed which survives any number of total failures as long as no more than fail simultaneously. For Paxos protocols, these reconfigurations can be handled as separate configurations.
Safety and liveness properties
In order to guarantee safety (also called "consistency"), Paxos defines three properties and ensures the first two are always held, regardless of the pattern of failures: Validity (or non-triviality) Only proposed values can be chosen and learned. Agreement (or consistency, or safety) No two distinct learners can learn different values (or there can't be more than one decided value). Termination (or liveness) If value C has been proposed, then eventually learner L will learn some value (if sufficient processors remain non-faulty).
Note that Paxos is not guaranteed to terminate, and thus does not have the liveness property. This is supported by the Fischer Lynch Paterson impossibility result (FLP) which states that a consistency protocol can only have two of safety, liveness, and fault tolerance. As Paxos's point is to ensure fault tolerance and it guarantees safety, it cannot also guarantee liveness.
Typical deployment
In most deployments of Paxos, each participating process acts in three roles: Proposer, Acceptor and Learner. This reduces the message complexity significantly, without sacrificing correctness:
By merging roles, the protocol "collapses" into an efficient client-master-replica style deployment, typical of the database community. The benefit of the Paxos protocols (including implementations with merged roles) is the guarantee of its safety properties.
A typical implementation's message flow is covered in the section Multi-Paxos.
Basic Paxos
This protocol is the most basic of the Paxos family. Each "instance" (or "execution") of the basic Paxos protocol decides on a single output value. The protocol proceeds over several rounds. A successful round has 2 phases: phase 1 (which is divided into parts a and b) and phase 2 (also divided into parts a and b). See below the description of the phases. Remember that we assume an asynchronous model, so e.g. a processor may be in one phase while another processor may be in another.
Phase 1
Phase 1a: Prepare
A Proposer creates a message, which we call a Prepare. The message is identified with a unique number, n, which must be greater than any number previously used in a Prepare message by this Proposer. Note that n is not the value to be proposed; it is simply a unique identifier of this initial message by the Proposer. In fact, the Prepare message needn't contain the proposed value (often denoted by v).
The Proposer chooses at least a Quorum of Acceptors and sends the Prepare message containing n to them. A Proposer should not initiate Paxos if it cannot communicate with enough Acceptors to constitute a Quorum.
Phase 1b: Promise
The Acceptors wait for a Prepare message from any of the Proposers. When an Acceptor receives a Prepare message, the Acceptor must examine the identifier number, n, of that message. There are two cases:
If n is higher than every previous proposal number received by the Acceptor (from any Proposer), then the Acceptor must return a message (called a Promise) to the Proposer, indicating that the Acceptor will ignore all future proposals numbered less than or equal to n. The Promise must include the highest number among the Proposals that the Acceptor previously accepted, along with the corresponding accepted value. The first Prepare message vacuously satisfies this condition. If n is less than or equal to any previous proposal number received by the Acceptor, the Acceptor needn't respond and can ignore the proposal. However, for the sake of optimization, sending a denial, or negative acknowledgement (NAK), response would tell the Proposer that it can stop its attempt to create consensus with proposal n.
Phase 2
Phase 2a: Accept
If a Proposer receives Promises from a Quorum of Acceptors, it needs to set a value v to its proposal. If any Acceptors had previously accepted any proposal, then they'll have sent their values to the Proposer, who now must set the value of its proposal, v, to the value associated with the highest proposal number reported by the Acceptors, let's call it z. If none of the Acceptors had accepted a proposal up to this point, then the Proposer may choose the value it originally wanted to propose, say x.
The Proposer sends an Accept message, (n, v), to a Quorum of Acceptors with the chosen value for its proposal, v, and the proposal number n (which is the same as the number contained in the Prepare message previously sent to the Acceptors). So, the Accept message is either (n, v=z) or, in case none of the Acceptors previously accepted a value, (n, v=x).
This Accept message should be interpreted as a "request", as in "Accept this proposal, please!".
Phase 2b: Accepted
If an Acceptor receives an Accept message, (n, v), from a Proposer, it must accept it if and only if it has not already promised (in Phase 1b of the Paxos protocol) to only consider proposals having an identifier greater than n.
If the Acceptor has not already promised (in Phase 1b) to only consider proposals having an identifier greater than n, it should register the value v (of the just received Accept message) as the accepted value (of the Protocol), and send an Accepted message to the Proposer and every Learner (which can typically be the Proposers themselves). Learners will learn the decided value only after receiving Accepted messages from a majority of acceptors, i.e. not after receiving just the first Accept message.
Else, it can ignore the Accept message or request.
Note that consensus is achieved when a majority of Acceptors accept the same identifier number (rather than the same value). Because each identifier is unique to a Proposer and only one value may be proposed per identifier, all Acceptors that accept the same identifier thereby accept the same value. These facts result in a few counter-intuitive scenarios that do not impact correctness: Acceptors can accept multiple values, a value may achieve a majority across Acceptors (with different identifiers) only to later be changed, and Acceptors may continue to accept proposals after an identifier has achieved a majority. However, the Paxos protocol guarantees that consensus is permanent and the chosen value is immutable.
When rounds fail
Rounds fail when multiple Proposers send conflicting Prepare messages, or when the Proposer does not receive a Quorum of responses (Promise or Accepted). In these cases, another round must be started with a higher proposal number.
Paxos can be used to select a leader