Paxos，是一个久负盛名的分布式系统一致性算法[协议]，其作者Leslie Lamport更因在分布式系统中的贡献获颁2013年的图灵奖、2014被选为ACM Fellow。这些都是计算机科学领域无上的荣誉。

Paxos算法本身其实并不复杂[虽然网上很多人认为其晦涩难懂]，算法难以理解的地方在于在设计这套算法的来龙去脉和其正确性的论证过程。换句话说，这套算法的流程不难理解，这套算法怎么设计出来的以及为什么这么好用的原因才是最难理解的。

这里插一句关于Paxos的念法，Paxos[Greek: Παξοί, pronounced Paksi in English]又名Paxi是希腊西南部一个风景如画的小岛。Paxos算法作者Lamport关于命名问题，这样解释道:I thought, and still think, that Paxos is an important algorithm. Inspired by my success at popularizing the consensus problem by describing it with Byzantine generals, I decided to cast the algorithm in terms of a parliament on an ancient Greek island. Leo Guibas suggested the name Paxos for the island.

为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题[Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息]；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。

先用Lamport说的这个例子解释Paxos算法流程，同时维基百科也是用这个例子：

有A1, A2, A3, A4, A5 5位议员，就税率问题进行决议，采用少数服从多数的机制，而且每个议员会直接同意他第一个收到的草案。每两位议员会有一个专门的信使负责彼此传递消息。议员A1决定将税率定为10%,因此它向所有人发出一个草案。这个草案的内容是：

现有的税率是什么？如果没有决定，则建议将其定为10%。时间：本届议会第3年3月15日；提案者：A1。

然后由专门负责传递给 A2, A3, A4, A5 4位议员消息的信使传给他们。最理想的情况是，所有信使安全抵达，然后4为议员批准了这项议题，然后信息回到A1。

我已收到你的提案，没有异议，并等待最终批准。

当A1议员等到其中两个信使到达的时候，他就收到了2份同意书，算上自己超过半数，那么他就会公开宣布，并由信使传达给各位议员：

税率已定为10%，新的提案不得再讨论本问题。

在上述情况，全体议员都同意这个草案，其实这就是我们之前文章介绍的2PC（二阶段提交）机制。A1为coordinator，A2-A5为cohort。所不同者，在于A1之后到了两份同意书达到多数后就宣布确定消息，而在2PC中，必须所有人都同意才可以（当然这个不是这么简单，但是在确定机制上是有这样的分别）。

现在在同一天的时间里，A5议员也提出一个草案：

现有的税率是什么？如果没有决定，则建议将其定为20%。时间：本届议会第3年3月15日；提案者：A5。

现在A1和A5同一天内发送了草案，并由各自的信使送达其他议员。A1的草案将由4位信使送到A2-A5那里。现在，负责A2和A3的信使将草案顺利送达，负责A4和A5的信使则不上班。A5的草案则顺利的送至A3和A4手中。现在, A1, A2, A3收到了A1的提案; A3, A4, A5收到了A5的提案。按照协议, A1, A2, A4, A5将接受他们收到的提案，信使将拿着同意书各自回到A1和A5。此时A1和A5手中各有2份同意书，而A3拥有决定性的一票。

这里例子又分了三种情况，

情况一

A1的信使到达A3，A3同意A1的议案，而A5的信使正好在返程当天到了轮休的日子，所以A1获得绝对多数后，让信使告诉议员，

税率已定为10%，新的提案不得再讨论本问题。

而过了好久A3又收到了A5的信使，但是之前的草案已经获得通过。所以A5得提议被否决，信使会带着A3的回复，回到A5。

税率已在之前的投票中定为10%，不得发起类似草案。

更有可能的是A5已经知道了之前的草案，因为A1和A5之间的信使已经传递了此项消息，只不过A3和A5之间的信使当时在放假。当然如果A1和A5之间的信使放了更长时间的假，那么这个回复就会重要一些，因为A5议员已经失联很久了。

情况二

依然假设A1的提案先送到A3处，但是这次A5的信使不是放假了，只是中途耽搁了一会。这次, A3依然会将”接受”回复给A1。但是在决议公开发布之前它又收到了A5的提案。这时协议有两种处理方式：

如果A5是个大人物

按照传统应该由谁先到谁获得同意回复，现在看来两份提案的时间一样（本届议会第3年3月15日）。只不过他已经回复了A1，但是A5是个惹不起的大人物。于是A3回复：

我已收到您的提案，等待最终批准，但是您之前有人提出将税率定为10%，请明察。

于是, A1和A5都收到了足够的回复。这时关于税率问题就有两个提案在同时进行。但是A5知道之前有人提出税率为10%。根据协议先到先得的策略，于是A1和A5都会向全体议员广播：

税率已定为10%，新的提案不得再讨论本问题。

A5是个无足轻重的小人物

这时A3不再理会他, A1不久后就会广播税率定为10%。

情况三

在这个情况中，我们将看见，根据提案的时间及提案者的权势[在分布系统中，是节点的重要性，优先级]决定是否应答是有意义的。在这里，时间和提案者的权势就构成了给提案编号的依据。

这样的编号符合”任何两个提案之间构成偏序”的要求。

A1和A5同样提出上述提案，这时A1可以正常联系A2和A3; A5也可以正常联系这两个人。

这次A2先收到A1的提案; A3则先收到A5的提案。A5更有权势。在这种情况下，已经回答A1的A2发现有比A1更有权势的A5提出了税率20%的新提案，于是回复A5说：

我已收到您的提案，等待最终批准。

而回复了A5的A3发现新的提案者A1是个小人物，不予理会。 A1没有达到多数，A5达到了，于是A5将主持投票，决议的内容是A5提出的税率20%。

如果A3决定平等地对待每一位议员，对A1做出”你之前有人提出将税率定为20%”的回复，则将造成混乱。这种情况下A1和A5都将试图主持投票并群发消息，但是这次两份提案的内容不同。

这种情况下, A3若对A1进行回复，只能说：

有更大的人物关注此事，请等待他做出决定。

另外，在这种情况下, A4与外界失去了联系。等到他恢复联系，并需要得知税率情况时，他（在最简单的协议中）将提出一个提案：

现有的税率是什么？如果没有决定，则建议将其定为15%。时间：本届议会第3年4月1日；提案者：A4

这时，（在最简单的协议中）其他议员将会回复：

税率已在之前的投票中定为20%，不得再提出此项草案!

此例子描述了大部分Paxos的流程。后续会介绍整个算法流程。

本文参考https://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95和http://www.solinx.co/archives/403