第一章 引言 1
1.1 定义 1
1.2 与计算机系统部件的关系 2
1.3 动机 3
1.4 与并行多处理器／多计算机系统的关系 4
1.4.1 并行系统的特性 4
1.4.2 Flynn的分类法 8
1.4.3 耦合、并行、并发及粒度 9
1.5 消息传递系统与共享内存系统的对比 11
1.5.1 在共享内存的系统上仿真消息传递 11
1.5.2 在消息传递系统上仿真共享内存 12
1.6 分布式通信的原语 12
1.6.1 阻塞／非阻塞，同步／异步原语 12
1.6.2 处理器同步性 15
1.6.3 库与标准 15
1.7 同步与异步执行 16
1.7.1 通过同步系统仿真异步系统 17
1.7.2 通过异步系统仿真同步系统 17
1.7.3 仿真 18
1.8 设计主题与挑战 18
1.8.1 从系统角度看分布式系统的挑战 19
1.8.2 分布式计算中的算法挑战 20
1.8.3 分布式计算的应用以及更新的挑战 25
1.9 关于主题的选择与覆盖 27
1.10 本章小结 27
1.11 习题 28
1.12 参考文献说明 29
参考文献 30
第二章 分布式计算模型 33
2.1 分布式程序 33
2.2 分布式运行模型 33
2.3 通信网络模型 36
2.4 分布式系统的全局状态 36
2.4.1 全局状态 37
2.5 分布式计算的运行分割 38
2.6 事件的过去和未来锥面 39
2.7 进程通信模型 40
2.8 本章小结 40
2.9 习题 40
2.10 参考文献说明 41
参考文献 41
第三章 逻辑时间 42
3.1 引言 42
3.2 逻辑时钟框架 43
3.2.1 定义 43
3.2.2 实现逻辑时钟 43
3.3 标量时间 44
3.3.1 定义 44
3.3.2 基本性质 45
3.4 向量时间 46
3.4.1 定义 46
3.4.2 基本性质 47
3.4.3 有关向量时钟的大小 48
3.5 向量时钟的有效实现 49
3.5.1 Singhal-Kshemkalyani的差量技术 50
3.5.2 Fowler-Zwaenepoel的直接依赖技术 51
3.6 Jard-Jourdan的自适应技术 54
3.7 矩阵时间 56
3.7.1 定义 56
3.7.2 基本性质 58
3.8 虚拟时间 58
3.8.1 虚拟时间的定义 58
3.8.2 与Lamport逻辑时钟比较 59
3.8.3 时间变形机制 60
3.8.4 本地控制机制 60
3.8.5 全局控制机制 62
3.9 物理时钟同步：NTP 64
3.9.1 动机 64
3.9.2 定义及术语 65
3.9.3 时钟不准确性 65
3.10 本章小结 67
3.11 习题 68
3.12 参考文献说明 68
参考文献 69
第四章 记录全局状态与快照算法 71
4.1 引言 71
4.2 系统模型和定义 73
4.2.1 系统模型 73
4.2.2 一致性全局状态 74
4.2.3 有关分割的解 74
4.2.4 记录全局快照时遇到的问题 75
4.3 FIFO通道的快照算法 75
4.3.1 Chandy-Lamport算法 75
4.3.2 被记录全局状态的性质 77
4.4 Chandy-Lamport算法的变种 78
4.4.1 Spezialetti-Kearns算法 79
4.4.2 Venkatesan快照增量算法 80
4.4.3 Helary波同步方法 81
4.5 非FIFO通道的快照算法 81
4.5.1 Lai-Yang算法 82
4.5.2 Li等人的算法 83
4.5.3 Mattern算法 84
4.6 因果传递系统快照 85
4.6.1 进程状态记录 85
4.6.2 Acharya-Badrinath算法中的通道状态记录 86
4.6.3 Alagar-Venkatesan算法中的通道状态记录 86
4.7 监控全局状态 88
4.8 一致性全局快照的必要和充分条件 88
4.8.1 Zigzag路径和一致性全局快照 89
4.9 找出分布式计算中的一致性全局快照 92
4.9.1 找出一致性全局快照 92
4.9.2 枚举式一致性快照Manivannan-Netzer-Singhal算法 94
4.9.3 在分布式计算中找出Z路径 96
4.10 本章小结 97
4.11 习题 98
4.12 参考文献说明 99
参考文献 99
第五章 术语和基本算法 102
5.1 拓扑抽象和覆盖 102
5.2 分类和基本概念 104
5.2.1 应用执行和控制算法执行 104
5.2.2 集中式算法和分布式算法 104
5.2.3 对称算法和非对称算法 105
5.2.4 匿名算法 105
5.2.5 一致算法 105
5.2.6 自适应算法 105
5.2.7 确定性执行对非确定性执行 105
5.2.8 执行抑制 106
5.2.9 同步系统和异步系统 107
5.2.10 联机算法与脱机算法 107
5.2.11 故障模型 107
5.2.12 无需等待算法 108
5.2.13 通信通道 109
5.3 复杂度测量和度量 109
5.4 程序结构 110
5.5 图的基本算法 111
5.5.1 使用洪泛法的同步单一启动者生成树算法 111
5.5.2 使用洪泛法的异步单一启动者生成树算法 113
5.5.3 使用洪泛法的异步并发启动者生成树算法 115
5.5.4 异步并发启动者深度优先搜索生成树算法 118
5.5.5 在一棵树上广播和聚播 119
5.5.6 单一源最短路径算法：同步Bellman-Ford 120
5.5.7 距离向量路径选择 121
5.5.8 单一源最短路径算法：异步Bellman-Ford 122
5.5.9 全源最短路径：异步分布式Floyd-Warshall 123
5.5.10 有约束的异步和同步洪泛法（W/O一棵生成树） 126
5.5.11 同步系统的最小权重生成树算法 128
5.5.12 异步系统的最小权重树 132
5.6 同步工具 133
5.7 最大独立集合 138
5.8 连通支配集 140
5.9 紧凑路由表 141
5.10 选领导者 142
5.11 设计分布式图算法的挑战 144
5.12 对象副本问题 144
5.12.1 问题定义 145
5.12.2 算法概要 145
5.12.3 读和写 146
5.12.4 收敛到一个副本模式 146
5.13 本章小结 149
5.14 习题 150
5.15 参考文献说明 152
参考文献 153
第六章 消息序与组通信 156
6.1 消息序的模式 157
6.1.1 异步执行过程 157
6.1.2 先进先出执行过程 157
6.1.3 因果序执行过程 158
6.1.4 同步执行过程 160
6.2 使用同步通信的异步执行过程 161
6.2.1 用同步通信可实现的执行过程 162
6.2.2 序样式的层次体系 165
6.2.3 两种仿真 165
6.3 异步系统中同步程序的序 166
6.3.1 会合 167
6.3.2 双路会合算法 167
6.4 组通信 171
6.5 因果序 171
6.5.1 Raynal-Schiper-Toueg算法［22］ 172
6.5.2 Kshemkalyani-Singhai最优算法［20,21］ 173
6.6 全序 180
6.6.1 为全序设计的集中式算法 180
6.6.2 三阶段分布式算法 181
6.7 多播相关术语 185
6.8 多播传播树 186
6.9 应用层多播算法的分类 190
6.10 容错组通信的语义 192
6.11 网络层的分布式多播算法 194
6.11.1 泛洪约束的反向路径转发 194
6.11.2 Steiner树 195
6.11.3 多播的成本函数 196
6.11.4 有界延迟的Steiner树 196
6.11.5 核基树 199
6.12 本章小结 199
6.13 习题 200
6.14 参考文献说明 201
参考文献 202
第七章 终止检测 204
7.1 引言 204
7.2 分布式计算的系统模型 205
7.3 基于快照的终止检测算法 205
7.3.1 非形式化描述 206
7.3.2 形式化描述 206
7.3.3 讨论 207
7.4 信用-传递终止检测算法 207
7.4.1 形式化描述 208
7.4.2 算法的正确性 208
7.5 基于生成树的终止检测算法 209
7.5.1 定义 209
7.5.2 一个简单的算法 210
7.5.3 正确的算法 210
7.5.4 一个例子 211
7.5.5 算法性能分析 213
7.6 消息-优化终止检测算法 213
7.6.1 主要思想 213
7.6.2 算法描述 214
7.6.3 算法性能分析 216
7.7 通用分布式计算模型中的终止检测 216
7.7.1 模型定义和假设 217
7.7.2 符号 217
7.7.3 终止定义 217
7.7.4 一个静态终止检测算法 218
7.7.5 一个动态终止检测算法 219
7.8 原子计算模型中的终止检测 221
7.8.1 执行的原子模型 221
7.8.2 一个简单的计数方法 221
7.8.3 四计数器方法 222
7.8.4 怀疑论者算法 223
7.8.5 时间算法 223
7.8.6 向量计数算法 225
7.8.7 信道计数算法 226
7.9 带错分布式系统中的终止检测 229
7.9.1 流检测方案 229
7.9.2 捕获快照 230
7.9.3 算法描述 231
7.9.4 算法性能分析 234
7.10 本章小结 234
7.11 习题 235
7.12 参考文献说明 235
参考文献 236
第八章 知识推理 238
8.1 Muddy children难题 238
8.2 知识的逻辑 239
8.2.1 知识操作符 239
8.2.2 回到muddy children难题 240
8.2.3 克里普克结构 240
8.2.4 使用克里普克结构解决muddy children难题 241
8.2.5 知识的属性 243
8.3 同步系统中的知识 244
8.4 异步系统中的知识 244
8.4.1 逻辑和定义 244
8.4.2 异步系统中的达成一致 245
8.4.3 共同知识的变体 246
8.4.4 并发共同知识 246
8.5 知识转移 250
8.6 知识和时钟 251
8.7 本章小结 253
8.8 习题 253
8.9 参考文献说明 254
参考文献 254
第九章 分布式互斥算法 256
9.1 引言 256
9.2 预备知识 257
9.2.1 系统模型 257
9.2.2 互斥算法的必备条件 257
9.2.3 性能指标 258
9.3 Lamport算法 259
9.4 Ricart-Agrawala算法 262
9.5 Singhal动态信息结构算法 264
9.5.1 算法描述 266
9.5.2 正确性 268
9.5.3 性能分析 269
9.5.4 异构流量模式下的适应性 270
9.6 Lodha和Kshemkalyani的公平互斥算法 270
9.6.1 系统模型 270
9.6.2 算法描述 270
9.6.3 安全性、公平性与活性 275
9.6.4 消息复杂性 275
9.7 基于仲裁团的互斥算法 275
9.8 Maekawa算法 276
9.8.1 死锁问题 277
9.9 Agarwal-EI Abbadi基于仲裁团的算法 278
9.9.1 构造树状结构仲裁团 279
9.9.2 构造树状结构仲裁团算法分析 280
9.9.3 有效性 280
9.9.4 树状结构仲裁团的例子 281
9.9.5 分布式互斥算法 282
9.9.6 正确性证明 283
9.10 基于令牌的算法 283
9.11 Suzuki-Kasami广播算法 283
9.12 基于树的Raymond算法 285
9.12.1 HOLDER变量 286
9.12.2 算法操作 287
9.12.3 算法描述 287
9.12.4 正确性 289
9.12.5 开销和性能分析 290
9.12.6 算法初始化 291
9.12.7 错误和恢复 291
9.13 本章小结 292
9.14 习题 292
9.15 参考文献说明 293
参考文献 293
第十章 死锁检测 296
10.1 简介 296
10.2 系统模型 296
10.2.1 等待图 297
10.3 预备知识 297
10.3.1 死锁处理策略 297
10.3.2 死锁检测问题 298
10.4 死锁模型 298
10.4.1 单资源模型 299
10.4.2 AND模型 299
10.4.3 OR模型 299
10.4.4 AND-OR模型 300
10.4.5 （p q）模型 300
10.4.6 无限制模型 300
10.5 Knapp分布式死锁检测算法分类 301
10.5.1 路径推送算法 301
10.5.2 边探测算法 301
10.5.3 基于计算分散的算法 301
10.5.4 基于全局状态检测的算法 302
10.6 单资源模型下的Mitchell-Merritt算法 302
10.7 针对AND模型的Chandy-Misra-Haas算法 304
10.8 针对OR模型的Chandy-Misra-Haas算法 305
10.9 针对（p q）模型的Kshemkalyani-Singhal算法 307
10.9.1 算法的非正式描述 308
10.9.2 算法描述 310
10.10 本章小结 315
10.11 习题 315
10.12 参考文献说明 315
参考文献 316
第十一章 全局谓词的检测 320
11.1 稳定谓词和不稳定谓词 320
11.1.1 稳定谓词 321
11.1.2 不稳定谓词 322
11.2 谓词的形态 323
11.2.1 谓词检测的复杂性 324
11.3 关系谓词的集中式算法 324
11.4 合取谓词 327
11.4.1 合取谓词基于区间的集中式算法 328
11.4.2 Possibly（φ）基于全局状态的集中式算法 331
11.5 合取谓词的分布式算法 333
11.5.1 Possibly（φ）基于状态的分布式令牌算法 333
11.5.2 Definitely（φ）基于区间的分布式令牌算法 334
11.5.3 Possibly（φ）基于区间的分布式捎带算法 338
11.6 谓词的进一步分类 342
11.7 本章小结 342
11.8 习题 343
11.9 参考文献说明 344
参考文献 344
第十二章 分布式共享内存 347
12.1 抽象化及其优势 347
12.2 内存一致性模型 349
12.2.1 强一致性、原子一致性及线性 350
12.2.2 顺序一致性 352
12.2.3 因果一致性 355
12.2.4 处理器一致性 356
12.2.5 慢内存 357
12.2.6 一致性模型的层次结构 358
12.2.7 其他基于同步指令的一致性模型 358
12.3 共享内存的互斥 360
12.3.1 Lamport面包店算法 360
12.3.2 Lamport's WRWM技术和快速互斥 362
12.3.3 互斥的硬件支持 364
12.4 等待无关性 366
12.5 寄存器层次和无等待模拟 367
12.5.1 构造1：SRSW安全寄存器到MRSW安全寄存器 369
12.5.2 构造2：SRSW普通寄存器到MRSW普通寄存器 370
12.5.3 构造3：布尔MRSW安全寄存器到整数MRSW安全寄存器 370
12.5.4 构造4：布尔MRSW安全寄存器到布尔MRSW普通寄存器 370
12.5.5 构造5：布尔MRSW普通寄存器到整数MRSW普通寄存器 371
12.5.6 构造6：布尔MRSW普通寄存器到整数MRSW原子寄存器 373
12.5.7 构造7：整数MRSW原子寄存器到整数MRMW原子寄存器 375
12.5.8 构造8：整数SRSW原子寄存器到整数MRSW原子寄存器 376
12.6 共享对象的无等待原子快照 378
12.7 本章小结 381
12.8 习题 381
12.9 参考文献说明 383
参考文献 383
第十三章 检查点和卷回恢复 386
13.1 介绍 386
13.2 背景和定义 387
13.2.1 系统模型 387
13.2.2 本地检查点 388
13.2.3 一致的系统状态 388
13.2.4 与外部世界的交互 389
13.2.5 不同消息类型 389
13.3 错误恢复中的问题 390
13.4 基于检查点的恢复 392
13.4.1 无协作检查点 392
13.4.2 协作式检查点 393
13.4.3 最小处理无阻塞检查点的不可能性 395
13.4.4 通信引导检查点 396
13.5 基于日志的卷回恢复 397
13.5.1 确定事件和非确定事件 397
13.5.2 悲观日志 398
13.5.3 乐观日志 399
13.5.4 因果日志 400
13.6 Koo-Toueg协同检查点算法 401
13.6.1 检查点算法 401
13.6.2 卷回恢复算法 403
13.7 异步检查点和恢复的Juang-Venkatesan算法 404
13.7.1 系统模型和假设 404
13.7.2 异步检查点 404
13.7.3 恢复算法 405
13.8 Manivannan-Singhal准同步检查点算法 407
13.8.1 检查点算法 408
13.8.2 恢复算法 410
13.8.3 复杂消息处理 413
13.9 基于矢量时间的Peterson-Kearns算法 415
13.9.1 系统模型 415
13.9.2 算法的非形式化描述 416
13.9.3 卷回协议的形式化描述 418
13.9.4 正确性证明 419
13.10 Helary-Mostefaoui-Netzer-Raynal通信引导协议 421
13.10.1 设计原则 421
13.10.2 检查点协议 424
13.11 本章小结 426
13.12 习题 427
13.13 参考文献说明 427
参考文献 428
第十四章 共识和协定算法 431
14.1 问题定义 431
14.1.1 拜占庭协定及相关问题 433
14.1.2 问题的等价性及标示 433
14.2 结果概观 434
14.3 无故障系统（同步或者异步）中的协定问题 435
14.4 有故障的同步系统（消息传输机制）中的协定问题 436
14.4.1 针对崩溃故障（同步系统）的共识算法 436
14.4.2 针对拜占庭错误的共识算法（同步系统） 437
14.5 有故障的异步消息传输系统中的协定问题 447
14.5.1 得到一致解的不可能性 447
14.5.2 结束可靠的广播 449
14.5.3 分布式事务提交 449
14.5.4 k-set共识问题 450
14.5.5 近似共识 450
14.5.6 重命名问题 455
14.5.7 可靠广播 460
14.6 异步系统中无等待共享内存的共识问题 461
14.6.1 不可能有解 461
14.6.2 共识数以及共识层级 463
14.6.3 共识对象的通用性 468
14.6.4 共享内存中的k-set共识 472
14.6.5 共享内存的重命名问题 473
14.6.6 使用分裂器解决共享内存重命名问题 474
14.7 本章小结 476
14.8 习题 477
14.9 参考文献说明 478
参考文献 479
第十五章 失效检测 481
15.1 引言 481
15.2 非可靠失效检测程序 482
15.2.1 系统模型 482
15.2.2 失效检测程序 483
15.2.3 完备性的准确性 483
15.2.4 失效检测程序类型 485
15.2.5 失效检测程序的可简约性 485
15.2.6 简约弱失效检测程序W成强失效检测程序S 486
15.2.7 简约最终弱失效检测程序◇W成最终强失效检测程序◇S 488
15.3 共识问题 490
15.3.1 解共识问题 490
15.3.2 使用强失效检测程序S的解决方案 490
15.3.3 使用最终强失效检测程序◇S的解决方案 492
15.4 原子广播 495
15.5 原子广播的解决方案 495
15.6 解决基本一致问题的最弱失效检测程序 497
15.6.1 实际的失效检测程序 497
15.6.2 对一致的最弱失效检测程序 499
15.6.3 终止可靠广播的最弱失效检测程序 499
15.7 失效检测程序的实现 500
15.8 自适应失效检测程序协议 502
15.8.1 懒惰失效检测协议 502
15.9 习题 505
15.10 参考文献说明 505
参考文献 506
第十六章 分布式系统中的验证 508
16.1 简介 508
16.2 背景和定义 508
16.2.1 认证的基础 509
16.2.2 主体的类型 509
16.2.3 认证协议的简单分类 509
16.2.4 标记法 510
16.2.5 密码协议的设计原则 510
16.3 基于对称密码系统的协议 511
16.3.1 基本协议 512
16.3.2 使用nonce的修正协议 512
16.3.3 Wide-mouth frog协议 513
16.3.4 基于认证服务器的协议 514
16.3.5 一次性口令方案 515
16.3.6 Otway-Rees协议 517
16.3.7 Kerberos认证服务 518
16.4 基于非对称密码系统的协议 522
16.4.1 基本协议 523
16.4.2 使用认证授权的修改协议 523
16.4.3 Needham-Schroeder协议 524
16.4.4 SSL协议 526
16.5 基于口令认证 529
16.5.1 加密密钥交换协议 529
16.5.2 安全远程口令协议 530
16.6 认证协议失效 531
16.7 本章小结 532
16.8 习题 533
16.9 参考文献说明 533
参考文献 534
第十七章 自稳定 537
17.1 介绍 537
17.2 系统模型 538
17.3 自稳定性定义 539
17.3.1 随机自稳定性及概率自稳定性 540
17.4 自稳定性算法设计中的问题 541
17.4.1 个体单元中的状态数 542
17.4.2 一致与非一致网络 546
17.4.3 中央和分布式守护程序 547
17.4.4 减少令牌环中的状态数 548
17.4.5 共享内存模型 549
17.4.6 互斥 549
17.4.7 自稳定的开销 550
17.5 设计自稳定系统的方法 550
17.5.1 分层和模块化 550
17.6 通信协议 552
17.7 自稳定分布式生成树 553
17.8 构建生成树的自稳定算法 554
17.8.1 Dolev、Israeli和Moran算法 554
17.8.2 构建生成树的Afek、Kutten和Yang算法 556
17.8.3 构建生成树的Arora和Gouda算法 557
17.8.4 构建生成树的Huang等人算法 557
17.8.5 构建生成树的Afek和Bremler算法 557
17.9 1-最大独立集合的匿名自稳定算法 558
17.10 概率自稳定头标选择算法 560
17.11 编译在自稳定中的作用 562
17.11.1 顺序程序的编译程序 563
17.11.2 异步消息传递系统的编译程序 563
17.11.3 异步共享内存系统编译程序 564
17.12 自稳定作为容错的一个解法 564
17.13 阻碍自稳定的因素 566
17.14 自稳定的局限 567
17.15 本章小结 568
17.16 习题 569
17.17 参考文献说明 569
参考文献 570
第十八章 对等计算及覆盖网络 576
18.1 概述 576
18.1.1 Napster 577
18.1.2 应用层覆盖网络 577
18.2 数据索引和覆盖网络 578
18.2.1 分布式索引 579
18.3 非结构化覆盖网络 580
18.3.1 非结构化覆盖网络：属性 580
18.3.2 Gnutella 580
18.3.3 Gnutella以及非结构化覆盖网络中的查找 581
18.3.4 复制策略 583
18.3.5 复制策略实现 585
18.4 Chord分布式哈希表 586
18.4.1 概述 586
18.4.2 简单查找 587
18.4.3 可扩展的查找 588
18.4.4 管理网络扰动 589
18.4.5 复杂度 592
18.5 内容寻址网络 593
18.5.1 概述 593
18.5.2 CAN初始化 594
18.5.3 CAN路由 594
18.5.4 CAN维护 595
18.5.5 CAN优化 597
18.5.6 CAN复杂度 598
18.6 Tapestry 598
18.6.1 概述 598
18.6.2 覆盖网络和路由 598
18.6.3 对象发布和对象查找 601
18.6.4 节点插入 602
18.6.5 节点删除 603
18.7 P2P系统设计中的其他挑战 604
18.7.1 公平：一个博弈游戏 604
18.7.2 信任或者声誉管理 605
18.8 在存储空间及路由长度间折中 605
18.8.1 统一DHT协议 605
18.8.2 有关DHT存储和路由距离的约束 607
18.9 复杂网络的图结构 607
18.10 Internet图 609
18.10.1 基本定理和其定义 609
18.10.2 Internet的特性 611
18.10.3 复杂网络的错误和攻击容忍 613
18.11 通用随机图网络 615
18.12 小世界网络 615
18.13 规模无关网络 616
18.13.1 主方程法 617
18.13.2 速率方程法 617
18.14 演化网络 618
18.14.1 扩展的Barabasi-Albert模型 619
18.15 本章小结 621
18.16 习题 621
18.17 参考文献说明 622
参考文献 622
索引 625