（接上篇《The Part-Time Parliament》译文（上））

2.2 初步协议

Paxos居民从条件B1(b)-B3(b)保持为真的需求派生出了初步协议，b是已经进行或者正在进行的所有投票的集合。协议指出了集合b是如何变化的，但从未明确计算过集合b。Paxos居民认为b只能由神观察到，凡人可能永远不知道。

每次投票由一个牧师发起，牧师选择投票编号，法令以及法定人数。法定人数中的每个牧师决定是否在本次投票中进行投票。发起者如何选择投票的编号，法令和法定人数，以及法定人数中的牧师决定是否进行投票的规则由B1(b)-B3(b)的需求决定。

为了满足B1，每次投票必须有一个独一无二的编号。牧师通过记住（在分类账上做笔记）先前提出的投票，可以容易地避免在两次不同的投票中提出相同的编号。为了避免不同的牧师用相同的编号提出投票，投票编号集合根据牧师的不同进行分区。虽然不知道这是如何实现的，但是一种显而易见的方法是让一个投票编号由一个整数和一个牧师对组成，使用字典序。如果在Paxos的字母表里，Γ在Λ之前出现，那么：

(13, Γρα ˘ ι) < (13, Λινσ ˘ ι) < (15, Γρα ˘ ι)

任何情况下，有一个没有边界的投票编号集合供每个牧师使用。

为了满足条件B2，每次投票的法定人数包含牧师中的µαδζ∂ωριτ˘ισΦτ。一开始，µαδζ∂ωριτ˘ισΦτ表示大多数牧师。随后，观察到胖的牧师很少移动，相比瘦的牧师，在议会厅待更多的时间。所以，µαδζ∂ωριτ˘ισΦτ表示全部体重超过所有牧师总体重一半的牧师集合，而不是简单的大多数牧师。一些瘦的牧师抱怨这不公平，用基于牧师出勤记录的象征性体重来替代真实的体重。选择µαδζ∂ωριτ˘ισΦτ的要求是任何两个包括µαδζ∂ωριτ˘ισΦτ的牧师集合至少有一个共同牧师。为了满足条件B2，牧师初始化投票B时，将B(qrm)定义为一个大多数集合。

条件B3要求，如果MaxVote(ba,Q,b)(dec)不为BLANK，那么法定人数为Q,投票编号为ba的法令一定为MaxVote(ba,Q,b)(dec)。如果MaxVote(ba,Q,b)(dec)等于BLANK，那么投票可以选择任何法令。为了满足B3(b)，在初始化法定人数为Q投票编号为ba的投票之前，一个牧师p必须知道MaxVote(ba,Q,b)(dec)。因此，p必须找到Q中每个牧师q的MaxVote(ba, q, b)。MaxVote(ba, q, b)表示在q投的所有的选票中，投票编号低于ba的最大投票编号的选票；如果q在投票编号低于ba的投票中没有进行任何投票，那么MaxVote(ba, q, b)为null(q)。

牧师p通过信息交换从q那获取MaxVote(ba, q, b)。因此，初步协议中p发起一次投票的前两步为：

(1) 牧师p选择一个新的投票编号ba，并且发送一个NextBallot(ba)消息给某个牧师集合。

(2) 牧师q收到NextBallot(ba)消息之后，发送一个LastVote(ba,v)消息给p作为响应。v是q投出的编号比ba小的最大投票编号的选票，如果q没有在任何比ba小的投票编号的投票中没有进行过投票，那么v为null选票null(q)

牧师q需要利用分类账后面的笔记，回忆他之前所投的选票。

q发送的LastVote(ba,v)消息中，v等于MaxVote(ba, q, b)。但如果新的投票被初始化，牧师投出选票，那么投票集合b会改变。既然牧师p在选择法令的时候，打算将v作为MaxVote(ba, q, b)的值，那么为了保证条件B3(b)满足，在q发送LastVote(ba,v)消息之后，保证MaxVote(ba, q, b)不改变是十分必要的。为了防止MaxVote(ba, q, b)改变，q不能在投票编号在v(bal)和ba之间的投票中进行投票。通过发送LastVote(ba,v)消息，q承诺不会进行这样的投票。（为了保证承诺，q需要在分类账上纪录必要的信息）

初步协议（由牧师p在第一步开始）接下来的两步如下：

