本书详细介绍了分布式算法及其理论，结合大量定理、引理、命题等的证明，讨论了点到点消息传递模型上的算法、计算机通信网络中实现的算法，重点是分布式应用的控制算法（如波动算法、广播算法、选举算法、同步系统算法等），还涉及了利用分布式算法实现容错计算、方向侦听和故障检测器等方面的内容。本书条理清晰、深入浅出，适合作为大学本科高年级和研究生的分布式算法课程的教材和参考书，对于具有实践经验的专业人员也大有帮助。
无
在过去几年里，分布式系统和分布式信息处理得到广泛关注。几乎每一所大学都会开设至少一门关于分布式算法设计的课程。出现了许多关于分布式系统原理方面的书籍，例如Tanenbaum［Tan96］和Sloman & Kramer［SK87］，但这些书籍主要是针对结构而不是算法。自从本书第1版问世以来，相继出版的分布式算法方面的著作有Barbosa［Bar96］、Lynch［Lyn96］和Attiya & Welch［AW98］。
因为算法是计算机应用的基础，因此需要一本专门介绍分布式算法的书。本书的目的是展示过去20年来分布式算法方面的诸多理论。本书可作为分布式算法1~2学期的教学用书，一学期的课程可由教师从本书中选择若干专题来安排。
本书也可作为相关专业的工程师和从事分布式系统研究的科研人员的参考书。
练习。每章（除第1章和第13章）后面附有一些习题和项目。项目通常要求读者开发涉及该章内容的一些应用。大多数情况下，没有提供“答案”。
致谢。本书经以下人士的仔细校对。他们是：Erwin Bakker、Hans Bodlaender、Stefan Dobrev、Petra van Haaften、Ted Herman、Jan van Leeuwen、Patrick Lentfert、Friedemann Mattern、Pascale van der Put、Peter Ruˇziˇcka、Martin Rudalics、Anneke Schoone和Kaisa Sere。他们对手稿质量的改进提出了有益的意见。此外，在Utrecht大学选修秋季“分布式算法”课程的学生们也提供了有益的建议。计算机科学系为所需的文本处理和输出提供了技术支持。Susan Parkinson进行了文字编辑。
Gerard Tel
1994年4月/2000年2月
（荷）Gerard Tel：Gerard Tel: 在荷兰Utrecht大学获得博士学位，现任Utrecht大学计算与信息科学学院助理教授，其主要研究方向包括复杂性、压缩、密码学、通信和编码等。出版过多本广受好评的著作。
霍红卫：霍红卫: 1963年8月出生，博士。现为西安电子科技大学计算机学院教授。主要研究方向：算法分析与设计、并行与分布式计算、遗传算法、生物信息学中的优化算法。著作有：《算法设计与分析》、《并行分类算法》和《Exercises & Solutions on Algorithms》。
本书是关于分布式算法的最优秀的著作之一。它系统地阐述了分布式算法设计的理论、方法和应用实例。目前，国内尚缺少专门介绍分布式算法的著作。我们希望本书能对我国高等院校的计算机教育有所帮助。
在过去的二十年里，分布式算法一直是备受关注的研究课题。这本成功的教科书的第二版，介绍了分布式算法研究领域的最新进展。新增了两章关于方向侦听和故障检测器的内容，代表了当今该领域最新技术发展水平。
本书分四部分：协议（第2章～第5章）、基本算法（第6章～第12章）、容错（第13章～第17章）和附录（附录A、附录B）。书中内容全面阐述了过去20年来分布式算法方面的诸多理论。本书主要内容及特点如下：
* 第一部分介绍了分布式系统和通信网络的基本概念，讨论了平衡滑动窗口协议和基于计时器的协议，以严谨简明的形式对路由算法作了系统论述，最后讨论了缓冲区有限时无死锁的包交换问题。
* 第二部分讨论了基本算法。包括：波动算法、遍历算法、广播算法、选举算法、终止检测算法、匿名网络的随机算法、快照算法、方向侦听与定向算法、死锁检测算法和同步系统算法。
* 第三部分讨论了容错问题。引入了健壮算法和稳定算法的概念。证明了同步系统的健壮性要比异步系统更大。最后讨论了故障检测和稳定算法。
* 第四部分介绍了伪代码使用约定、图和网络中的一些基本概念和常用术语。
所有算法既给出严格的数学定义及类Pascal语言的形式描述，又以算法不变式作为手段给出算法正确性的形式证明，充分反映了作者在分布式算法方面的造诣。
本书适合作为高等院校分布式算法、分布式计算课程的本科生和研究生教材，同时可作为从事分布式系统设计与应用的专业人员的参考书。
由于时间较紧及译者水平有限，译文难免有错误及不妥之处，恳请读者批评指正。
霍红卫
西安电子科技大学计算机学院
2003年12月
第1章 导论: 分布式系统 1
1.1 分布式系统的定义 1
1.1.1 动机 1
1.1.2 计算机网络 3
1.1.3 广域网络 3
1.1.4 局域网 5
1.1.5 多处理器计算机 6
1.1.6 协同操作进程 8
1.2 体系结构和语言 10
1.2.1 结构 10
1.2.2 OSI参考模型 11
1.2.3 局域网络OSI模型：IEEE标准 13
1.2.4 语言支持 14
1.3 分布式算法 15
1.3.1 分布式算法与集中式算法 15
1.3.2 一个例子：单消息通信 16
1.3.3 研究领域 20
1.4 本书概要 21
第一部分 协 议
第2章 模型 25
2.1 转移系统和算法 25
2.1.1 转移系统 26
2.1.2 异步消息传递系统 26
2.1.3 同步消息传递系统 27
2.1.4 公平性 28
2.2 转移系统性质的证明 29
2.2.1 安全性 29
2.2.2 活动性 30
2.3 事件的因果序和逻辑时钟 31
2.3.1 事件的独立性和相关性 32
2.3.2 执行的等价性：计算 33
2.3.3 逻辑时钟 35
2.4 附加假设，复杂度 37
2.4.1 网络拓扑结构 37
2.4.2 信道性质 38
2.4.3 实时性假设 39
2.4.4 进程知识 40
2.4.5 分布式算法的复杂度 40
习题 41
第3章 通信协议 43
3.1 平衡滑动窗口协议 44
3.1.1 协议表示 44
3.1.2 协议的正确性证明 46
3.1.3 协议讨论 47
3.2 基于计时器的协议 49
3.2.1 协议表示 51
3.2.2 协议的正确性证明 54
3.2.3 协议讨论 57
习题 60
第4章 路由算法 61
4.1 基于目的节点的路由 62
4.2 所有点对之间的最短路径问题 65
4.2.1 Floyd-Warshall算法 65
4.2.2 Toueg最短路径算法 67
4.2.3 讨论以及更多算法 70
4.3 变更算法 73
4.3.1 算法描述 74
4.3.2 变更算法的正确性 78
4.3.3 算法讨论 79
4.4 带有压缩路由表的路由 80
4.4.1 树标号模式 80
4.4.2 区间路由 82
4.4.3 前缀路由 88
4.5 分级路由 90
习题 92
第5章 无死锁的包交换 93
5.1 引言 93
5.2 有结构的方法 94
5.2.1 缓冲图 95
5.2.2 图G 的定向 97
5.3 无结构的方法 100
5.3.1 前向计数控制器和后向计数控制器 100
5.3.2 前向状态控制器和后向状态控制器 101
5.4 需进一步研究的问题 102
5.4.1 拓扑变化 102
5.4.2 其他类型的死锁 103
5.4.3 活锁 104
习题 105
第二部分 基 本 算 法
第6章 波动算法与遍历算法 107
6.1 波动算法的定义和使用 107
6.1.1 波动算法定义 107
6.1.2 波动算法的一些基本结果 109
6.1.3 具有反馈的信息传播 110
6.1.4 同步 111
6.1.5 计算下确界函数 111
6.2 波动算法集 112
6.2.1 环网算法 112
6.2.2 树算法 113
6.2.3 回波算法 115
6.2.4 轮询算法 116
6.2.5 相位算法 117
6.2.6 Finn算法 118
6.3 遍历算法 120
6.3.1 遍历团 121
6.3.2 遍历圆环 121
6.3.3 遍历超立方体 122
6.3.4 遍历连通网络 123
6.4 深度优先搜索的时间复杂度 124
6.4.1 分布式深度优先搜索 125
6.4.2 线性时间的深度优先搜索算法 126
6.4.3 具有近邻知识的深度优先搜索 130
6.5 遗留问题 130
6.5.1 波动算法综述 130
6.5.2 计算和 130
6.5.3 时间复杂度的另一种定义 132
习题 134
第7章 选举算法 137
7.1 引言 137
7.1.1 本章所做假设 138
7.1.2 选举和波动 138
7.2 环网 140
7.2.1 LeLann和Chang-Roberts算法 140
7.2.2 Peterson/Dolev-Klawe-Rodeh算法 144
7.2.3 一个下界 146
7.3 任意网 148
7.3.1 废止和快速算法 149
7.3.2 Gallager-Humblet-Spira算法 151
7.3.3 GHS算法的全局描述 152
7.3.4 GHS算法的详细描述 153
7.3.5 GHS算法的讨论和变化 157
7.4 Korach-Kutten-Moran算法 158
7.4.1 模块构造 158
7.4.2 KKM算法的应用 161
习题 162
第8章 终止检测 165
8.1 预备知识 165
8.1.1 定义 165
8.1.2 两个下界 167
8.1.3 终止进程 169
8.2 计算树和森林 169
8.2.1 Dijkstra-Scholten算法 169
8.2.2 Shavit-Francez算法 172
8.3 基于波动的方法 175
8.3.1 Dijkstra-Feijen-Van Gasteren算法 175
8.3.2 基本消息的计数：Safra算法 178
8.3.3 利用确认 181
8.3.4 带波动的终止检测 183
8.4 其他方法 184
8.4.1 信用-恢复算法 184
8.4.2 基于时戳的终止检测方法 186
习题 188
第9章 匿名网络 191
9.1 预备知识 192
9.1.1 定义 192
9.1.2 概率算法的分类 194
9.1.3 本章考虑的问题 195
9.1.4 同步消息传递与异步消息传递 195
9.2 确定算法 196
9.2.1 确定性的选举：否定性的结果 196
9.2.2 环上函数计算 197
9.3 概率选举算法 200
9.4 网络规模计算 202
9.4.1 否定性结果 203
9.4.2 计算环规模的算法 204
习题 206
第10章 快照 209
10.1 预备知识 209
10.2 两个快照算法 212
10.2.1 Chandy-Lamport算法 212
10.2.2 Lai-Yang算法 213
10.3 使用快照算法 214
10.3.1 计算信道状态 214
10.3.2 快照的适时性 215
10.3.3 稳定性检测 216
10.4 应用：死锁检测 217
10.4.1 基本计算模型和问题阐述 217
10.4.2 全局-标记算法 219
10.4.3 受限模型的死锁检测 220
习题 221
第11章 方向侦听与定向 223
11.1 引言和定义 223
11.1.1 方向侦听的定义和特性 223
11.1.2 利用方向侦听 225
11.1.3 具有方向侦听的广播 226
11.2 环和弦环的选举算法 228
11.2.1 Franklin算法 228
11.2.2 Attiya改进 229
11.2.3 最小化弦数 230
11.2.4 1-弦线性算法 232
11.3 超立方体上的计算 234
11.3.1 基线：没有拓扑知识 235
11.3.2 进行比赛的算法 235
11.3.3 多路径流量算法 237
11.3.4 使用掩码的有效超立方体算法 240
11.3.5 无标号超立方体上的选举算法 241
11.4 与复杂度有关的问题 242
11.4.1 团或任意图的定向 242
11.4.2 位复杂度和多路径流量算法 243
11.4.3 Verweij随机漫步算法 244
11.5 结论和未解决的问题 246
11.5.1 利用方向侦听 246
11.5.2 复杂度归约 246
11.5.3 当前研究 247
习题 247
第12章 网络中的同步 249
12.1 预备知识 249
12.1.1 同步网络 249
12.1.2 通过同步提高效率 250
12.1.3 异步有限延迟网络 251
12.2 同步网络中的选举 254
12.2.1 网络规模已知 254
12.2.2 网络规模未知 255
12.2.3 补充结果 256
12.3 同步器算法 256
12.3.1 简单同步器 256
12.3.2 a 、b 和g 同步器 258
12.4 应用：广度优先搜索 260
12.4.1 同步BFS算法 261
12.4.2 与同步器组合 261
12.4.3 异步BFS算法 261
12.5 Archimedean 假设 264
习题 265
第三部分 容 错
第13章 分布式系统中的容错 267
13.1 利用容错算法的原因 267
13.2 健壮算法 268
13.2.1 故障模型 268
13.2.2 判定问题 269
13.2.3 第14章到第16章综述 270
13.2.4 本书中没有涉及的主题 271
13.3 稳定算法 271
第14章 异步系统中的容错 273
14.1 一致性的不可能性 273
14.1.1 表示、定义及基本结果 273
14.1.2 不可能性证明 274
14.1.3 讨论 275
14.2 初始死进程 276
14.3 确定可实现实例 277
14.3.1 可解问题：重命名 278
14.3.2 扩展的不可能性结果 280
14.4 概率一致性算法 282
14.4.1 损毁-健壮一致协议 282
14.4.2 Byzantine-健壮一致性协议 285
14.5 弱终止性 288
习题 290
第15章 同步系统中的容错 293
15.1 同步判定协议 293
15.1.1 弹性界限 294
15.1.2 Byzantine广播算法 295
15.1.3 多项式级的广播算法 297
15.2 鉴别协议 300
15.2.1 高度弹性的协议 301
15.2.2 数字签名的实现 303
15.2.3 ElGamal签名模式 303
15.2.4 RSA签名模式 304
15.2.5 Fiat-Shamir签名模式 305
15.2.6 概述和讨论 306
15.3 时钟同步 308
15.3.1 读取远程时钟 308
15.3.2 分布式时钟同步 310
15.3.3 轮模型的实现 313
习题 314
第16章 故障检测 315
16.1 模型和定义 315
16.1.1 四种基本检测器类型 316
16.1.2 故障检测器的用途和缺陷 317
16.2 用弱精确检测器解一致性问题 318
16.3 最终弱精确检测器 319
16.3.1 弹性上界 319
16.3.2 一致算法 320
16.4 故障检测器的实现 321
16.4.1 同步系统：完美检测 321
16.4.2 部分同步系统：最终完美检测 321
16.4.3 小结 322
习题 323
第17章 稳定性 325
17.1 引言 325
17.1.1 定义 325
17.1.2 稳定系统中的通信 326
17.1.3 例子：Dijkstra令牌环 327
17.2 图论算法 329
17.2.1 环定向 329
17.2.2 最大匹配 331
17.2.3 选举和生成树构造 332
17.3 稳定方法学 334
17.3.1 协议组合 334
17.3.2 计算最小路径 338
17.3.3 结论和讨论 342
习题 342
第四部分 附 录
附录A 伪代码使用约定 345
附录B 图和网络 349
参考文献 359
主题词索引 375
