分布式算法 (2008 年度畅销榜NO.6197 )

在本书中，作者给出设计，实现和分析分布式算法的蓝图。本书适合学生、程序员、系统分析员和研究人员等不同类型的读者。本书包括这个领域最重要的算法和不可能解．而且都采用简单的自动机理论进行论述。对所有算法的正确性都给予证明．并且根据精确定义的复杂度标准分析算法的复杂度。其中涉及的问题包括资源分配、通信、分布式处理器之间的一致性、数据一致性、死锁检测、领导者进程的选取、全局快照等。\r\n\r\n 本书的内容按照系统模型组织，首先是根据定时模型．然后在定时模型内再根据进程间的通信机制。不同系统的材料分别独立成章，便于查阅。\r\n\r\n 本书论述十分严谨，但又很直观．便于读者迅速理解。本书也为读者提供设计新的算法和证明新的不可能解的基本数学工具。而且，它教给读者怎样对分布式系统进行严格的推理 —包括形式化建模，为它们所需的行为设计精确的指标，证明它们的正确性．并且用实际的度量标准来评价它们的性能。\r\n\r\n 本书对分布式算法进行全面介绍，包括最为重要的算法和不可能性结果。绝大部分的解都给出了数学证明。这些算法都根据精确定义的复杂度衡量方法进行分析。本书还讲述针对许多典型问题的算法、各类系统模型及其能力。章后提供大量习题并列出了详细的参考文献。\r\n\r\n 本书可作为高等院校计算机系研究生的教材，尤其适合对计算机理论或体系结构感兴趣的学生学习，还适合分布式设计人员、研究人员及其相关技术人员参考。\r\n
\r\n

