分布式算法（典藏版）

目　　录
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.5.1　领导者选举　327
16.5.2　广度优先搜索　327
16.5.3　短路径　328
16.5.4　广播与确认　328
16.5.5　独立集　328
16.6　时间下界　328
16.7　参考文献注释　331
16.8　习题　331
第17章　共享存储器与网络　333
17.1　从异步共享存储器模型到异步
网络模型的转换　333
17.1.1　问题　333
17.1.2　无故障时的策略　334
17.1.3　容忍进程故障的算法　339
17.1.4　对于n/2故障的不可能性
结果　342
17.2　从异步网络模型到异步共享存储器模型的转换　343
17.2.1　发送/接收系统　344
17.2.2　广播系统　345
17.2.3　异步网络中一致性的
不可能性　346
17.3　参考文献注释　346
17.4　习题　346
第18章