分布式算法：直观方法（原书第2版）

本书是一本享誉世界的分布式算法经典指南，以独特的“直观方法”颠覆传统编写模式。它摒弃了复杂艰深的数学模型，转而通过丰富的示例、清晰的解释和精心设计的练习，引导读者快速建立分布式算法的直觉思维。目标是让读者在最短时间内，深刻理解算法的本质，而非陷入形式化论证的泥潭。此外，书中还包含证明概要，并在附录提供了许多算法的伪代码描述，用以论证算法的正确性或解释基本结果背后的思想。

本书是一本独具特色的分布式算法指南，其核心在于通过丰富的实例解析与实战练习来传授知识，而非深究复杂的数学模型。本书的目标是重点培养读者的算法思维，避开形式化证明，帮助读者快速掌握大量经典算法。书中采用简明非正式的算法描述、启发性案例与实践练习相结合的方式，讲述分布式算法的精髓，并附有大量算法伪代码。本版本内容全面更新，新增了关于分布式事务与安全性（涵盖区块链与量子密码学）的章节，并补充了回滚恢复算法、共享内存的共识算法等前沿主题。本书适合作为计算机专业高年级本科生或研究生的教材，也可供相关领域研究人员案头参考。

荷兰阿姆斯特丹自由大学计算机科学系理论计算机科学教授，同时他还是埃因霍温科技大学控制系统技术组的随机设计教授。他具有阿姆斯特丹大学计算机科学博士学位和数学硕士学位。