(3) 在收到某个大多数集合Q中的所有牧师发送的LastVote(ba,v)消息之后，牧师p使用投票编号b，法定人数Q以及法令d初始化一次新的投票，d满足条件B3。然后p将这次投票记在他分类账的背面，并且给Q中的每个牧师发送一个BeginBallot(ba, d)消息。

(4) 在收到BeginBallot(ba, d)消息之后，牧师q决定是否在投票编号为ba的投票中进行投票。（如果投票会违反他在其他投票中发送LastVote(b’, v’)信息时所做的承诺，他将不会投票。）如果q决定进行投票，他会发送一个Voted(ba, q)消息给p，并且在分类账的背面纪录下此次选票。

步骤(3)的执行意味着在b中加入了投票B，B(bal) = ba, B(qrm) = Q, B(vot) = （在这次投票中还没有人进行了投票），B(dec) = d。在步骤(4)，如果牧师q决定在这次投票中进行投票，那么执行步骤4就是通过将q加入B(vot)中来改变投票集合b。

即使投票不会违反之前所做的承诺，牧师在步骤(4)中也可以不进行投票。事实上，在协议中的所有步骤都是可选的。例如，牧师q可以忽略NextBallot(b)消息，不执行步骤2。牧师响应的失败可能会妨碍进展，但是不会造成任何不一致性，因为不会使条件B1(b)-B3(b)不满足。既然没有收到消息的唯一影响就是妨碍一个行为发生，那么信息丢失也不会造成不一致性。因此，即使牧师离开会议厅或者信息丢失，协议也能保证一致性。

重复收到一个信息可能使一个行为被重复执行。除了在步骤(3)，执行多次行为不产生影响。例如，在步骤4发送几个Voted(ba, q)消息和发送一个消息有相同的效果。当执行步骤3时，我们使用分类账后面的笔记来防止步骤3被重复执行。因此，即使信使传送同一消息几次，一致性条件仍能保持。

步骤(1)-(4)描述了初始化一次投票以及对该投票进行投票的完整协议。剩下的就是决定投票的结果，并当法令被选中时，宣布出来。当且仅当法定人数中的每个牧师都投票了，才能说一次投票是成功的。一次成功投票的法令就是会议选中的法令。剩下的协议如下：

(5) 如果p从Q（投票编号为ba的投票的法定人数）中的每个牧师q那都收到了一个Voted(ba, q)消息，那么他将d（投票的法令）写入他的分类账并给每个牧师发送Success(d)信息。

(6) 在收到Success(d)信息之后，牧师在他的分类账中写入法令d。

步骤(1)-(6)描述了如何进行单次投票。初步协议允许任何牧师在任何时间初始化一次新的投票。每一步都满足条件B1(b)-B3(b)，所以整个协议也满足这些条件。既然只有在投票成功时，牧师才将法令写入分类账中，定理1意味着牧师的分类账是一致的。初步协议没有处理进展问题。

在步骤(3)中，如果条件B3决定法令d，那么有可能法令已经写入某个牧师的分类账中。该牧师不需要在法定人数Q中，他可能已经离开了议会厅。因此，如果步骤3在选择d上允许任何更大的自由，一致性将不能得到保证。

2.3 基本协议

在初步协议中，牧师必须要纪录：（i）他初始化的投票的编号；（ii）他投的每个选票；（iii）已经发送的每个LastVote信息。对于忙碌的牧师来说，追踪所有的消息是很困难的。Paxos居民因此通过限制初步协议得到了更具有实际意义的基本协议，在基本协议中，每个牧师p只需在他分类账的背面纪录下列信息：

lastTried[p] ：p尝试发起的最后一次投票的投票编号；如果没有，为负无穷。

prevVote[p] ：p在他所投的最大编号的投票中，投出的选票；如果没有投过票，为负无穷。

nextBal[p] ：p发送的LastVote(ba,v)信息中，最大的ba；如果他还没有发送LastVote信息，为负无穷。

初步协议的步骤(1)-(6)描述了牧师p如何发起一次投票。初步协议允许p并发执行任意数量的投票。在基本协议中，p一次只能执行一次投票——投票编号为lastTried[p]。在p初始化这次投票之后，他会忽视之前初始化的投票的有关信息。牧师p将所有有关投票编号为lastTried[p]的投票的进展信息写在一张纸上。如果这张纸丢了，他将停止执行这次投票。

