1.3 本书内容综述

本书包括的具体主题如下。

模型和证明方法 有关形式化模型和证明方法的内容分散在第2、8、9、14和23章中，这几章是本书中各主要部分（同步网络算法、异步共享存储器算法、异步网络算法和部分同步算法）的起始章节。这些内容独立成章，以方便读者参考。首次阅读时你可能更愿意跳过建模部分的某些内容，以后在理解算法的相关内容时根据需要再回来参考它们。我们尽量合理组织本书，使得算法易读和易理解，而不需要太多的形式化建模工作。

我们用到的模型都是基于状态机的，通常有无限多个状态和与其迁移相关的显式名字。一个状态机既可以用于对分布式系统的一个组件建模，也可以用于对整个分布式系统建模。状态机的每个状态表示这个组件或系统的一个瞬时快照，它包括诸如每一处理器的存储状态、每一运行程序的程序计数器以及通信系统中传递的消息等信息。迁移描述了系统中发生的变化，如消息的发送和接收引起的变化，或者由本地计算引起的变化。我们对同步网络、异步系统和基于时序的系统分别给出不同的模型。

对于分布式系统而言，形式化模型的一个重要用途是作为所要解决问题的规格说明以及算法正确性证明的基础。这样的规格说明和证明可以用许多特定风格的和特别的方法来实现。然而，某些方法会经常采用，所以我们在有关模型的章节中明确地描述了它们。这些方法包括不变式断言和模拟。不变式断言是在系统的所有可达状态中都为真的属性。断言通常通过对系统运行的步数做归纳来证明。模拟是一对系统之间的形式化关系，一个系统代表要解决的问题，另一个系统代表解决方案；或者一个系统代表高级的、抽象的解决方案，另一个系统代表具体的方案。模拟关系一般也用归纳法证明。

第2章介绍了第一个模型，它是针对同步网络的。这是一个很简单的模型，仅仅描述了消息交换和计算的同步轮。第8章介绍一个异步网络的通用模型——输入/输出自动机（I/O自动机）模型。模型的名字表明它明确区分输入和输出迁移，即环境对系统的通信和系统向环境的通信。在一个I/O自动机中，从某一给定的状态开始可能有几个迁移；例如，涉及不同处理器的迁移能够以任意次序执行。因为模型允许迁移次序具有如此大的灵活性，我们引入活性的概念以表示某些迁移最终一定会发生。该模型一个有用的特点是它具有一个并行的合成操作，使得将那些以I/O自动机表示的系统组件进行合并后，仍然可以使用I/O自动机来表示合并后的系统。通常，可以基于组件正确性的证明，以模块化的方式来证明合成自动机的正确性。

第8章中的模型很通用，它足以描述异步的共享存储器系统和异步网络（以及许多其他类型的异步系统）；第9章和第14章中分别介绍针对共享存储器系统和消息传递系统模型进行裁剪所需要的额外结构。

最后，第23章介绍了基于时序的系统的模型。这些模型同样是状态机，但是这里的状态包括时序信息，如当前时间和不同事件的调度时间。这些模型使我们可以描述基于时序的系统的典型结构，如本地时钟和超时。

同步网络算法 我们考虑的最简单的（即有最少不确定性的）模型是同步网络模型，模型中所有的处理器都在同步轮中进行通信和计算。我们不考虑同步的共享存储器算法，因为它们构成了一大研究分支（见本章后面的参考文献注释）。在网络环境中，我们假设处理器在图或有向图G中的节点上，并通过沿G的边发送消息与它的邻接节点通信。

在第3～7章中，我们考虑同步网络中几个典型的分布式问题。在第3章中，我们从一个涉及环网中计算的简单例子开始。问题是：假设节点上的每个处理器除了一个唯一的标识符（UID）之外都相同，怎样在环网中选出一个唯一的领导者节点？这里主要的不确定性是处理器实际拥有的UID集合是未知的（尽管已知没有两个处理器有相同的UID）；而且，网络的规模通常是未知的。这个问题主要用于令牌环的局域环网上，其中假设总有一个令牌在循环，使得当前所有者拥有发起通信的特权。然而，令牌有时会丢失，因此处理器有必要执行一个算法来重新产生丢失的令牌。这个重新产生的过程就等于是选出一个领导者。关于领导者选举问题，我们给出了一些基本的理论复杂度的结论。特别是，我们证明了所需的时间和通信量（即消息数）的界限。

