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

paxos

zookeeper

需积分: 10 195 浏览量更新于2023-03-16 评论收藏 1.11MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

《The Part-Time Parliament》 1

The Part-Time Parliament 兼职议会 Leslie Lamport

1. The Problem ...................................................................................................................... 2

1.1. Paxos 岛 ..................................................................................................................... 2

1.2. 要求(Requirements)................................................................................................... 3

1.3. 假设（Assumptions） ............................................................................................... 4

2. The Single-Decree Synod ................................................................................................... 4

2.1. 数学结论 .................................................................................................................... 5

2.2. 初级协议（The Preliminary Protocol） .................................................................... 9

2.3. 基本协议（The Basic Protocol） ............................................................................ 11

2.4. 完整的神会协议（The Complete Synod Protocol） .............................................. 12

3. The Multi-Decree Parliament .......................................................................................... 14

3.1. 协议 .......................................................................................................................... 14

3.2. 协议特性 (Properties of the Protocol) ................................................................... 15

3.2.1 法令的顺序 ............................................................................................................ 15

3.2.2 关上门之后 ............................................................................................................ 15

3.3. 更进一步(Further Development) ............................................................................ 16

3.3.1

选择一个总统

....................................................................................................... 16

3.3.2

长律簿

................................................................................................................... 16

3.3.3

官员化

................................................................................................................... 17

3.3.4 法律的学习 ........................................................................................................... 18

3.3.5 不诚实的议员和无心之过 .................................................................................... 19

3.3.6 选择新的议员 ........................................................................................................ 20

4. 与计算机科学的关系 ..................................................................................................... 21

4.1. 状态机模式 (The State Machine Approach) .......................................................... 21

4.2. 提交协议 (Commit Protocols) ................................................................................ 22

5. 附录：神会协议一致性的证明 ..................................................................................... 23

6. 翻译后记 ......................................................................................................................... 24

《The Part-Time Parliament》 2

The Part-Time Parliament (兼职议会)

Leslie Lamport

这篇论文前不久在 TOCS 编辑室的档案柜后面被发现。尽管年代久远，主要作者仍然认为它值得发表。

因为作者最近在希腊的一些小岛上做野外作业不能到达，所以请求我来准备它。

作者貌似是个只业余对计算机科学感兴趣的考古学家。这非常不幸；尽管他描述的模糊的古代 Paxos

文明对于大多数计算机科学家不感兴趣，但它的议会系统对于怎样在异步环境中实现一个分布式计算

系统来说是个杰出的模式。Paxos 人对他们协议的一些改良貌似在系统的文献中确实找不到。

作者在第 4 节中确实简短讨论了 Paxos 议会和分布式计算的关系。计算机科学家可能会想要首先阅读

这一节。甚至在这之前，他们或许想要阅读 Lampson[1996]对这个算法向计算机科学家作的解释。这

个算法也在[1997]被 De Prisco 更正式的描述过。我在第 4 节的末尾加上了古代协议和近期研究之间关

系的更进一步说明。

1. The Problem

1.1. Paxos 岛

在这个千年的早期（公元 10 世纪初），爱琴海上的小岛 Paxos 是一个兴盛的商业贸易中心（这

应该不会和爱奥尼亚的的 Paxoi 岛混淆，Poxoi 有时也被破读为 Paxos）。经济发展带来了政

治的进步。Paxos 的公民们用议会形式的政府取代了原先的神权统治。但是对 Paxos 人来说，

做生意才是头等大事，城市职责反在其次，没有 Paxos 人愿意把他全部的时间投入到议会事

务中。所以 Paxos 的议会必须在每个议员都可能随时缺席的情况下也能工作下去。

兼职议会所面对的问题正好能对应于今天的容错式分布式系统所面对的问题：议员对应于分

布式系统中的处理进程(processes)，而议员的缺席对应于处理进程的宕机。因此 Paxos 人的

解决方法或许值得计算机科学借鉴。我这里会介绍 Paxos 议会协议的一个简短历史，接下来

会简短讨论一下其与分布式系统的相关性。

Paxos 文明已毁灭于一次异族入侵，考古学家只是最近才开始发掘他们的历史。我们对于

Paxos 议会的所知因此比较零散。虽然基本协议是知道的，但对许多细节我们却一无所知，

而这正是我们感兴趣的地方，因此我将忝为推测 Paxos 人在这些具体细节上可能的做法。

《The Part-Time Parliament》 3

1.2. 要求(Requirements)

议会的主要任务就是决定这片土地上的法律，法律是由议会通过的一系列法令定义的。一个

现代的议会可以雇佣秘书来记录它的每一个活动，但是在 Paxos 没有一个人愿意始终呆在议

会大厅里作为一个秘书从头到尾参与每一个会议。取而代之的是每一个议员都会维护一个律