在初步协议中，牧师q发送LastVote(ba,v)信息表示他的承诺：不在投票编号为v(bal)和ba之间的投票中进行投票。在基本协议中，它表示一个更强的承诺——不在投票编号小于ba的投票中进行投票。这个更强的承诺或许使他不能在基本协议的第(4)步进行投票，但是在初步协议中是可以投票的。然而，既然初步协议总是给p不进行投票的自由，基本协议不需要他做任何初步协议不允许的事。

初步协议的(1)-(6)步变成了如下所示的基本协议的(1)-(6)步：（p进行一次投票所需的所有信息，除了lastTried[p]，prevVote[p]和nextBal[p]，都记在一张纸上）

(1) 牧师p选择一个比lastTried[p]大的新的投票编号ba，将lastTried[p]设置为ba，并且给某个牧师集合发送NextBallot(ba)消息。

(2) 牧师q从p处收到NextBallot(ba)消息并且ba>nextBal[q]时，q将nextBal[q]设置为ba，并且给p发送LastVote(ba, v)消息，v等于prevVote[q]。（如果banextBal[q]，那么就忽略NextBallot(ba)消息）

(3) 在从某个大多数集合Q中的每个牧师那都收到LastVote(ba, v)（ba= lastTried[p]）消息之后，牧师p初始化一次新投票，投票编号为ba，法定人数为Q，法令为d，d的选择满足条件B3。p给Q中所有牧师接着发送BeginBallot(ba, d)消息。

(4) 在牧师q收到BeginBallot(ba, d)消息并且ba= nextBal[q]，q在投票编号为ba的投票中投出选票，将prevVote[q]设置为此选票，并且给p发送一个Voted(ba, q)消息。（如果banextBal[q]，那么就忽略BeginBallot(ba, d)消息）

(5) 如果p从Q（投票编号为ba的投票中的法定人数）中的每个牧师q那都收到了Voted(ba, q)消息，并且ba = lastTried[p]，那么p将d（投票的法令）写入分类账中并给每个牧师发送Success(d)消息。

(6) 在收到Success(d)消息之后，牧师在分类账中记下法令d。

基本协议是初步协议的限制版本，意味着基本协议允许的每个行为在初步协议中都被允许。既然初步协议满足一致性条件，基本协议也满足一致性条件。就像初步协议，基本协议不需要采取任何行为，所以它不解决进展问题。

从B1-B3中派生出基本协议，所以很明显满足一致性条件。然而，一些类似“很明显”的古代智慧有时是错的，多疑的Paxos公民需要一个更严谨的证据。Paxos数学家将协议满足一致性条件的证明放在了附录中。

2.4 完整的会议协议

基本协议满足了一致性，但是并不能确保进程。因为它只描述了牧师可能做什么，并没有要求一定做什么。完整的会议协议和基本协议一样包括进行一次投票同样的6个步骤。为了帮助实现进展，完整的协议包括明显的附加要求——牧师尽快执行协议的2-6步。然而，为了满足进展需求，必须要有某个牧师执行步骤1，发起一次投票。完整的会议协议关键在于决定牧师应该什么时候发起一次投票。

不发起投票当然会妨碍进展。然而，发起太多投票也会妨碍进展。如果ba比任何其他的投票编号都大，那么在步骤(2)中牧师q接收NextBallot(ba)消息会引出一个承诺，阻止他在步骤(4)中为之前发起的投票进行投票。因此，新投票的初始化可能会阻止之前发起的投票成功。如果在之前的投票有机会成功之前，用不断增加的投票编号持续发起新投票，将会导致不能取得进展。

实现进展需要新投票被初始化直到有一次投票成功，但是新投票不要经常被初始化。为了发展完整的协议，Paxos居民首先得知道信使传送消息，牧师进行响应所需的时间。他们得出不离开会议厅的信使总能在4分钟之内传达一个消息，会议厅的牧师总能在收到消息的7分钟之内进行响应。因此，如果p发送一个消息给q，q发送响应给p时，p和q都在会议厅内，那么在没有信使离开会议厅的情况下，p将在22分钟内收到这个响应。（牧师p在7分钟之内发送信息，q在4分钟之内收到信息，在7分钟之内做出响应，响应将在4分钟之内到达p处。）