出版者的话\r\n专家指导委员会\r\n译者序\r\n前言\r\n第1章 引言 1\r\n1.1 相关主题 1\r\n1.2 我们的观点 2\r\n1.3 本书内容综述 3\r\n1.4 参考文献注释 7\r\n1.5 标记 7\r\n第一部分 同步网络算法\r\n第2章 建模I：同步网络模型 10\r\n2.1 同步网络系统 10\r\n2.2 故障 11\r\n2.3 输入和输出 11\r\n2.4 运行 11\r\n2.5 证明方法 12\r\n2.6 复杂度度量 12\r\n2.7 随机化 12\r\n2.8 参考文献注释 13\r\n第3章 同步环中的领导者选择 14\r\n3.1 问题 14\r\n3.2 相同进程的不可能性结果 14\r\n3.3 基本算法 15\r\n3.4 通信复杂度为O(n log n)的算法 17\r\n3.5 非基于比较的算法 19\r\n3.5.1 时间片算法 20\r\n3.5.2 变速算法 20\r\n3.6 基于比较的算法的下界 21\r\n3.7 非基于比较的算法的下界* 25\r\n3.8 参考文献注释 26\r\n3.9 习题 27\r\n第4章 一般同步网络中的算法 29\r\n4.1 一般网络中的领导者选举 29\r\n4.1.1 问题 29\r\n4.1.2 简单的洪泛算法 29\r\n4.1.3 降低通信复杂度 31\r\n4.2 广度优先搜索 32\r\n4.2.1 问题 32\r\n4.2.2 基本的广度优先搜索算法 33\r\n4.2.3 应用 34\r\n4.3 最短路径 35\r\n4.4 最小生成树 36\r\n4.4.1 问题 36\r\n4.4.2 基本定理 36\r\n4.4.3 算法 37\r\n4.5 最大独立集 39\r\n4.5.1 问题 40\r\n4.5.2 随机化算法 40\r\n4.5.3 分析* 42\r\n4.6 参考文献注释 43\r\n4.7 习题 43\r\n第5章 链路故障时的分布式一致性 46\r\n5.1 协同攻击问题—确定性版本 46\r\n5.2 协同攻击问题—随机化版本 48\r\n5.2.1 形式化模型 49\r\n5.2.2 算法 49\r\n5.2.3 不一致的下限 52\r\n5.3 参考文献注释 54\r\n5.4 习题 54\r\n第6章 进程故障下的分布式一致性 56\r\n6.1 问题 56\r\n6.2 针对停止故障的算法 58\r\n6.2.1 基本算法 58\r\n6.2.2 减少通信 59\r\n6.2.3 指数信息收集算法 61\r\n6.2.4 带鉴别的Byzantine一致性 66\r\n6.3 针对Byzantine故障的算法 66\r\n6.3.1 举例 66\r\n6.3.2 Byzantine一致性问题的EIG算法 68\r\n6.3.3 使用二元Byzantine一致的一般\r\n的Byzantine一致性问题 71\r\n6.3.4 减少通信开销 72\r\n6.4 Byzantine一致性问题中进程的个数 74\r\n6.5 一般图中的Byzantine一致性问题 78\r\n6.6 弱Byzantine一致性 81\r\n6.7 有停止故障时的轮数 82\r\n6.8 参考文献注释 88\r\n6.9 习题 89\r\n第7章 更多的一致性问题 93\r\n7.1 k一致性问题 93\r\n7.1.1 问题 93\r\n7.1.2 算法 93\r\n7.1.3 下界* 95\r\n7.2 近似一致性 102\r\n7.3 提交问题 105\r\n7.3.1 问题 105\r\n7.3.2 两阶段提交 106\r\n7.3.3 三阶段提交 107\r\n7.3.4 消息数的下界 109\r\n7.4 参考文献注释 111\r\n7.5 习题 111\r\n第二部分 异步算法\r\n第8章 建模II：异步系统模型 114\r\n8.1 输入/输出自动机 114\r\n8.2 自动机的操作 118\r\n8.2.1 合成 118\r\n8.2.2 隐藏 121\r\n8.3 公平性 121\r\n8.4 问题的输入和输出 123\r\n8.5 属性与证明方法 124\r\n8.5.1 不变式断言 124\r\n8.5.2 轨迹属性 124\r\n8.5.3 安全与活性属性 125\r\n8.5.4 合成推理 126\r\n8.5.5 层次化证明 128\r\n8.6 复杂度衡量 130\r\n8.7 不可区分运行 131\r\n8.8 随机化 131\r\n8.9 参考文献注释 131\r\n8.10 习题 132\r\n第二部分A 异步共享存储器算法\r\n第9章 建模III：异步共享存储器模型 136\r\n9.1 共享存储器系统 136\r\n9.2 环境模型 138\r\n9.3 不可区分状态 140\r\n9.4 共享变量类型 140\r\n9.5 复杂度衡量 144\r\n9.6 故障 144\r\n9.7 随机化 145\r\n9.8 参考文献注释 145\r\n9.9 习题 145\r\n第10章 互斥 146\r\n10.1 异步共享存储器模型 146\r\n10.2 问题 148\r\n10.3 Dijkstra的互斥算法 151\r\n10.3.1 算法 151\r\n10.3.2 正确性证明 154\r\n10.3.3 互斥条件的一个断言证明 156\r\n10.3.4 运行时间 157\r\n10.4 互斥算法的更强条件 158\r\n10.5 锁定权互斥算法 159\r\n10.5.1 双进程算法 159\r\n10.5.2 n进程算法 163\r\n10.5.3 锦标赛算法 167\r\n10.6 使用单写者共享存储器的算法 170\r\n10.7 Bakery算法 171\r\n10.8 寄存器数量的下界 173\r\n10.8.1 基本事实 174\r\n10.8.2 单写者共享变量 175\r\n10.8.3 多写者共享变量 175\r\n10.9 使用读-改-写共享变量的互斥 179\r\n10.9.1 基本问题 179\r\n10.9.2 有界绕过次数 180\r\n10.9.3 锁定权 185\r\n10.9.4 模拟证明 187\r\n10.10 参考文献注释 189\r\n10.11 习题 190\r\n第11章 资源分配 194\r\n11.1 问题 194\r\n11.1.1 显式资源说明和互斥说明 194\r\n11.1.2 资源分配问题 195\r\n11.1.3 哲学家用餐问题 196\r\n11.1.4 解法的受限形式 197\r\n11.2 对称哲学家用餐算法的不存在性 197\r\n11.3 右-左哲学家用餐算法 199\r\n11.3.1 等待链 199\r\n11.3.2 基本算法 200\r\n11.3.3 扩展 202\r\n11.4 哲学家用餐随机算法* 204\r\n11.4.1 算法* 205\r\n11.4.2 正确性* 207\r\n11.5 参考文献注释 212\r\n11.6 习题 213\r\n第12章 一致性 215\r\n12.1 问题 215\r\n12.2 使用读/写共享存储器的一致性 217\r\n12.2.1 限制 218\r\n12.2.2 术语 218\r\n12.2.3 双价初始化 218\r\n12.2.4 无等待终止的不可能性 219\r\n12.2.5 单故障终止的不可能性结果 221\r\n12.3 读/改/写共享存储器上的一致性\r\n问题 223\r\n12.4 其他共享存储器类型 224\r\n12.5 异步共享存储器系统中的可计算性* 224\r\n12.6 参考文献注释 225\r\n12.7 习题 226\r\n第13章 原子对象 229\r\n13.1 定义和基本结论 229\r\n13.1.1 原子对象的定义 229\r\n13.1.2 规范无等待原子对象自动机 235\r\n13.1.3 原子对象的合成 237\r\n13.1.4 原子对象和共享变量 237\r\n13.1.5 显示原子性的一个充分条件 241\r\n13.2 用读/写变量实现读-改-写原子对象 242\r\n13.3 共享存储器的原子快照 243\r\n13.3.1 问题 243\r\n13.3.2 带无界变量的一个算法 244\r\n13.3.3 带有界变量的一个算法* 247\r\n13.4 读/写原子对象 250\r\n13.4.1 问题 250\r\n13.4.2 证明原子性的其他引理 250\r\n13.4.3 带无界变量的一个算法 251\r\n13.4.4 两个写者的有界算法 254\r\n13.4.5 使用快照的算法 258\r\n13.5 参考文献注释 259\r\n13.6 习题 260\r\n第二部分B 异步网络算法\r\n第14章 建模IV：异步网络模型 264\r\n14.1 发送/接收系统 264\r\n14.1.1 进程 264\r\n14.1.2 发送/接收通道 264\r\n14.1.3 异步发送/接收系统 268\r\n14.1.4 使用可靠FIFO通道的发送/\r\n接收系统的特征 268\r\n14.1.5 复杂度度量 269\r\n14.2 广播系统 269\r\n14.2.1 进程 269\r\n14.2.2 广播通道 270\r\n14.2.3 异步广播系统 270\r\n14.2.4 采用可靠广播通道的广播系统\r\n的特征 270\r\n14.2.5 复杂度度量 271\r\n14.3 多播系统 271\r\n14.3.1 进程 271\r\n14.3.2 多播通道 271\r\n14.3.3 异步多播系统 272\r\n14.4 参考文献注释 272\r\n14.5 习题 272\r\n第15章 基本异步网络算法 274\r\n15.1 环中的领导者选举 274\r\n15.1.1 LCR算法 275\r\n15.1.2 HS算法 278\r\n15.1.3 Peterson Leader算法 278\r\n15.1.4 通信复杂度的下界 281\r\n15.2 任意网络中的领导者选举 286\r\n15.3 生成树的构造. 广播和敛播 287\r\n15.4 广度优先搜索和最短路径 290\r\n15.5 最小生成树 295\r\n15.5.1 问题描述 295\r\n15.5.2 同步算法：回顾 296\r\n15.5.3 GHS算法：概要 296\r\n15.5.4 更详细的算法 297\r\n15.5.5 特殊消息 299\r\n15.5.6 复杂度分析 301\r\n15.5.7 GHS算法的正确性证明 301\r\n15.5.8 简单“同步”策略 302\r\n15.5.9 应用到领导者选举算法中 302\r\n15.6 参考文献注释 303\r\n15.7 习题 303\r\n第16章 同步器 307\r\n16.1 问题 307\r\n16.2 局部同步器 309\r\n16.3 安全同步器 313\r\n16.3.1 前端自动机 314\r\n16.3.2 通道自动机 315\r\n16.3.3 安全同步器 315\r\n16.3.4 正确性 315\r\n16.4 安全同步器的实现 316\r\n16.4.1 同步器Alpha 316\r\n16.4.2 同步器Beta 317\r\n16.4.3 同步器Gamma 317\r\n16.5 应用 320\r\n16.5.1 领导者选举 321\r\n16.5.2 深度优先搜索 321\r\n16.5.3 最短路径 321\r\n16.5.4 广播与确认 321\r\n16.5.5 最大独立集 321\r\n16.6 时间下界 321\r\n16.7 参考文献注释 324\r\n16.8 习题 324\r\n第17章 共享存储器与网络 326\r\n17.1 从共享存储器模型到网络模型\r\n的转换 326\r\n17.1.1 问题 326\r\n17.1.2 无故障时的策略 327\r\n17.1.3 容忍进程故障的算法 332\r\n17.1.4 对于n/2故障的不可能性结果 335\r\n17.2 从网络模型转换到共享存储器模型 336\r\n17.2.1 发送/接收系统 336\r\n17.2.2 广播系统 338\r\n17.2.3 异步网络中一致性的不可能性 338\r\n17.3 参考文献注释 339\r\n17.4 习题 339\r\n第18章 逻辑时间 341\r\n18.1 异步网络的逻辑时间 341\r\n18.1.1 发送/接收系统 341\r\n18.1.2 广播系统 343\r\n18.2 使用逻辑时间的异步算法 344\r\n18.2.1 时钟的走动 344\r\n18.2.2 延迟未来事件 345\r\n18.3 应用 346\r\n18.3.1 银行系统 346\r\n18.3.2 全局快照 348\r\n18.3.3 模拟一台单状态机器 349\r\n18.4 从实际时间算法到逻辑时间算法\r\n的变换* 352\r\n18.5 参考文献注释 352\r\n18.6 习题 353\r\n第19章 一致全局快照和稳定属性检测 355\r\n19.1 发散算法的终止检测 355\r\n19.1.1 问题 355\r\n19.1.2 DijkstraScholten算法 356\r\n19.2 一致全局快照 360\r\n19.2.1 问题 360\r\n19.2.2 ChandyLamport算法 361\r\n19.2.3 应用 364\r\n19.3 参考文献注释 366\r\n19.4 习题 367\r\n第20章 网络资源分配 369\r\n20.1 互斥 369\r\n20.1.1 问题 369\r\n20.1.2 模拟共享存储器 370\r\n20.1.3 循环令牌算法 370\r\n20.1.4 基于逻辑时间的算法 372\r\n20.1.5 LogicalTimeME算法的改进 374\r\n20.2 通用资源分配 376\r\n20.2.1 问题 376\r\n20.2.2 着色算法 377\r\n20.2.3 基于逻辑时间的算法 377\r\n20.2.4 无环有向图算法 378\r\n20.2.5 哲学家饮水* 379\r\n20.3 参考文献注释 383\r\n20.4 习题 383\r\n第21章 带进程故障的异步网络计算 386\r\n21.1 网络模型 386\r\n21.2 有故障环境中一致性的不可能性 387\r\n21.3 随机算法 388\r\n21.4 故障检测器 390\r\n21.5 k一致性 393\r\n21.6 近似一致性 394\r\n21.7 异步网络的计算能力* 395\r\n21.8 参考文献注释 396\r\n21.9 习题 396\r\n第22章 数据链路协议 399\r\n22.1 问题阐述 399\r\n22.2 Stenning协议 400\r\n22.3 位变换协议 403\r\n22.4 可重排序的有界标志协议 406\r\n22.4.1 关于重排序和复制的不可能\r\n性结论 407\r\n22.4.2 容许丢失和重排序的有界标\r\n志协议 408\r\n22.4.3 不存在容许消息丢失和重排序\r\n的高效协议 412\r\n22.5 容许进程崩溃 414\r\n22.5.1 简单的不可能性结论 415\r\n22.5.2 更复杂的不可能性结论 415\r\n22.5.3 实用的协议 418\r\n22.6 参考文献注释 423\r\n22.7 习题 423\r\n第三部分 部分同步算法\r\n第23章 建模V: 部分同步系统模型 428\r\n23.1 MMT 定时自动机 428\r\n23.1.1 基本定义 428\r\n23.1.2 操作 432\r\n23.2 通用定时自动机 434\r\n23.2.1 基本定义 434\r\n23.2.2 将MMT自动机转化为通用定时\r\n自动机 437\r\n23.2.3 操作 440\r\n23.3 属性和证明方法 441\r\n23.3.1 不变式 441\r\n23.3.2 定时轨迹属性 443\r\n23.3.3 模拟 444\r\n23.4 构造共享存储器和网络系统的模型 449\r\n23.4.1 共享存储器系统 449\r\n23.4.2 网络 449\r\n23.5 参考文献注释 449\r\n23.6 习题 450\r\n第24章 部分同步的互斥 452\r\n24.1 问题 452\r\n24.2 单寄存器算法 453\r\n24.3 对时间故障的回复性 459\r\n24.4 不可能性结果 461\r\n24.4.1 时间下界 462\r\n24.4.2 最终时间界限的不可能性结果* 462\r\n24.5 参考文献注释 463\r\n24.6 习题 463\r\n第25章 部分同步的一致性 466\r\n25.1 问题 466\r\n25.2 故障检测器 467\r\n25.3 基本结论 468\r\n25.3.1 上界 468\r\n25.3.2 下界 469\r\n25.4 有效算法 470\r\n25.4.1 算法 471\r\n25.4.2 安全属性 472\r\n25.4.3 活性和复杂度 473\r\n25.5 涉及时间不确定性的下界* 475\r\n25.6 其他结果* 480\r\n25.6.1 同步进程. 异步通道* 480\r\n25.6.2 异步进程. 同步通道* 481\r\n25.6.3 最终时间界限* 481\r\n25.7 小结 483\r\n25.8 参考文献注释 483\r\n25.9 习题 483\r\n参考文献 486\r\n索引 512 \r\n
\r\n

