前言

什么是分布式算法

在过去的几十年里，我们在分布式系统和网络领域经历了前所未有的增长。目前分布式计算涵盖了当今计算机和通信领域中发生的许多活动。事实上，分布式计算具有相当多样化的应用领域。互联网是分布式系统，无线通信、云计算或并行计算、多核系统、移动网络也是如此。此外，蚁群、大脑甚至人类社会都可以被建模为分布式系统。

这些应用的共同点是，系统中的许多处理器或实体（通常称为节点）在任何时刻都是活跃的。节点有一定的自由度：有自己的硬件和软件。然而，这些节点可以共享共同的资源和信息，为了解决涉及几个甚至所有节点的问题，协调是必要的。

尽管有这些共性，但人脑与多核处理器当然有很大的不同。由于这种差异，人们在分布式计算领域研究了许多不同的模型和参数。在一些系统中，节点是同步运行的，在另一些系统中，节点是异步运行的。有简单的同构系统，也有异构系统，异构系统中包含不同类型的节点，它们可能具有不同的能力、目标等，需要进行交互。有不同的通信技术：节点可以通过交换消息进行通信，也可以通过共享内存进行通信。偶尔通信基础设施是为某一应用量身定做的，有时人们不得不使用给定的基础设施。分布式系统中的节点经常共同解决一个全局性的任务，偶尔节点是自主的代理，有自己的议程，并竞争共同的资源。

有时可以认为节点工作正常，有时节点可能发生故障。与单节点系统相比，分布式系统在发生故障的情况下仍可能正常工作，因为其他节点可以接管故障节点的工作。故障有不同的种类：节点可能只是崩溃，也可能表现出一种任意的、错误的行为，甚至可能达到无法与恶意（也就是拜占庭）行为区分的程度。也有可能节点确实遵循了规则，然而它们调整参数以获得系统的最大收益，换句话说，节点的行为是自私的。

显然，可以研究的模型有很多（甚至还有更多的模型组合）。我们现在不对它们进行详细讨论，只是在使用它们时进行定义。学完本书，读者应该知道最重要的概念，并且应该有一个大致的印象。

本书概览

本书介绍分布式计算的基本原理，突出常见的主题和技术。特别是，我们研究了分布式系统设计的一些基本问题：

●通信：通信不是免费的，通信成本往往决定了本地处理或存储的成本。有时我们甚至认为除了通信之外的一切都免费。

●协调：如何协调一个分布式系统，让它有效地执行一些任务？有多少开销是不可避免的？

●容错性：分布式系统的一个主要优点是即使在出现故障的情况下系统作为一个整体也能生存下来。

●本地性：网络在不断发展。幸运的是，完成一个任务并不总是需要全局信息，通常情况下，如果节点能与邻居通信就足够了。本地性解决方案是否可行，是本书的核心话题之一。

●并行性：如果提高计算能力，比如增加可以分担工作量的节点数量，那么完成一个任务的速度有多快？对于一个给定的问题，并行性有多大可能？

●打破对称性：有时需要选择一些节点来协调计算或通信。这是由一种叫作打破对称性的技术来实现的。

●同步：如何在异步环境中实现同步算法？

●不确定性：如果用一个词来恰当地描述本书，那大概就是“不确定性”。由于整个系统是分布式的，一个节点不可能知道其他节点在这个确切的时刻在做什么，尽管缺乏全局知识，但还是需要节点完成手头的任务。

最后，还有一些领域我们不会在本书中涉及，主要是因为这些主题非常重要，有单独的书来讲述它们。这类主题的例子是分布式编程或安全/密码学。

综上所述，在本书中，我们探讨基本的算法思想和下界技术，这两方面可以说是分布式计算和网络算法的“珠玑”。

前言注释

关于本书主题已经有许多优秀的教科书。最密切相关的书是由David Peleg[Pel00]所著的，它提供了一些素材。Peleg的书重点讨论网络分区、覆盖、分解和跨接器（这是一个有趣的领域，我们在本书中只是有所提及）。有大量的教科书与本书的一两章内容重叠，例如，[Lei92，Bar96，Lyn96，Tel01，AW04，HKP+05，CLRS09，Suo12，TR18]。另一门相关课程是由James Aspnes[Asp]所作，还有一门课程是由Jukka Suomela[Suo14]所作。

本书的一些章节是与（已经毕业的）博士生合作编写的。许多同事和学生帮助改进了本书。感谢Georg Bachmeier、Philipp Brandes、Raphael Eidenbenz、Roland Flury、Klaus-Tycho Förster、Stephan Holzer、Barbara Keller、Fabian Kuhn、Michael Kuhn、Christoph Lenzen、Darya Melnyk、Thomas Locher、Remo Meier、Thomas Moscibroda、Regina O'Dell、Yvonne-Anne Pignolet、Noy Rotbart、Jochen Seidel、Stefan Schmid、Johannes Schneider、Jara Uitto、Pascal von Rickenbach。

参考文献