分布式算法（典藏版）

前　　言
Distributed Algorithms
分布式算法是用于解决多个互连处理器运行问题的算法。分布式算法的各部分并发和独立地运行，每一部分只承载有限的信息。即使处理器和通信信道以不同的速度运作，或即使某些构件出了故障，这些算法仍然应该正常运行。
分布式算法有广泛的应用：电信、分布式信息处理、科学计算以及实时进程控制。例如，电话系统、航班订票系统、银行系统、全球信息系统、天气预报系统以及飞机和核电站控制系统都严重依赖于分布式算法。很明显，确保分布式算法准确、高效地运行是非常重要的。然而，由于这种算法的执行环境很复杂，所以设计分布式算法就成了一项困难的
任务。
本书对分布式算法这个领域做了全面的介绍，包括为重要的算法和不可能性结果，且都在一种简单的自动机理论环境中呈现。几乎所有的解都附有数学证明（至少是粗略的）。每个算法都根据精确定义的复杂度衡量方法进行了分析。总之，这些内容为更深入地理解分布式算法打下了牢固的基础。
本书面向不同层次的读者。首先，本书可以作为计算机系一年级研究生的教材，尤其适合于对计算机系统、理论或两者怀有浓厚兴趣的学生学习。其次，本书可作为分布式系统设计人员的短期培训教材。后，它也可作为参考手册，供设计人员、学生、研究人员以及任何对该领域感兴趣的人使用。
本书包含了针对很多典型问题的算法，如在几种不同系统环境下的一致性（consensus）、通信、资源分配和同步问题。这些算法和相应结果基于分布式环境的基本假设来组织。组织的层基于时序模型（timing model）—同步、异步或部分同步；第二层基于进程间的通信机制—共享存储器或消息传递。每种系统模型都用数章来阐述：每一部分的头一章提出所述系统类型的形式化模型，余下各章介绍算法和不可能性结果。从头至尾，本书进行了严密的论述，然而非常简明易懂。
由于该领域很广阔，变化也很快，因此本书并不包罗万象，只包括根本的结果。若以复杂度来衡量，这些结果并不总是的，但它们比较简单且能够阐明重要的通用设计和推理方法。
本书将会介绍分布式计算领域中许多重要的问题、算法和不可能性结果。当实际系统中出现这些问题的时候，你就能将它们识别出来，并进而利用本书介绍的算法来解决它们，或者应用不可能性结果来证明它们是不可解的。本书还介绍各类系统模型及其能力。这样一来，你自己就可以设计出新算法（甚至还可以证明出新的不可能性结果）。后，本书还会让你相信，严格推导分布式算法和系统是可行的：形式化建模，给出其所需行为的精确规格说明，严格证明它们符合规格说明，确定合适的复杂度衡量标准以及按照这些标准进行分析。
使用本书
预备知识　阅读本书需要对基本的本科离散数学（包括数学归纳和渐近分析）、一些编程技能以及计算机系统相当熟悉。有关随机算法的部分还需要基本的概率知识。有关串行算法及其分析的本科课程对阅读本书有帮助，但并不是必要的。
章节关系　本书的编排原则是使读者能比较独立地阅读不同模型的各章内容。各章之间的依赖关系如图A所示。例如，如果想尽快了解异步网络，就可以跳过第5～7章。还可以只读算法部分，而不必先阅读算法所依赖的建模部分。

