在计算机科学领域，分布式共识问题非常有用，但是Paxos算法因难以理解而臭名昭著。在分布式系统课程中学习Paxos算法。
那么，从哪里开始呢？就个人而言，这里不以算法的逐步分解开始。相反，从算法尝试解决的问题开始，然后一起反复提出和解决问题。
问题
有一组代理节点（CLIENTs），他们希望在选择的内容中选择一个数字。只要每个人都同意相同的数字，任何数字都可以。
在这里，我们将做出一些假设使这个问题有意义：
- 所有代理节点（包括但不限于 CLIENTs，因为稍后会添加更多类型的代理节点）都按规矩地执行了规定的算法，并且没有恶意尝试欺骗其他代理。（行话：拜占庭式的故障不会发生。）
- 可以通过互相发送消息来相互交谈，但是他们彼此之间发送的消息可能要花费很长时间才能到达目的地，并且可能会丢失（但永远不会改变注意）。
代理也可能“失败”。但是，失败的意思等同于发送到该代理或从该代理发送的所有消息永远丢失。但是，无论是否有此假设，都不会改变算法。
为了不使事情复杂化，本文仅解决“单轮”共识问题，即作为该算法的输出，所有CLIENTs 将获得一个他们同意的数字。
开始尝试解决方案
当尝试解决诸如此类的复杂问题时，通常最好从简化问题入手。
迭代0
首先，不考虑完全可靠。如果将可靠性抛诸脑后，那么很容易想出一个非常简单的解决方案：添加了一个代理（称之为COORDINATOR）。CLIENTS将他们选择的任何号码用PROPOSAL(client【i】,x) 消息发送给COORDINATOR。x是client【i】选择的号码。COORDINATOR选择了任意proposal (say, x'x′)，并告知其他client关于这个决定。具体来说，COORDINATOR 只会回复一个CHOSEN(x′) 给所有的PROPOSAL（…），这些消息PROPOSAL可能已收到或者即将收到。
如果假设没有消息丢失，那么CLIENTS会得到一个数字。而且由于只选择了一个号码，因此它们都将获得相同的号码。
也很容易看出为什么这种解决方案不切实际：它只有一个故障点。一旦单台COORDINATOR故障，无法进一步开展工作。
迭代1
乍看之下，要改善这一点几乎很容易：只需添加更多 COORDINATORs！
当然可以多个 {COORDINATOR} 可以消除单点故障。但是，如果有多个COORDINATORs，他们可能会分别做出不同的决定，从而有分歧。
如果让多个COORDINATOR在回应之前达成共识？但是，等等，这听起来不熟悉吗？有一群代理节点达成协议，这正是添加多个COORDINATORs要解决的事情。我们只是使问题循环。
退一步思考。有没有办法让客户达成协议而无需COORDINATORs互相交流？
换句话说，多个COORDINTORs，是否有确定性算法可以挑选出一种对消息丢失具有鲁棒性的特定算法？
这听起来可能很难，但实际上非常简单：选择由一半以上的COORDINATOR支持的决策。
不会有都超过一半的两个决定 ；如果一个决定没有那么多COORDINATOR s支持它，它似乎没有更多的支持，丢失消息。
这种方法类似于多数投票，我们称之为COORDINATOR的决定VOTE(client【i】,x)，x是第i个COORDINATOR选举出来的。每个COORDINATOR有一个投票权，而且只能做出一个决定。
显然，这种解决方案不能无限可靠。如果超过一半的COORDINATORs失败了，永远不会达到多数。但这已经比第一个解决方案好得多，并且可靠性随着COORDINATORs增加。因此，它足够好。
该解决方案实际上可能并不起作用：根本没有多数！例如，三个提案中的每个提案都有可能获得三分之一的选票。在这种情况下，将会进入僵局。
迭代2
同样，解决方案似乎很简单：如果出现僵局，请重试。
但是话又说回来，事情并不是那么简单。
首先，COORDINATORs需要知道重试。否则，因为每个COORDINATOR只有一票，即使CLIENT重试了也不能在投票。
为此，将所有发送的消息中添加个尝试ID。即PROPOSAL(client【i】,x)变成PROPOSAL(#attempt,clienti,x)。每次CLIENT重试，将#attempt 1。并且只回应最近的讯息 #attempt。
现在好了吗？很不幸的是，不行。考虑这种情况：
有2位客户。他们提出了他们的号码，COORDINATOR对它们进行投票，并全部同意一个数字x1，但是，所有的VOTE（…） 消息在途中丢失了，client2继续重试。COORDINATORs再次投票，并得到 x_2。这次，发送到客户端client1丢包了。
COORDINATOR的两次不同选择x_1和x_2让两个客户不一致。
这里有一个重要的结论。每当一个COORDINATOR，发出一个 VOTE（...，coord_i，x），CLIENT有可能会采用x。如果COORDINATOR 曾经发出过两张不同的票x，CLIENT有可能会不同意。
换句话说，COORDINATOR 已经发送并透露了它的选票，它必须坚持下去。
这似乎与尝试背道而驰： COORDINATORs无法更改投票，重试的目的是什么？僵局将永远是僵局。
看来通过这种投票已陷入僵局。问题出在以下事实：COORDINATORs的投票。
那么，如果引入一种非承诺投票方式呢？
迭代3
继续探索这个想法。COORDINATORs 现在可以发送一个TENTATIVEVOTE(#attempt,coordi,x) 消息，暂时投票 x。
显然，CLIENT无法采用x。那么，这次投票有什么好处呢？
嗯，对，这可以使我们占多数。
暂时的投票不会直接直接导致选择正确的CLIENT，但它可以告诉我们何时COORDINA达成大多数一致。
一旦CLIENT看到多数投票，它可以向COORDINATOR要求进行实际投票。（我们将此消息称为 PLEASEVOTE(#attempt,clienti)）。凭直觉，COORDINATOR必须在实际投票中与他们的临时投票相同。
如果一切顺利，我们将获得多数同意。如果没有多数COORDINATORs甚至都不会开始投票，因此他们可以任意改变主意。所以CLIENTs可能会开始另一次可能有不同结果的尝试。
如果事情进展不顺利怎么办？如果一些COORDINATORs未收到消息PLEASEVOTE消息 ？在这种情况下，COORDINATORs本来可以投票的，他们的决定无法改变。也就是说，在所有后续尝试中，这些COORDINATORs不管投票是临时投票还是实际投票，都会一如既往地投票。但这对我们来说并不构成问题。暂定票中的多数票，现在我们巩固了部分暂定票。我们至少有一种方法可以在下一轮中取得多数席位：每个人的投票都与本轮相同。我们可以在以后的所有回合中归纳证明这一点。
由此，我们可以大致了解算法的功能：随着尝试的进行，越来越多COORDINATORs开始下定决心要承诺的数字，同时确保仍能达到多数。最终，毕竟COORDINATORs已经下定了决心，归纳起来一定是其中的大多数。从那时起，他们将反复将此决定广播给CLIENTs，直到所有 CLIENTs得到了这个信息。
至此，我们有一个有效的算法。
实际算法
让我们整理思路，压缩算法描述，以便于理解。
首先，有#attempt附加到每封邮件所附的号码。每次尝试重新尝试时，此数字都会增加。如果一个 CLIENT看到一条带有#attempt比最近的更大，它知道已经发起了新尝试，因此它将中止当前尝试并参与新尝试。如果一个COORDINATOR看到一条带有#attempt比它曾经见过最大的小，它将知道该消息是过时的，因此它将丢弃该消息。
顺便说一句，让我们描述一次尝试会发生什么。
每次尝试可以分为两个阶段：
- 第1阶段：将CLIENT每个发送其PROPOSAL（…） 到COORDINATORs。COORDINATORs回复TENTATIVEVOTE(…,x)。每个CLIENT等待暂定选票，直到获得多数票为止。如果未达到多数，请重试。
- 阶段2：如果达到多数，则CLIENTs发送PLEASEVOTE，COORDINATORs实际投票。他们的实际票数将与他们各自的暂定票相同。每CLIENT等待投票直到获得多数票，然后采用多数票。
回到Paxos
这里算法确实与官方Paxos有所不同。首先，代理的名称是不同的。我们所说的CLIENTs对应PROPOSERs和LEARNERs，COORDINATORs对应ACCEPTORs.。
除此之外，还存在协议差异。
首先，COORDINATORs 不必发送TENTATIVEVOTE(…) 给所有人，他们只需要将其发送给他同一的CLIENT。这样不会让所有CLIENT 同一时间发送PLEASEVOTE。
之后，在阶段1和阶段2中不必要地多次发送了proposed number。阶段1用于获得多数方，在该阶段中proposed number实际上并不重要。因此，PROPOSAL移除了x，不用投票给一个数字，他们投票给一个CLIENTS，只需将临时投票发送给CLIENTS。最终，在客户获得大多数临时选票后，客户会发送PLEASEVOTE（x），所有 COORDINATORs 得到该消息将投票 XX。当然，如果COORDINATOR已经在上一轮中投票过了，它必须告诉CLIENT选择已经投票的x，否则 PLEASEVOTE（x） 将被浪费，因为COORDINATORs 无法改变主意。
（经过修改的算法具有更好的属性。在我们的算法中，我们只是确保每次尝试后仍然可以实现多数；在Paxos中，每轮COORDINATORs 投票将全部投给相同的数字。）
有了这些小的更改，我们就可以将算法映射回Paxos：
代理节点：
- CLIENT => PROPOSER（提出建议）和 LEARNER（采用结果数）
- COORDINATOR =>ACCEPTOR
消息交互：
- PROPOSAL（＃attempt，client_i） => PREPARE（＃attempt，client_i）
- TENTATIVE（＃attempt，coord_i） => PROMISE}（＃attempt，coord_i）
- PLEASEVOTE（＃attempt，client_i，x） => ACCEPT（＃attempt，client_i，x）
- VOTE（＃attempt，coord_i，x） =>ACCEPTED（＃attempt，coord_i，x）