译 者 序
分布式计算是随着计算机网络的发展而兴起的, 现已成为提高问题求解规模和速度. 提高系统可靠性的重要手段, 在数值模拟和生物工程等应用领域中被广泛应用. 随着网络技术的发展以及网络计算的兴起, 分布式计算技术也在不断地发展和完善中, 在计算机技术的发展和应用中发挥着越来越重要的作用. 在我国科学工程计算部门和高等院校中, 有越来越多的科技工作者开始学习和研究分布式计算技术.
分布式计算包括三个层面的内容：作为底层的分布式系统, 作为理论指导的分布式算法, 以及结合具体问题的程序实现. 其中, 分布式算法处于重要地位, 它是分布式系统的体现, 更是分布式程序设计的基础和灵魂. 分布式算法的一个重要特点是, 它并不仅是抽象的理论研究, 而且是与具体的分布式系统和应用问题密切相关的.
然而, 在分布式算法的研究中, 国内的有关资料十分缺乏, 因此我们翻译了本书, 它有几个显著特点：
全面：本书分三部分, 分别对同步算法. 异步算法和部分同步算法进行全面的介绍, 可以作为一本分布式算法的完全手册.
严谨：书中的算法和概念都给出准确的定义, 性能的分析评价都给出严格的证明, 可以作为进一步深入理论研究的基础.
深入浅出：虽然算法理论有很强的抽象性, 但是本书能够用浅显的语言和大量的图示作出详尽的讲解, 阅读本书只需要读者具备一些基本的离散数学和概率知识. 因此, 本书可以适合不同层次的读者.
本书的翻译是专门从事分布式算法的科研工作者通力合作的结果, 其中清华大学计算机系舒继武副教授翻译了序言和第1章至第7章, 南京大学计算机系李国东副教授翻译了第8章至第13章和第15章至第20章, 北京大学计算机系余华山博士翻译了第14章和第21章至第25章, 全书由舒继武和李国东统稿和审校.
此书的翻译过程中, 我们深切体会到本书作者在分布式算法方面的造诣, 自身也获得了提高. 希望本书能使国内的学者共享本书作者的思想和结晶.
由于分布式算法是一个蓬勃发展的领域, 译者水平有限, 加上时间仓促, 书中的错误在所难免, 竭诚欢迎广大读者批评指正.
译 者
2003年9月