接着，在第4章中，我们简略探讨了在更一般的网络中用到的基本算法。特别地，我们给出了一些用于解决诸如领导者选举、广度优先搜索、寻找最短路径、寻找最小生成树以及寻找节点的最大独立集等基本问题的算法。这里，典型的不确定性来自未知的UID和未知的网络图。

然后，在第5章和第6章，我们考虑在一个分布式网络中达成一致的问题。在有些问题中，一些处理器需要达成一个共同的决定，即使开始时它们对决定应该是什么样子存在分歧。现实中会产生许多一致性问题，例如：处理器能监测飞机上不同的高度计，并且试图就高度达成一致；或者处理器能对某个其他的系统组件进行故障诊断，试图把各个处理器的诊断结果综合成一个共同的决定，即是否替换这一组件。

这里，我们考虑的不确定性不仅源于初始判断的差异，而且源于链路或处理器的故障。在第5章中我们考虑链路因丢失消息而产生故障的情况。在第6章中我们考虑两种不同类型的处理器故障：停止故障，即发生故障的处理器在某一点停止执行本地的协议；Byzantine故障，即发生故障的处理器表现出完全随意的行为（其限制是不能破坏系统中它不能访问的部分）。对可以容忍的错误数目、时间以及通信量，我们都给出了界限。

最后，在第7章中，我们考虑了一些基本的一致性问题的扩展和变形，包括：在一个小的值集合上的一致，而不是仅仅对单个值的一致；对一个实数值的近似一致；分布式数据库的提交问题。

异步的共享存储器算法 经过同步算法的热身（其中只有少量的不确定性），我们开始学习难度更大的异步算法。现在我们不再假设处理器按锁-步同步，而是可以按任意次序交错执行各步，对单个处理器的速度也没有限制。典型情况下，它和外部环境的交互（通过输入和输出事件）是不断进行的，而不是仅仅包含初始的输入和最终的输出。在这种环境中得到的结果与在同步网络中得到的结果大不相同。

第10～13章包括了异步的共享存储器算法。在第10章中，我们考虑的第一个问题是互斥问题。这是在分布式算法领域中最基本的问题之一，也是历史上第一个得到深入的理论研究的问题。本质上讲，这个问题涉及对单一、不可分的资源进行访问时的管理，这种资源在某一时刻只能支持一个用户访问。从另一角度看，我们可以认为这个问题是要确保某些程序段在临界区内执行，临界区不允许两个进程同时执行。这个问题在集中式和分布式操作系统中都会遇到。除了与步骤次序有关的基本的不确定性，还有与哪些用户何时访问资源有关的不确定性。

我们给出了一系列共享存储器的互斥算法，从Dijkstra在1965年提出的经典算法开始，列出了一系列能更好地保证正确性的算法。这些算法中的大部分基于那些只能用读操作和写操作来访问的存储器；对于这种读/写共享存储器模型，我们也给出了必须用到的共享变量的数目下限。我们也考虑了使用一个更强的共享存储器——读-改-写存储器的问题；在这种情况下，我们给出了所需存储器大小的上下限。除了给出算法和下限，我们把互斥问题作为一个实例来阐明异步分布式算法的许多重要概念。这些概念包括通用建模方法；原子性、公平性、演进性和容错的概念；不变式断言和模拟证明；时间分析技术。

在第11章中，我们将互斥问题扩展为更复杂的资源分配问题，涉及更多的资源和对资源使用方式的更详尽的要求。例如，我们考虑哲学家用餐问题，这是一个典型的资源分配问题，涉及在处理器环中分配成对的共享资源。

在第12章中，我们在异步共享存储器模型中重新考虑一致性问题。这一章的主要结论是一个基本的事实，即如果共享存储器仅仅支持读写操作，那么在发生故障的情况下，基本的一致性问题在这样的环境中不可解。相反，对于较强的共享存储器类型，如读-改-写存储器，存在对这个问题的简单解法。

接着，在第13章中，我们介绍了原子对象。在此之前，我们假设处理器对存储器的访问是即时的。原子对象分别接受调用和做出响应动作，但除此之外它的表现和即时访问的共享变量很相似。我们定义了原子对象，并证明了一些基本结论，这些结论说明了怎样使用它们来构造系统；特别是它们可用于代替共享变量。同时我们考虑了使用更弱原语（共享变量或较弱类型的原子对象）来实现更强原子对象的几个算法。这些算法的一个有趣的属性是无等待，这意味着不管其他并发操作是否出错，在已实现的对象上的任一操作必须完成。