簿（ledger），用来记录一系列已通过的法令，每个法令会带有一个编号。例如议员Λ (译者

注：由于古希腊字母比较难输入，原文中的希腊文姓名统一用其中的一个字母代替)的律簿

里有这样一个条目：

155：橄榄税是每吨 3 个银币

如果她相信议会通过的第 155 号法令设置了橄榄的赋税为每吨 3 个银币。律簿是由檫不掉的

墨水书写的，所以其中的条目不能被改变。

议会协议的第一个需求就是律簿的一致性。也就是任何两个律簿都不能有互相矛盾的内容。

假设议员Φ 在他的律簿中有这样一个条目：

132：只有橄榄油可以用来做灯

那么就不会有其他议员的律簿会记录不同内容的第 132 号法令。当然，另一个议员的律簿里

可能还没有第 132 号法令的记录，如果他还不知道第 132 号法令已经通过了。

仅仅有律簿的一致性（Consistency）还不够，因为让每个律簿都保留空白也能满足一致性。

所以需要一些要求（Requirement）来保证法令能最终通过并被记录在律簿中。在现代的议

会中，议员达不成一致妨碍了法令的通过。但是在 Paxon 不是这种状况，这里盛行的是相互

信任的气氛，议员愿意通过任何被提交的法令。但是他们好游历的特性却造成了问题。假如

一组议员通过了 37 号法令：

37：禁止在圣殿的墙上种植

然后离开议会厅参加宴会去了，接下来另外一组议员进来议会厅，不知道刚刚发生了什么事

情，然后也通过了一个冲突的 37 号法令：

37：允许自由的艺术表达

那么一致性就失去了

除非足够多的议员在议会厅里呆足够长的时间，否则进展性(Progress)无法保证。因为 Paxos

的议员不愿意缩减他们在外面的活动，所以无法保证任何法令都会最终被通过。但是无论如

何，议员们愿意保证，只要他们在议会厅中，他们和他们的助手就会快速的处理所有的议会

事务。这个保证使 Paxos 公民们能够设计出一个满足如下进展性条件（Progress Conditon）

的议会协议：

《The Part-Time Parliament》 4

如果议员中的多数［在翻译进展条件时，我将 Paxos 的单词μ α δ ζ 翻译为议员

中的多数。2.2 节中提出了另一个可取的翻译，并做了讨论］都在议会厅中，

并且在一个足够长的时间内没有人进出议会厅，那么任一被某个议员提议的法

令都将会被通过，并且每一个被通过的法令都会出现在议会厅中每个议员的律

簿上

1.3. 假设（Assumptions）

通过提供给议员必要的资源，议会协议的要求(requirements)是可以达到的。每个议员收到

了一个结实耐用的律簿来记录法令，一支笔，和擦不掉墨水。议员如果离开过议会厅，可能

会在回来后忘记了他们曾经做过什么（（比如）在一个悲剧的事故里，议员 Twvey 被掉下来

的雕像击中了头部而永久失忆了~~ = =！），所以他们会把一些重要的议会任务记在律簿的背

面。律簿上的法令条目永远不会改变，但是律簿背面的备注(notes)可能会被划掉。进展条件

的达成要求议员能够度量时间的流逝，所以给了他们简单的沙漏计时器。

议员任何时候都会带着他们的律簿，并且总是能够从律簿上阅读到法令条目和尚未划掉的备

注。律簿由最精良的羊皮纸做成，只用来记录最重要的备注(notes)。其他备注会被记录到小

纸条(a slip of paper)上，这些小纸条可能会在议员离开议会厅后丢失。

议会厅里比较嘈杂，影响听觉，不可能在里面做演讲。议员只能通过信使来通信，并且有专

款来供议员雇用任意多他们需要的信使。信使不会篡改消息，但是他可能会忘记他递送过了

某个消息，并再次递送它。像他们服务的议员一样，信使也只花他们部分的时间在议会职责

上。一个信使在投递一个消息前可能会离开议会厅去从事其他的事情，比如一次为期 6 个月

的航海。他甚至可能会一去不复返，在这种情况下消息永远也不会被送达。

尽管议员和信使可以随时离开或进入，但是只要他们在议会厅里，他们就会专注于议会事务。

只要呆在议会厅，信使会很快速的投递消息，议员会立即快速的处理任何他们收到的消息。

Paxos 的官方记录声称议员和信使绝对的诚实并严格遵循议会协议。大多数学者仅仅把这当

做将 Paxos 描绘为在道德上优越于其东方邻国的宣传。不诚实，尽管稀少，但毫无疑问一定

是存在的，但由于官方文本里从未提及，我们也不知道议会是怎样应付不诚实的议员或信使

的。在 3.3.5 节讨论了已经发现的迹象

2. The Single-Decree Synod