图A　各章之间的依赖关系
带星号的小节　在本书中，有几个小节的标题打了星号。它们的内容不太基本或者说比其他部分更深。次阅读的时候可以忽略这些内容而不会有什么影响。
课程　本书的第1版已经在MIT（麻省理工学院）的研究生导论课中用了很多年，并且在一些计算机软件和应用公司的系统设计师夏季课程中用了三年。本书包括足够一年课程的内容，所以对一些短期课程来说必须有所取舍（注意看章节之间的关系）。
例如，在学习异步网络计算的一个学期的课程中，可以选择第3、4、6章，7.2节，第12章和第14～21章，参考一些有关建模的章节（第2、8和9章），并根据需要加入第10、11和13章中的一些定义。在学习分布一致性的一个学期的课程中，可以选择第2～9章、第12章、13.1节，以及第15、17、21、23和25章。还有其他多种可能组合。如果你是这个领域的研究者，你可以用所在领域的更新或者更特别的研究结果来补充本书。
在为系统设计师提供的一两周的短期课程中，可以突出所有章节的重点，在较高的层次上讨论关键结果和关键证明思想，而无须讲解太多细节。
错误　如果在本书中发现了错误，或者对本书有什么建设性建议，请告诉我。特别欢迎对额外问题的建议。请发送email到distalgs@theory.lcs.mit.edu。
致谢
我很难一一列举出所有对本书的出版做出贡献的人们，因为本书是多年教学和研究的成果，得到了许多学生和研究人员的帮助。即使这样，我还是想尽力而为。
本书是MIT的研究生课程6.852（分布式算法）讲稿的终版本。在我早期组织素材的过程中，学生们学过这门课。这些学生在1990年和1992年帮助我完成了讲稿的在线版本。有几位课程助教对我整理笔记给予了极大的帮助，他们是Ken Goldman、Isaac Saias和Boaz Patt-Shamir。助教Jennifer Welch 和Rainer Gawlick也帮了我很大的忙。
许多同事和学生与我一起研究过本书中的一些结果，与我一起讨论了其他人的工作，这对我充分理解素材帮助很大。其中包括Yehuda Afek、Eshrat Arjomandi、Hagit Attiya、Baruch Awerbuch、Bard Bloom、Alan Borodin、James Burns、Soma Chaudhuri、Brian Coan、Harish Devarajan、Danny Dolev、Cynthia Dwork、Alan Fekete、Michael Fischer、Greg Frederickson、Eli Gafni、Rainer Gawlick、Ken Goldman、Art Harvey、Maurice Herlihy、Paul Jackson、Jon Kleinberg、Leslie Lamport、Butler Lampson、Victor Luchangco、Yishay Mansour、Michael Merritt、Michael Paterson、Boaz Patt-Shamir、Gary Peterson、Shlomit Pinter、Stephen Ponzio、Isaac Saias、Russel Schaffer、Roberto Segala、Nir Shavit、Liuba Shrira、J?rgen S?gaard-Andersen、Eugene Stark、Larry Stockmeyer、Mark Tuttle、Frits Vaandrager、George Varghese、Bill Weihl、Jennifer Welch和Lenore Zuck。尤其感谢其中的两位：我的导师Michael Fischer和我的学生Mark Tuttle。从1978年开始，Michael就与我一起致力于研究这个当时还很小但看起来很有前途的领域，而Mark Tuttle的硕士论文定义并发展了I/O自动机模型。
我还要感谢Ajoy Datta、Roberto De Prisco、Alan Fekete、Faith Fich、Rainer Gawlick、Shai Halevi、Jon Kleinberg、Richard Ladner、John Leo、Victor Luchangco、Michael Melliar-Smith、Michael Merritt、Daniele Micciancio、Boaz Patt-Shamir、Anya Pogosyants、Stephen Ponzio、Sergio Rajsbaum、Roberto Segala、Nir Shavit、Mark Smith、Larry Stockmeyer、Mark Tuttle、George Varghese、Jennifer Welch和Lenore Zuck，他们审阅了全书的各部分草稿并提出了很多有用的建议。特别是Ajoy、Faith和George，他们使用本书的早期版本作为教材来教学，给出了很多宝贵的意见。此外，我要感谢 Joanne Talbot 不厌其烦地排版、画图、搜集参考文献，以及不停地打印文稿等。David Jones也参与了排版工作。在此, 我还要感谢 John Guttag、Paul Penfield 和其他MIT EECS的成员，他们为我安排了写书的时间。Morgan Kaufmann的Bruce Spatz又一次鼓励并帮助我做这个艰巨的工作，他总能给我正确的建议。在本书后付梓阶段，Morgan Kaufmann的Julie Pabst和Diane Cerra给了我很大帮助。同时，也感谢Babel出版社的Ed Sznyter的LATEX技术。
后也是重要的，我要感谢体贴我的家人Dennis、Patrick和Mary Lynch，他们体谅我为本书所做的一切工作，同时帮我处理了其他的事情。特别感谢Dennis，当我把大部分时间花在计算机前时，Dennis在为我准备美味的海鲜晚餐，甚至把我的浴室和洗衣房翻修
一新！

Nancy A. Lynch
Cambridge, Massachusetts

本书对分布式算法进行了全面介绍，包括同步模型、异步模型和部分同步模型，针对这些模型讨论互斥性、一致性和通信问题，为设计、实现和分析分布式算法提供了蓝图。本书对分布式算法领域的许多经典问题给出了多种解决算法或者不可能性结果，绝大部分的算法附有详细的证明过程，并且有jing确的复杂度衡量。本书还配有大量习题，并在每章后列出了详细的参考文献。本书可作为高等院校计算机专业的研究生教材，尤其适合对计算机理论或体系结构感兴趣的学生学习，还适合分布式领域的设计人员和研究人员参考。