前言
第 1 章 引言　　　　　　　1
第 2 章 预备知识　　　　　　2
2.1 数学概念　　　　　　2
2.1.1 集合与序　　　　　2
2.1.2 算法的复杂度　　　　3
2.1.3 数的特殊运算　　　　4
2.2 消息传递　　　　　　4
2.2.1 转换系统　　　　　5
2.2.2 状态和事件　　　　 5
2.2.3 断言　　　　　　6
2.2.4 因果序　　　　　 6
2.2.5 逻辑时钟　　　　　7
2.2.6 基本算法和控制算法　　 8
2.3 共享内存　　　　　　8
2.4 练习　　　　　　　11
第 3 章 快照算法　　　　　 13
3.1 Chandy-Lamport 算法　　 14
3.2 Lai-Yang 算法　　　　15
3.3 Peterson-Kearns 回滚恢复
算法　　　　　　　16
3.4 练习　　　　　　　18
第 4 章 波算法　　　　　　 20
4.1 遍历算法　　　　　　20
4.1.1 Tarry 算法　　　　 20
4.1.2 深度优先搜索　　　　21
4.2 树算法　　　　　　 23
4.3 Echo 算法　　　　　 24
4.4 练习　　　　　　　25
第 5 章 死锁检测　　　　　 27
5.1 等待图　　　　　　 27
5.2 Bracha-Toueg 算法　　　 29
5.3 练习　　　　　　　35
第 6 章 终止检测算法　　　　 37
6.1 Dijkstra-Scholten 算法　　 37
6.2 Rana 算法　　　　　 39
6.3 Safra 算法　　　　　 41
6.4 分权终止检测算法　　　 42
6.5 容错型分权终止检测算法　　44
6.6 练习　　　　　　　45
第 7 章 垃圾回收算法　　　　 47
7.1 引用计数　　　　　　47
7.1.1 间接引用计数　　　　48
7.1.2 加权引用计数　　　　48
7.2 垃圾回收意味着终止检测　　49
7.3 追踪式　　　　　　 50
7.4 练习　　　　　　　50
第 8 章 路由算法　　　　　 52
8.1 Chandy-Misra 算法　　　52
8.2 Merlin-Segall 算法　　　54
8.3 Toueg 算法　　　　 57
8.4 Frederickson 算法　　　 59
8.5 分组交换方法　　　　 63
8.5.1 目的地控制器和
Hops-So-Far 控制器　　 64
VI 分布式算法：直观方法（原书第 2 版）
8.5.2 无环有向覆盖控制器
(Acyclic Orientation
Cover Controller)　　　64
8.6 互联网的路由算法　　　 66
8.7 练习　　　　　　　67
第 9 章 选举算法　　　　　 70
9.1 环选举算法　　　　 70
9.1.1 Chang-Roberts 算法　　 70
9.1.2 Franklin 算法　　　71
9.1.3 Dolev-Klawe-Rodeh 算法 72
9.2 树选举算法　　　　 73
9.3 带消波的 Echo 算法　　　75
9.4 最小生成树算法　　　　76
9.5 练习　　　　　　　81
第 10 章 匿名网络　　　　　 83
10.1 匿名环中选举的不可能性　 83
10.2 概率算法　　　　　84
10.3 环的 Itai-Rodeh 选举算法　 84
10.4 匿名网中带消波的 Echo
算法　　　　　　 86
10.5 计算匿名环长度是不可能的 88
10.6 计算环长度的 Itai-Rodeh
算法　　　　　　 88
10.7 IEEE 1394 中的选举算法　90
10.8 练习　　　　　　 91
第 11 章 同步网　　　　　 93
11.1 Awerbuch 同步器　　　 93
11.1.1 α 同步器　　　　 93
11.1.2 β 同步器　　　　 94
11.1.3 γ 同步器　　　　 94
11.2 带本地时钟的有界延迟网络 95
11.3 有界期望延迟的匿名环
选举算法　　　　　97
11.4 练习　　　　　　 99
第 12 章 崩溃共识算法　　　 100
12.1 1-崩溃共识的不可能性　　100
12.2 Bracha-Toueg 的崩溃
共识算法　　　　　101
12.3 故障检测器　　　　 103
12.4 弱精确故障检测器的共识
算法　　　　　　 104
12.5 Chandra-Toueg 算法　　 105
12.6 共享内存的共识算法　　 107
12.7 练习　　　　　　 108
第 13 章 拜占庭故障的共识算法　111
13.1 拜占庭共识的 Bracha-Toueg
算法　　　　　　 111
13.2 Mahaney-Schneider
同步器　　　　　 115
13.3 Lamport-Shostak-Pease
广播算法　　　　　116
13.4 Lamport-Shostak-Pease
认证算法　　　　　120
13.5 练习　　　　　　 122
第 14 章 互斥算法　　　　　124
14.1 Ricart-Agrawala 算法　　124
14.2 Raymond 算法　　　　125
14.3 Agrawal-El Abbadi 算法　 128
14.4 Peterson 算法　　　　130
14.4.1 两进程间的互斥　　　130
14.4.2 多进程间的互斥　　　131
14.5 Bakery 算法　　　　 133
14.6 Fischer 算法　　　　 135
14.7 Test-and-Test-and-Set 锁 136
14.7.1 Test-and-Set 锁　　 136
14.7.2 Test-and-Test-and-
目 录 VII
Set 锁　　　　　136
14.8 队列锁　　　　　　137
14.8.1 Anderson 锁　　　 137
14.8.2 CLH 锁　　　　138
14.8.3 MCS 锁　　　　 139
14.8.4 超时　　　　　140
14.9 练习　　　　　　 141
第 15 章 屏障　　　　　　 144
15.1 反转感应屏障　　　　144
15.2 组合树屏障　　　　 145
15.3 竞赛屏障　　　　 148
15.4 传播屏障　　　　 151
15.5 练习　　　　　　 152
第 16 章 分布式事务　　　　 153
16.1 事务的串行化　　　　153
16.2 两阶段和三阶段提交协议 157
16.3 事务内存　　　　 158
16.4 练习　　　　　　 160
第 17 章 自稳定　　　　　162
17.1 用 Dijkstra 令牌环的互斥　162
17.2 Arora-Gouda 的生成
树算法　　　　　 165
17.3 Afek-Kutten-Yung 的生成
树算法　　　　　 167
17.4 练习　　　　　　 169
第 18 章 安全性　　　　　171
18.1 基本技术　　　　 171
18.1.1 加密散列函数　　　171
18.1.2 公钥密码学　　　172
18.1.3 工作量证明　　　174
18.2 区块链　　　　　　174
18.3 量子密码学　　　　 177
18.3.1 量子运算　　　 178
18.3.2 BB84 密钥分配协议　　180
18.4 练习　　　　　　 181
第 19 章 在线调度　　　　　183
19.1 作业　　　　　　 183
19.2 作业调度器　　　　 184
19.2.1 周期作业调度　　　185
19.2.2 非周期作业调度　　　186
19.2.3 偶发作业调度　　　188
19.3 资源访问控制　　　　189
19.4 练习　　　　　　 191
附录 A 伪代码　　　　　　194
A.1 Chandy-Lamport 快照
算法　　　　　　 194
A.2 Lai-Yang 快照算法　　　195
A.3 Cidon 深度优先搜索算法　 196
A.4 树算法　　　　　　197
A.5 Echo 算法　　　　　198
A.6 Shavit-Francez 终止检测
算法　　　　　　 198
A.7 Rana 终止检测算法　　199
A.8 Safra 终止检测算法　　 200
A.9 分权终止检测算法　　　201
A.10 Chandy-Misra 路由算法　 202
A.11 Merlin-Segall 路由算法　 203
A.12 Toueg 路由算法　　　 204
A.13 Frederickson 宽度优先搜索
算法　　　　　　 205
A.14 Dolev-Klawe-Rodeh 选举
算法　　　　　　 207
A.15 Gallager-Humblet-Spira 最小
生成树算法　　　　 208
A.16 IEEE 1394 选举算法　　211
A.17 Awerbuch 同步算法　　 212
VIII 分布式算法：直观方法（原书第 2 版）
A.18 Ricart-Agrawala 互斥
算法　　　　　　 213
A.19 Raymond 互斥算法　　 214
A.20 Agrawal-El Abbadi 互斥
算法　　　　　　 216
A.21 MCS 队列锁算法　　　217
A.22 带超时机制的 CLH 队列锁
算法　　　　　　 218
A.23 Afek-Kutten-Yung 生成树
算法　　　　　　 219
参考文献　　　　　　　　222