分布式算法

出版者的话
专家指导委员会
译者序
前言
第1章   引言 1
1.1   相关主题 1
1.2   我们的观点 2
1.3   本书内容综述 3
1.4   参考文献注释 7
1.5   标记 7
第一部分   同步网络算法
第2章   建模I：同步网络模型 10
2.1   同步网络系统 10
2.2   故障 11
2.3   输入和输出 11
2.4   运行 11
2.5   证明方法 12
2.6   复杂度度量 12
2.7   随机化 12
2.8   参考文献注释 13
第3章   同步环中的领导者选择 14
3.1   问题 14
3.2   相同进程的不可能性结果 14
3.3   基本算法 15
3.4   通信复杂度为O(n log n)的算法 17
3.5   非基于比较的算法 19
3.5.1   时间片算法 20
3.5.2   变速算法 20
3.6   基于比较的算法的下界 21
3.7   非基于比较的算法的下界* 25
3.8   参考文献注释 26
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   问题 32
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   算法 37
4.5   最大独立集 39
4.5.1   问题 40
4.5.2   随机化算法 40
4.5.3   分析* 42
4.6   参考文献注释 43
4.7   习题 43
第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   问题 56
6.2   针对停止故障的算法 58
6.2.1   基本算法 58
6.2.2   减少通信 59
6.2.3   指数信息收集算法 61
6.2.4   带鉴别的Byzantine一致性 66
6.3   针对Byzantine故障的算法 66
6.3.1   举例 66
6.3.2   Byzantine一致性问题的EIG算法 68
6.3.3   使用二元Byzantine一致的一般
的Byzantine一致性问题 71
6.3.4   减少通信开销 72
6.4   Byzantine一致性问题中进程的个数 74
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   算法 93
7.1.3   下界* 95
7.2   近似一致性 102
7.3   提交问题 105
7.3.1   问题 105
7.3.2   两阶段提交 106
7.3.3   三阶段提交 107
7.3.4   消息数的下界 109
7.4   参考文献注释 111
7.5   习题 111
第二部分   异步算法
第8章   建模II：异步系统模型 114
8.1   输入/输出自动机 114
8.2   自动机的操作 118
8.2.1   合成 118
8.2.2   隐藏 121
8.3   公平性 121
8.4   问题的输入和输出 123
8.5   属性与证明方法 124
8.5.1   不变式断言 124
8.5.2   轨迹属性 124
8.5.3   安全与活性属性 125
8.5.4   合成推理 126
8.5.5   层次化证明 128
8.6   复杂度衡量 130
8.7   不可区分运行 131
8.8   随机化 131
8.9   参考文献注释 131
8.10   习题 132
第二部分A   异步共享存储器算法
第9章   建模III：异步共享存储器模型 136
9.1   共享存储器系统 136
9.2   环境模型 138
9.3   不可区分状态 140
9.4   共享变量类型 140
9.5   复杂度衡量 144
9.6   故障 144
9.7   随机化 145
9.8   参考文献注释 145
9.9   习题 145
第10章   互斥 146
10.1   异步共享存储器模型 146
10.2   问题 148
10.3   Dijkstra的互斥算法 151
10.3.1   算法 151
10.3.2   正确性证明 154
10.3.3   互斥条件的一个断言证明 156
10.3.4   运行时间 157
10.4   互斥算法的更强条件 158
10.5   锁定权互斥算法 159
10.5.1   双进程算法 159
10.5.2   n进程算法 163
10.5.3   锦标赛算法 167
10.6   使用单写者共享存储器的算法 170
10.7   Bakery算法 171
10.8   寄存器数量的下界 173
10.8.1   基本事实 174
10.8.2   单写者共享变量 175
10.8.3   多写者共享变量 175
10.9   使用读-改-写共享变量的互斥 179
10.9.1   基本问题 179
10.9.2   有界绕过次数 180
10.9.3   锁定权 185
10.9.4   模拟证明 187
10.10   参考文献注释 189
10.11   习题 190
第11章   资源分配 194
11.1   问题 194
11.1.1   显式资源说明和互斥说明 194
11.1.2   资源分配问题 195
11.1.3   哲学家用餐问题 196
11.1.4   解法的受限形式 197
11.2   对称哲学家用餐算法的不存在性 197
11.3   右-左哲学家用餐算法 199
11.3.1   等待链 199
11.3.2   基本算法 200
11.3.3   扩展 202
11.4   哲学家用餐随机算法* 204
11.4.1   算法* 205
11.4.2   正确性* 207
11.5   参考文献注释 212
11.6   习题 213
第12章   一致性 215
12.1   问题 215
12.2   使用读/写共享存储器的一致性 217
12.2.1   限制 218
12.2.2   术语 218
12.2.3   双价初始化 218
12.2.4   无等待终止的不可能性 219
12.2.5   单故障终止的不可能性结果 221
12.3   读/改/写共享存储器上的一致性
问题 223
12.4   其他共享存储器类型 224
12.5   异步共享存储器系统中的可计算性* 224
12.6   参考文献注释 225
12.7   习题 226
第13章   原子对象 229
13.1   定义和基本结论 229
13.1.1   原子对象的定义 229
13.1.2   规范无等待原子对象自动机 235
13.1.3   原子对象的合成 237
13.1.4   原子对象和共享变量 237
13.1.5   显示原子性的一个充分条件 241
13.2   用读/写变量实现读-改-写原子对象 242
13.3   共享存储器的原子快照 243
13.3.1   问题 243
13.3.2   带无界变量的一个算法 244
13.3.3   带有界变量的一个算法* 247
13.4   读/写原子对象 250
13.4.1   问题 250
13.4.2   证明原子性的其他引理 250
13.4.3   带无界变量的一个算法 251
13.4.4   两个写者的有界算法 254
13.4.5   使用快照的算法 258
13.5   参考文献注释 259
13.6   习题 260
第二部分B   异步网络算法
第14章   建模IV：异步网络模型 264
14.1   发送/接收系统 264
14.1.1   进程 264
14.1.2   发送/接收通道 264
14.1.3   异步发送/接收系统 268
14.1.4   使用可靠FIFO通道的发送/
接收系统的特征 268
14.1.5   复杂度度量 269
14.2   广播系统 269
14.2.1   进程 269
14.2.2   广播通道 270
14.2.3   异步广播系统 270
14.2.4   采用可靠广播通道的广播系统
的特征 270
14.2.5   复杂度度量 271
14.3   多播系统 271
14.3.1   进程 271
14.3.2   多播通道 271
14.3.3   异步多播系统 272
14.4   参考文献注释 272
14.5   习题 272
第15章   基本异步网络算法 274
15.1   环中的领导者选举 274
15.1.1   LCR算法 275
15.1.2   HS算法 278
15.1.3   Peterson Leader算法 278
15.1.4   通信复杂度的下界 281
15.2   任意网络中的领导者选举 286
15.3   生成树的构造. 广播和敛播 287
15.4   广度优先搜索和最短路径 290
15.5   最小生成树 295
15.5.1   问题描述 295
15.5.2   同步算法：回顾 296
15.5.3   GHS算法：概要 296
15.5.4   更详细的算法 297
15.5.5   特殊消息 299
15.5.6   复杂度分析 301
15.5.7   GHS算法的正确性证明 301
15.5.8   简单“同步”策略 302
15.5.9   应用到领导者选举算法中 302
15.6   参考文献注释 303
15.7   习题 303
第16章   同步器 307
16.1   问题 307
16.2   局部同步器 309
16.3   安全同步器 313
16.3.1   前端自动机 314
16.3.2   通道自动机 315
16.3.3   安全同步器 315
16.3.4   正确性 315
16.4   安全同步器的实现 316
16.4.1   同步器Alpha 316
16.4.2   同步器Beta 317
16.4.3   同步器Gamma 317
16.5   应用 320
16.5.1   领导者选举 321
16.5.2   深度优先搜索 321
16.5.3   最短路径 321
16.5.4   广播与确认 321
16.5.5   最大独立集 321
16.6   时间下界 321
16.7   参考文献注释 324
16.8   习题 324
第17章   共享存储器与网络 326
17.1   从共享存储器模型到网络模型
的转换 326
17.1.1   问题 326
17.1.2   无故障时的策略 327
17.1.3   容忍进程故障的算法 332
17.1.4   对于n/2故障的不可能性结果 335
17.2   从网络模型转换到共享存储器模型 336
17.2.1   发送/接收系统 336
17.2.2   广播系统 338
17.2.3   异步网络中一致性的不可能性 338
17.3   参考文献注释 339
17.4   习题 339
第18章   逻辑时间 341
18.1   异步网络的逻辑时间 341
18.1.1   发送/接收系统 341
18.1.2   广播系统 343
18.2   使用逻辑时间的异步算法 344
18.2.1   时钟的走动 344
18.2.2   延迟未来事件 345
18.3   应用 346
18.3.1   银行系统 346
18.3.2   全局快照 348
18.3.3   模拟一台单状态机器 349
18.4   从实际时间算法到逻辑时间算法
的变换* 352
18.5   参考文献注释 352
18.6   习题 353
第19章   一致全局快照和稳定属性检测 355
19.1   发散算法的终止检测 355
19.1.1   问题 355
19.1.2   DijkstraScholten算法 356
19.2   一致全局快照 360
19.2.1   问题 360
19.2.2   ChandyLamport算法 361
19.2.3   应用 364
19.3   参考文献注释 366
19.4   习题 367
第20章   网络资源分配 369
20.1   互斥 369
20.1.1   问题 369
20.1.2   模拟共享存储器 370
20.1.3   循环令牌算法 370
20.1.4   基于逻辑时间的算法 372
20.1.5   LogicalTimeME算法的改进 374
20.2   通用资源分配 376
20.2.1   问题 376
20.2.2   着色算法 377
20.2.3   基于逻辑时间的算法 377
20.2.4   无环有向图算法 378
20.2.5   哲学家饮水* 379
20.3   参考文献注释 383
20.4   习题 383
第21章   带进程故障的异步网络计算 386
21.1   网络模型 386
21.2   有故障环境中一致性的不可能性 387
21.3   随机算法 388
21.4   故障检测器 390
21.5   k一致性 393
21.6   近似一致性 394
21.7   异步网络的计算能力* 395
21.8   参考文献注释 396
21.9   习题 396
第22章   数据链路协议 399
22.1   问题阐述 399
22.2   Stenning协议 400
22.3   位变换协议 403
22.4   可重排序的有界标志协议 406
22.4.1   关于重排序和复制的不可能
性结论 407
22.4.2   容许丢失和重排序的有界标
志协议 408
22.4.3   不存在容许消息丢失和重排序
的高效协议 412
22.5   容许进程崩溃 414
22.5.1   简单的不可能性结论 415
22.5.2   更复杂的不可能性结论 415
22.5.3   实用的协议 418
22.6   参考文献注释 423
22.7   习题 423
第三部分   部分同步算法
第23章   建模V:   部分同步系统模型 428
23.1   MMT   定时自动机 428
23.1.1   基本定义 428
23.1.2   操作 432
23.2   通用定时自动机 434
23.2.1   基本定义 434
23.2.2   将MMT自动机转化为通用定时
自动机 437
23.2.3   操作 440
23.3   属性和证明方法 441
23.3.1   不变式 441
23.3.2   定时轨迹属性 443
23.3.3   模拟 444
23.4   构造共享存储器和网络系统的模型 449
23.4.1   共享存储器系统 449
23.4.2   网络 449
23.5   参考文献注释 449
23.6   习题 450
第24章   部分同步的互斥 452
24.1   问题 452
24.2   单寄存器算法 453
24.3   对时间故障的回复性 459
24.4   不可能性结果 461
24.4.1   时间下界 462
24.4.2   最终时间界限的不可能性结果* 462
24.5   参考文献注释 463
24.6   习题 463
第25章   部分同步的一致性 466
25.1   问题 466
25.2   故障检测器 467
25.3   基本结论 468
25.3.1   上界 468
25.3.2   下界 469
25.4   有效算法 470
25.4.1   算法 471
25.4.2   安全属性 472
25.4.3   活性和复杂度 473
25.5   涉及时间不确定性的下界* 475
25.6   其他结果* 480
25.6.1   同步进程. 异步通道* 480
25.6.2   异步进程. 同步通道* 481
25.6.3   最终时间界限* 481
25.7   小结 483
25.8   参考文献注释 483
25.9   习题 483
参考文献 486
索引 512