前言

分布式算法是用于解决多个互连处理器运行问题的算法。分布式算法的各部分并发和独立地运行，每一部分只承载有限的信息。即使处理器和通信信道以不同的速度运作，或即使某些构件出了故障，这些算法仍然应该正常运行。

分布式算法有广泛的应用：电信、分布式信息处理、科学计算以及实时进程控制。例如，电话系统、航班订票系统、银行系统、全球信息系统、天气预报系统以及飞机和核电站控制系统都严重依赖于分布式算法。很明显，确保分布式算法准确、高效地运行是非常重要的。然而，由于这种算法的执行环境很复杂，所以设计分布式算法就成了一项极端困难的任务。

本书对分布式算法这个领域做了全面的介绍，包括最为重要的算法和不可能性结果，且都在一种简单的自动机理论环境中呈现。几乎所有的解都附有数学证明（至少是粗略的）。每个算法都根据精确定义的复杂度衡量方法进行了分析。总之，这些内容为更深入地理解分布式算法打下了牢固的基础。

本书面向不同层次的读者。首先，本书可以作为计算机系一年级研究生的教材，尤其适合于对计算机系统、理论或两者怀有浓厚兴趣的学生学习。其次，本书可作为分布式系统设计人员的短期培训教材。最后，它也可作为参考手册，供设计人员、学生、研究人员以及任何对该领域感兴趣的人使用。

本书包含了针对很多典型问题的算法，如在几种不同系统环境下的一致性（consensus）、通信、资源分配和同步问题。这些算法和相应结果基于分布式环境的基本假设来组织。组织的第一层基于时序模型（timing model）——同步、异步或部分同步；第二层基于进程间的通信机制——共享存储器或消息传递。每种系统模型都用数章来阐述：每一部分的头一章提出所述系统类型的形式化模型，余下各章介绍算法和不可能性结果。从头至尾，本书进行了严密的论述，然而非常简明易懂。

由于该领域很广阔，变化也很快，因此本书并不包罗万象，只包括最根本的结果。若以复杂度来衡量，这些结果并不总是最优的，但它们比较简单且能够阐明重要的通用设计和推理方法。

本书将会介绍分布式计算领域中许多重要的问题、算法和不可能性结果。当实际系统中出现这些问题的时候，你就能将它们识别出来，并进而利用本书介绍的算法来解决它们，或者应用不可能性结果来证明它们是不可解的。本书还介绍各类系统模型及其能力。这样一来，你自己就可以设计出新算法（甚至还可以证明出新的不可能性结果）。最后，本书还会让你相信，严格推导分布式算法和系统是可行的：形式化建模，给出其所需行为的精确规格说明，严格证明它们符合规格说明，确定合适的复杂度衡量标准以及按照这些标准进行分析。

使用本书

预备知识 阅读本书需要对基本的本科离散数学（包括数学归纳和渐近分析）、一些编程技能以及计算机系统相当熟悉。有关随机算法的部分还需要基本的概率知识。有关串行算法及其分析的本科课程对阅读本书有帮助，但并不是必要的。

章节关系 本书的编排原则是使读者能比较独立地阅读不同模型的各章内容。各章之间的依赖关系如图A所示。例如，如果想尽快了解异步网络，就可以跳过第5～7章。还可以只读算法部分，而不必先阅读算法所依赖的建模部分。

带星号的小节 在本书中，有几个小节的标题打了星号。它们的内容不太基本或者说比其他部分更深。第一次阅读的时候可以忽略这些内容而不会有什么影响。

课程 本书的第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、Jϕrgen Sϕgaard-Andersen、Eugene Stark、Larry Stockmeyer、Mark Tuttle、Frits Vaandrager、George Varghese、Bill Weihl、Jennifer Welch和Lenore Zuck。尤其感谢其中的两位：我的导师Michael Fischer和我的学生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出版社的Ed Sznyter的LATEX技术。

最后也是最重要的，我要感谢体贴我的家人Dennis、Patrick和Mary Lynch，他们体谅我为本书所做的一切工作，同时帮我处理了其他的事情。特别感谢Dennis，当我把大部分时间花在计算机前时，Dennis在为我准备美味的海鲜晚餐，甚至把我的浴室和洗衣房翻修一新！

Nancy A.Lynch

Cambridge, Massachusetts