Paxos 议会由更早期的牧师的宗教仪式会议（Synod，以下简称神会）演化而来。这种神会每

19 年召集一次来选择一个象征性的法令。几个世纪以来，神会约定俗成地要求所有牧师都

到场来选择一个法令。但是随着商业的繁荣，牧师开始在神会期间就进进出出会议厅，最后

旧的协议失效了，一个神会没有达成任何法令就结束了。为了避免重复这种宗教上的灾难，

Paxos 的宗教领袖请求数学家制定一个协议来达成神会法令。协议的要求和假定本质上与后

来的议会协议是一样的，除了一点不同：神会只允许在律簿上包含一条法令，而后来的议会

《The Part-Time Parliament》 5

可以包含一系列法令。神会协议在本章中描述，议会协议在第三章中描述。

数学家通过几个步骤来得到神会协议。首先他们证明了一个满足特定约束的协议能够保证一

致性，并且可以进展下去。由这些约束直接得出了一个初级协议。初级协议的一个约束版本

提供了能够保证一致性，但是不能保证进展性的基本协议（basic protocol）。通过进一步约

束基本协议得到了能够满足一致性和进展性要求的完整神会协议(synod protocol) [神会协议

的完整的发现历史已不可考。就像现代的计算机科学家，Paxos 的数学家将描述优美的逻辑

推演，描述毫不相干的算法是如何推演产生的。我们知道数学结论（2.1 节的定理 1 和 2）

确实是在协议产生之前作出的。当数学家在回复关于协议的请求，试图证明不可能有一个满

足要求的协议时，发现了这些数学结论］

2.1 节描述了这些数学结论。2.2-2.4 节非正式地描述了这些协议。在附录中给出了基本协议

的更正式的描述和正确性证明。

2.1. 数学结论

神会法令从多轮带编号的表决(ballot)中选择。一轮表决是对一个单条法令的投票。在每次表

决中，牧师只有两种选择：对这个法令投票（表示赞成这个法令），或不投票（不赞成）［像

许多现代国家一样，Paxos 并没有完全领会古希腊民主的精髓］。与一轮表决相关联的是一个

牧师的集合，称为法定人数集（quorum）。当且仅当法定人数集中的每个牧师都赞成这个法

令时，这轮表决才是成功的。正式的表述是，一轮表决Ｂ由下面 4 个要素组成：（除非特别

说明，集合指有限集合）





一条法令（被投票的那条 decree）





一个牧师的非空集合（表决的法定人数集 quorum）





一个牧师的集合（所有对法令作出投票（赞成）的牧师）





这轮表决的编号

说一轮表决Ｂ是成功的，当且仅当Ｂqrm  Ｂvot，所以一轮成功的投票是每一个法定人数

集的成员都投了票的(赞成票，不赞成则不投票)。

表决的编号从一个无界有序的数字集合中选取。如果





> 



，则说



比 B 大。但这并

不能表明表决进行的顺序。一个大的表决实际上可以在一个小的表决之前发生。（这里故意

将 later 翻译成了大，省得 later 和 before 掺杂不清）

Paxos 的数学家在一个由多轮表决构成的集合上定义了 3 个条件，然后展示了如果已经进

行过的表决满足这些条件，那么一致性会得到保证，进行性也是可能的。头两个条件比较简

单，可以被非正式的描述如下：

B1()：中的每一轮表决，都有一个唯一的编号

B2()：中任意两轮表决的法定人数集中，至少有一个公共的牧师成员

剩余23页未读，继续阅读

架构随笔

粉丝: 18
资源: 12

会员权益专享

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

评论0

会员权益专享

最新资源

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

评论0

《The Part-Time Parliament》分布式一致性协议Paxos论文翻译

The Part-Time Parliament

The_Part-Time_Parliament (Paxos算法中文翻译)

深入理解分布式共识算法

一篇学会rocketmq

directive 2014/53/eu of the european parliament and of the council

The Part-Time Parliament+ Paxos Made Simple+ paxos made live-paper

European_Parliament_Proceedings_Parallel_Corpus_1996-2011.torrent

European Parliament - Questions and Declarations-数据集

2024-2030全球及中国控制膨胀合金箔行业研究及十五五规划分析报告.docx

通信历年真题选择题汇总1.(DOC).doc

电子通信设计资料电子万年历设计与制作论文资料

JSP-SSM健身俱乐部客户关系管理系统可升级SpringBoot源码.7z

2024-2030全球及中国超级殷钢 32-5行业研究及十五五规划分析报告.docx

2023年贴剂行业竞争格局与市场机会.pptx

linux nginx免安装文件

按点击量排序-基于内容的课程推荐网站的设计与实现(SSM+html).zip

OSP项目施工组织方案.docx

小型婚礼（可动态添加祝福语）程序文件jquery

AI相关领域论文+英文中文+论文攻读

会员权益专享

最新资源