假定只有单个牧师p正在发起投票，并且他通过在协议的第(1)步给每个牧师发送消息来发起投票。如果p在大多数牧师都在会议厅的时候发起投票，那么他可以在发起投票的22分钟之内开始执行步骤3，在另外22分钟之内执行步骤5。如果他不能在这些时间内执行这些步骤，那么或者在p发起投票之后，有牧师或信使离开了会议厅或者另一个牧师之前已经发起了一个更大编号的投票（在p成为发起投票的唯一牧师之前）。为了处理后者的可能性，p必须知道其他牧师使用的比lastTried[p]更大的投票编号。可以通过扩展协议来实现，可以要求如果牧师q从p处收到了NextBallot(ba)消息或者BeginBallot(ba, d)消息，并且b<nextBal[q]，那么他会给p发送一个包括nextBal[q]的消息。牧师p将用一个更大的投票编号来初始化一次新的投票。

依然假定只有单个牧师p正在发起投票，假定他需要发起一次新投票当且仅当: (i)p在之前的22分钟之内没有成功执行步骤3或步骤5，或者(ii)他知道另一个牧师已经初始化一个更大编号的投票。如果p锁了会议厅的门并且大多数牧师在里面，那么一个法令将会在99分钟之内被通过并且纪录在会议厅所有牧师的分类账上。（可能是p用22分钟的时间开始下一次投票，又一个22分钟的时间发现另一个牧师已经发起了一个更大编号的投票，然后55分钟的时间来完成步骤1-6，投票成功。）因此，如果只有单个不离开会议厅的牧师在发起投票，进程条件将会被满足。

完整的协议因此包括一个程序来选择单个牧师（被称为总统），来发起投票。在大多数政府中，选择一个总统是个很困难的问题。然而，因为大多数政府要求任何时候都只有一位总统，这才是困难的原因。例如，在美国，如果某些人认为布什当选总统，而另一些人认为杜卡基斯当选总统，就会产生混乱。因为他们其中一个或许会决定将一个提案写进法律而另一个决定否决该提案。然而，在Paxos的会议中，有多个总统或许只会阻碍进展，不会造成不一致性。对于满足进展条件的完整的协议，选择总统的方法只需满足下列总统选择条件：

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

如果满足总统选择要求，那么完整的协议将会有属性——如果大多数的牧师在会议厅并且T+99分钟内没有人进入或者离开会议厅，那么T+99分钟之后，会议厅中的每个牧师的分类账上，都会有一个法令。

Paxos居民将会议厅中所有牧师的姓名按字典序进行排序，谁的姓名在最后，谁就被选为总统，尽管我们不知道为什么要这么做。如果会议厅中的牧师至少每T-11分钟一次给其他每个牧师发送包含他姓名的消息，总统选择条件将会被满足，并且，当且仅当牧师T分钟内没有收到来自“更高姓名”的牧师的消息，他将会认为他自己是总统。

完整的会议协议是从基本协议中得来，并要求牧师及时执行2-6步，加入了选择总统（总统负责发起投票）的方法，并且要求总统在适当的时候（T分钟后）发起投票。协议的许多细节还不知道。本文已经描述过选择总统的简单方法以及决定什么时候总统应该发起一次新投票的简单方法，但是他们明显不是Paxos居民使用的方法。本文所列的方法需要总统在已经选好法令之后，依然发起投票，以此来确保刚刚进入会议厅的牧师知道选中的法令。很明显，有更好的方法使牧师知道已经选中的法令。同样的，在选择总统的过程中，每个牧师也可以发送lastTried[p]的值给其他的牧师，使得总统在第一次发起投票时，选择一个足够大的投票编号。

Paxos居民意识到任何实现进展条件的协议一定要包括测量时间的流逝。上述给出的选择总统以及发起投票的协议可以通过设置计时器以及当超时发生时，做出相应的行为（假定计时器完美准确），很容易被制定为精确的算法。更进一步的分析显示，这样的协议可以在计时器的精度有界的情况下起作用。Paxos熟练的技工可以构建合适的沙漏计时器。

在Paxos数学家的深思熟虑下，大家相信，他们一定找出了满足总统选择条件的最佳的算法。我们只能希望这个算法在对于Paxos小岛的进一步研究中被发现。

（剩下内容在《The Part-Time Parliament》译文（下）中）