The Part-Time Parliament

论文地址：The Part-Time Parliament – Lamport ’90/’98

这是由总共10篇组成的关于共识的系列文章的第2部分。

这家论文的来龙去脉很深。最初提交于1990年，当时的研究人员似乎并不重视它，因为它的表现是一个寓言，并未能欣赏我们今天所知的Paxos算法的基本贡献。又过了8年，论文才最终发表。见兰波特在其出版物页122号文件下对该故事的描述。就我个人而言，我觉得这是一种非常有效的形式，可以帮助主题看起来不那么吓人。毕竟，Paxos因难以理解和实现而臭名昭著——每一点都有帮助。Paxos是当今众多重要分布式系统（例如Google的大多数大型系统）的核心，或者说是其灵感来源。这是一种我希望能在这种形式下给你一种味道的纸张-强烈建议仔细阅读原稿。

这一幕发生在爱琴海的帕克索斯岛，忙碌的立法者不得不在贸易和政治义务之间折腾，因此只能兼职履行议会的职责。

兼职议会的管理问题与当今容错分布式系统所面临的问题有着显著的对应关系，在这种系统中，立法者对应于过程，而离开议会则对应于失败。因此，帕克森的解决方案可能会引起计算机科学家的一些兴趣。我在这里介绍了Paxos议会协议的简短历史，然后对其与分布式系统的相关性进行了更简短的讨论。

第一个LAMPORT描述了一个基础问题，一个会议必须在一个法令上达成一致。然后，这将扩展到通过多项法令的连续议会。最后讨论了一系列的优化和增强。所有这些协议的上下文如下：

帕克森议会要求分类账的一致性（其中规定了法令），这意味着没有两个分类账可以包含相互矛盾的信息。为了不通过任何法令来满足这一要求，它们还要求取得进展：

如果立法会议员过半数在会议厅，而在足够长的时间内没有人进入或离开会议厅，则会通过立法会议员在会议厅提出的任何法令，而通过的每一项法令都会出现在会议厅每一位立法会议员的名册上。

立法者得到沙漏计时器来测量时间的流逝。不幸的是，他们议会会议厅的音响效果很差，所以只能通过信使进行交流。

一个信使可以指望不口齿不清的信息，但他可能会忘记他已经传递了一个信息，并再次传递。像他们所服务的立法者一样，信使们只把他们的一部分时间用于议会职责。信使可能会离开会议厅去做一些生意，可能在传递信息之前要进行六个月的航行。他甚至可能永远离开，在这种情况下，信息永远不会被传递…。当他们留在会议厅时，信使及时传递信息，立法者对他们收到的任何信息都迅速作出反应。

单一政令会议
单一法令是通过一系列投票选出的。每一张选票都与一组被称为法定人数的牧师联系在一起，每个牧师可以选择投赞成票或弃权票。只有在达到法定人数的每位牧师投票时，投票才能成功。

一组选票上的三个基本条件足以表明一致同意，而且有可能取得进展。

每一张选票都有唯一的票号
每两张选票的数量至少有一位牧师是相同的
如果一个或多个神父在一次投票的法定人数中以较低票数投票，则在本次投票中考虑的法令受到以下限制：让E为神父已投票的较低票数的集合，让R为E中票数最高的集合。本次投票的法令必须是与R的法令相同。
根据这些规则可以推断，如果一组选票中的任何一张B是成功的，那么以后的任何一张B的选票都是为同一个法令而进行的，因此任何两张成功的选票都必须为同一个法令而进行。一个简单的矛盾证明了这一点，一个脚注将使读者对如何写一个21世纪的证明微笑：

帕克森数学家总是对重要的定理提供精心的、结构化的证明。他们不像现代数学家那样老练，他们可以省略许多细节，写出段落式的证明，从不出错。

如果有足够的牧师在会议厅，就有可能在保持这些规则的同时进行一次成功的投票。虽然这不能保证进展，但它确实表明，基于规则的投票协议不会死锁。

初步方案：
**

• **牧师p选择一个新的b号选票，并发送下一个b号信息给一些牧师
• 牧师q通过发送最后一票（b，v）消息来响应此消息，其中v是q所投的最大票数小于b的选票（如果没有这样的选票，则为空票）。
• 在收到某个多数派Q中每个牧师的最后一次投票（b，v）信息后，牧师发起一次新的投票，编号为b，quorum Q，和d号令。选择d号令是为了满足第三条规则。他把选票记录在账本的背面，并把一个beginbalot（b，d）信息发给Q中的每个牧师。
• 在收到beginbalot（b，d）消息后，牧师q决定是否投票。投票不是强制性的，但是如果这样做会违反他为其他投票发送的最后一次投票（b’，d’）信息，牧师就不能投票。如果投票，他会向p发送一条投票（b，q）消息，并将投票记录在他的分类账中。
• 如果p收到了来自q中每个牧师的投票（b，q）消息，那么他会在他的分类账中写入d，并将成功（d）消息发送给q中的每个牧师。
• 当牧师收到一条成功的消息时，他会在他的账本上输入d号令。

