{"history":[],"article":{"id":"1764a6a7-70f0-4121-9ef0-f787c4bd36a9","title":"Paxos (computer science)","slug":"paxos-computer-science","content":":::summary\n:::\n\n# \n**Paxos** is a family of protocols for solving [consensus](https://bliptext.com/articles/consensus-computer-science) in a network of unreliable or fallible processors.\nConsensus is the process of agreeing on one result among a group of participants.\nThis problem becomes difficult when the participants or their communications may experience failures.\nConsensus protocols are the basis for the [state machine replication](https://bliptext.com/articles/state-machine-replication) approach to [distributed computing](https://bliptext.com/articles/distributed-computing), as suggested by [Leslie Lamport](https://bliptext.com/articles/leslie-lamport) and surveyed by [Fred Schneider](https://bliptext.com/articles/fred-b-schneider).\nState machine replication is a technique for converting an algorithm into a fault-tolerant, distributed implementation.\nAd-hoc techniques may leave important cases of failures unresolved.\nThe principled approach proposed by Lamport et al. ensures all cases are handled safely.\nThe [Paxos](https://bliptext.com/articles/paxi) protocol was first submitted in 1989 and named after a fictional legislative consensus system used on the [Paxos](https://bliptext.com/articles/paxi) island in Greece, where Lamport wrote that the parliament had to function \"even though legislators continually wandered in and out of the parliamentary Chamber\".\nIt was later published as a journal article in 1998.\nThe 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.\nAlthough no deterministic fault-tolerant consensus protocol can guarantee progress in an asynchronous network (a [result](https://bliptext.com/articles/consensus-computer-science) proved in a paper by [Fischer](https://bliptext.com/articles/michael-j-fischer), [Lynch](https://bliptext.com/articles/nancy-lynch) and [Paterson](https://bliptext.com/articles/mike-paterson) ), Paxos guarantees safety (consistency), and the conditions that could prevent it from making progress are difficult to provoke.\nPaxos is usually used where durability is required (for example, to replicate a file or a [database](https://bliptext.com/articles/database)), in which the amount of durable state could be large.\nThe protocol attempts to make progress even during periods when some bounded number of replicas are unresponsive.\nThere is also a mechanism to drop a permanently failed replica or to add a new replica.\n\n# History\nThe topic predates the protocol.\nIn 1988, [Lynch](https://bliptext.com/articles/nancy-lynch), [Dwork](https://bliptext.com/articles/cynthia-dwork) and [Stockmeyer](https://bliptext.com/articles/larry-stockmeyer) had demonstrated the solvability of consensus in a broad family of \"partially synchronous\" systems.\nPaxos has strong similarities to a protocol used for agreement in \"viewstamped replication\", first published by Oki and [Liskov](https://bliptext.com/articles/barbara-liskov) in 1988, in the context of distributed transactions.\nNotwithstanding 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.\nReconfigurable state machines have strong ties to prior work on reliable group multicast protocols that support dynamic group membership, for example [Birman](https://bliptext.com/articles/ken-birman)'s work in 1985 and 1987 on the [virtually synchronous](https://bliptext.com/articles/virtual-synchrony) [gbcast](https://bliptext.com/articles/gbcast) protocol.\nHowever, gbcast is unusual in supporting durability and addressing partitioning failures.\nMost reliable multicast protocols lack these properties, which are required for implementations of the state machine replication model.\nThis point is elaborated in a paper by [Lamport](https://bliptext.com/articles/leslie-lamport), [Malkhi](https://bliptext.com/articles/dahlia-malkhi) and Zhou.\nPaxos protocols are members of a theoretical class of solutions to a problem formalized as uniform agreement with crash failures.\nLower bounds for this problem have been proved by [Keidar](https://bliptext.com/articles/idit-keidar) and Shraer.\nDerecho, a C++ software library for cloud-scale state machine replication, offers a Paxos protocol that has been integrated with self-managed virtually synchronous membership.\nThis protocol matches the Keidar and Shraer optimality bounds, and maps efficiently to modern [remote DMA (RDMA)](https://bliptext.com/articles/remote-direct-memory-access) datacenter hardware (but uses TCP if RDMA is not available).\n\n# Assumptions\nIn order to simplify the presentation of Paxos, the following assumptions and definitions are made explicit.\nTechniques to broaden the applicability are known in the literature, and are not covered in this article.\n\n## Processors\n\n## Network\n\n## Number of processors\nIn general, a consensus algorithm can make progress using n=2F+1 processors, despite the simultaneous failure of any F processors: in other words, the number of non-faulty processes must be strictly greater than the number of faulty processes.\nHowever, using reconfiguration, a protocol may be employed which survives any number of total failures as long as no more than F fail simultaneously.\nFor Paxos protocols, these reconfigurations can be handled as separate configurations.\n\n# Safety and liveness properties\nIn 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:\nNote that Paxos is not guaranteed to terminate, and thus does not have the liveness property.\nThis 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.\nAs Paxos's point is to ensure fault tolerance and it guarantees safety, it cannot also guarantee liveness.\n\n# Typical deployment\nIn most deployments of Paxos, each participating process acts in three roles: Proposer, Acceptor and Learner.\nThis reduces the message complexity significantly, without sacrificing correctness:\nIn Paxos, clients send commands to a leader.\nDuring normal operation, the leader receives a client's command, assigns it a new command number i, and then begins the ith instance of the consensus algorithm by sending messages to a set of acceptor processes.\nBy merging roles, the protocol \"collapses\" into an efficient client-master-replica style deployment, typical of the database community.\nThe benefit of the Paxos protocols (including implementations with merged roles) is the guarantee of its [safety properties](https://bliptext.com/articles/).\nA typical implementation's message flow is covered in the section [Multi-Paxos](https://bliptext.com/articles/).\n\n# Basic Paxos\nThis protocol is the most basic of the Paxos family.\nEach \"instance\" (or \"execution\") of the basic Paxos protocol decides on a single output value.\nThe protocol proceeds over several rounds.\nA 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).\nSee below the description of the phases.\nRemember that we assume an asynchronous model, so e.g. a processor may be in one phase while another processor may be in another.\n\n## Phase 1\n\n### Phase 1a: Prepare\n\n### Phase 1b: Promise\n\n## Phase 2\n\n### Phase 2a: Accept\nThis Accept message should be interpreted as a \"request\", as in \"Accept this proposal, please!\".\n\n### Phase 2b: Accepted\nNote that consensus is achieved when a majority of Acceptors accept the same identifier number (rather than the same value).\nBecause 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.\nThese facts result in a few counter-intuitive scenarios that do not impact correctness: [Acceptors can accept multiple values](https://bliptext.com/articles/paxos-computer-science), [a value may achieve a majority across Acceptors (with different identifiers) only to later be changed](https://bliptext.com/articles/paxos-computer-science), and [Acceptors may continue to accept proposals after an identifier has achieved a majority](https://bliptext.com/articles/paxos-computer-science).\nHowever, the Paxos protocol guarantees that consensus is permanent and the chosen value is immutable.\n\n## When rounds fail\n\n## Paxos can be used to select a leader\nNotice that a Proposer in Paxos could propose \"I am the leader\" (or, for example, \"Proposer X is the leader\").\nBecause 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.\nThis satisfies the needs of leader election because there is a single node believing it is the leader and a single node known to be the leader at all times.\n\n## Graphic representation of the flow of messages in the basic Paxos\nThe following diagrams represent several cases/situations of the application of the Basic Paxos protocol.\nSome cases show how the Basic Paxos protocol copes with the failure of certain (redundant) components of the distributed system.\nNote 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).\n\n### Basic Paxos without failures\nIn 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).\nThis diagram represents the case of a first round, which is successful (i.e. no process in the network fails).\nHere, V is the last of (Va, Vb, Vc).\n# [frame | upload.wikimedia.org/wikipedia/commons/5/57/Basic///Paxos///without///failures.svg]\n\n### Error cases in basic Paxos\nThe simplest error cases are the failure of an Acceptor (when a Quorum of Acceptors remains alive) and failure of a redundant Learner.\nIn 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).\n\n### Basic Paxos when an Acceptor fails\nIn the following diagram, one of the Acceptors in the Quorum fails, so the Quorum size becomes 2.\nIn this case, the Basic Paxos protocol still succeeds.\nClient Proposer Acceptor Learner\n| | | | | | | X>| | | | | | Request\n| X->|->|->| | | Prepare(1)\n| | | | ! | | !! FAIL !!\n| |<-X--X | | Promise(1,{Va, Vb, null})\n| X->|->| | | Accept!(1,V)\n| |<-X--X->|->| Accepted(1,V)\n|<-X--X Response\n| | | | | |\n\n### Basic Paxos when a redundant learner fails\nIn the following case, one of the (redundant) Learners fails, but the Basic Paxos protocol still succeeds.\nClient Proposer Acceptor Learner\n| | | | | | | X>| | | | | | Request\n| X->|->|->| | | Prepare(1)\n| |<-X--X--X | | Promise(1,{Va,Vb,Vc})\n| X->|->|->| | | Accept!(1,V)\n| |<-X--X--X-->|->| Accepted(1,V)\n| | | | | | ! !! FAIL !!\n|<-X Response\n| | | | | |\n\n### Basic Paxos when a Proposer fails\nIn this case, a Proposer fails after proposing a value, but before the agreement is reached.\nSpecifically, it fails in the middle of the Accept message, so only one Acceptor of the Quorum receives the value.\nMeanwhile, a new Leader (a Proposer) is elected (but this is not shown in detail).\nNote that there are 2 rounds in this case (rounds proceed vertically, from the top to the bottom).\nClient Proposer Acceptor Learner\n| | | | | | | X->| | | | | | Request\n| X>|->|->| | | Prepare(1)\n| || | | | | Accept!(1,V)\n| ! | | | | | | | | | | | | !! NEW LEADER !!\n| X->|->|->| | | Prepare(2)\n| |<-X--X--X | | Promise(2,{V, null, null})\n| X->|->|->| | | Accept!(2,V)\n| |<-X--X--X-->|->| Accepted(2,V)\n|<-X--X Response\n| | | | | | |\n\n### Basic Paxos when multiple Proposers conflict\nThe most complex case is when multiple Proposers believe themselves to be Leaders.\nFor instance, the current leader may fail and later recover, but the other Proposers have already re-selected a new leader.\nThe recovered leader has not learned this yet and attempts to begin one round in conflict with the current leader.\nIn the diagram below, 4 unsuccessful rounds are shown, but there could be more (as suggested at the bottom of the diagram).\nClient Proposer Acceptor Learner\n| | | | | | | X->| | | | | | Request\n| X>|->|->| | | Prepare(1)\n| ||->|->| | | Prepare(2)\n| |<-X--X--X | | Promise(2,{null,null,null})\n| | | | | | | | !! OLD LEADER recovers\n| | | | | | | | !! OLD LEADER tries 2, denied\n| X>|->|->| | | Prepare(2)\n| ||->|->| | | Prepare(3)\n| ||->|->| | | Accept!(2,Va)\n| | |<-X--X--X | | Nack(3)\n| | | | | | | | !! NEW LEADER tries 4\n| | X->|->|->| | | Prepare(4)\n| | |<-X--X--X | | Promise(4,{null,null,null})\n| | | | | | | | !! OLD LEADER proposes, denied\n| X>|->|->| | | Accept!(3,Vb)\n| ||->|->| | | Prepare(1)\n|<-X--X--X | | Promise(1,{null,null,null})\nx->| | | | | Accept!(1,V1)\n| | X>|->| Accepted(1,V1)\n! | | | | | | !! FAIL !!\n| | | | | | X->|->| | | Prepare(2)\n|<-X--X | | Promise(2,{null,null})\nX-->|->|->| | | Accept!(2,V2)\n|<--X--X--X-->|->| Accepted(2,V2)\n| | | | | |\n\n### Basic Paxos where a multi-identifier majority is insufficient\nIn the following case, one Proposer achieves acceptance of value V1 of one Acceptor before failing.\nA new Proposer prepares the Acceptors that never accepted V1, allowing it to propose V2.\nThis Proposer is able to get one Acceptor to accept V2 before failing.\nA new Proposer finds a majority that includes the Acceptor that has accepted V1, and must propose it.\nThe Proposer manages to get two Acceptors to accept it before failing.\nAt this point, three Acceptors have accepted V1, but not for the same identifier.\nFinally, a new Proposer prepares the majority that has not seen the largest accepted identifier.\nThe value associated with the largest identifier in that majority is V2, so it must propose it.\nThis Proposer then gets all Acceptors to accept V2, achieving consensus.\nProposer Acceptor Learner\n| | | | | | | | | | | X--->|->|->|->|->| | | Prepare(1)\n|<---X--X--X--X--X | | Promise(1,{null,null,null,null,null})\nx--->| | | | | | | Accept!(1,V1)\n| | | | X-->|->| Accepted(1,V1)\n! | | | | | | | | | | !! FAIL !!\n| | | | | | | | | | X--->|->|->|->| | | Prepare(2)\n|<---X--X--X--X | | Promise(2,{null,null,null,null})\nX--->| | | | | | Accept!(2,V2)\n| | | | X--->|->| Accepted(2,V2)\n! | | | | | | | | | !! FAIL !!\n| | | | | | | | | X->|>|->|->| | | Prepare(3)\n|<-X-X--X--X | | Promise(3,{V1,null,null,null})\nX--->|->| | | | Accept!(3,V1)\n| | | | X--X->|->| Accepted(3,V1)\n! | | | | | | | | !! FAIL !!\n| | | | | | | | X-->|->|--->| | | Prepare(4)\n|<--X--X--|--|--X | | Promise(4,{V1(1),V2(2),null})\nX-->|->|->|->|->| | | Accept!(4,V2)\n| X--X--X--X--X-->|->| Accepted(4,V2)\n\n### Basic Paxos where new Proposers cannot change an existing consensus\nIn the following case, one Proposer achieves acceptance of value V1 of two Acceptors before failing.\nA 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.\nAs such, even though the Proposer doesn't see the existing consensus, the Proposer's only option is to propose the value already agreed upon.\nNew Proposers can continually increase the identifier to restart the process, but the consensus can never be changed.\nProposer Acceptor Learner\n| | | | | | | X->|->|->| | | Prepare(1)\n|<-X--X--X | | Promise(1,{null,null,null})\nx->|->| | | | Accept!(1,V1)\n| | X--X->|->| Accepted(1,V1)\n! | | | | | | !! FAIL !!\n| | | | | | X->|->| | | Prepare(2)\n|<-X--X | | Promise(2,{V1,null})\nX-->|->|->| | | Accept!(2,V1)\n|<--X--X--X-->|->| Accepted(2,V1)\n| | | | | |\n\n# Multi-Paxos\nA typical deployment of Paxos requires a continuous stream of agreed values acting as commands to a distributed state machine.\nIf each command is the result of a single instance of the [Basic Paxos](https://bliptext.com/articles/) protocol, a significant amount of overhead would result.\nIf the leader is relatively stable, phase 1 becomes unnecessary.\nThus, it is possible to skip phase 1 for future instances of the protocol with the same leader.\nTo achieve this, the round number I is included along with each value which is incremented in each round by the same Leader.\nMulti-Paxos reduces the failure-free message delay (proposal to learning) from 4 delays to 2 delays.\n\n## Graphic representation of the flow of messages in the Multi-Paxos\n\n### Multi-Paxos without failures\nIn the following diagram, only one instance (or \"execution\") of the basic Paxos protocol, with an initial Leader (a Proposer), is shown.\nNote that a Multi-Paxos consists of several instances of the basic Paxos protocol.\nClient Proposer Acceptor Learner\n| | | | | | | --- First Request ---\nX>| | | | | | Request\n| X->|->|->| | | Prepare(N)\n| |<-X--X--X | | Promise(N,I,{Va,Vb,Vc})\n| X->|->|->| | | Accept!(N,I,V)\n| |<-X--X--X-->|->| Accepted(N,I,V)\n|<-X--X Response\n| | | | | | |\nwhere V = last of (Va, Vb, Vc).\n\n### Multi-Paxos when phase 1 can be skipped\nIn 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.\nNote that the Leader should be stable, i.e. it should not crash or change.\nClient Proposer Acceptor Learner\n| | | | | | | --- Following Requests ---\nX>| | | | | | Request\n| X->|->|->| | | Accept!(N,I+1,W)\n| |<-X--X--X-->|->| Accepted(N,I+1,W)\n|<-X--X Response\n| | | | | | |\n\n### Multi-Paxos when roles are collapsed\nA common deployment of the Multi-Paxos consists in collapsing the role of the Proposers, Acceptors and Learners to \"Servers\".\nSo, in the end, there are only \"Clients\" and \"Servers\".\nThe 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\".\nClient Servers\n| | | | --- First Request ---\nX>| | | Request\n| X->|->| Prepare(N)\n| |<-X--X Promise(N, I, {Va, Vb})\n| X->|->| Accept!(N, I, Vn)\n| X<>X<>X Accepted(N, I) || | | Request\n| X->|->| Accept!(N,I+1,W)\n| X<>X<>X Accepted(N,I+1)\n||->|->| | | Accept!(N,I,V)\nX--->|->|--->| | Accept!(N,I,V) (re-transmit, include Aux)\nX--->|->| | | Accept!(N,I+1,W) (Aux not participating)\n\n# Fast Paxos\nFast Paxos generalizes [Basic Paxos](https://bliptext.com/articles/) to reduce end-to-end message delays.\nIn Basic Paxos, the message delay from client request to learning is 3 message delays.\nFast 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.\nIntuitively, if the leader has no value to propose, then a client could send an Accept! message to the Acceptors directly.\nThe Acceptors would respond as in Basic Paxos, sending Accepted messages to the leader and every Learner achieving two message delays from Client to Learner.\nIf the leader detects a collision, it resolves the collision by sending Accept! messages for a new round which are Accepted as usual.\nThis coordinated recovery technique requires four message delays from Client to Learner.\nThe final optimization occurs when the leader specifies a recovery technique in advance, allowing the Acceptors to perform the collision recovery themselves.\nThus, uncoordinated collision recovery can occur in three message delays (and only two message delays if all Learners are also Acceptors).\n\n## Message flow: Fast Paxos, non-conflicting\nClient Leader Acceptor Learner\n| | | | | | | | | X->|->|->|->| | | Any(N,I,Recovery)\n| | | | | | | | X--->|->|->|->| | | Accept!(N,I,W)\n| |<-X--X--X--X-->|->| Accepted(N,I,W)\n||->|->|->| Accepted(N,I,V)\n| | |<---|<-|<-X--X->|->| Accepted(N,I,W)\n| | | | | | | | | | | | | | | | | | !! Detect collision & recover\n| | X--->|->|->|->| | | Accept!(N+1,I,W)\n| | |<---X--X--X--X->|->| Accepted(N+1,I,W)\n|<-X--X Response(W)\n| | | | | | | | |\nConflicting proposals with uncoordinated recovery.\nClient Leader Acceptor Learner\n| | | | | | | | | | | X--->|->|->|->| | | Any(N,I,Recovery)\n| | | | | | | | | | | | | | | | | | !! Concurrent conflicting proposals\n| | | | | | | | | !! received in different order\n| | | | | | | | | !! by the Acceptors\n| X--?|-?|-?|-?| | | Accept!(N,I,V)\nX-?|-?|-?|-?| | | Accept!(N,I,W)\n| | | | | | | | | | | | | | | | | | !! Acceptors disagree on value\n| | |<---X--X->|->|->|->| Accepted(N,I,V)\n| | |<---|<-|<-X--X->|->| Accepted(N,I,W)\n| | | | | | | | | | | | | | | | | | !! Detect collision & recover\n| | |<---X--X--X--X->|->| Accepted(N+1,I,W)\n|<-X--X Response(W)\n| | | | | | | | |\n\n## Message flow: Fast Paxos with uncoordinated recovery, collapsed roles\n(merged Acceptor/Learner roles)\nClient Servers\n| | | | | | | | X->|->|->| Any(N,I,Recovery)\n| | | | | | | | | | | | !! Concurrent conflicting proposals\n| | | | | | !! received in different order\n| | | | | | !! by the Servers\n| X?|-?|-?|-?| Accept!(N,I,V)\nX---?|-?|-?|-?| Accept!(N,I,W)\n| | | | | | | | | | | | !! Servers disagree on value\n| | X<>X->|->| Accepted(N,I,V)\n| | |<-|<-X<>X Accepted(N,I,W)\n| | | | | | | | | | | | !! Detect collision & recover\n| | X<>X<>X<>X Accepted(N+1,I,W)\n|<---X--X--X--X Response(W)\n| | | | | |\n\n# Generalized Paxos\nGeneralized consensus explores the relationship between the operations of the replicated state machine and the consensus protocol that implements it.\nThe main discovery involves optimizations of Paxos when conflicting proposals could be applied in any order.\ni.e., when the proposed operations are [commutative operations](https://bliptext.com/articles/commutative) for the state machine.\nIn such cases, the conflicting operations can both be accepted, avoiding the delays required for resolving conflicts and re-proposing the rejected operations.\nThis concept is further generalized into ever-growing sequences of commutative operations, some of which are known to be stable (and thus may be executed).\nThe 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.\n\n## Example\nIn 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.\nNote that in this table indicates operations which are non-commutative.\nA possible sequence of operations :\n<1:Read(A), 2:Read(B), 3:Write(B), 4:Read(B), 5:Read(A), 6:Write(A)>\nSince commutes with both and , one possible permutation equivalent to the previous order is the following:\n<1:Read(A), 2:Read(B), 5:Read(A), 3:Write(B), 4:Read(B), 6:Write(A)>\nIn practice, a commute occurs only when operations are proposed concurrently.\n# [13px | upload.wikimedia.org/wikipedia/commons/4/48/Dark///Red///x.svg]\n\n## Message flow: Generalized Paxos (example)\nResponses not shown.\nNote: message abbreviations differ from previous message flows due to specifics of the protocol, see for a full discussion.\nClient Leader Acceptor Learner\n| | | | | | | | !! New Leader Begins Round\n| | X->|->|->| | | Prepare(N)\n| | |<-X- X- X | | Promise(N,null)\n| | X->|->|->| | | Phase2Start(N,null)\n| | | | | | | | | | | | | | | | !! Concurrent commuting proposals\n| X--- ?|-?|-?|-?| | | Propose(ReadA)\nX---?|-?|-?|-?| | | Propose(ReadB)\n| | X--X-->|->| Accepted(N,)\n| | ||->| Accepted(N,)\n| | | | | | | | | | | | | | | | !! No Conflict, both accepted\n| | | | | | | | Stable = \n| | | | | | | | | | | | | | | | !! Concurrent conflicting proposals\nX---?|-?|-?|-?| | | Propose()\n| X?|-?|-?|-?| | | Propose(ReadB)\n| | | | | | | | | | X--X-->|->| Accepted(N, . )\n| | ||->| Accepted(N, . )\n| | | | | | | | | | | | | | | | !! Conflict detected, leader chooses\n| | | | | | | | commutative order:\n| | | | | | | | V = \n| | | | | | | | | | X->|->|->| | | Phase2Start(N+1,V)\n| | |<-X- X- X>|->| Accepted(N+1,V)\n| | | | | | | | Stable = .\n| | | | | | | | \n| | | | | | | | | | | | | | | | !! More conflicting proposals\nX---?|-?|-?|-?| | | Propose(WriteA)\n| X?|-?|-?|-?| | | Propose(ReadA)\n| | | | | | | | | | X--X-->|->| Accepted(N+1, . )\n| | ||->| Accepted(N+1, . )\n| | | | | | | | | | | | | | | | !! Leader chooses order:\n| | | | | | | | W = \n| | | | | | | | | | X->|->|->| | | Phase2Start(N+2,W)\n| | |<-X- X- X>|->| Accepted(N+2,W)\n| | | | | | | | Stable = .\n| | | | | | | | .\n| | | | | | | | \n| | | | | | | |\n\n## Performance\nThe above message flow shows us that Generalized Paxos can leverage operation semantics to avoid collisions when the spontaneous ordering of the network fails.\nThis allows the protocol to be in practice quicker than Fast Paxos.\nHowever, when a collision occurs, Generalized Paxos needs two additional round trips to recover.\nThis situation is illustrated with operations WriteB and ReadB in the above schema.\nIn the general case, such round trips are unavoidable and come from the fact that multiple commands can be accepted during a round.\nThis makes the protocol more expensive than Paxos when conflicts are frequent.\nHopefully two possible refinements of Generalized Paxos are possible to improve recovery time.\n\n# Byzantine Paxos\nPaxos may also be extended to support arbitrary failures of the participants, including lying, fabrication of messages, collusion with other participants, selective non-participation, etc.\nThese types of failures are called [Byzantine failures](https://bliptext.com/articles/byzantine-fault-tolerance), after the solution popularized by Lamport.\nByzantine Paxos introduced by Castro and [Liskov](https://bliptext.com/articles/barbara-liskov) adds an extra message (Verify) which acts to distribute knowledge and verify the actions of the other processors:\n\n## Message flow: Byzantine Multi-Paxos, steady state\nClient Proposer Acceptor Learner\n| | | | | | | X>| | | | | | Request\n| X->|->|->| | | Accept!(N,I,V)\n| | X<>X<>X | | Verify(N,I,V) - BROADCAST\n| |<-X--X--X-->|->| Accepted(N,V)\n|<-X--X Response(V)\n| | | | | | | Fast Byzantine Paxos introduced by Martin and [Alvisi](https://bliptext.com/articles/lorenzo-alvisi) removes this extra delay, since the client sends commands directly to the Acceptors.\nNote the Accepted message in Fast Byzantine Paxos is sent to all Acceptors and all Learners, while Fast Paxos sends Accepted messages only to Learners):\n\n## Message flow: Fast Byzantine Multi-Paxos, steady state\nClient Acceptor Learner\n| | | | | | X->|->|->| | | Accept!(N,I,V)\n| X<>X<>X-->|->| Accepted(N,I,V) - BROADCAST\n|<---X--X Response(V)\n| | | | | |\nThe failure scenario is the same for both protocols; Each Learner waits to receive F+1 identical messages from different Acceptors.\nIf 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:\n\n## Message flow: Fast Byzantine Multi-Paxos, failure\nClient Acceptor Learner\n| | | ! | | !! One Acceptor is faulty\nX->|->|->!\n| | Accept!(N,I,V)\n| X<>X<>X-->|->| Accepted(N,I,{V,W}) - BROADCAST\n| | | ! | | !! Learners receive 2 different commands\n| | | ! | | !! Correct Acceptors notice error and choose\n| X<>X<>X-->|->| Accepted(N,I,V) - BROADCAST\n|<---X--X Response(V)\n| | | ! | |\n\n# Adapting Paxos for RDMA networks\nWith the emergence of very high speed reliable datacenter networks that support remote DMA ([RDMA](https://bliptext.com/articles/remote-direct-memory-access)), 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.\nThe Derecho C++ Paxos library is an open-source Paxos implementation that explores this option.\nDerecho 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.\nThe 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.\nSo doing enables Derecho to sustain the full bidirectional RDMA data rate.\nIn 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.\nIn high-speed RDMA networks, even small delays can be large enough to prevent utilization of the full potential bandwidth.\n\n# Production use of Paxos","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T07:57:18.115Z","updated_at":"2025-01-26T07:57:18.115Z","search_vector":"'comput':2 'paxo':1 'scienc':3","search_content":" \n \n\n# \n**Paxos** is a family of protocols for solving [consensus](https://bliptext.com/articles/consensus-computer-science) in a network of unreliable or fallible processors.\nConsensus is the process of agreeing on one result among a group of participants.\nThis problem becomes difficult when the participants or their communications may experience failures.\nConsensus protocols are the basis for the [state machine replication](https://bliptext.com/articles/state-machine-replication) approach to [distributed computing](https://bliptext.com/articles/distributed-computing), as suggested by [Leslie Lamport](https://bliptext.com/articles/leslie-lamport) and surveyed by [Fred Schneider](https://bliptext.com/articles/fred-b-schneider).\nState machine replication is a technique for converting an algorithm into a fault-tolerant, distributed implementation.\nAd-hoc techniques may leave important cases of failures unresolved.\nThe principled approach proposed by Lamport et al. ensures all cases are handled safely.\nThe [Paxos](https://bliptext.com/articles/paxi) protocol was first submitted in 1989 and named after a fictional legislative consensus system used on the [Paxos](https://bliptext.com/articles/paxi) island in Greece, where Lamport wrote that the parliament had to function \"even though legislators continually wandered in and out of the parliamentary Chamber\".\nIt was later published as a journal article in 1998.\nThe 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.\nAlthough no deterministic fault-tolerant consensus protocol can guarantee progress in an asynchronous network (a [result](https://bliptext.com/articles/consensus-computer-science) proved in a paper by [Fischer](https://bliptext.com/articles/michael-j-fischer), [Lynch](https://bliptext.com/articles/nancy-lynch) and [Paterson](https://bliptext.com/articles/mike-paterson) ), Paxos guarantees safety (consistency), and the conditions that could prevent it from making progress are difficult to provoke.\nPaxos is usually used where durability is required (for example, to replicate a file or a [database](https://bliptext.com/articles/database)), in which the amount of durable state could be large.\nThe protocol attempts to make progress even during periods when some bounded number of replicas are unresponsive.\nThere is also a mechanism to drop a permanently failed replica or to add a new replica.\n\n# History\nThe topic predates the protocol.\nIn 1988, [Lynch](https://bliptext.com/articles/nancy-lynch), [Dwork](https://bliptext.com/articles/cynthia-dwork) and [Stockmeyer](https://bliptext.com/articles/larry-stockmeyer) had demonstrated the solvability of consensus in a broad family of \"partially synchronous\" systems.\nPaxos has strong similarities to a protocol used for agreement in \"viewstamped replication\", first published by Oki and [Liskov](https://bliptext.com/articles/barbara-liskov) in 1988, in the context of distributed transactions.\nNotwithstanding 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.\nReconfigurable state machines have strong ties to prior work on reliable group multicast protocols that support dynamic group membership, for example [Birman](https://bliptext.com/articles/ken-birman)'s work in 1985 and 1987 on the [virtually synchronous](https://bliptext.com/articles/virtual-synchrony) [gbcast](https://bliptext.com/articles/gbcast) protocol.\nHowever, gbcast is unusual in supporting durability and addressing partitioning failures.\nMost reliable multicast protocols lack these properties, which are required for implementations of the state machine replication model.\nThis point is elaborated in a paper by [Lamport](https://bliptext.com/articles/leslie-lamport), [Malkhi](https://bliptext.com/articles/dahlia-malkhi) and Zhou.\nPaxos protocols are members of a theoretical class of solutions to a problem formalized as uniform agreement with crash failures.\nLower bounds for this problem have been proved by [Keidar](https://bliptext.com/articles/idit-keidar) and Shraer.\nDerecho, a C++ software library for cloud-scale state machine replication, offers a Paxos protocol that has been integrated with self-managed virtually synchronous membership.\nThis protocol matches the Keidar and Shraer optimality bounds, and maps efficiently to modern [remote DMA (RDMA)](https://bliptext.com/articles/remote-direct-memory-access) datacenter hardware (but uses TCP if RDMA is not available).\n\n# Assumptions\nIn order to simplify the presentation of Paxos, the following assumptions and definitions are made explicit.\nTechniques to broaden the applicability are known in the literature, and are not covered in this article.\n\n## Processors\n\n## Network\n\n## Number of processors\nIn general, a consensus algorithm can make progress using n=2F+1 processors, despite the simultaneous failure of any F processors: in other words, the number of non-faulty processes must be strictly greater than the number of faulty processes.\nHowever, using reconfiguration, a protocol may be employed which survives any number of total failures as long as no more than F fail simultaneously.\nFor Paxos protocols, these reconfigurations can be handled as separate configurations.\n\n# Safety and liveness properties\nIn 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:\nNote that Paxos is not guaranteed to terminate, and thus does not have the liveness property.\nThis 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.\nAs Paxos's point is to ensure fault tolerance and it guarantees safety, it cannot also guarantee liveness.\n\n# Typical deployment\nIn most deployments of Paxos, each participating process acts in three roles: Proposer, Acceptor and Learner.\nThis reduces the message complexity significantly, without sacrificing correctness:\nIn Paxos, clients send commands to a leader.\nDuring normal operation, the leader receives a client's command, assigns it a new command number i, and then begins the ith instance of the consensus algorithm by sending messages to a set of acceptor processes.\nBy merging roles, the protocol \"collapses\" into an efficient client-master-replica style deployment, typical of the database community.\nThe benefit of the Paxos protocols (including implementations with merged roles) is the guarantee of its [safety properties](https://bliptext.com/articles/).\nA typical implementation's message flow is covered in the section [Multi-Paxos](https://bliptext.com/articles/).\n\n# Basic Paxos\nThis protocol is the most basic of the Paxos family.\nEach \"instance\" (or \"execution\") of the basic Paxos protocol decides on a single output value.\nThe protocol proceeds over several rounds.\nA 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).\nSee below the description of the phases.\nRemember that we assume an asynchronous model, so e.g. a processor may be in one phase while another processor may be in another.\n\n## Phase 1\n\n### Phase 1a: Prepare\n\n### Phase 1b: Promise\n\n## Phase 2\n\n### Phase 2a: Accept\nThis Accept message should be interpreted as a \"request\", as in \"Accept this proposal, please!\".\n\n### Phase 2b: Accepted\nNote that consensus is achieved when a majority of Acceptors accept the same identifier number (rather than the same value).\nBecause 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.\nThese facts result in a few counter-intuitive scenarios that do not impact correctness: [Acceptors can accept multiple values](https://bliptext.com/articles/paxos-computer-science), [a value may achieve a majority across Acceptors (with different identifiers) only to later be changed](https://bliptext.com/articles/paxos-computer-science), and [Acceptors may continue to accept proposals after an identifier has achieved a majority](https://bliptext.com/articles/paxos-computer-science).\nHowever, the Paxos protocol guarantees that consensus is permanent and the chosen value is immutable.\n\n## When rounds fail\n\n## Paxos can be used to select a leader\nNotice that a Proposer in Paxos could propose \"I am the leader\" (or, for example, \"Proposer X is the leader\").\nBecause 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.\nThis satisfies the needs of leader election because there is a single node believing it is the leader and a single node known to be the leader at all times.\n\n## Graphic representation of the flow of messages in the basic Paxos\nThe following diagrams represent several cases/situations of the application of the Basic Paxos protocol.\nSome cases show how the Basic Paxos protocol copes with the failure of certain (redundant) components of the distributed system.\nNote 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).\n\n### Basic Paxos without failures\nIn 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).\nThis diagram represents the case of a first round, which is successful (i.e. no process in the network fails).\nHere, V is the last of (Va, Vb, Vc).\n# [frame | upload.wikimedia.org/wikipedia/commons/5/57/Basic///Paxos///without///failures.svg]\n\n### Error cases in basic Paxos\nThe simplest error cases are the failure of an Acceptor (when a Quorum of Acceptors remains alive) and failure of a redundant Learner.\nIn 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).\n\n### Basic Paxos when an Acceptor fails\nIn the following diagram, one of the Acceptors in the Quorum fails, so the Quorum size becomes 2.\nIn this case, the Basic Paxos protocol still succeeds.\nClient Proposer Acceptor Learner\n| | | | | | | X>| | | | | | Request\n| X->|->|->| | | Prepare(1)\n| | | | ! | | !! FAIL !!\n| | |->| | | Accept!(1,V)\n| | |->| Accepted(1,V)\n| | | | | | | Request\n| X->|->|->| | | Prepare(1)\n| | |->|->| | | Accept!(1,V)\n| | |->| Accepted(1,V)\n| | | | | | ! !! FAIL !!\n| | | | | | | Request\n| X>|->|->| | | Prepare(1)\n| | | | | | | Accept!(1,V)\n| ! | | | | | | | | | | | | !! NEW LEADER !!\n| X->|->|->| | | Prepare(2)\n| | |->|->| | | Accept!(2,V)\n| | |->| Accepted(2,V)\n| | | | | | | Request\n| X>|->|->| | | Prepare(1)\n| | |->|->| | | Prepare(2)\n| | |->|->| | | Prepare(2)\n| | |->|->| | | Prepare(3)\n| | |->|->| | | Accept!(2,Va)\n| | | |->|->| | | Prepare(4)\n| | | |->|->| | | Accept!(3,Vb)\n| | |->|->| | | Prepare(1)\n| | | | | | Accept!(1,V1)\n| | X>|->| Accepted(1,V1)\n! | | | | | | !! FAIL !!\n| | | | | | X->|->| | | Prepare(2)\n| |->|->| | | Accept!(2,V2)\n| |->| Accepted(2,V2)\n| | | | | |\n\n### Basic Paxos where a multi-identifier majority is insufficient\nIn the following case, one Proposer achieves acceptance of value V1 of one Acceptor before failing.\nA new Proposer prepares the Acceptors that never accepted V1, allowing it to propose V2.\nThis Proposer is able to get one Acceptor to accept V2 before failing.\nA new Proposer finds a majority that includes the Acceptor that has accepted V1, and must propose it.\nThe Proposer manages to get two Acceptors to accept it before failing.\nAt this point, three Acceptors have accepted V1, but not for the same identifier.\nFinally, a new Proposer prepares the majority that has not seen the largest accepted identifier.\nThe value associated with the largest identifier in that majority is V2, so it must propose it.\nThis Proposer then gets all Acceptors to accept V2, achieving consensus.\nProposer Acceptor Learner\n| | | | | | | | | | | X--->|->|->|->|->| | | Prepare(1)\n| | | | | | | | Accept!(1,V1)\n| | | | X-->|->| Accepted(1,V1)\n! | | | | | | | | | | !! FAIL !!\n| | | | | | | | | | X--->|->|->|->| | | Prepare(2)\n| | | | | | | Accept!(2,V2)\n| | | | X--->|->| Accepted(2,V2)\n! | | | | | | | | | !! FAIL !!\n| | | | | | | | | X->|>|->|->| | | Prepare(3)\n| |->| | | | Accept!(3,V1)\n| | | | X--X->|->| Accepted(3,V1)\n! | | | | | | | | !! FAIL !!\n| | | | | | | | X-->|->|--->| | | Prepare(4)\n| |->|->|->|->| | | Accept!(4,V2)\n| X--X--X--X--X-->|->| Accepted(4,V2)\n\n### Basic Paxos where new Proposers cannot change an existing consensus\nIn the following case, one Proposer achieves acceptance of value V1 of two Acceptors before failing.\nA 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.\nAs such, even though the Proposer doesn't see the existing consensus, the Proposer's only option is to propose the value already agreed upon.\nNew Proposers can continually increase the identifier to restart the process, but the consensus can never be changed.\nProposer Acceptor Learner\n| | | | | | | X->|->|->| | | Prepare(1)\n| |->| | | | Accept!(1,V1)\n| | X--X->|->| Accepted(1,V1)\n! | | | | | | !! FAIL !!\n| | | | | | X->|->| | | Prepare(2)\n| |->|->| | | Accept!(2,V1)\n| |->| Accepted(2,V1)\n| | | | | |\n\n# Multi-Paxos\nA typical deployment of Paxos requires a continuous stream of agreed values acting as commands to a distributed state machine.\nIf each command is the result of a single instance of the [Basic Paxos](https://bliptext.com/articles/) protocol, a significant amount of overhead would result.\nIf the leader is relatively stable, phase 1 becomes unnecessary.\nThus, it is possible to skip phase 1 for future instances of the protocol with the same leader.\nTo achieve this, the round number I is included along with each value which is incremented in each round by the same Leader.\nMulti-Paxos reduces the failure-free message delay (proposal to learning) from 4 delays to 2 delays.\n\n## Graphic representation of the flow of messages in the Multi-Paxos\n\n### Multi-Paxos without failures\nIn the following diagram, only one instance (or \"execution\") of the basic Paxos protocol, with an initial Leader (a Proposer), is shown.\nNote that a Multi-Paxos consists of several instances of the basic Paxos protocol.\nClient Proposer Acceptor Learner\n| | | | | | | --- First Request ---\nX>| | | | | | Request\n| X->|->|->| | | Prepare(N)\n| | |->|->| | | Accept!(N,I,V)\n| | |->| Accepted(N,I,V)\n| | | | | | | Request\n| X->|->|->| | | Accept!(N,I+1,W)\n| | |->| Accepted(N,I+1,W)\n| | | | Request\n| X->|->| Prepare(N)\n| | |->| Accept!(N, I, Vn)\n| X<>X<>X Accepted(N, I) | | | | Request\n| X->|->| Accept!(N,I+1,W)\n| X<>X<>X Accepted(N,I+1)\n| |->|->| | | Accept!(N,I,V)\nX--->|->|--->| | Accept!(N,I,V) (re-transmit, include Aux)\nX--->|->| | | Accept!(N,I+1,W) (Aux not participating)\n\n# Fast Paxos\nFast Paxos generalizes [Basic Paxos](https://bliptext.com/articles/) to reduce end-to-end message delays.\nIn Basic Paxos, the message delay from client request to learning is 3 message delays.\nFast 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.\nIntuitively, if the leader has no value to propose, then a client could send an Accept! message to the Acceptors directly.\nThe Acceptors would respond as in Basic Paxos, sending Accepted messages to the leader and every Learner achieving two message delays from Client to Learner.\nIf the leader detects a collision, it resolves the collision by sending Accept! messages for a new round which are Accepted as usual.\nThis coordinated recovery technique requires four message delays from Client to Learner.\nThe final optimization occurs when the leader specifies a recovery technique in advance, allowing the Acceptors to perform the collision recovery themselves.\nThus, uncoordinated collision recovery can occur in three message delays (and only two message delays if all Learners are also Acceptors).\n\n## Message flow: Fast Paxos, non-conflicting\nClient Leader Acceptor Learner\n| | | | | | | | | X->|->|->|->| | | Any(N,I,Recovery)\n| | | | | | | | X--->|->|->|->| | | Accept!(N,I,W)\n| | |->| Accepted(N,I,W)\n| |->|->|->| Accepted(N,I,V)\n| | | |->| Accepted(N,I,W)\n| | | | | | | | | | | | | | | | | | !! Detect collision & recover\n| | X--->|->|->|->| | | Accept!(N+1,I,W)\n| | | |->| Accepted(N+1,I,W)\n| |->|->|->| | | Any(N,I,Recovery)\n| | | | | | | | | | | | | | | | | | !! Concurrent conflicting proposals\n| | | | | | | | | !! received in different order\n| | | | | | | | | !! by the Acceptors\n| X--?|-?|-?|-?| | | Accept!(N,I,V)\nX-?|-?|-?|-?| | | Accept!(N,I,W)\n| | | | | | | | | | | | | | | | | | !! Acceptors disagree on value\n| | | |->|->|->| Accepted(N,I,V)\n| | | |->| Accepted(N,I,W)\n| | | | | | | | | | | | | | | | | | !! Detect collision & recover\n| | | |->| Accepted(N+1,I,W)\n| |->|->| Any(N,I,Recovery)\n| | | | | | | | | | | | !! Concurrent conflicting proposals\n| | | | | | !! received in different order\n| | | | | | !! by the Servers\n| X?|-?|-?|-?| Accept!(N,I,V)\nX---?|-?|-?|-?| Accept!(N,I,W)\n| | | | | | | | | | | | !! Servers disagree on value\n| | X<>X->|->| Accepted(N,I,V)\n| | | X Accepted(N,I,W)\n| | | | | | | | | | | | !! Detect collision & recover\n| | X<>X<>X<>X Accepted(N+1,I,W)\n| \nSince commutes with both and , one possible permutation equivalent to the previous order is the following:\n \nIn practice, a commute occurs only when operations are proposed concurrently.\n# [13px | upload.wikimedia.org/wikipedia/commons/4/48/Dark///Red///x.svg]\n\n## Message flow: Generalized Paxos (example)\nResponses not shown.\nNote: message abbreviations differ from previous message flows due to specifics of the protocol, see for a full discussion.\nClient Leader Acceptor Learner\n| | | | | | | | !! New Leader Begins Round\n| | X->|->|->| | | Prepare(N)\n| | | |->|->| | | Phase2Start(N,null)\n| | | | | | | | | | | | | | | | !! Concurrent commuting proposals\n| X--- ?|-?|-?|-?| | | Propose(ReadA)\nX---?|-?|-?|-?| | | Propose(ReadB)\n| | X--X-->|->| Accepted(N, )\n| | | |->| Accepted(N, )\n| | | | | | | | | | | | | | | | !! No Conflict, both accepted\n| | | | | | | | Stable = \n| | | | | | | | | | | | | | | | !! Concurrent conflicting proposals\nX---?|-?|-?|-?| | | Propose( )\n| X?|-?|-?|-?| | | Propose(ReadB)\n| | | | | | | | | | X--X-->|->| Accepted(N, . )\n| | | |->| Accepted(N, . )\n| | | | | | | | | | | | | | | | !! Conflict detected, leader chooses\n| | | | | | | | commutative order:\n| | | | | | | | V = \n| | | | | | | | | | X->|->|->| | | Phase2Start(N+1,V)\n| | | |->| Accepted(N+1,V)\n| | | | | | | | Stable = .\n| | | | | | | | \n| | | | | | | | | | | | | | | | !! More conflicting proposals\nX---?|-?|-?|-?| | | Propose(WriteA)\n| X?|-?|-?|-?| | | Propose(ReadA)\n| | | | | | | | | | X--X-->|->| Accepted(N+1, . )\n| | | |->| Accepted(N+1, . )\n| | | | | | | | | | | | | | | | !! Leader chooses order:\n| | | | | | | | W = \n| | | | | | | | | | X->|->|->| | | Phase2Start(N+2,W)\n| | | |->| Accepted(N+2,W)\n| | | | | | | | Stable = .\n| | | | | | | | .\n| | | | | | | | \n| | | | | | | |\n\n## Performance\nThe above message flow shows us that Generalized Paxos can leverage operation semantics to avoid collisions when the spontaneous ordering of the network fails.\nThis allows the protocol to be in practice quicker than Fast Paxos.\nHowever, when a collision occurs, Generalized Paxos needs two additional round trips to recover.\nThis situation is illustrated with operations WriteB and ReadB in the above schema.\nIn the general case, such round trips are unavoidable and come from the fact that multiple commands can be accepted during a round.\nThis makes the protocol more expensive than Paxos when conflicts are frequent.\nHopefully two possible refinements of Generalized Paxos are possible to improve recovery time.\n\n# Byzantine Paxos\nPaxos may also be extended to support arbitrary failures of the participants, including lying, fabrication of messages, collusion with other participants, selective non-participation, etc.\nThese types of failures are called [Byzantine failures](https://bliptext.com/articles/byzantine-fault-tolerance), after the solution popularized by Lamport.\nByzantine Paxos introduced by Castro and [Liskov](https://bliptext.com/articles/barbara-liskov) adds an extra message (Verify) which acts to distribute knowledge and verify the actions of the other processors:\n\n## Message flow: Byzantine Multi-Paxos, steady state\nClient Proposer Acceptor Learner\n| | | | | | | X>| | | | | | Request\n| X->|->|->| | | Accept!(N,I,V)\n| | X<>X<>X | | Verify(N,I,V) - BROADCAST\n| | |->| Accepted(N,V)\n| |->|->| | | Accept!(N,I,V)\n| X<>X<>X-->|->| Accepted(N,I,V) - BROADCAST\n| |->|->!\n| | Accept!(N,I,V)\n| X<>X<>X-->|->| Accepted(N,I,{V,W}) - BROADCAST\n| | | ! | | !! Learners receive 2 different commands\n| | | ! | | !! Correct Acceptors notice error and choose\n| X<>X<>X-->|->| Accepted(N,I,V) - BROADCAST\n|<---X--X Response(V)\n| | | ! | |\n\n# Adapting Paxos for RDMA networks\nWith the emergence of very high speed reliable datacenter networks that support remote DMA ([RDMA](https://bliptext.com/articles/remote-direct-memory-access)), 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.\nThe Derecho C++ Paxos library is an open-source Paxos implementation that explores this option.\nDerecho 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.\nThe 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.\nSo doing enables Derecho to sustain the full bidirectional RDMA data rate.\nIn 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.\nIn high-speed RDMA networks, even small delays can be large enough to prevent utilization of the full potential bandwidth.\n\n# Production use of Paxos","revisionCount":0},"hasMore":false,"nextCursor":null}