View source for Paxos (computer science)

{{Short description|Family of protocols for solving consensus}}
'''Paxos''' is a family of protocols for solving [[Consensus (computer science)|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.<ref name="agree"/>

Consensus protocols are the basis for the [[State machine replication|state machine replication]] approach to [[Distributed computing|distributed computing]], as suggested by [[Biography:Leslie Lamport|Leslie Lamport]]<ref name="clocks"/> and surveyed by [[Biography:Fred B. Schneider|Fred Schneider]].<ref name="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".<ref name="Lamport"/> It was later published as a journal article in 1998.<ref name="paxos"/>

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 [[Consensus (computer science)#The FLP impossibility result for asynchronous deterministic consensus|result]] proved in a paper by [[Biography:Michael J. Fischer|Fischer]], [[Biography:Nancy Lynch|Lynch]] and [[Biography:Mike Paterson|Paterson]]<ref name="flp"/>), 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|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 ==
The topic predates the protocol. In 1988, [[Biography:Nancy Lynch|Lynch]], [[Biography:Cynthia Dwork|Dwork]] and [[Biography:Larry Stockmeyer|Stockmeyer]] had demonstrated <ref name="LDS88"/> the solvability of consensus in a broad family of "partially synchronous" systems.  Paxos has strong similarities to a protocol used for agreement in "viewstamped replication", first published by Oki and [[Biography:Barbara Liskov|Liskov]] in 1988, in the context of distributed transactions.<ref name="vr"/>  Notwithstanding this prior work, Paxos offered a particularly elegant formalism, and included one of the earliest proofs of safety for a fault-tolerant distributed consensus protocol.

Reconfigurable state machines have strong ties to prior work on reliable group multicast protocols that support dynamic group membership, for example Birman's work in 1985 and 1987 on the [[Virtual synchrony|virtually synchronous]] [[Gbcast|gbcast]]<ref name="BJ87"/> protocol. However, gbcast is unusual in supporting durability and addressing partitioning failures.
Most reliable multicast protocols lack these properties, which are required for implementations of the state machine replication model.
This point is elaborated in a paper by [[Biography:Leslie Lamport|Lamport]], [[Biography:Dahlia Malkhi|Malkhi]] and Zhou.<ref name="LMZ10"/>

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.<ref name=optimality/>  Derecho,<ref name=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 direct memory access|remote DMA (RDMA)]] datacenter hardware (but 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 fault tolerance|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 which 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 <math>n=2F+1</math> processors, despite the simultaneous failure of any <math>F</math> processors:<ref name="consensus"/> 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 F fail simultaneously. For Paxos protocols, these reconfigurations can be handled as separate ''configurations''.<ref>{{Cite journal|last1=Van Renesse|first1=Robbert|last2=Altinbuken|first2=Deniz|date=2015-02-17|title=Paxos Made Moderately Complex|url=https://doi.org/10.1145/2673577|journal=ACM Computing Surveys|volume=47|issue=3|pages=42:1–42:36|doi=10.1145/2673577|issn=0360-0300}}</ref>

== 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.<ref name=fast/>
; Agreement (or ''consistency'', or ''safety''): No two distinct learners can learn different values (or there can't be more than one decided value)<ref name=fast/><ref name=general/>
; Termination (or liveness): If value C has been proposed, then eventually learner L will learn some value (if sufficient processors remain non-faulty).<ref name=general/>

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)<ref name=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.<ref name="live"/>  This reduces the message complexity significantly, without sacrificing correctness:

{{cquote|''In Paxos, clients send commands to a leader. During normal operation, the leader receives a client's command, assigns it a new command number <math>i</math>, and then begins the <math>i</math><sup>th</sup> instance of the consensus algorithm by sending messages to a set of acceptor processes.''<ref name=general/>}}

By merging roles, the protocol "collapses" into an efficient client-master-replica style deployment, typical of the database community.<ref name=techtalk/>  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 (which is 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", identified with a number ''n''. Note that ''n'' is not the value to be proposed and maybe agreed on, but just a number which uniquely identifies this initial message by the proposer (to be sent to the acceptors). The number ''n'' must be greater than any number used in any of the previous ''Prepare'' messages by this Proposer. Then, it sends the ''Prepare'' message containing ''n'' to at least a Quorum of Acceptors. Note that the ''Prepare'' message only contains the number ''n'' (that is, it does not have to contain e.g. the proposed value, often denoted by ''v''). The Proposer decides who is in the Quorum{{how|date=October 2018}}. A Proposer should not initiate Paxos if it cannot communicate with at least a Quorum of Acceptors.

==== Phase 1b: ''Promise'' ====

: Any of the ''Acceptors'' waits for a ''Prepare'' message from any of the ''Proposers''. If an Acceptor receives a Prepare message, the Acceptor must look at the identifier number ''n'' of the just received ''Prepare'' message. There are two cases.

::If ''n'' is higher than every previous proposal number received, from any of the Proposers, by the Acceptor, then the Acceptor must return a message, which we call a "Promise", to the Proposer, to ignore all future proposals having a number less than ''n''. If the Acceptor ''accepted'' a proposal at some point in the past, it must include the previous proposal number, say ''m'', and the corresponding accepted value, say ''w'', in its response to the Proposer.

:: Otherwise (that is, ''n'' is less than or equal to any previous proposal number received from any Proposer by the Acceptor) the Acceptor can ignore the received proposal. It does not have to answer in this case for Paxos to work. However, for the sake of optimization, sending a denial (''Nack'') 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''.<ref name="paxos-simple"/>

: 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|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, which means, 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: [[Paxos (computer science)#Basic Paxos where an Acceptor accepts Two Different Values|Acceptors can accept multiple values]], [[Paxos (computer science)#Basic Paxos where a multi-identifier majority is insufficient|a value may achieve a majority across Acceptors (with different identifiers) only to later be changed]], and [[Paxos (computer science)#Basic Paxos where new Proposers cannot change an existing consensus|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 ===

Notice that a Proposer in Paxos could propose "I am the leader," (or, for example, "Proposer X is the leader").<ref name="elas_Lead">{{Cite web |title=Leader Election, Why Should I Care? |author= |work=Elastic Blog |date= 13 September 2013|access-date=27 February 2021 |url= https://www.elastic.co/blog/found-leader-election-in-general}}</ref> Because of the agreement and validity guarantees of Paxos, if accepted by a Quorum, then the Proposer is now known to be the leader to all other nodes. This satisfies the needs of leader election<ref>I. Gupta, R. van Renesse, and K. P. Birman, 2000, A Probabilistically Correct Leader Election Protocol for Large Groups, ''Technical Report'' , Cornell University</ref> because there is a single node believing it is the leader and a single node known to be the leader at all times.

=== Graphic representation of the flow of messages in the basic Paxos ===

The following diagrams represent several cases/situations of the application of the Basic Paxos protocol. Some cases show how the Basic Paxos protocol copes with the failure of certain (redundant) components of the distributed system.

Note that the values returned in the ''Promise'' message are "null" the first time a proposal is made (since no Acceptor has accepted a value before in this round).

==== Basic Paxos without failures ====

In the diagram below, there is 1 Client, 1 Proposer, 3 Acceptors (i.e. the Quorum size is 3) and 2 Learners (represented by the 2 vertical lines). This diagram represents the case of a first round, which is successful (i.e. no process in the network fails).
[[File:Basic Paxos without failures.svg|none|frame]]
Here, V is the last of (Va, Vb, Vc).
==== Error cases in basic Paxos ====

The simplest error cases are the failure of an Acceptor (when a Quorum of Acceptors remains alive) and failure of a redundant Learner. In these cases, the protocol requires no "recovery" (i.e. it still succeeds): no additional rounds or messages are required, as shown below (in the next two diagrams/cases).

==== Basic Paxos when an Acceptor fails ====

In the following diagram, one of the Acceptors in the Quorum fails, so the Quorum size becomes 2. In this case, the Basic Paxos protocol still succeeds.

<pre>Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |          |  |  !       |  |  !! FAIL !!
   |         |<---------X--X          |  |  Promise(1,{Va, Vb, null})
   |         X--------->|->|          |  |  Accept!(1,V)
   |         |<---------X--X--------->|->|  Accepted(1,V)
   |<---------------------------------X--X  Response
   |         |          |  |          |  |
</pre>

==== Basic Paxos when a redundant learner fails ====

In the following case, one of the (redundant) Learners fails, but the Basic Paxos protocol still succeeds. 

<pre>Client Proposer         Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |<---------X--X--X       |  |  Promise(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(1,V)
   |         |<---------X--X--X------>|->|  Accepted(1,V)
   |         |          |  |  |       |  !  !! FAIL !!
   |<---------------------------------X     Response
   |         |          |  |  |       |
</pre>

==== Basic Paxos when a Proposer fails ====

In this case, a Proposer fails after proposing a value, but before the agreement is reached. Specifically, it fails in the middle of the Accept message, so only one Acceptor of the Quorum receives the value. Meanwhile, a new Leader (a Proposer) is elected (but this is not shown in detail). Note that there are 2 rounds in this case (rounds proceed vertically, from the top to the bottom).

<pre>Client  Proposer        Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(1)
   |      |<------------X--X--X       |  |  Promise(1,{Va, Vb, Vc})
   |      |             |  |  |       |  |
   |      |             |  |  |       |  |  !! Leader fails during broadcast !!
   |      X------------>|  |  |       |  |  Accept!(1,V)
   |      !             |  |  |       |  |
   |         |          |  |  |       |  |  !! NEW LEADER !!
   |         X--------->|->|->|       |  |  Prepare(2)
   |         |<---------X--X--X       |  |  Promise(2,{V, null, null})
   |         X--------->|->|->|       |  |  Accept!(2,V)
   |         |<---------X--X--X------>|->|  Accepted(2,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |
</pre>

==== Basic Paxos when multiple Proposers conflict ====

The most complex case is when multiple Proposers believe themselves to be Leaders.  For instance, the current leader may fail and later recover, but the other Proposers have already re-selected a new leader.  The recovered leader has not learned this yet and attempts to begin one round in conflict with the current leader. In the diagram below, 4 unsuccessful rounds are shown, but there could be more (as suggested at the bottom of the diagram).

<pre>Client   Proposer       Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(1)
   |      |<------------X--X--X       |  |  Promise(1,{null,null,null})
   |      !             |  |  |       |  |  !! LEADER FAILS
   |         |          |  |  |       |  |  !! NEW LEADER (knows last number was 1)
   |         X--------->|->|->|       |  |  Prepare(2)
   |         |<---------X--X--X       |  |  Promise(2,{null,null,null})
   |      |  |          |  |  |       |  |  !! OLD LEADER recovers
   |      |  |          |  |  |       |  |  !! OLD LEADER tries 2, denied
   |      X------------>|->|->|       |  |  Prepare(2)
   |      |<------------X--X--X       |  |  Nack(2)
   |      |  |          |  |  |       |  |  !! OLD LEADER tries 3
   |      X------------>|->|->|       |  |  Prepare(3)
   |      |<------------X--X--X       |  |  Promise(3,{null,null,null})
   |      |  |          |  |  |       |  |  !! NEW LEADER proposes, denied
   |      |  X--------->|->|->|       |  |  Accept!(2,Va)
   |      |  |<---------X--X--X       |  |  Nack(3)
   |      |  |          |  |  |       |  |  !! NEW LEADER tries 4
   |      |  X--------->|->|->|       |  |  Prepare(4)
   |      |  |<---------X--X--X       |  |  Promise(4,{null,null,null})
   |      |  |          |  |  |       |  |  !! OLD LEADER proposes, denied
   |      X------------>|->|->|       |  |  Accept!(3,Vb)
   |      |<------------X--X--X       |  |  Nack(4)
   |      |  |          |  |  |       |  |  ... and so on ...
</pre>

==== Basic Paxos where an Acceptor accepts Two Different Values ====
In the following case, one Proposer achieves acceptance of value V1 by one Acceptor before failing.  A new Proposer prepares the Acceptors that never accepted V1, allowing it to propose V2. Then V2 is accepted by all Acceptors, including the one that initially accepted V1. 

<pre>Proposer    Acceptor     Learner
 |  |       |  |  |       |  |
 X--------->|->|->|       |  |  Prepare(1)
 |<---------X--X--X       |  |  Promise(1,{null,null,null})
 x--------->|  |  |       |  |  Accept!(1,V1)
 |  |       X------------>|->|  Accepted(1,V1)
 !  |       |  |  |       |  |  !! FAIL !!
    |       |  |  |       |  |
    X--------->|->|       |  |  Prepare(2)
    |<---------X--X       |  |  Promise(2,{null,null})
    X------>|->|->|       |  |  Accept!(2,V2)
    |<------X--X--X------>|->|  Accepted(2,V2)
    |       |  |  |       |  |
</pre>

==== Basic Paxos where a multi-identifier majority is insufficient ====
In the following case, one Proposer achieves acceptance of value V1 of one Acceptor before failing.  A new Proposer prepares the Acceptors that never accepted V1, allowing it to propose V2. This Proposer is able to get one Acceptor to accept V2 before failing.  A new Proposer finds a majority that includes the Acceptor that has accepted V1, and must propose it. The Proposer manages to get two Acceptors to accept it before failing.  At this point, three Acceptors have accepted V1, but not for the same identifier.  Finally, a new Proposer prepares the majority that has not seen the largest accepted identifier.  The value associated with the largest identifier in that majority is V2, so it must propose it.  This Proposer then gets all Acceptors to accept V2, achieving consensus. 

<pre>  Proposer           Acceptor        Learner
 |  |  |  |       |  |  |  |  |       |  |
 X--------------->|->|->|->|->|       |  |  Prepare(1)
 |<---------------X--X--X--X--X       |  |  Promise(1,{null,null,null,null,null})
 x--------------->|  |  |  |  |       |  |  Accept!(1,V1)
 |  |  |  |       X------------------>|->|  Accepted(1,V1)
 !  |  |  |       |  |  |  |  |       |  |  !! FAIL !!
    |  |  |       |  |  |  |  |       |  |
    X--------------->|->|->|->|       |  |  Prepare(2)
    |<---------------X--X--X--X       |  |  Promise(2,{null,null,null,null})
    X--------------->|  |  |  |       |  |  Accept!(2,V2)
    |  |  |       |  X--------------->|->|  Accepted(2,V2)
    !  |  |       |  |  |  |  |       |  |  !! FAIL !!
       |  |       |  |  |  |  |       |  | 
       X--------->|---->|->|->|       |  |  Prepare(3)
       |<---------X-----X--X--X       |  |  Promise(3,{V1,null,null,null})
       X--------------->|->|  |       |  |  Accept!(3,V1)
       |  |       |  |  X--X--------->|->|  Accepted(3,V1)
       !  |       |  |  |  |  |       |  |  !! FAIL !!
          |       |  |  |  |  |       |  |
          X------>|->|------->|       |  |  Prepare(4)
          |<------X--X--|--|--X       |  |  Promise(4,{V1(1),V2(2),null})
          X------>|->|->|->|->|       |  |  Accept!(4,V2)
          |       X--X--X--X--X------>|->|  Accepted(4,V2)
</pre>

==== Basic Paxos where new Proposers cannot change an existing consensus ====
In the following case, one Proposer achieves acceptance of value V1 of two Acceptors before failing.  A new Proposer may start another round, but it is now impossible for that proposer to prepare a majority that doesn't include at least one Acceptor that has accepted V1.  As such, even though the Proposer doesn't see the existing consensus, the Proposer's only option is to propose the value already agreed upon.  New Proposers can continually increase the identifier to restart the process, but the consensus can never be changed. 

<pre>Proposer    Acceptor     Learner
 |  |       |  |  |       |  |
 X--------->|->|->|       |  |  Prepare(1)
 |<---------X--X--X       |  |  Promise(1,{null,null,null})
 x--------->|->|  |       |  |  Accept!(1,V1)
 |  |       X--X--------->|->|  Accepted(1,V1)
 !  |       |  |  |       |  |  !! FAIL !!
    |       |  |  |       |  |
    X--------->|->|       |  |  Prepare(2)
    |<---------X--X       |  |  Promise(2,{V1,null})
    X------>|->|->|       |  |  Accept!(2,V1)
    |<------X--X--X------>|->|  Accepted(2,V1)
    |       |  |  |       |  |
</pre>

== Multi-Paxos ==
A typical deployment of Paxos requires a continuous stream of agreed values acting as commands to a distributed state machine.  If each command is the result of a single instance of the Basic Paxos protocol, a significant amount of overhead would result.

If the leader is relatively stable, phase 1 becomes unnecessary. Thus, it is possible to skip phase 1 for future instances of the protocol with the same leader.

To achieve this, the round number {{mono|I}} is included along with each value which is incremented in each round by the same Leader.  Multi-Paxos reduces the failure-free message delay (proposal to learning) from 4 delays to 2 delays.

=== Graphic representation of the flow of messages in the Multi-Paxos ===

==== Multi-Paxos without failures ====

In the following diagram, only one instance (or "execution") of the basic Paxos protocol, with an initial Leader (a Proposer), is shown. Note that a Multi-Paxos consists of several instances of the basic Paxos protocol.

<pre>Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |<---------X--X--X------>|->|  Accepted(N,I,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |
</pre>

where V = last of (Va, Vb, Vc).

==== Multi-Paxos when phase 1 can be skipped ====

In this case, subsequent instances of the basic Paxos protocol (represented by ''I+1'') use the same leader, so the phase 1 (of these subsequent instances of the basic Paxos protocol), which consist of the Prepare and Promise sub-phases, is skipped. Note that the Leader should be stable, i.e. it should not crash or change.

<pre>Client   Proposer       Acceptor     Learner
   |         |          |  |  |       |  |  --- Following Requests ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I+1,W)
   |         |<---------X--X--X------>|->|  Accepted(N,I+1,W)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |
</pre>

==== Multi-Paxos when roles are collapsed ====

A common deployment of the Multi-Paxos consists in collapsing the role of the Proposers, Acceptors and Learners to "Servers". So, in the end, there are only "Clients" and "Servers".

The following diagram represents the first "instance" of a basic Paxos protocol, when the roles of the Proposer, Acceptor and Learner are collapsed to a single role, called the "Server".

<pre>Client      Servers
   |         |  |  | --- First Request ---
   X-------->|  |  |  Request
   |         X->|->|  Prepare(N)
   |         |<-X--X  Promise(N, I, {Va, Vb})
   |         X->|->|  Accept!(N, I, Vn)
   |         X<>X<>X  Accepted(N, I)
   |<--------X  |  |  Response
   |         |  |  |
</pre>

==== Multi-Paxos when roles are collapsed and the leader is steady ====

In the subsequent instances of the basic Paxos protocol, with the same leader as in the previous instances of the basic Paxos protocol, the phase 1 can be skipped.

<pre>Client      Servers
   X-------->|  |  |  Request
   |         X->|->|  Accept!(N,I+1,W)
   |         X<>X<>X  Accepted(N,I+1)
   |<--------X  |  |  Response
   |         |  |  |
</pre>

== Optimisations ==

A number of optimisations can be performed to reduce the number of exchanged messages, to improve the performance of the protocol, etc. A few of these optimisations are reported below.

: "We can save messages at the cost of an extra message delay by having a single distinguished learner that informs the other learners when it finds out that a value has been chosen. Acceptors then send ''Accepted'' messages only to the distinguished learner.  In most applications, the roles of leader and distinguished learner are performed by the same processor.<ref name=cheap/>

: "A leader can send its ''Prepare'' and ''Accept!'' messages just to a quorum of acceptors. As long as all acceptors in that quorum are working and can communicate with the leader and the learners, there is no need for acceptors not in the quorum to do anything.<ref name=cheap/>

: "Acceptors do not care what value is chosen. They simply respond to ''Prepare'' and ''Accept!'' messages to ensure that, despite failures, only a single value can be chosen. However, if an acceptor does learn what value has been chosen, it can store the value in stable storage and erase any other information it has saved there. If the acceptor later receives a ''Prepare'' or ''Accept!'' message, instead of performing its Phase1b or Phase2b action, it can simply inform the leader of the chosen value.<ref name=cheap/>

: "Instead of sending the value v, the leader can send a hash of v to some acceptors in its ''Accept!'' messages. A learner will learn that v is chosen if it receives ''Accepted'' messages for either v or its hash from a quorum of acceptors, and at least one of those messages contains v rather than its hash. However, a leader could receive ''Promise'' messages that tell it the hash of a value v that it must use in its Phase2a action without telling it the actual value of v. If that happens, the leader cannot execute its Phase2a action until it communicates with some process that knows v."<ref name=cheap/>

: "A proposer can send its proposal only to the leader rather than to all coordinators. However, this requires that the result of the leader-selection algorithm be broadcast to the proposers, which might be expensive. So, it might be better to let the proposer send its proposal to all coordinators. (In that case, only the coordinators themselves need to know who the leader is.)<ref name=fast/>

: "Instead of each acceptor sending ''Accepted'' messages to each learner, acceptors can send their ''Accepted'' messages to the leader and the leader can inform the learners when a value has been chosen. However, this adds an extra message delay.<ref name=fast/>

: "Finally, observe that phase 1 is unnecessary for round 1 .. The leader of round 1 can begin the round by sending an ''Accept!'' message with any proposed value."<ref name=fast/>

== Cheap Paxos ==

Cheap Paxos extends Basic Paxos to tolerate F failures with F+1 main processors and F auxiliary processors by dynamically reconfiguring after each failure.

This reduction in processor requirements comes at the expense of liveness; if too many main processors fail in a short time, the system must halt until the auxiliary processors can reconfigure the system.  During stable periods, the auxiliary processors take no part in the protocol.

<blockquote>"With only two processors p and q, one processor cannot distinguish failure of the other processor from failure of the communication medium. A third processor is needed. However, that third processor does not have to participate in choosing the sequence of commands. It must take action only in case p or q fails, after which it does nothing while either p or q continues to operate the system by itself. The third processor can therefore be a small/slow/cheap one, or a processor primarily devoted to other tasks."<ref name=cheap/></blockquote>

=== Message flow: Cheap Multi-Paxos ===

An example involving three main acceptors, one auxiliary acceptor and quorum size of three, showing failure of one main processor and subsequent reconfiguration:

<pre>            {  Acceptors  }
Proposer     Main       Aux    Learner
|            |  |  |     |       |  -- Phase 2 --
X----------->|->|->|     |       |  Accept!(N,I,V)
|            |  |  !     |       |  --- FAIL! ---
|<-----------X--X--------------->|  Accepted(N,I,V)
|            |  |        |       |  -- Failure detected (only 2 accepted) --
X----------->|->|------->|       |  Accept!(N,I,V)  (re-transmit, include Aux)
|<-----------X--X--------X------>|  Accepted(N,I,V)
|            |  |        |       |  -- Reconfigure : Quorum = 2 --
X----------->|->|        |       |  Accept!(N,I+1,W) (Aux not participating)
|<-----------X--X--------------->|  Accepted(N,I+1,W)
|            |  |        |       |
</pre>

== Fast Paxos ==

Fast Paxos generalizes Basic Paxos to reduce end-to-end message delays.  In Basic Paxos, the message delay from client request to learning is 3 message delays.  Fast Paxos allows 2 message delays, but requires that (1) the system be composed of ''3f+ 1'' acceptors to tolerate up to ''f'' faults (instead of the classic 2f+1), and (2) the Client to send its request to multiple destinations.

Intuitively, if the leader has no value to propose, then a client could send an ''Accept!'' message to the Acceptors directly.  The Acceptors would respond as in Basic Paxos, sending ''Accepted'' messages to the leader and every Learner achieving two message delays from Client to Learner.

If the leader detects a collision, it resolves the collision by sending ''Accept!'' messages for a new round which are ''Accepted'' as usual.  This coordinated recovery technique requires four message delays from Client to Learner.

The final optimization occurs when the leader specifies a recovery technique in advance, allowing the Acceptors to perform the collision recovery themselves.  Thus, uncoordinated collision recovery can occur in three message delays (and only two message delays if all Learners are also Acceptors).

=== Message flow: Fast Paxos, non-conflicting ===

<pre>Client    Leader         Acceptor      Learner
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Any(N,I,Recovery)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Accept!(N,I,W)
   |         |<---------X--X--X--X------>|->|  Accepted(N,I,W)
   |<------------------------------------X--X  Response(W)
   |         |          |  |  |  |       |  |
</pre>

=== Message flow: Fast Paxos, conflicting proposals ===

<small>Conflicting proposals with coordinated recovery.  Note: the protocol does not specify how to handle the dropped client request.</small>

<pre>Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      X------->|->|->|->|      |  |  Accept!(N+1,I,W)
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |
</pre>

<small>Conflicting proposals with uncoordinated recovery. </small>

<pre>Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      X------->|->|->|->|      |  |  Any(N,I,Recovery)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |
</pre>

=== Message flow: Fast Paxos with uncoordinated recovery, collapsed roles ===

<small>(merged Acceptor/Learner roles)</small>
<pre>Client         Servers
 |  |         |  |  |  |
 |  |         X->|->|->|  Any(N,I,Recovery)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Concurrent conflicting proposals
 |  |         |  |  |  |  !!   received in different order
 |  |         |  |  |  |  !!   by the Servers
 |  X--------?|-?|-?|-?|  Accept!(N,I,V)
 X-----------?|-?|-?|-?|  Accept!(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Servers disagree on value
 |  |         X<>X->|->|  Accepted(N,I,V)
 |  |         |<-|<-X<>X  Accepted(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Detect collision & recover
 |  |         X<>X<>X<>X  Accepted(N+1,I,W)
 |<-----------X--X--X--X  Response(W)
 |  |         |  |  |  |
</pre>

== Generalized Paxos ==

Generalized consensus explores the relationship between the operations of the replicated state machine and the consensus protocol that implements it.<ref name=general/> The main discovery involves optimizations of Paxos when conflicting proposals could be applied in any order.  i.e., when the proposed operations are commutative operations for the state machine. In such cases, the conflicting operations can both be accepted, avoiding the delays required for resolving conflicts and re-proposing the rejected operations.

This concept is further generalized into ever-growing sequences of commutative operations, some of which are known to be stable (and thus may be executed).  The protocol tracks these sequences ensuring that all proposed operations of one sequence are stabilized before allowing any operation non-commuting with them to become stable.

=== Example ===

In order to illustrate Generalized Paxos, the example below shows a message flow between two concurrently executing clients and a replicated state machine implementing read/write operations over two distinct registers A and B.

{| class="wikitable"
|+ Commutativity Table
|-
!          !! Read(A) !! Write(A) !! Read(B) !! Write(B)
|-
! Read(A)
            |         || {{na}}   ||         ||
|-
! Write(A) 
            |{{na}}   || {{na}}   ||         ||
|-
! Read(B)
            |         ||          ||         || {{na}}
|-
! Write(B) 
            |         ||          ||{{na}}   || {{na}}
|}
Note that [[File:Dark Red x.svg|13px]] in this table indicates operations which are non-commutative.

A possible sequence of operations :
<pre> <1:Read(A), 2:Read(B), 3:Write(B), 4:Read(B), 5:Read(A), 6:Write(A)> </pre>

Since <code>5:Read(A)</code> commutes with both <code>3:Write(B)</code> and <code>4:Read(B)</code>, one possible permutation equivalent to the previous order is the following:
<pre> <1:Read(A), 2:Read(B), 5:Read(A), 3:Write(B), 4:Read(B), 6:Write(A)> </pre>

In practice, a commute occurs only when operations are proposed concurrently.

=== Message flow: Generalized Paxos (example) ===

<small>Responses not shown. Note: message abbreviations differ from previous message flows due to specifics of the protocol, see <ref name=paxos-family/> for a full discussion.</small>
<pre>
Client      Leader  Acceptor       Learner
 |  |         |      |  |  |         |  |  !! New Leader Begins Round
 |  |         X----->|->|->|         |  |  Prepare(N)
 |  |         |<-----X- X- X         |  |  Promise(N,null)
 |  |         X----->|->|->|         |  |  Phase2Start(N,null)
 |  |         |      |  |  |         |  | 
 |  |         |      |  |  |         |  |  !! Concurrent commuting proposals
 |  X------- ?|-----?|-?|-?|         |  |  Propose(ReadA)
 X-----------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         X------X-------------->|->|  Accepted(N,<ReadA,ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! No Conflict, both accepted
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Concurrent conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(<WriteB,ReadA>)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N,<WriteB,ReadA> . <ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB> . <WriteB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Conflict detected, leader chooses
 |  |         |      |  |  |         |  |  commutative order:
 |  |         |      |  |  |         |  |  V = <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Phase2Start(N+1,V)
 |  |         |<-----X- X- X-------->|->|  Accepted(N+1,V)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  | !! More conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(WriteA)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadA)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N+1,<WriteA> . <ReadA>)
 |  |         |<--------X- X-------->|->|  Accepted(N+1,<ReadA> . <WriteA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Leader chooses order:
 |  |         |      |  |  |         |  |  W = <WriteA, ReadA>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Phase2Start(N+2,W)
 |  |         |<-----X- X- X-------->|->|  Accepted(N+2,W)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB> .
 |  |         |      |  |  |         |  |           <WriteA, ReadA>
 |  |         |      |  |  |         |  |
</pre>

=== Performance ===

The above message flow shows us that Generalized Paxos can leverage operation semantics to avoid collisions when the spontaneous ordering of the network fails. This allows the protocol to be in practice quicker than Fast Paxos. However, when a collision occurs, Generalized Paxos needs two additional round trips to recover. This situation is illustrated with operations WriteB and ReadB in the above schema.

In the general case, such round trips are unavoidable and come from the fact that multiple commands can be accepted during a round. This makes the protocol more expensive than Paxos when conflicts are frequent. Hopefully two possible refinements of Generalized Paxos are possible to improve recovery time.<ref name="fggc"/>

* First, if the coordinator is part of every quorum of acceptors (round N is said ''centered''), then to recover at round N+1 from a collision at round N, the coordinator skips phase 1 and proposes at phase 2 the sequence it accepted last during round N. This reduces the cost of recovery to a single round trip.
* Second, if both rounds N and N+1 use a unique and identical centered quorum, when an acceptor detects a collision at round N, it spontaneously proposes at round N+1 a sequence suffixing both (i) the sequence accepted at round N by the coordinator and (ii) the greatest non-conflicting prefix it accepted at round N. For instance, if the coordinator and the acceptor accepted respectively at round N <WriteB, ReadB>  and <ReadB, ReadA> , the acceptor will spontaneously accept <WriteB, ReadB, ReadA> at round N+1. With this variation, the cost of recovery is a single message delay which is obviously optimal. Notice here that the use of a unique quorum at a round does not harm liveness. This comes from the fact that any process in this quorum is a read quorum for the prepare phase of the next rounds.<ref>{{Cite book|last1=Lamport|first1=Leslie|last2=Malkhi|first2=Dahlia|last3=Zhou|first3=Lidong|title=Proceedings of the 28th ACM symposium on Principles of distributed computing |chapter=Vertical paxos and primary-backup replication |date=2009|series=PODC '09|location=New York, NY, USA|publisher=ACM|pages=312–313|doi=10.1145/1582716.1582783|isbn=9781605583969|citeseerx=10.1.1.150.1791|s2cid=2763624 }}</ref>

== Byzantine Paxos ==

Paxos may also be extended to support arbitrary failures of the participants, including lying, fabrication of messages, collusion with other participants, selective non-participation, etc.  These types of failures are called [[Byzantine fault tolerance#Byzantine failures|Byzantine failures]], after the solution popularized by Lamport.<ref name="byzgen"/>

Byzantine Paxos<ref>{{cite journal|last1=Castro|first1=Miguel|last2=Liskov|first2=Barbara|title=Practical Byzantine Fault Tolerance|journal=Proceedings of the Third Symposium on Operating Systems Design and Implementation|date=February 1999|pages=173–186|url=http://pmg.csail.mit.edu/papers/osdi99.pdf|access-date=5 March 2018}}</ref> introduced by Castro and [[Biography:Barbara Liskov|Liskov]] adds an extra message (Verify) which acts to distribute knowledge and verify the actions of the other processors:

=== Message flow: Byzantine Multi-Paxos, steady state ===

<pre>Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |          X<>X<>X       |  |  Verify(N,I,V) - BROADCAST
   |         |<---------X--X--X------>|->|  Accepted(N,V)
   |<---------------------------------X--X  Response(V)
   |         |          |  |  |       |  |
</pre>
Fast Byzantine Paxos<ref>{{cite journal|last1=Martin|first1=Jean-Philippe|last2=Alvisi|first2=Lorenzo|title=Fast Byzantine Consensus|journal=IEEE Transactions on Dependable and Secure Computing|date=July 2006|volume=3|issue=3|pages=202–215|doi=10.1109/TDSC.2006.35|url=https://www.cs.utexas.edu/~lorenzo/papers/fab.pdf|access-date=5 March 2018}}</ref> introduced by Martin and [[Biography:Lorenzo Alvisi|Alvisi]] removes this extra delay, since the client sends commands directly to the Acceptors.

Note the ''Accepted'' message in Fast Byzantine Paxos is sent to all Acceptors and all Learners, while Fast Paxos sends ''Accepted'' messages only to Learners):

=== Message flow: Fast Byzantine Multi-Paxos, steady state ===

<pre>Client    Acceptor     Learner
   |      |  |  |       |  |
   X----->|->|->|       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  |       |  |
</pre>

The failure scenario is the same for both protocols;  Each Learner waits to receive F+1 identical messages from different Acceptors.  If this does not occur, the Acceptors themselves will also be aware of it (since they exchanged each other's messages in the broadcast round), and correct Acceptors will re-broadcast the agreed value:

=== Message flow: Fast Byzantine Multi-Paxos, failure ===

<pre>Client    Acceptor     Learner
   |      |  |  !       |  |  !! One Acceptor is faulty
   X----->|->|->!       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,{V,W}) - BROADCAST
   |      |  |  !       |  |  !! Learners receive 2 different commands
   |      |  |  !       |  |  !! Correct Acceptors notice error and choose
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  !       |  |
</pre>

== Adapting Paxos for RDMA networks ==

With the emergence of very high speed reliable datacenter networks that support remote DMA ([[Remote direct memory access|RDMA]]), there has been substantial interest in optimizing Paxos to leverage hardware offloading, in which the network interface card and network routers provide reliability and network-layer congestion control, freeing the host CPU for other tasks.  The [http://GitHub.com/Derecho-Project Derecho C++ Paxos library] is an open-source Paxos implementation that explores this option.<ref name=Derecho/>  

Derecho offers both a classic Paxos, with data durability across full shutdown/restart sequences, and vertical Paxos (atomic multicast), for in-memory replication and state-machine synchronization.  The Paxos protocols employed by Derecho needed to be adapted to maximize asynchronous data streaming and remove other sources of delay on the leader's critical path.  So doing enables Derecho to sustain the full bidirectional RDMA data rate.  In contrast, although traditional Paxos protocols can be migrated to an RDMA network by simply mapping the message send operations to native RDMA operations, doing so leaves round-trip delays on the critical path.  In high-speed RDMA networks, even small delays can be large enough to prevent utilization of the full potential bandwidth.

== Production use of Paxos ==
{{sources|section|date=October 2018}}

* Google uses the Paxos algorithm in their Chubby [[Distributed lock manager|distributed lock service]] in order to keep replicas consistent in case of failure.<ref>{{cite web |last1=Burrows |first1=Mike |title=The Chubby lock service for loosely-coupled distributed systems |url=https://static.googleusercontent.com/media/research.google.com/en//archive/chubby-osdi06.pdf |publisher=OSDI}}</ref>  Chubby is used by [[Software:Bigtable|Bigtable]] which is now in production in Google Analytics and other products.
* Google Spanner and Megastore use the Paxos algorithm internally.
* The [https://web.archive.org/web/20180809051426/http://openreplica.org/ OpenReplica replication service] uses Paxos to maintain replicas for an open access system that enables users to create fault-tolerant objects. It provides high performance through concurrent rounds and flexibility through dynamic membership changes.
* IBM supposedly uses the Paxos algorithm in their [[IBM SAN Volume Controller]] product to implement a general purpose fault-tolerant virtual machine used to run the configuration and control components of the [[Storage virtualization|storage virtualization]] services offered by the cluster. ([https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf Original MIT & IBM research paper])
* Microsoft uses Paxos in the [http://research.microsoft.com/pubs/64604/osr2007.pdf Autopilot cluster management service] from Bing, and in Windows Server Failover Clustering.
* [[Company:WANdisco|WANdisco]] have implemented Paxos within their DConE active-active replication technology.<ref name="WANdisco">Aahlad et al.(2011). [https://www.wandisco.com/get?f=documentation%2Fwhitepapers%2FWANdisco_DConE_White_Paper.pdf “The Distributed Coordination Engine (DConE)”] {{Webarchive|url=https://web.archive.org/web/20160415093538/https://www.wandisco.com/get?f=documentation%2Fwhitepapers%2FWANdisco_DConE_White_Paper.pdf |date=2016-04-15 }}. WANdisco white paper.</ref>
* [[Software:XtreemFS|XtreemFS]] uses a Paxos-based [[Lease (computer science)|lease]] negotiation algorithm for fault-tolerant and consistent replication of file data and metadata.<ref name="flease">Kolbeck, Björn; Högqvist, Mikael; Stender, Jan; Hupfeld, Felix (2011). [http://www.xtreemfs.org/publications/flease_paper_ipdps.pdf “Flease - Lease Coordination without a Lock Server”]. 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2011).</ref>
* Heroku uses [https://github.com/ha/doozerd Doozerd] which implements Paxos for its consistent distributed data store.
* [[Software:Ceph|Ceph]] uses Paxos as part of the monitor processes to agree which OSDs are up and in the cluster.
* The MariaDB Xpand distributed SQL database uses Paxos for [https://mariadb.com/docs/xpand/architecture/components/xpand/consistency/ distributed transaction resolution].
* [[Software:Neo4j|Neo4j]] HA graph database implements Paxos, replacing [[Software:Apache ZooKeeper|Apache ZooKeeper]] from v1.9
* [[Software:Apache Cassandra|Apache Cassandra]] NoSQL database uses Paxos for  [https://www.datastax.com/dev/blog/lightweight-transactions-in-cassandra-2-0 Light Weight Transaction feature only]
* Amazon Elastic Container Services uses Paxos to maintain [https://www.allthingsdistributed.com/2015/07/under-the-hood-of-the-amazon-ec2-container-service.html a consistent view of cluster state]
* Amazon DynamoDB uses the Paxos algorithm for [https://www.usenix.org/system/files/atc22-elhemali.pdf leader election and consensus].

== See also ==
* Two generals problem
* [[Chandra–Toueg consensus algorithm]]
* State machine
* [[Raft (computer science)|Raft]]

== References ==

{{reflist|refs=
<ref name="agree">{{cite journal
  | last1       = Pease
  | first1      = Marshall
  | last2       = Shostak
  | first2      = Robert
  | last3       = Lamport
  | first3      = Leslie
  |date=April 1980
  | title      = Reaching Agreement in the Presence of Faults
  | journal    = Journal of the Association for Computing Machinery
  | volume     = 27
  | issue      = 2
  | pages = 228–234
 | doi = 10.1145/322186.322188
 | s2cid = 6429068
 | url        = http://research.microsoft.com/users/lamport/pubs/pubs.html#reaching
  | access-date = 2007-02-02
  | doi-access= free
  }}</ref>
<ref name="schneider">{{cite journal
  | last    = Schneider
  | first   = Fred
  | year    = 1990
  | title   = Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial
  | journal = ACM Computing Surveys
  | volume  = 22
  | issue   = 4
  | url     = http://www.cs.cornell.edu/fbs/publications/smsurvey.pdf
  | doi     = 10.1145/98163.98167
  | pages   = 299–319
  | citeseerx   = 10.1.1.69.1536
  | s2cid = 678818
 }}</ref>
<ref name="clocks">{{cite journal
  | last       = Lamport
  | first      = Leslie
  |date=July 1978
  | title      = Time, Clocks and the Ordering of Events in a Distributed System
  | journal    = [[Communications of the ACM]]
  | volume     = 21
  | issue      = 7
  | pages      = 558–565
  | url        = http://research.microsoft.com/users/lamport/pubs/pubs.html#time-clocks
  | access-date = 2007-02-02
  | doi        = 10.1145/359545.359563
  | s2cid = 215822405
 | doi-access= free
  }}</ref>
<ref name="Lamport">[http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#lamport-paxos Leslie Lamport's history of the paper]</ref>
<ref name="paxos">{{cite journal
  | last       = Lamport
  | first      = Leslie
  |date=May 1998
  | title      = The Part-Time Parliament
  | journal    = ACM Transactions on Computer Systems
  | volume     = 16
  | issue      = 2
  | pages      = 133–169
  | url        = http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-paxos
  | access-date = 2007-02-02
  | doi        = 10.1145/279227.279229
  | s2cid = 421028
 | doi-access= free
  }}</ref>
<ref name="LMZ10">{{cite journal
  | title = Reconfiguring a State Machine
  | first1  = Leslie
  | last1   = Lamport
  | first2  = Dahlia
  | last2   = Malkhi
  | first3  = Lidong
  | last3   = Zhou
  | journal = SIGACT News
  | volume = 41
  | number = 1
  |date=March 2010
  | pages = 63–73
  | doi=10.1145/1753171.1753191
  | citeseerx  = 10.1.1.212.2168
  | s2cid = 15189602
 }}</ref>
<ref name="BJ87">{{cite journal
  | title = Reliable Communication in the Presence of Failures
  | first1 = Kenneth
  | last1 = Birman
  | first2 = Thomas
  | last2 = Joseph
  | journal = ACM Transactions on Computer Systems
  |date=February 1987
  | volume = 5
 | pages = 47–76
  | doi = 10.1145/7351.7478
 | hdl = 1813/6534
 | s2cid = 11224827
 | hdl-access = free
  }}</ref>
<ref name="LDS88">{{cite journal
  | title   = Consensus in the Presence of Partial Synchrony
  | url     = http://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf
  | first1  = Cynthia
  | last1   = Dwork
  | first2  = Nancy
  | last2   = Lynch
  | first3  = Larry
  | last3   = Stockmeyer
  | journal = Journal of the ACM
  | volume  = 35
  | number  = 2
  |date=April 1988
  | pages   = 288–323
  | doi=10.1145/42282.42283
  | citeseerx     = 10.1.1.13.3423
  | s2cid = 17007235
 }}</ref>
<ref name="vr">{{cite conference
  | last1     = Oki
  | first1    = Brian
  | last2     = Liskov
  | first2    = Barbara
  | year      = 1988
  | title     = Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems
  | book-title = PODC '88: Proceedings of the seventh annual ACM Symposium on Principles of Distributed Computing
  | pages     = 8–17
  | url       = http://portal.acm.org/citation.cfm?id=62549
  | doi       = 10.1145/62546.62549
  }}</ref>
<ref name="flp">{{cite journal
  | last    = Fischer
  | first   = M.
  |date=April 1985
  | title   = Impossibility of distributed consensus with one faulty process
  | journal = Journal of the ACM
  | volume  = 32
  | issue   = 2
  | pages   = 374–382
  | doi     = 10.1145/3149.214121
  | s2cid = 207660233
 | doi-access= free
  }}</ref>
<ref name="cheap">{{cite conference
  | last1     = Lamport
  | first1    = Leslie
  | last2     = Massa
  | first2    = Mike
  | year      = 2004
  | title     = Cheap Paxos
  | book-title = Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004)
  | url       = http://research.microsoft.com/users/lamport/pubs/pubs.html#web-dsn-submission
  }}</ref>
<ref name="fast">{{cite web
  | last  = Lamport
  | first = Leslie
  | year  = 2005
  | title = Fast Paxos
  | url   = http://research.microsoft.com/users/lamport/pubs/pubs.html#fast-paxos
  }}</ref>
<ref name="general">{{cite journal
  | last  = Lamport
  | first = Leslie
  | year  = 2005
  | title = Generalized Consensus and Paxos
  | url   = http://research.microsoft.com/users/lamport/pubs/pubs.html#generalized
  }}</ref>
<ref name="techtalk">{{cite AV media
  | people  = Quesada Torres, Luis
  | date = 2018
  | title = The Paxos Algorithm
  | publisher = Google TechTalks
  | url   = https://www.youtube.com/watch?v=d7nAGI_NZPk
  }}</ref>
<!--unused<ref name="byzantine">{{cite web
  | last  = Castro
  | first = Miguel
  | year  = 2001
  | title = Practical Byzantine Fault Tolerance
  | url   = http://citeseer.ist.psu.edu/castro01practical.html
  }}</ref>-->
<ref name="consensus">{{cite web
  | last  = Lamport
  | first = Leslie
  | year  = 2004
  | title = Lower Bounds for Asynchronous Consensus
  | url   = http://research.microsoft.com/users/lamport/pubs/pubs.html#lower-bound
  }}</ref>
<ref name="live">{{cite book
  | last1     = Chandra
  | first1    = Tushar
  | last2     = Griesemer
  | first2    = Robert
  | last3     = Redstone
  | first3    = Joshua
  | title = Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing
 | chapter = Paxos made live
 | date = 2007
 | year      = 2007
  | pages    = 398–407
  | url       = http://research.google.com/pubs/pub33002.html
  | doi    = 10.1145/1281100.1281103
  | isbn    = 9781595936165
  | s2cid = 207164635
 }}</ref>
<ref name="paxos-simple">Lamport, Leslie (2001). [http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#paxos-simple Paxos Made Simple] ''ACM SIGACT News (Distributed Computing Column) 32'', 4 (Whole Number 121, December 2001) 51-58.</ref>
<ref name="byzgen">{{cite journal
  | last1       = Lamport
  | first1      = Leslie
  | last2       = Shostak
  | first2      = Robert
  | last3       = Pease
  | first3      = Marshall
  |date=July 1982
  | title      = The Byzantine Generals Problem
  | journal    = ACM Transactions on Programming Languages and Systems
  | volume     = 4
  | issue      = 3
  | pages      = 382–401
  | url        = http://research.microsoft.com/users/lamport/pubs/pubs.html#byz
  | access-date = 2007-02-02
  | doi        = 10.1145/357172.357176
  | citeseerx      = 10.1.1.64.2312
  | s2cid = 55899582
 }}</ref>
<ref name="fggc">{{cite conference
  | last1     = Pierre
  | first1    = Sutra
  | last2     = Marc
  | first2    = Shapiro
  | year      = 2011
  | title     = Fast Genuine Generalized Consensus
  | book-title = SRDS'11: 30th IEEE Symposium on Reliable Distributed Systems
  | url       = http://pagesperso-systeme.lip6.fr/Marc.Shapiro/papers/FGGC-SRDS-2011.pdf
  }}</ref>
<ref name="paxos-family">{{cite web
  | last  = Turner
  | first = Bryan
  | year  = 2007
  | title = The Paxos Family of Consensus Protocols
  | url   = http://www.fractalscape.org/2007/10/01/paxos-family.html
  }}</ref>
<ref name="optimality">{{cite conference
  | last1 = Keidar
  | last2 = Shraer
  | first2 = Alexander
  | year = 2006
  | title = Timeliness, failure-detectors, and consensus performance. 
  | book-title = PODC '06: Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing
  | doi =  10.1145/1146381.1146408
}}</ref>
<ref name="Derecho">{{cite journal
  | last1       = Jha
  | first1      = Sagar
  | last2       = Behrens
  | first2      = Jonathan
  | last3       = Gkountouvas
  | first3      = Theo
  | last4       = Milano
  | first4      = Matthew
  | last5       = Song
  | first5      = Weijia
  | last6       = Tremel
  | first6      = Edward
  | last7       = van Renesse
  | first7      = Robbert
  | last8       = Zink
  | first8      = Sydney
  | last9       = Birman
  | first9      = Ken
  | date=April 2019
  | title      = Derecho: Fast State Machine Replication for Cloud Services
  | journal    = ACM Transactions on Computer Systems
  | volume     = 36
  | issue      = 2
  | doi=10.1145/3302258
| s2cid = 218482757
 }}</ref>
}}

== External links ==
* [http://www.lamport.org/ Leslie Lamport's home page]
* [http://research.microsoft.com/users/lamport/pubs/pubs.html#paxos-simple Paxos Made Simple]
* [https://paxos.systems/ Paxos Made Moderately Complex]
* [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5607 Revisiting the Paxos Algorithm]
* [http://research.microsoft.com/users/lamport/pubs/pubs.html#paxos-commit Paxos Commit]
* [http://research.google.com/archive/chubby.html Google Whitepaper: Chubby Distributed Lock Service]
* [http://research.google.com/archive/bigtable.html Google Whitepaper: Bigtable A Distributed Storage System for Structured Data]
* [http://www.fractalscape.org/2007/10/01/paxos-family.html Survey of Paxos Algorithms (2007)]
* [https://web.archive.org/web/20180809051426/http://openreplica.org/ OpenReplica Open Replication Service]
* [https://web.archive.org/web/20160303212934/http://ftfile.rodia.pl/ FTFile: Fault Tolerant File library]
* [http://isis2.codeplex.com Isis2 library (the SafeSend primitive is a free, open source implementation of Paxos)]
* [http://www.usenix.org/event/osdi08/tech/full_papers/mao/mao.pdf Mencius - Circular rotating Paxos for geo-distributed systems]
* [http://www.wandisco.com/ WANdisco - Active-Active Replication solutions for Hadoop, Subversion & GIT]
* [http://libpaxos.sourceforge.net/ libpaxos, a collection of open source implementations of the Paxos algorithm]
* [https://github.com/solatis/libpaxos-cpp libpaxos-cpp, a C++ implementation of the paxos distributed consensus algorithm]
* [http://www.navigators.di.fc.ul.pt/software/jitt/jbp.html JBP - Java Byzantine Paxos]
* [http://code.google.com/p/erlpaxos/ erlpaxos, Paxos by Erlang]
* [https://github.com/cocagne/paxos/ paxos - Straight-forward paxos implementation in Python & Java]
* [http://mpaxos.com/ Manhattan Paxos (mpaxos), Paxos in C, supporting multiple paxos groups and efficient transactions across them.]
* [http://de.slideshare.net/jexp/new-neo4j-auto-ha-cluster|HA Clustering with Neo4j]
* [https://arxiv.org/abs/1407.1237 HT-Paxos]
* [https://github.com/Tencent/paxosstore PaxosStore, paxos implementation in WeChat]
* [https://www.datastax.com/dev/blog/lightweight-transactions-in-cassandra-2-0 LWT in Cassandra]
* [https://www.youtube.com/watch?v=d7nAGI_NZPk Google TechTalks: The Paxos Algorithm]

{{DEFAULTSORT:Paxos Algorithm}}
[[Category:Distributed algorithms]]
[[Category:Fault-tolerant computer systems]]

{{Sourceattribution|Paxos (computer science)}}