Paxos

 

需求场景

议会的主要任务是制定部落法令，这些制定的法令必须经过议会通过。一个先进的国会议会将雇佣一个书记来记录议会活动，但在帕克森没有人愿意留在会议室全程当秘书。取而代替的，每个帕克森立法者保管一个帐本，在帐本上，他们记录了按编号顺序的通过的法令，例如立法者Λ˘ινχ∂的帐本有这样一条登记记录：

155: 橄榄税每吨3德拉克马

如果她认为155号法令被议会通过对橄榄税每吨3德拉克马。就在帐本上用擦不掉的墨水写下记录，并且其他登记记录是不能改变生效的。

 

议会程序的首要需求是需要保证帐本的前后一致，意味着不应该存在两个帐本存在不一致的矛盾信息。如果立法者Φισ∂ρ的帐本有这样一条登记记录：

132:灯具必须用橄榄油

那么其他立法者不应该有一条不一致的132号法令的登记记录。但是，如果其他立法者还没有学习到这条法令已经被通过，在他们的帐本里可能就没有这样一条132号法令的登记记录。

 

仅仅保证帐本的一致是不够的，由于可能使得所有帐本空白而变得无法满足需求。有些需求是要保证法令最终通过并记录到帐本中。在现代议会中，立法者之间的分歧阻碍了法令的通过。在相互信任的情况下，帕克森中没有这种情况。帕克森的议员们愿意通过任何提议的法令。但是，他们的兼职性质导致了一个问题。如果一组立法者通过了一条法令：

37: 禁止在寺庙墙壁上绘画

然后退出了议事过程，这时另一组立法者进入议事过程，在不知道刚刚发生了什么的情况下，通过了一条冲突的法令：

37:艺术表达自由的保障

除非有足够多的立法者在会议室里待了足够长的时间，否则进展无法得到保证。

 

问题

•假想

只有给立法者们提供必要的资源，议会程序的要求才能实现。立法者需要一本耐用的羊皮纸作为帐本来记录法令，还需要一支笔以及擦不掉的墨水供应。立法者们离开议事厅后可能忘记做了什么事，因此他将在羊皮纸帐本后面记录笔记以提醒他们重要的议会任务。由一系列还没有改变生效的法令开始，但记录的笔记可以划掉。实现议会程序推进需要立法者们通过简单的沙漏计时以便能够记录走过的时间。

 

立法者们随时带着他们的羊皮纸帐本，以便随时都可以看到这些还没有改变生效的法令以及还没有被划掉的笔记。帐本是用非常好的羊皮纸做的，并且只用来记录重要的事情。立法者们还会在纸条上记录其他的笔记，离开议事厅的时候这种纸条可能会丢失。

 

议事厅的场面是很嘈杂的，无法做演讲。立法者们只能通过信差沟通，并且需要提供储备基金来雇佣需要的尽可能多的信差。信差可以保证不会窜改消息，但是可能忘记已经传递过消息而再次传递。正如立法者们的职责服务，信差们也只花部分时间在议会职责上。信差也可能离开议事厅从事些商业活动，比如在传递消息之前，可能从事个6个月的远航。他也可能永远离开不在议事厅，这种情况下消息将永远传递不出去。

 

尽管立法者和信差们随时都有可能进来或者离开不在议事厅，当在议事厅的时候他们致力于议会活动。当他们留在议事厅的时候，信差们能够及时的传递消息，立法者们能够立即响应接收到的任何消息。

 

帕克森官方记录断定立法者和信差们是勤勤恳恳小心翼翼并且严格遵守议会程序。多数学者都以此为宣传，意在描绘Paxos对其东部邻国的优越性。不诚实的行为，虽然罕见，但也确实存在。然而，因为它从来没有在官方文件中提到过，我们很少有经验来处理如何应对欺诈的立法议会或信使。在第3.3.5章节中讨论了哪些情况没有被考虑到。

 

单一法令议会

•故事

•故事中的人物角色

<!--[if ppt]-->•<!--[endif]-->

故事

虚构了一个帕克森议会，这个帕克森议会由早期的一个祭司宗教会议逐渐演变形成，每19年召开一次，选举并颁布一条法令。几个世纪以来，会议通过惯例程序选举并颁布法令，所有祭司必须出席。但随着商业日渐繁荣，议会进行时祭司们在议事厅开始变得闲散起来。最终，原来选举并颁布法令的惯例程序变得无效，最终会议无法选举并颁布法令。为了防止历史灾难再次出现，帕克森宗教领袖请数学家制订一套选举并颁布法令的有效程序。这套程序的场景和假设条件跟国会目前情况差不多，除了维护一系列的法令，国会部落的书记还是希望维护最多一条法令。最终法令选举颁布程序将在这里描述；议会程序将在第3章描述。