然后对这个协议进行了一个改进，称为基本协议，它减少了每个牧师需要保留的信息量。尤其是，牧师只需记录：

• 他试图发起的最后一次投票的数目
• 他所投的最高票数的选票
• 他最后一次投票（b，v）的最大票数b

基本协议是初步协议的一个受限版本，这意味着基本协议允许的每一个操作也由初步协议允许。由于初步方案满足一致性条件，基本方案也满足该条件。与初步议定书一样，基本议定书不要求采取任何行动，因此不涉及进展问题。

为了确保进展，必须选出一名牧师，叫总统开始投票。总统选举的标准是：

如果没有人进入或离开会议室，那么在T分钟后，会议室里只有一位牧师会认为自己是总统。

实现这一目标的一种方法是选择名字按字母顺序排在最后的牧师，每个牧师至少每T（信息往返时间）分钟向会议室中的所有其他牧师广播一次他们的名字。如果一个牧师在T分钟内没有收到一个更高的牧师的信息，他就认为自己是总统。

从基本协议中获得完整的议会协议，要求牧师立即执行步骤2-6，添加选择发起投票的主席的方法，并要求主席在适当的时间发起投票。协议的许多细节尚不清楚。我已经描述了选择总统和决定总统何时开始新的投票的简单方法，但它们无疑不是帕索斯使用的方法。

多法令议会
议会需要通过一系列法令，而不是仅仅通过一项法令。

从逻辑上讲，议会议定书为每一个法令编号使用了一个完整的议会议定书的单独实例。然而，在所有这些情况下都选出了一位总统，他只执行了一次议定书的前两个步骤。

当一位新总统当选时，如果他的账本在其他牧师之后，就把他丢失的法令的细节发给他。账本上的任何剩余缺口，如果当时在密室的牧师无法填补（因为所有参与传递这些编号法令的牧师都已离开密室），则由一项特别的“无效”法令（“2月底是国家橄榄日”）填补。

议会议定书的一致性和进展性直接来自于它所衍生的议会议定书的相应性质。据我们所知，帕克森一家从来不费心写一份对议会议定书的精确描述，因为它很容易从议会议定书中衍生出来。

我们知道，当议会开会时，没有牧师进出会议厅，在收到通过法令的请求时，采取了以下步骤：

• 总统向法定人数中的每一位成员发了一封Beginbalot电报
• 法定人数中的每一位立法委员都向总统发了一份经过表决的电文
• 总统向每一位立法者发出了成功的信息。

假设议会由N名立法者组成，法定人数约为N/2，则总共有3条信息延迟和约3N条信息。此外，如果议会很忙，总统将把一项法令的beginbalot电文与前一项法令的成功电文结合起来，每项法令总共只有2N条电文。

观察、优化和增强
（这里省略了很多细节，详见全文）。

在选举新总统时，最好不要选一个长期不在会议室的人，因为他的账本上有很多事情要补上
账本可以压缩以避免过长
立法者可以将裁决委托给官僚，官僚在租赁的基础上拥有决策权
普通公民需要一种了解法律的方法，“如果一次调查先于第二次调查，那么第二次调查不能揭示比第一次调查更早的法律状况。”确保这一点的简单方法是为每一次调查通过一项法令。

对每一项调查通过一项法令很快就被证明太麻烦了。Paxons认识到，如果他们通过改变preces的解释来削弱单调性条件，那么一种更简单的方法是可能的。他们决定，为了使一个事件先于另一个事件，第一个事件不仅必须在更早的时间发生，而且必须能够对第二个事件产生因果影响……通过在所有商业交易和查询中使用法令编号满足较弱的单调性条件。

与计算机科学的关系
帕克森议会的协议提供了另一种实现任意状态机的方法。立法者的法律手册对应于机器状态，而通过一项法令对应于执行一项国家机器命令。与早期算法相比，该算法的鲁棒性更低，成本更低。它不能容忍任意的、恶意的失败，也不能保证有限的时间响应。然而，尽管任何数量的进程和通信路径（良性的）失败，一致性仍然保持。Paxon算法适用于对可靠性要求不高的系统，而这些系统无法证明极为容错的实时实现的代价是合理的。