南希·A. 林奇（Nancy A. Lynch）　麻省理工学院电子工程和计算机科学系教授，领导麻省理工学院的分布式系统理论研究组，在分布式算法和不可能解以及分布式系统的形式化建模和证明方面编写了大量著作。

目　　录
Distributed Algorithms
译者序
前言
第1章　引言　1
1.1　相关主题　1
1.2　我们的观点　2
1.3　本书内容综述　4
1.4　参考文献注释　7
1.5　标记　8
部分　同步网络算法
第2章　建模I：同步网络模型　10
2.1　同步网络系统　10
2.2　故障　11
2.3　输入和输出　11
2.4　运行　12
2.5　证明方法　12
2.6　复杂度度量　12
2.7　随机化　13
2.8　参考文献注释　13
第3章　同步环中的领导者选择　14
3.1　问题　14
3.2　相同进程的不可能性结果　15
3.3　基本算法　15
3.4　通信复杂度为O (nlogn）的算法　17
3.5　非基于比较的算法　20
3.5.1　时间片算法　20
3.5.2　变速算法　20
3.6　基于比较的算法的下界　22
3.7　非基于比较的算法的下界*　26
3.8　参考文献注释　27
3.9　习题　27
第4章　一般同步网络中的算法　29
4.1　一般网络中的领导者选举　29
4.1.1　问题　29
4.1.2　简单的洪泛算法　29
4.1.3　降低通信复杂度　31
4.2　广度优先搜索　32
4.2.1　问题　33
4.2.2　基本的广度优先搜索算法　33
4.2.3　应用　34
4.3　短路径　35
4.4　小生成树　36
4.4.1　问题　36
4.4.2　基本定理　36
4.4.3　算法　38
4.5　独立集　40
4.5.1　问题　40
4.5.2　随机化算法　41
4.5.3　分析*　42
4.6　参考文献注释　44
4.7　习题　44
第5章　链路故障时的分布式
一致性　46
5.1　协同攻击问题—确定性版本　46
5.2　协同攻击问题—随机化版本　48
5.2.1　形式化模型　49
5.2.2　算法　49
5.2.3　不一致的下限　52
5.3　参考文献注释　54
5.4　习题　54
第6章　进程故障下的分布式
一致性　56
6.1　问题　57
6.2　针对停止故障的算法　58
6.2.1　基本算法　58
6.2.2　减少通信　60
6.2.3　指数信息收集算法　61
6.2.4　带鉴别的Byzantine一致性　66
6.3　针对Byzantine故障的算法　66
6.3.1　举例　67
6.3.2　Byzantine一致性问题的EIG
算法　68
6.3.3　使用二元Byzantine一致性的
一般Byzantine一致性问题　71
6.3.4　减少通信开销　72
6.4　Byzantine一致性问题中进程的
个数　75
6.5　一般图中的Byzantine一致性
问题　78
6.6　弱Byzantine一致性　81
6.7　有停止故障时的轮数　82
6.8　参考文献注释　88
6.9　习题　89
第7章　更多的一致性问题　93
7.1　k一致性问题　93
7.1.1　问题　93
7.1.2　算法　94
7.1.3　下界*　95
7.2　近似一致性　103
7.3　提交问题　106
7.3.1　问题　106
7.3.2　两阶段提交　107
7.3.3　三阶段提交　108
7.3.4　消息数的下界　110
7.4　参考文献注释　112
7.5　习题　112
第二部分　异步算法
第8章　建模II：异步系统模型　116
8.1　输入/输出自动机　116
8.2　自动机的操作　120
8.2.1　合成　120
8.2.2　隐藏　123
8.3　公平性　123
8.4　问题的输入和输出　126
8.5　属性与证明方法　126
8.5.1　不变式断言　126
8.5.2　轨迹属性　126
8.5.3　安全与活性属性　127
8.5.4　合成推理　129
8.5.5　层次化证明　131
8.6　复杂度衡量　133
8.7　不可区分的运行　134
8.8　随机化　134
8.9　参考文献注释　134
8.10　习题　135
第二部分A?异步共享存储器算法
第9章　建模III：异步共享存储器
模型　138
9.1　共享存储器系统　138
9.2　环境模型　140
9.3　不可区分状态　141
9.4　共享变量类型　142
9.5　复杂度衡量　145
9.6　故障　146
9.7　随机化　146
9.8　参考文献注释　146
9.9　习题　146
第10章　互斥　148
10.1　异步共享存储器模型　148
10.2　问题　150
10.3　Dijkstra的互斥算法　153
10.3.1　算法　153
10.3.2　正确性证明　156
10.3.3　互斥条件的一个断言式
证明　158
10.3.4　运行时间　159
10.4　互斥算法的更强条件　160
10.5　锁定权互斥算法　162
10.5.1　双进程算法　162
10.5.2　n进程算法　165
10.5.3　锦标赛算法　169
10.6　使用单写者共享寄存器的算法　172
10.7　Bakery算法　174
10.8　寄存器数量的下界　176
10.8.1　基本事实　177
10.8.2　单写者共享变量　177
10.8.3　多写者共享变量　178
10.9　使用读–改–写共享变量的
互斥　182
10.9.1　基本问题　182
10.9.2　有界绕过次数　183
10.9.3　锁定权　188
10.9.4　模拟证明　190
10.10　参考文献注释　193
10.11　习题　193
第11章　资源分配　197
11.1?问题　197
11.1.1　显式资源规格说明和互斥规格说明　197
11.1.2　资源分配问题　198
11.1.3　哲学家用餐问题　199
11.1.4　解法的受限形式　200
11.2　对称哲学家用餐算法的
不存在性　200
11.3　右–左哲学家用餐算法　202
11.3.1　等待链　202
11.3.2　基本算法　203
11.3.3　扩展　205
11.4　随机哲学家用餐算法*　208
11.4.1　算法*　208
11.4.2　正确性*　210
11.5　参考文献注释　216
11.6　习题　216
第12章　一致性　218
12.1?问题　218
12.2　使用读/写共享存储器的一致性
问题　220
12.2.1　限制　221
12.2.2　术语　221
12.2.3　双价初始化　222
12.2.4　无等待终止性的不可能性　222
12.2.5　单故障终止性的不可能性
结果　224
12.3　读/改/写共享存储器上的
一致性问题　227
12.4　其他共享存储器类型　227
12.5　异步共享存储器系统中的可
计算性*　227
12.6　参考文献注释　229
12.7　习题　229
第13章　原子对象　232
13.1　定义和基本结论　232
13.1.1　原子对象的定义　233
13.1.2　规范无等待原子对象
自动机　238
13.1.3　原子对象的合成　240
13.1.4　原子对象和共享变量　240
13.1.5　显示原子性的一个充分
条件　245
13.2　用读/写变量实现读–改–写
原子对象　246
13.3　共享存储器的原子快照　247
13.3.1　问题　247
13.3.2　带无界变量的一个算法　248
13.3.3　带有界变量的一个算法*　251
13.4　读/写原子对象　254
13.4.1　问题　254
13.4.2　证明原子性的其他引理　255
13.4.3　带无界变量的一个算法　256
13.4.4　两个写者的有界算法　259
13.4.5　使用快照的算法　 263
13.5　参考文献注释　264
13.6　习题　265
第二部分B　异步网络算法
第14章　建模IV：异步网络模型　268
14.1　发送/接收系统　268
14.1.1　进程　268
14.1.2　发送/接收通道　269
14.1.3　异步发送/接收系统　272
14.1.4　使用可靠FIFO通道的发送/
接收系统的属性　272
14.1.5　复杂度度量　273
14.2　广播系统　274
14.2.1　进程　274
14.2.2　广播通道　274
14.2.3　异步广播系统　275
14.2.4　采用可靠广播通道的广播系统的属性　275
14.2.5　复杂度度量　275
14.3　多播系统　275
14.3.1　进程　276
14.3.2　多播通道　276
14.3.3　异步多播系统　276
14.4　参考文献注释　277
14.5　习题　277
第15章　基本异步网络算法　279
15.1　环中的领导者选举　279
15.1.1　LCR算法　279
15.1.2　HS算法　283
15.1.3　PetersonLeader算法　283
15.1.4　通信复杂度的下界　286
15.2　任意网络中的领导者选举　291
15.3　生成树的构造、广播和敛播　292
15.4　广度优先搜索和短路径　295
15.5　小生成树　300
15.5.1　问题描述　301
15.5.2　同步算法：回顾　301
15.5.3　GHS算法：概要　302
15.5.4　更详细的算法　303
15.5.5　特殊消息　305
15.5.6　复杂度分析　306
15.5.7　GHS算法的正确性证明　307
15.5.8　简单“同步”策略　308
15.5.9　应用到领导者选举算法中　308
15.6　参考文献注释　309
15.7　习题　309
第16章　同步器　313
16.1　问题　313
16.2　局部同步器　315
16.3　安全同步器　319
16.3.1　前端自动机　320
16.3.2　通道自动机　321
16.3.3　安全同步器的任务　321
16.3.4　正确性　322
16.4　安全同步器的实现　322
16.4.1　同步器Alpha　322
16.4.2　同步器Beta　323
16.4.3　同步器Gamma　323
16.5　应用　327
16.