我们会给出怎样用读/写共享变量来实现快照原子对象；快照原子对象接受快照操作，立即返回所有存储位置的值。我们还会给出怎样用单写者的读/写共享存储器来实现多写者/多读者的原子对象。

异步网络算法 在第15～22章中，我们进一步研究了异步网络中的算法。和同步网络一样，系统以图或有向图来表示，节点是处理器，边是通信链路，但是系统不在同步轮中运行。现在，消息可以在任意时间到达，处理器可以以任意速度运行。相对于同步网络环境和异步共享存储器环境，这里的系统组件之间的耦合更松散。因此，这种模型的不确定性又增加了。

我们从第15章开始，在异步网络环境中重新考虑第4章里的问题和算法。例如，我们重新考虑领导者选举问题、广度优先搜索和最短路径、广播和敛播以及最小生成树。尽管有些算法几乎不用修改就可以使用，但大部分需要较大的改动。把第4章的简单同步最小生成树算法扩展到异步网络环境尤其困难。

第15章说明对异步网络编程是困难的，接下来的四章就是要解决这个问题。在第16～19章中，我们介绍了四种简化技术，这些技术被形式化为算法变换，允许异步网络模拟更简单或更强的模型。这些变换使得针对更简单或更强的模型设计的算法可以运行在更复杂的异步网络模型中。

在第16章中介绍的第一种技术是引入同步器。同步器是一种系统组件，它使得（无故障的）异步网络可以模拟第2～4章中的同步网络（没有故障的那些）。我们给出了有效的实现，并且把这些实现和一个下限结果做比较，其中这个下限结果似乎表明任何这样的模拟都是无效的。这种表面上的矛盾其实依赖于待解决问题的类型。

在第17章中介绍的第二种技术是用异步网络模型模拟异步共享存储器模型。这使得第10～13章中介绍的那些异步共享存储器算法可以用在异步网络中。

在第18章中介绍的第三种技术是给异步分布式网络中的事件分配一致的逻辑时间。这种技术允许异步网络模拟一个网络，该网络中的节点可以访问一个完全同步的实时时钟。它的重要应用是允许一个异步网络模拟一个集中式（非分布式）状态机。

第19章介绍了第四种技术，在异步网络算法运行时监控该算法。例如，这可以用于调试，用于产生备份版本，或者用于检测算法的稳定属性。稳定属性是一旦发生就会永远保持的属性，如系统终止或死锁。有助于检测稳定属性的一种基本原语其实就是这样的一种能力，即产生分布式算法的状态的一致全局快照。我们给出了几种产生这样的快照的方法，并且描述了怎样使用快照来检测稳定属性。

有了这些有力的工具之后，我们来考虑异步网络环境中的特定问题。在第20章中，我们重新考虑资源分配问题。例如，我们给出了在异步网络中解决互斥问题和哲学家用餐问题的方法。

在第21章中，我们考虑了出现停止故障时异步网络中的计算问题。首先，用第17章中的变换，我们证明了一致性问题从共享存储器环境到网络环境的不可能性结果。围绕这个固有的限制我们考虑了几种方法；例如，我们给出了一个随机化算法来解决一致性问题，介绍了怎样用所谓的故障检测器来解决一致性问题，说明了怎样达到近似一致而不是精确一致。

在第22章中，我们考虑数据链路问题。数据链路协议用于在不可靠的底层通道上实现可靠的通信链路。首先我们给出交替位（Alternating Bit）协议，这个简单协议不但本身有趣，而且在并发算法证明领域也是一个著名的标准研究案例。对于底层通道出现不同类型故障行为的环境，我们也给出了这个问题的其他各种算法和不可能性结果。

部分同步算法 部分同步模型处于同步和异步模型之间。在部分同步模型中，我们假设处理器知道一些时间信息，如能够访问实际时间或近似时间，或者某种类型的超时机制。或者，我们可以假设处理器每步的时间和消息发送的时间在已知的上下限之间。由于部分同步系统具有比异步系统更少的不确定性，你可能以为它们更容易编程。然而，时序引起了更多的复杂问题——例如，算法的正确性通常严重依赖于时序假设。因此，部分同步环境的算法和证明通常比异步环境更复杂。

在第24章中，我们给出在时序环境中解决互斥问题所需时间的上下限。在第25章中，我们给出一致性问题的上下界。因为部分同步分布式算法是当前研究的一个主题，我们只给出这种模型的初步结论。