<!--[if ppt]-->•<!--[endif]-->

数学家最终推导出的法令选举颁布程序有好几步。首先。。。

 

单一法令议会

•数学理论

议会的法令通过一系列编号的选票选举，每张选票在单一法令上代表着一个公民投票。对于每张选票，祭司只能选择选举通过或者拒绝通过，和每张选票（是否选举通过）息息相关的是一个被称为达到祭司投票选举通过的法定人数的集合。只有当达到法定人数的祭司选举通过，选票才被投票通过。原则上，一张选票B由以下四部分组成（除非另有规定，该集合意味着是个有限集）

 

Bdec   表示一部法令（将被通过的法令）

Bqrm    表示一个非空集的祭司集合（达到法定人数选举该法令的祭司）

Bvot    表示祭司集合（这些参加投票选举法令的祭司）

Bbal  表示选票编号

只有当Bqrm 是Bvot 的子集的时候，该选票才被认为被选举通过，因此，只有达到法定人数的祭司成员选举通过该选票才被通过。

 

选票编号从一个无线有序数字集合中选择。如果B’bal > Bbal ,那么就认为选票B’比B提交得晚。但是，选票编号对于选票的选举投票执行并不意味着什么；晚提交的选票实际上也可以比先提交的选票先执行选票投票。

<!--[if ppt]-->•<!--[endif]-->

 

单一法令议会

帕克森数学家对选票集B的定义了三个条件，并且指出如果满足这些条件，就能保证一致性并尽可能向前推进。前两个条件很简单，可以通俗的描述如下：

 

B1(B)  选票集B中的每张选票都有一个选票编号。

B2(B)  选票集B中达到法定人数的祭司投票的任何两张选票，至少有一个祭司都投票了这两张选票。

 

第三个条件比较复杂。帕克森的一个原稿如下，比较乱，这么陈述的。

 

B3(B)  选票集B中每张选票B，投票选票B的法定人数中的任何祭司投了选票集B中之前的一张选票，那么选票B就作为最新的投票的判决成为法令B。

 

图1用以辅助说明这种难以理解的文字描述，通过一个由5个祭司A, B, Γ, ∆以及E组成的议会，以及5张选票组成的选票集B来说明条件B3(B)。选票集B包含5张选票，对于每张选票，

 

单一法令议会

 

 

单一法令议会

•准备工作程序

在要求保证B1(B)–B3(B)这几个条件的前提下，帕克森推导出了准备工作程序， B表示所有已经或者将被执行投票的选票集。程序说明了选票集B的变化，但不会明确的预测。只有上帝知道最终选举的投票，其他人根本不知道。

 

祭司初始化每张选票，通过每张选票的编号记录谁投了这张选票，裁定并达到法定人数。达到法定人数的每位祭司决定是否投票选举这张选票。从满足条件B1(B)–B3(B)的需求开始推导，规则决定了祭司如何通过选票编号进行投票，裁定并达到法定人数以及决定是否投票选举一张选票。

 

单一法令议会

 

为了满足条件B1，每个祭司必须接收一个唯一编号。通过在帐本上记笔记记录哪些选票之前已经初始化过，祭司可以很容易的避免使用同一个编号初始化两张不同的选票。为了保证不同的祭司使用同一个编号初始化选票，选票编号集中所有可能的选票编号是在参与投票选举的祭司范围内进行分段。这个怎么做到还没有明确下来，一个显著的方法就是把祭司（编号）和一个整数组成对根据字典顺序来作为选票编号，这样

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

在字母表中Γ出现在Λ的前面。这样在任何情况下，就可以知道每位祭司都有一个供自己使用的选票编号的无限集。

 

 

单一法令议会

 

为了满足条件B2，这里选择祭司中的µαδζ∂ωριτ˘ιστ作为一张选票的法定人数投票。最初，µαδζ∂ωριτ˘ιστ仅仅指简单的多数祭司投票。后来发现，相对那些不认真不怎么重视议会的祭司，那些认真重视议会的祭司很少离开，并且愿意发更多的时间在议事厅，因此，µαδζ∂ωριτ˘ιστ是指那些总的权重大于所有祭司的总权重的一半的祭司投票。当一些不认真不怎么重视议会的祭司抱怨这样不公平的时候，最后根据祭司的出勤记录这种象征性的权重来来替代。对µαδζ∂ωριτ˘ιστ最主要的要求就是任何达到法定人数投票的两张选票，至少有一个祭司都投票了这两张选票。为了满足条件B2，祭司初始化选票B并用Bqrm表示达到法定人数的多数祭司集。

 

 

