The-Part-Time-Parliament(Paxos算法中文翻译)

《ThePart-TimeParliament》1ThePart-TimeParliament兼职议会LeslieLamport1.TheProblem......................................................................................................................21.1.Paxos岛.....................................................................................................................21.2.要求(Requirements)...................................................................................................31.3.假设（Assumptions）...............................................................................................42.TheSingle-DecreeSynod...................................................................................................42.1.数学结论....................................................................................................................52.2.初级协议（ThePreliminaryProtocol）....................................................................92.3.基本协议（TheBasicProtocol）............................................................................112.4.完整的神会协议（TheCompleteSynodProtocol）..............................................123.TheMulti-DecreeParliament..........................................................................................143.1.协议..........................................................................................................................143.2.协议特性(PropertiesoftheProtocol)...................................................................153.2.1法令的顺序............................................................................................................153.2.2关上门之后............................................................................................................153.3.更进一步(FurtherDevelopment)............................................................................163.3.1选择一个总统.......................................................................................................163.3.2长律簿...................................................................................................................163.3.3官员化...................................................................................................................173.3.4法律的学习...........................................................................................................183.3.5不诚实的议员和无心之过....................................................................................193.3.6选择新的议员........................................................................................................204.与计算机科学的关系.....................................................................................................214.1.状态机模式(TheStateMachineApproach)..........................................................214.2.提交协议(CommitProtocols)................................................................................225.附录：神会协议一致性的证明.....................................................................................236.翻译后记.........................................................................................................................24《ThePart-TimeParliament》2ThePart-TimeParliament(兼职议会)LeslieLamport这篇论文前不久在TOCS编辑室的档案柜后面被发现。尽管年代久远，主要作者仍然认为它值得发表。因为作者最近在希腊的一些小岛上做野外作业不能到达，所以请求我来准备它。作者貌似是个只业余对计算机科学感兴趣的考古学家。这非常不幸；尽管他描述的模糊的古代Paxos文明对于大多数计算机科学家不感兴趣，但它的议会系统对于怎样在异步环境中实现一个分布式计算系统来说是个杰出的模式。Paxos人对他们协议的一些改良貌似在系统的文献中确实找不到。作者在第4节中确实简短讨论了Paxos议会和分布式计算的关系。计算机科学家可能会想要首先阅读这一节。甚至在这之前，他们或许想要阅读Lampson[1996]对这个算法向计算机科学家作的解释。这个算法也在[1997]被DePrisco更正式的描述过。我在第4节的末尾加上了古代协议和近期研究之间关系的更进一步说明。1.TheProblem1.1.Paxos岛在这个千年的早期（公元10世纪初），爱琴海上的小岛Paxos是一个兴盛的商业贸易中心（这应该不会和爱奥尼亚的的Paxoi岛混淆，Poxoi有时也被破读为Paxos）。经济发展带来了政治的进步。Paxos的公民们用议会形式的政府取代了原先的神权统治。但是对Paxos人来说，做生意才是头等大事，城市职责反在其次，没有Paxos人愿意把他全部的时间投入到议会事务中。所以Paxos的议会必须在每个议员都可能随时缺席的情况下也能工作下去。兼职议会所面对的问题正好能对应于今天的容错式分布式系统所面对的问题：议员对应于分布式系统中的处理进程(processes)，而议员的缺席对应于处理进程的宕机。因此Paxos人的解决方法或许值得计算机科学借鉴。我这里会介绍Paxos议会协议的一个简短历史，接下来会简短讨论一下其与分布式系统的相关性。Paxos文明已毁灭于一次异族入侵，考古学家只是最近才开始发掘他们的历史。我们对于Paxos议会的所知因此比较零散。虽然基本协议是知道的，但对许多细节我们却一无所知，而这正是我们感兴趣的地方，因此我将忝为推测Paxos人在这些具体细节上可能的做法。《ThePart-TimeParliament》31.2.要求(Requirements)议会的主要任务就是决定这片土地上的法律，法律是由议会通过的一系列法令定义的。一个现代的议会可以雇佣秘书来记录它的每一个活动，但是在Paxos没有一个人愿意始终呆在议会大厅里作为一个秘书从头到尾参与每一个会议。取而代之的是每一个议员都会维护一个律簿（ledger），用来记录一系列已通过的法令，每个法令会带有一个编号。例如议员Λ(译者注：由于古希腊字母比较难输入，原文中的希腊文姓名统一用其中的一个字母代替)的律簿里有这样一个条目：155：橄榄税是每吨3个银币如果她相信议会通过的第155号法令设置了橄榄的赋税为每吨3个银币。律簿是由檫不掉的墨水书写的，所以其中的条目不能被改变。议会协议的第一个需求就是律簿的一致性。也就是任何两个律簿都不能有互相矛盾的内容。假设议员Φ在他的律簿中有这样一个条目：132：只有橄榄油可以用来做灯那么就不会有其他议员的律簿会记录不同内容的第132号法令。当然，另一个议员的律簿里可能还没有第132号法令的记录，如果他还不知道第132号法令已经通过了。仅仅有律簿的一致性（Consistency）还不够，因为让每个律簿都保留空白也能满足一致性。所以需要一些要求（Requirement）来保证法令能最终通过并被记录在律簿中。在现代的议会中，议员达不成一致妨碍了法令的通过。但是在Paxon不是这种状况，这里盛行的是相互信任的气氛，议员愿意通过任何被提交的法令。但是他们好游历的特性却造成了问题。假如一组议员通过了37号法令：37：禁止在圣殿的墙上种植然后离开议会厅参加宴会去了，接下来另外一组议员进来议会厅，不知道刚刚发生了什么事情，然后也通过了一个冲突的37号法令：37：允许自由的艺术表达那么一致性就失去了除非足够多的议员在议会厅里呆足够长的时间，否则进展性(Progress)无法保证。因为Paxos的议员不愿意缩减他们在外面的活动，所以无法保证任何法令都会最终被通过。但是无论如何，议员们愿意保证，只要他们在议会厅中，他们和他们的助手就会快速的处理所有的议会事务。这个保证使Paxos公民们能够设计出一个满足如下进展性条件（ProgressConditon）的议会协议：《ThePart-TimeParliament》4如果议员中的多数［在翻译进展条件时，我将Paxos的单词μαδζ翻译为议员