第1章 引言

1.1 相关主题

分布式算法（distributed algorithm）的概念包括大量并发算法，这些算法有着广泛的应用。最初，分布式算法这个术语用来指在那些分布在一个大地理区域中的多个处理器上运行的算法。多年之后，该术语的应用更为广泛。现在的分布式算法不仅包括运行在局域网上的算法，甚至还包括针对共享存储器多处理器的算法。造成这种状况的原因是：人们逐渐认识到，用在上述不同环境下的算法有许多共同之处。

分布式算法得到了广泛的应用：电信、分布式信息处理、科学计算以及实时进程控制。当我们为某项应用搭建一个系统时，其中一个重要的环节是设计、实现和分析分布式算法。这些算法和它们要解决的问题构成了本书中涉及的研究领域的相关主题。

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

● 进程间通信（IPC）的方法：分布式算法运行在一组处理器上，而这些处理器需要通过某种方式进行通信。一些常规的通信方法包括访问共享存储器、发送点对点消息或广播消息（在广域网或局域网上）以及执行远程过程调用。

● 时序模型：关于系统中事件的时序可做几种不同的假设，这反映了算法可能用到的不同时序信息类型。一种极端情况是处理器完全同步，通信和计算在完美的锁一步同步中进行。另一种极端情况是它们完全异步，以任意的速度和次序运行。两者之间有大量可能的假设，这些假设可以归为部分同步的，在这些情况下，处理器具有关于事件时序的部分信息。例如，处理器的相对速度可能有界限，或者处理器可以访问近似同步的时钟。

● 故障模型：算法运行时的底层硬件可能被假设为完全可靠的。或者，算法可能需要容忍一定限度的故障行为。这些故障行为可能包括处理器故障，即处理器可能在给出或不给出警告的情况下停止工作；也可能暂时发生错误；或表现出严重的Byzantine故障，即一个出错的处理器可以做出任意动作。出错行为也包括通信机制的故障，包括消息丢失或消息重复。

● 需解决的问题：当然，算法也视它们试图解决的问题而相异。我们考虑的典型问题就是在上面提到的应用领域内产生的问题。这些问题包括资源分配、通信、分布式处理器之间的一致性、数据库并发控制、死锁检测、全局快照、同步以及各种对象类型的实现等。

本书不讲述某些并发算法，如并行随机存取机（PRAM）算法和针对固定连接网络（如数组、树和超立方体）的算法。与大部分并发算法不同，本书提到的算法具有更高程度的不确定性（uncertainty）和行为独立性（independence of activity）。本书中的算法必须面对的几种不确定性和行为独立性包括：

● 处理器数目未知

● 网络拓扑结构未知

● 不同位置上的独立输入

● 几个程序立即运行，在不同时间开始，以不同速度运行

● 处理器的不确定性

● 不确定的消息传递次数

● 不确定的消息顺序

● 处理器和通信故障

幸运的是，并不是每个算法都要面对这些不确定性和行为独立性！

由于这些不确定性，分布式算法的行为经常很难理解。由于多个处理器并行执行代码，其执行步骤以某种不确定的方式相互交错，因此即使算法的代码很短，也可能在输入相同的情况下，算法有多种不同的表现。因此，通过准确预测算法到底如何执行来理解算法通常是不可能的。这与其他并行算法相反，例如，在PRAM算法中，我们通常能够预测某一时刻算法将要做什么。对于分布式算法，我们最好去理解它的行为中某些已选定的属性，而不是去理解它的所有行为。

在过去的15年里，分布式算法的研究已经发展成一个相当一致的领域。该领域的研究风格大致如下：首先，确认在实际分布式计算中的重要问题，并定义适合对问题进行数学研究的抽象版本；然后，开发出解决问题的算法，精确地描述这些算法，证明它们能解决出现的问题，并且根据不同度量标准来分析其复杂度。算法的设计者通常会试图降低算法的复杂度。同时，要证明不可能性结果和下限，给出问题如何才能可解的限制以及其求解代价。所有这些工作的基础是分布式系统的数学模型。

这些结论构成了十分有趣的数学理论。但它们不仅仅是数学理论：这里讲到的问题声明可用于对实际系统的某些部分建立形式化规格说明；这里讲到的算法（很多情况下）可用于实际的设计；这里给出的不可能性结果会告诉设计者应在何时停止做一些事情。所有这些结果，加上底层的数学模型，有助于设计者理解他们构建的系统。