单一法令议会

 

条件B3要求如果MaxVote(b, Q, B)dec不为空，那么编号为b，达到法定祭司投票人数Q必须令MaxVote(b, Q, B)dec成为法令。如果MaxVote(b, Q, B)dec为空，那么任何选票都可以成为法令。为了保证条件B3(B) ，在使用选票编号b以及达到法定祭司投票人数Q初始化一张新的选票之前，祭司p必须找出MaxVote(b, Q, B)dec。为了做到这个，祭司p必须从Q中的每个祭司中找到MaxVote(b, Q, B)dec。

 

单一法令议会

 

回想到发现最大编号的选票投票MaxVote(b, q, B)小于所有投票中被q投票的选票b ，或者选票的法定投票人数q为空（即q中所有祭司没有投票任何编号了的选票）小于选票b 。祭司p通过交换消息从q中获得MaxVote(b, q, B)。那么，祭司p发起的程序中前两步的单次投票就是：

 

（1）祭司p选择一个新的选票编号b，并且发送一个NextBallot(b)消息给一些祭司。

 

（2）

 

祭司p必须在帐本的后面用笔记记录他之前投了哪张选票。

 

当祭司p发送LastVote(b, v)消息的时候，v等于MaxVote(b, q, B)。

 

 

 

单一法令议会

 

 

•基本程序

在准备程序阶段，祭司必须记录已经初始化好了的每张选票编号(i)，每一个投票提议(ii)以及发送的每个最终投票提议消息。对于忙碌的祭司们，维护这些跟踪信息非常困难。在每个祭司p不得不只在帐本后面维护以下信息的情况下，因此，帕克森限制准备工作程序，以获得更实用的基本程序。

 

lastTried[p]  祭司p尝试初始化的最终投票数，如果没有的话就无限小（−∞）。

prevVote[p]  祭司p投票批准的最大编号的选票，如果还没有投票就无限小（−∞）。

nextBal[p]  祭司p发送的最终投票提议消息LastVote(b, v)的最大值，如果从没发送消息的话就无限小（−∞）。

 

准备工作程序的第1-6步描述了

 

<!--[if ppt]-->•<!--[endif]-->

 

 

 

单一法令议会

 

 

•最终议会程序

基本程序保证了一致性，但是它无法保证任何进展，因为它只规定一个牧师可能做什么，它并没有要求他做什么事情。最终议会程序和基本程序一样由六个步骤组成以执行投票。为了帮助取得进展，它包括了一个明显的额外要求以使牧师尽快的执行步骤2，6的程序。然而，为了满足这一进展情况，必须要求一些牧师执行步骤1以发起一次投票。最终议会程序的关键在于确定一个牧师应该何时发起一个投票。

 

从不发起一次投票肯定会阻碍进展。但是发起太多投票同样会阻碍进展。

 

<!--[if ppt]-->•<!--[endif]-->

 

 

 

多法令议会

 

 

当议会成立，议会程序满足了它的一致性和进展的要求。第3.1和3.2章节描述了最初的议会程序的推导和性能特征。第3.3节讨论了协议的进一步发展演变。

 

 

多法令议会

 

•程序

不再只通过一条法令，帕克森国会不得不需要通过一系列编号的法令。在议会程序中，部落领袖被选举出来了。任何人需要通过一条法令必须先通知部落领袖，部落领袖分配一个编号给法令，并试图通过法令。从逻辑上讲，议会程序为每个法令编号使用一个单独的最终议会程序实例。但是，只能为所有的这些实例选定一个领袖，他只执行程序的前两个步骤一次。

 

从议会程序的关键可以看出，在议会程序中，直到步骤3，领袖并不选择法令或者达到法定人数投票的祭司。

 

当新领袖收到来自每位达到法定人数投票的祭司成员的回复后，就准备为议会程序的每个实例执行步骤3。对于某些有限数量的实例（法令编号）， B3决定了步骤3中法令的选举结果。

 

这种简单协议的以下这些修改得到实际的帕克森议会程序。

-对于结果已知的法令编号，是没有理由通过议会程序的。

<!--[if ppt]-->-<!--[endif]-->

<!--[if ppt]-->-<!--[endif]-->

 

 

<!--[if ppt]-->•<!--[endif]-->

 

 

 

多法令议会

•程序的性能特征

<!--[if ppt]-->•<!--[endif]-->

 

多法令议会

 

 

•未来发展

<!--[if ppt]-->•<!--[endif]-->