第1章 引言

1.1 相关主题

分布式算法（distributed algorithm）的概念包括大量并发算法，这些算法有着广泛的应用。

分布式算法有许多种。它们的分类所依据的属性包括：

• 进程间通信（IPC）的方法：分布式算法运行在一组处理器上，而这些处理器需要通过某种方式进行通信。一些常规的通信方法包括访问共享存储器、发送点对点消息或广播消息（在广域网或局域网上）以及执行远程过程调用。
• 时序模型：关于系统中事件的时序可做几种不同的假设。一种极端情况是处理器完全同步，通信和计算在完美的锁一步同步中进行。另一种极端情况是它们完全异步，以任意的速度和次序运行。
• 故障模型：算法运行时的底层硬件可能被假设为完全可靠的。或者，算法可能需要容忍一定限度的故障行为。
• 需要解决的问题：这些问题包括资源分配、通信、分布式处理器之间的一致性、数据库并发控制、死锁检测、全局快照、同步以及各种对象类型的实现等。

与大部分并发算法不同，本书提到的算法具有更高程度的不确定性（uncertainty）和行为独立性（independence of activity）。本书中的算法必须面对的几种不确定性的独立行为包括：

• 处理器数目未知
• 网络拓扑结构未知
• 不同位置上的独立输入
• 几个程序立即运行，在不同时间开始，以不同速度运行
• 处理器的不确定性
• 不确定的消息传递次数
• 不确定的消息顺序
• 处理器和通信故障

1.2 我们的观点

模型之间最深层的区别在于对时序的假设，同时IPC机制和故障假设也是重要的因素。

我们考虑的时序模型如下：

• 同步模型：假设各部分同时执行各个步骤，也就是说，运行依照同步轮前进。
• 异步模型：假设不同部分以任意顺序、按任意速度执行各个步骤。
• 部分同步（基于时序）模型：假设对事件的相对时序做一些限制，但运行并不像同步模型那样严格遵循锁-同步机制。

我们用来分类的下一个基础是IPC机制。在本书中我们考虑了共享存储器和消息传递。

我们在不同的模型下提出相同的问题时，将会看到，假设中很小的不同会导致结果产生巨大的差别。

1.3 本书内容综述

模型证明和方法

我们用到的模型都是基于状态机的，通常由无限多个状态和与其迁移相关的显式名字。状态机的每个状态标识这个组件或系统的一个瞬时快照，它包括诸如每一处理器的存储状态、每一运行程序的程序计数器以及通信系统中传递的消息等信息。

第2章介绍了第一个模型，它是针对同步网络的。这是一个很简单的模型，仅仅描述了消息交换和计算的同步轮。

第8章介绍一个异步网络的通用模型——输入/输出自动机（I/O自动机）模型，它足以描述异步的共享存储器系统和异步网络（以及许多其他类型的异步系统）。

第9章和第14章中分别介绍针对共享存储器系统和消息传递系统模型进行裁剪所需要的额外结构。

最后第23章介绍了基于时序的系统的模型。这些模型同样是状态机，但这里的状态包括时序信息，如当前时间和不同事件的调度时间。

同步网络算法

我们考虑的最简单的（即有最少不确定性的）模型是同步网络模型，模型中的所有处理器都在同步轮中进行通信和计算。

在第3章中，我们从一个设计环网中计算的简单例子开始。问题是：假设节点上的每个处理器除了唯一的标识符（UID）之外都相同，怎样在环网中选出一个唯一的领导者节点？

在第4章中，我们简略探讨了在更一般的网络中用到的基本算法。特别的，我们给出了一些用于解决诸如领导者选举、广度优先搜索、寻找最短路径、寻找最小生成树以及寻找节点的最大独立集等基本问题的算法。

在第5章和第6章，我们考虑在一个分布式网络中达成一致的问题。这里，我们考虑的不确定性不仅源于初始判断的差异，而且源于链路或处理器的故障。

在第5章中，我们考虑链路因丢失消息而产生故障的情况。

在第6章中，我们考虑两种不同类型的处理器故障：停止故障，即发生故障的处理器在某一点停止执行本地的协议；Byzantine故障，即发生故障的处理器表现出完全随意的行为（其限制是不能破坏系统中它不能访问的部分）。

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

异步的共享存储器算法

在第10章中，我们考虑的第一个问题是互斥问题。本质上讲，这个问题涉及对单一、不可分的资源进行访问时的管理，这种资源在某一时刻只能支持一个用户访问。从另一角度看，我们可以认为这个问题是要确保某些程序段在临界区内执行，临界区不允许两个进程同时执行。

在第11章中，我们将互斥问题扩展为更复杂的资源分配问题，涉及更多的资源和对资源使用方式的更详尽的要求。

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

在第13章中，我们介绍了原子对象。这些算法的一个有趣的属性是无等待，这意味着不管其他并发操作是否出错，在已实现的对象上的任一操作必须完成。

异步网络算法

消息可以在任意时间到达，处理器可以以任意速度运行。相对于同步网络环境和异步共享存储器环境，这里的系统组件之间的耦合更松散。

我们从第15章开始，在异步网络环境中重新考虑第4章里的问题和算法。

第15章说明对异步网络编程是困难的，接下来的四章就是要解决这个问题。

在第16章中介绍的第一种技术是引入同步器。

在第17章中介绍的第二种技术是用异步网络模型模拟异步共享存储器模型。

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

第19章介绍了第四种技术，在异步网络算法运行时监控该算法。

有了这些有力的工具之后，我们来考虑异步网络中的特定问题。在第20章中，我们重新考虑资源分配问题。

在第21章中，我们考虑了出现停止故障时异步网络中的计算问题。

在第22章中，我们考虑数据链路问题。数据链路协议用于在不可靠的底层通道上实现可靠的通信链路。

部分同步算法

部分同步模型处于同步和异步模型之间。在部分同步模型中，我们假设处理器知道一些时间信息，如能够访问实际时间或近似时间，或者某种类型的超时机制。或者，我们可以假设处理器每步的时间和消息发送的时间在已知的上下限之间。

在第24章中，我们给出在时序环境中解决问题所需时间的上下限。

在第25章中，我们给出一致性问题的上下界。