在计算机科学领域，Paxos算法以其难以理解而臭名昭著。我必须在我的分布式系统课上学习Paxos算法。我甚至通过将Leslie Lamport的TLA+翻译成Python来实现它。但我直到很久以后才明白这一点。
现在我对帕克索斯有了比以前更好的理解，我想向其他人解释一下。不是因为我想帮助别人，而是因为我发现解释事情是在我自己的理解中找到盲点的一个很好的方法。
那么，我们从哪里开始呢？就我个人而言，我不喜欢从一步一步地分解算法开始，然后证明这些步骤为什么会做它们声称的事情的解释。相反，我更喜欢从算法试图解决的问题开始，然后与读者一起迭代地提出解决方案。所以这就是我要做的。现在你明白标题了吧。
小免责声明：本文中使用的词汇表与Paxos通常使用的词汇表不同。我只是挑了一些最有意义的作为我的叙述。
分布式共识问题非常有用，所以读者可能不需要受到激励。在这里，我将简单地说明问题。
有一组座席(让我们称他们为$\sc{client}s$)想要从他们的选择中选择一个号码。任何数字都可以，只要每个人都同意相同的数字。
所有代理(包括但不限于$\sc{client}s$，因为我们稍后将添加更多类型的代理)都表现良好。这意味着他们都忠实地执行规定的算法，不要恶意欺骗其他特工。(如果你喜欢行话：拜占庭式的失败不会发生。)。
代理可以通过相互发送消息来相互通信，但它们发送给对方的消息可能需要任意长时间才能到达目的地，并且可能会丢失(但永远不会更改)。
代理也可能失败。但是，失败相当于发送到该代理/从该代理发送的所有消息都将永远丢失。所以，不管我们有没有这个假设，都不会改变我们想出的算法。
此外，为了不使事情复杂化，我们在本文中只解决了单轮共识问题，这意味着作为此算法的输出，所有$\sc{client}$都将获得他们达成一致的单个数字。
当试图解决像这样的复杂问题时，从简化问题开始通常是个好主意。首先，让我们忽略完全可靠的需要。
如果我们抛开可靠性不谈，应该很容易得出一个非常简单的解决方案：我们添加一个代理(让我们称其为$\sc{COUNTOR}$)。$\sc{CLIENTS}$在$\sc{Proposal}(client_i，x)$消息中将他们选择的任何数字发送到$\sc{COUNTOR}$，其中$x$是$i$-TH$\sc{CLIENT}$建议的数字。$\sc{协调器}$选择任意建议(例如，$x&39；$)，并将此决定通知其他$\sc{client}s$。具体地说，$\sc{协调器}$将用$\sc{SELECTED}(x'；)$消息回复它已接收和将接收的所有$\sc{建议}(\ldots)$消息。
如果我们假设没有消息丢失，那么很容易看到每个$\sc{client}$都会有一个数字。因为只选择了一个数字，所以他们都会得到相同的数字。
也很容易看出为什么这个解决方案不切实际：它有一个单点故障。一旦单数$\sc{COUNTOR}$失败，就无法取得进一步的进展。
当然，更多的$\sc{coorator}s$将消除单点故障。但是，如果存在多个$\sc{协调器}$，则它们可能会单独做出不同的决定，从而导致$\sc{client}$存在分歧。
如果我们让$\sc{协调员}的$在他们之间达成协议，然后再响应，会怎么样？但是等等，这听起来不是很耳熟吗？让一组代理达成协议，这正是我们添加$\sc{协调员}$来解决的问题。我们只是把问题循环起来了。
让我们退后一步。有没有办法让客户端在不让$\sc{协调员}的$相互通信的情况下达成协议？
换句话说，在$\sc{协调器}$的决策中，是否有确定性算法可以挑选出对消息丢失具有健壮性的特定算法？
这听起来可能很难，但实际上很简单：选择得到$\sc{协调员}$一半以上支持的决定。
不可能有两个决策同时有超过一半的$\sc{COHORIOR}$支持它们；如果一个决策没有那么多$\sc{COHORIOR}$支持它，它似乎不会因为消息丢失而获得更多的支持$\sc{COUNTOR}$。
由于此方法类似于多数票，因此让我们从现在开始调用$\sc{COUNTOR}$Decisions$\sc{VOTE}(coord_i，x)$，其中$x$是$i$-TH$\sc{COUNTOR}$选择的数字。每个$\sc{协调器}$都有一个投票权，因为他们每个人只做出一个决定。
显然，我们的解决方案不可能无限可靠。如果$\sc{协调员}$的一半以上出现故障，则永远不会达到多数。但是这已经比我们的第一个解决方案好很多了，而且可靠性随着$\sc{COUNTOR}$的数量而增加。所以我们就说它足够好了。
遗憾的是，这个解决方案实际上并不管用：可能根本不会有多数！例如，有可能其中三个提案各获得三分之一的选票。在那种情况下，我们会陷入僵局。
首先，需要让$\sc{COUNTOR}%s$知道重试。否则，因为每个$\sc{协调员}$只有一次投票，所以即使$\sc{客户端}$重试，他们也无法再次投票。
为此，我们将尝试ID附加到所有发送的消息。即$\sc{Proposal}(Client_i，x)$变为$\sc{Proposal}(\#尝试，Client_i，x)$，依此类推。$\sc{client}$每次重试时，它都会将$\#ATTENT$增加到它已知的最大$\#ATTENT$+1。$\sc{COUNTOR}s$应该只响应具有最新$\#ATTENT$的消息。
有两个客户。他们提出了他们的数字，$\sc{协调员}$对他们进行了投票，所有人都同意了一个数字，$x_1$，一切都很好。但是，所有$\sc{VOTE}(\ldots)$消息在发送到$CLIENT_2$的过程中丢失，而$CLIENT_1$则正常接收所有消息。此时，$CLIENT_1$思想$x_1$是数字，但$CLIENT_2$继续重试。$\sc{协调员}%s$再次投票，获得$x_2$。这一次，发送到$CLIENT_1$的所有消息都丢失了。
这里有一个重要的见解。每当$\sc{协调器}$(例如$coord_i$)发出$\sc{VOTE}(\ldots，coord_i，x)$时，某些$\sc{客户端}$就有可能采用$x$。如果$coord_i$曾经发出两个不同$x$的投票，则某些$\sc{client}$可能会不同意。
换句话说，一旦$\sc{协调员}$透露了它的投票，它就必须坚持它。
这似乎与我们的尝试背道而驰：如果$\sc{协调员}的$不能更改他们的投票，重试的意义何在？僵局将是永远的僵局。
看起来我们用这种投票方式走进了死胡同。问题似乎源于$\sc{协调员}的$必须致力于他们的投票这一事实。
让我们来探讨一下这个想法。比方说，$\sc{协调器}s$现在可以发送$\sc{尝试性}\sc{投票}(\#尝试，coord_i，x)$消息，以试探性地投票给$x$。
暂定投票不会直接导致$\sc{客户}$之间的协议，这是正确的，但它可以向我们显示何时在$\sc{协调员}$之间形成了多数。
一旦$\sc{client}$获得多数暂定投票，它就可以向$\sc{协调员}s$发送消息以请求实际投票。(让我们称此消息为$\sc{请}\sc{投票}(\#尝试，客户端_I)$)。直观地说，$\sc{协调员}s$必须在实际投票中与他们的暂定投票进行相同的投票。
如果一切顺利，我们将获得多数票并达成协议。如果没有多数，协调员甚至不会开始投票，所以他们可以自由改变主意。因此，$\sc{client}s$可能会开始另一次尝试，但可能会有不同的结果。
如果事情进展不顺利怎么办？如果$\sc{请}\sc{VOTE}$消息没有被某些$\sc{COUNTOR}$接收到怎么办？在这种情况下，某些$\sc{COUNTOR}$将会投票，并且他们的决定无法更改。也就是说，在随后的所有尝试中，这些$\sc{协调员}$将始终投票给他们所投的票，无论它是试探性投票还是实际投票。但这并不会给我们带来问题。暂定投票占多数，现在我们巩固了部分暂定投票。至少还有一种方法可以让我们在下一轮投票中获得多数：每个人都投和本轮一样的票。我们可以在未来的所有回合中归纳地证明这一点。
由此，我们可以大致了解算法是如何工作的：随着尝试的进行，越来越多的$\sc{协调员}的$开始决定他们将致力于哪个数字，同时确保仍然可以达到大多数。最终，当所有的协调人都下定决心后，通过归纳，他们中的大多数人肯定会占多数。从那时起，他们将只向$\sc{client}s$重复广播此决定，直到所有$\sc{client}s$都收到该消息。
让我们理清思路，精简算法的描述，使其易于理解。
首先，有附加到每条消息的$\#尝试$编号。每次进行新的尝试时，此数字都会增加。如果$\sc{client}$看到消息的$\#尝试$大于其最近的$\#尝试$，则它知道已启动新的尝试，因此它将中止当前的尝试并参与较新的尝试。如果$\sc{协调器}$看到消息的$#尝试$小于它所见过的最大$#尝试$，它将知道该消息已过时，因此它将丢弃该消息。
阶段1：$\sc{client}s$每个都将其$\sc{proposal}(\ldots)$发送到$\sc{协调器}s$。$\sc{协调员}%s$回复为$\sc{暂定}\sc{投票}(\ldots，x)$。每个$\sc{client}$都等待临时投票，直到它们达到多数。如果未达到多数，请重试。
阶段2：如果达到多数，$\sc{client}s$发送$\sc{请}\sc{VOTE}$，$\sc{协调员}s$实际投票。他们的实际票数将与他们各自的暂定票数相同。每个$\sc{client}$等待投票，直到它们达到多数，然后采用多数数。
我们的算法看起来确实与官方的Paxos略有不同。首先，特工的名字是不同的。我们所说的$\sc{client}s$，Lamport称为$\sc{proposer}s$；以及$\sc{协调员}s$，$\sc{接受者}s$。
首先，$\sc{协调员}的$don不需要将$\sc{临时}\sc{投票}(\ldots)$发送给每个人，他们只需将其发送到他们同意的$\sc{客户端}$。这样我们就不会让每个$\sc{client}s$同时发送$\sc{请}\sc{VOTE}$，这将是低效的。
之后，我们注意到建议的数字在第一阶段和第二阶段被不必要地多次发送，第一阶段是用来达到多数的，建议的数字在该阶段实际上并不重要。因此，我们从$\sc{Proposal}$中删除$x$；在$\sc{Temposal}\sc{Vote}$中，他们投票给$\sc{Client}$，只将临时投票发送给该$\sc{Clients}$，而不是投票给一个数字。最后，在客户端收到大多数暂定投票后，它会发送$\sc{请}\sc{VOTE}(X)$，因此收到该消息的所有$\sc{COUNTOR}s$都将投票给$x$。当然，如果$\sc{COUNTOR}$已经在上一轮投票，它必须告诉$\sc{CLIENT}$，以便它可以选择已经投票的$x$，否则它的$\sc{请}\sc{VOTE}(X)$将被浪费，因为$\sc{COUNTOR}s$无法改变主意。
(改进后的算法性能略有改善。在我们的算法中，我们只需确保在每次尝试后仍有可能获得多数；在Paxos中，每一轮投票都将投票给相同的数字。)