Nancy A.Lynch 是麻省理工学院电子工程和计算机科学系的教授. 领导麻省理工学院的分布式系统理论研究组. 在分布式算法和不可能解以及分布式系统的形式化建模和证明方面, 她编写了大量的著作.

前 言
分布式算法是用于解决多个互连处理器运行问题的算法. 分布式算法的各部分并发和独立地运行, 每一部分只承载有限的信息. 即使处理器和通信信道以不同的速度运作, 或即使某些构件出了故障, 这些算法仍然应该工作正常.
分布式算法有广泛的应用：电信. 分布式信息处理. 科学计算以及实时进程控制. 例如, 今天的电话系统. 航班订票系统. 银行系统. 全球信息系统. 天气预报系统以及飞机和核电站控制系统都严重依赖于分布式算法. 很明显, 确保分布式算法准确. 高效地运行是非常重要的. 然而, 由于这种算法的执行环境很复杂, 所以设计分布式算法就成为了一项极端困难的任务.
本书对分布式算法这个领域做了全面的介绍—包括最为重要的算法和不可能性结果, 且都是在一种简单的自动机理论环境中呈现. 几乎所有的解都给出了数学证明（至少是粗略的）. 这些算法都根据精确定义的复杂度衡量方法进行了分析. 总之, 这些材料为更深入地理解分布式算法打下了牢固的基础.
本书面向不同层次的读者. 首先, 本书可以作为计算机系一年级研究生的教材, 尤其适合于对计算机系统. 理论或两者怀有浓厚兴趣的学生. 第二, 本书可作为分布式系统设计人员的短期培训教材. 最后, 它也可作为参考手册, 供设计人员. 学生. 研究人员以及任何对该领域感兴趣的个人使用.
本书包含了针对很多典型问题的算法, 如在几种不同系统环境下的一致性(consensus). 通信. 资源分配和同步问题. 这些算法和结论基于分布式环境的基本假设来组织. 组织的第一层基于时序模型（timing model）—同步. 异步或部分同步, 第二层基于进程间的通信机制—共享存储器或消息传递. 每种系统模型都用数章来阐述：每一组的头一章提出所述系统类型的形式化模型, 余下各章介绍了算法和不可能性结果. 从头至尾, 我们进行了严密的论述, 然而非常简明易懂.
由于该领域很广阔也很活跃, 因此本书不想去包罗万象. 我们只是将最根本的结果选进了本书. 若以复杂度来衡量, 这些结果并不总是最优的, 但它们比较简单且能够阐明重要的通用设计和推理方法.
本书将会介绍分布式计算领域中许多最重要的问题. 算法和不可能性结果. 当实际系统中出现这些问题的时候, 你就能将它们识别出来, 并进而利用本书介绍的算法来解决它们, 或者应用不可能性结果来证明它们是不可解的. 本书还介绍各类系统模型及其能力. 这样一来, 你自己就可以设计出新算法（甚至还可以证明出新的不可能性结果）. 最后, 本书还会让你相信, 严格推导分布式算法和系统是可行的：形式化建模, 给出其所需行为的精确规格说明, 严格证明它们符合规格说明, 确定合适的复杂度衡量标准以及按照这些标准进行分析.
使用本书
预备知识 阅读本书所需的预备知识是基本的本科离散数学（包括数学归纳和渐进分析）. 一些编程技能以及对计算机系统相当熟悉. 有关随机算法的部分还需要基本的概率知识. 有关串行算法及其分析的本科课程对阅读本书有帮助, 但并不是必需的.
章节关系 本书的编排原则是使读者能比较独立地阅读不同模型的各章. 各章之间的依赖关系如图A所示. 例如, 如果想尽快了解异步网络, 就可以跳过第5~7章. 还可以只读算法部分, 而不必先阅读算法所依赖的建模部分.
图A 各章之间的依赖关系
带星号的小节 在本书目录中, 有几个小节的标题打了星号. 它们的内容不太基本或者说比其他部分更深. 第一次阅读的时候可以忽略这些内容, 不会有什么影响.
课程 本书的第1版已经在MIT（麻省理工学院）的研究生导论课中用了很多年, 并且在一些计算机软件和应用公司的系统设计师夏季课程中用了三年. 本书包括足够一年课程的内容, 所以对一些短期课程来说必须有所取舍（注意看章节之间的关系）.
例如, 在强调异步网络计算的一个学期的课程中, 可以选择第3. 4. 6章. 7.2节. 第12章. 和第14~21章, 参考一些有关建模的章节（第2. 8和9章）, 并根据需要加入第10. 11和13章中的一些定义. 在强调对分布一致性进行详细研习的一个学期的课程中, 可以选择第2~9. 12章. 13.1节. 第15. 17. 21. 23和25章. 还有其他多种可能组合. 如果你是这个领域的研究者, 你可以用所在领域的研究报告中更新或者更特别的结论来补充本书.
在为系统设计师提供的一两周的短期课程中, 可以涉及全部章节的重点, 在较高的层次上讨论关键结论和关键证明思想, 而无需讲解太多细节.
错误 如果在本书中发现了错误, 以及对本书有什么建设性建议, 请告诉我. 特别欢迎对额外问题的建议. 请发送email到：distalgs@theory.lcs.mit.edu.
致谢
我们很难一一列举出所有对本书的出版做出贡献的人们, 因为本书是多年教学和研究的成果, 得到了许多学生和研究人员的帮助. 即使这样, 我还是想尽力而为.
本书是MIT的研究生课程6.852（分布式算法）讲稿的最终版本. 在我早期组织材料的过程中, 学生们学过这门课. 这些学生在1990和1992年给予了特别的帮助, 当时是他们帮助我完成了讲稿的在线版本. 有几位课程助教对我整理笔记给予了极大的帮助, 他们是：Ken Goldman. Isaac Saias和Boaz Patt-Shamir. 助教Jennifer Welch 和Rainer Gawlick也帮了我很大的忙.
许多同事和学生与我一起研究本书中的一些结果, 或者与我一起讨论其他人的工作, 这对我充分理解资料帮助很大. 其中包括：Yehuda Afek. Eshrat Arjomandi. Hagit Attiya. Baruch Awerbuch. Bard Bloom. Alan Borodin. James Burns. Soma Chaudhuri. Brian Coan. Harish Devarajan. Danny Dolev. Cynthia Dwork. Alan Fekete. Michael Fischer. Greg Frederickson. Eli Gafni. Rainer Gawlick. Ken Goldman. Art Harvey. Maurice Herlihy. Paul Jackson. Jon Kleinberg. Leslie Lamport. Butler Lampson. Victor Luchangco. Yishay Mansour. Michael Merritt. Michael Paterson. Boaz Patt-Shamir. Gary Peterson. Shlomit Pinter. Stephen Ponzio. Isaac Saias. Russel Schaffer. Roberto Segala. Nir Shavit. Liuba Shrira. Jfrgen Sfgaard-Andersen. Eugene Stark. Larry Stockmeyer. Mark Tuttle. Frits Vaandrager. George Varghese. Bill Weihl. Jennifer Welch和Lenore Zuck. 尤其感谢其中的两位：我的导师Michael 和我的学生Mark Tuttle. 从1978年以来, Michael就开始与我一起致力于研究这个当时还很小但看起来很有前途的领域, 而Mark Tuttle的硕士论文定义并发展了I/O自动机模型.
我还要感谢Ajoy Datta. Roberto De Prisco. Alan Fekete. Faith Fich. Rainer Gawlick. Shai Halevi. Jon Kleinberg. Richard Ladner. John Leo. Victor Luchangco. Michael Melliar-Smith. Michael Merritt. Daniele Micciancio. Boaz Patt-Shamir. Anya Pogosyants. Stephen Ponzio. Sergio Rajsbaum. Roberto Segala. Nir Shavit. Mark Smith. Larry Stockmeyer. Mark Tuttle. George Varghese. Jennifer Welch和Lenore Zuck, 他们审阅了全书的各部分草稿并提出了很多有用的建议. 特别是Ajoy. Faith和George, 他们使用本书的早期版本作为教材来教学, 给出了很多宝贵的意见. 此外, 我要感谢 Joanne Talbot 不厌其烦的排版. 画图. 搜集参考文献, 以及不停地打印文稿等. David Jones也参予了排版工作. 在此, 我还要感谢 John Guttag. Paul Penfield 和其他MIT EECS的成员, 他们为我安排了写书的时间. Morgan Kaufmann的Bruce Spatz又一次鼓励并帮助我做这个艰巨的工作, 他总能给我正确的建议. 在本书最后成型阶段, Morgan Kaufmann的Julie Pabst和Diane Cerra给了我很大帮助. 同时, 也感谢Babel Press的Ed Sznyter的技术.
最后也是最重要的, 我要感谢体贴我的家人Dennis. Patrick和Mary Lynch, 他们体谅我为本书所做的一切工作. 同时为我料理了其他的事情. 特别感谢Dennis, 当我把大部分时间花在电脑前时, Dennis却在为我准备美味的海鲜晚餐, 甚至把我的浴室和洗衣房翻修一新！
Nancy A. Lynch
Cambridge, Massachusetts