这篇文章通过一个有效的例子描述了一个名为Paxos 的分布式一致性算法。

分布式一致性算法用于使一组计算机能够就单个值达成一致，例如通常使用两阶段或三阶段提交做出的提交或回滚决策。只要选择一个值，算法的其他值就没有关系了。

在分布式系统中，这很难，因为机器之间的消息可能会丢失或无限期延迟，或者机器本身可能会发生故障。

Paxos保证节点只会选择单个值（意味着它保证安全），但不保证在大多数节点不可用时能不能去到值

一般的做法

一个Paxos的节点可以采取任何或所有三个角色：proposer，acceptor和learner。

一个proposer提议一个值是需要同意才行的，它发一个包含值的提议给所有的acceptor，acceptor决定是否同意这个值。

每个acceptor独立选择一个值–它可能收到多个来自不同proposer的提议–并将其决定发送给learner，以确定是否已接受任何值。

对于Paxos接受的值，大多数acceptor必须选择相同的值。实际上，单个节点可以承担许多或所有这些角色，但在本节的示例中，每个角色都在一个单独的节点上运行，如下所示。

图1：基本Paxos架构。一些proposer向acceptor提出建议。当acceptor接受一个值时，它会将结果发送给learner节点。

Paxos示例

在标准的Paxos算法中，proposer向acceptor发送两种类型的消息：准备和接受请求。

在该算法的第一阶段，proposer向每个acceptor发送包含建议值v和提议号n的准备请求。

对于其他proposer的提案号，每个proposer的提议号必须是正数的，单调递增的，唯一的，自然的数字。

在下面说明的示例中，有两个proposer，两个都提出准备请求。来自proposer A的请求和来自proposer B的请求首先到达acceptor X和acceptor Y，而来自proposer B的请求首先到达acceptor Z。

图2：proposer A和B各自向每个接受者发送准备请求。在这个例子中，proposer A的请求首先到达接acceptor X和Y，而proposer B的请求首先到达acceptor Z.

如果接收准备请求的acceptor没有看到另一个提议，则acceptor以准备响应作出响应，该准备响应承诺永远不接受具有较低提议编号的另一提议。

这在下面的图3中说明，其显示了每个接受者对他们收到的第一个准备请求的响应。

图3：每个acceptor响应它收到的第一个准备请求消息。

最终，acceptor Z接收proposer A的请求，acceptor X和acceptor Y接收proposer B的请求。

如果acceptor已经看到具有更高提议号的请求，则忽略准备请求，proposer A对acceptor Z的请求就是这种情况。

如果acceptor没有看到更高编号的请求，它再次承诺忽略具有较低提议编号的任何请求，并发回其已接受的编号最高的提议以及该提议的值。

proposer B对acceptor X和acceptor Y的请求就是这种情况，如下图所示：

图4：acceptor Z忽略了proposer A的请求，因为它已经看到了更高编号的提议（4> 2）。acceptor X和Y用他们先前确认的最高请求来响应proposer B的请求，并承诺忽略任何编号较低的提议。

一旦proposer收到大多数acceptor的准备响应，它就可以发出接受请求。

由于proposer A仅收到表明没有先前提案[no previous]的响应，因此它向acceptor发送与初始提案相同的提议编号和值的接受请求（n = 2，v = 8）。

然而，这些请求被每一个acceptor忽略，因为acceptor都承诺不接受的提议号低于请求4（响应准备请求给proposer B）。

proposer B向每个acceptor发送包含其先前使用的提议号（n = 4）的接受请求，并且这个接受请求还包含了在其收到的准备响应消息中与最高提议号相关联的值（v = 8）。

请注意，这不是proposer B最初提出的值，而是它看到的准备响应消息中的最高值。

图5，proposer B发送一个接受请求给每个acceptor,这个请求包含了它之前的提议号(4)和它从[n=2,v=8]中看到的值（8）

如果acceptor收到的接受请求的提议号大于或等于之前它保证的，那么它接受并向每个learner节点发送通知。

当learner发现大多数`acceptor已接受某个值时，Paxos算法会选择这个值，如下所示：

一旦Paxos选择了一个值，与其他proposer的进一步沟通就无法改变这个值。

如果另一个proposer（proposer C）发送的提议号比之前看到的提议号更高，并且具有不同的值（例如，n = 6，v = 7），则每个acceptor都会使用之前的最高提议号进行响应（n = 4，v = 8）。

这要求proposer C发送包含[n = 6，v = 8] 的接受请求，该请求仅确认已经选择的值。此外，如果一些少acceptor还没有选择一个价值，这个过程可以确保他们最终就同一价值达成共识。

Lamport和Baker等人在论文中讨论了对标准Paxos算法的各种效率改进。例如，如果proposer知道它是第一个建议值的话，则准备请求不再是必须的了。

因为这种请求的提议编号为0，如果收到任何更高编号的请求的话，这种请求就会被忽略的。