1.2 我们的观点

本书研究的领域是分布式算法。因为这是一个非常广阔和活跃的领域，我们不能进行全面的研究，必须有所取舍，所以我们试图选出本领域在理论上和实际上最基本的一些结果。就复杂度来讲，它们不一定是最优的结果，但我们更倾向于选出那些简单且体现了重要的设计和推理方法的结论。我们给出的结果包括一部分在本领域内相当典型的问题，如领导者选举、网络搜索、构造生成树、分布一致性、互斥、资源分配、构造对象、同步、全局快照以及可靠通信。这些问题在不同应用中重复出现。我们会在几个不同的系统模型中考虑这些问题。

本书的一大特点是，我们根据一个几乎统一的形式化框架来给出所有的算法、不可能性结果和下限。这个框架包括少量针对不同类型分布式系统的形式化自动机理论模型，以及使用这些模型来对系统进行推理的标准方法。我们的框架基于自动机理论，而不是基于某种特定的形式语言或形式证明逻辑。这使得我们可以用基本的集合论数学来表达结论，而不用过多地担心语言细节。这样也有灵活性，因为可以在同一框架内运用多种语言和逻辑来对算法进行描述和推理。使用形式化框架可以对所有的结论进行严密的处理。

对于严密性还需要多说几句。在分布式算法领域内，严密的处理十分重要，因为其中有许多微妙的因素。如果不注意这一点，就很难避免错误。然而，很难说清怎样做出完全严密的表达（既足够简练又易于直观理解）。在本书中，我们综合使用了直观的和严密的推理。也就是说，我们给出相应形式化模型的精确描述。对于算法，我们有时用形式化模型精确描述，有时用文字描述，有时两者都用。在讨论算法正确性时，严密的程度可能变化很大：有时给出很形式化的证明，有时仅给出直观的概述。然而，我们希望提供足够的工具，以便在需要时可以将直观概述扩展为形式化证明。我们一般根据形式化模型来给出严密的不可能性证明。

因为有许多不同的环境和问题要考虑，所以很难说怎样组织这些材料最好。我们首先是按照形式化模型组织的——特别是根据模型中对结论影响最大的方面描述，其次是根据抽象的问题描述。模型之间最深层的区别在于对时序的假设，同时IPC机制和故障假设也是重要的因素。

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

● 同步模型：这种模型最容易描述、编程和推理。我们假设各部分同时执行各个步骤，也就是说，运行依照同步轮前进。当然，在大部分分布式系统中，实际情况并非如此，但是无论如何，同步模型是很有用的。理解怎样在一个同步模型中解决问题，往往是理解怎样在更现实的模型中解决它的有用的中间步骤。例如，有时一个实际的分布式系统可以“模拟”一个同步系统。而且，同步系统的不可能性结果可以直接用于表现更差的模型。然而，在许多种类的分布式系统中实现同步模型是不可能或无效的。

● 异步模型：这里我们假设不同部分以任意顺序、按任意速度执行各个步骤。尽管有几个细微之处，主要涉及活性（liveness）的考虑，这种模型还是比较容易描述的。因为有事件顺序的额外不确定性，它比同步模型更难编程。然而，异步模型允许程序员忽略特定的时序问题。与典型的分布式系统相比，由于异步模型对时间所做的假设更少，因此为异步模型设计的算法是通用和可移植的：它们可以保证按任意的时序在网络中正确运行。然而，异步模型有时不能高效解决问题，有的问题甚至不能解决。

● 部分同步（基于时序）模型：这里我们假设对事件的相对时序做一些限制，但运行并不像同步模型那样严格遵循锁-步机制。这些模型是最实际的，但也是最难编程的。利用事件时序知识所设计的算法可以是高效的，但也可能是脆弱的，因为如果时序假设被打破的话它们就不能正确运行。

我们用来分类的下一个基础是IPC机制。在本书中，我们考虑了共享存储器和消息传递。我们首先给出了共享存储器模型，因为它更为强大，且更易理解，也因为共享存储器环境中的许多技术和结论修改后可以用于网络环境。接下来，我们根据研究的问题来组织材料。最后，我们研究了许多在不同的故障假设下的问题。当我们在不同的模型下提出相同的问题时，将会看到，假设中很小的不同会导致结果产生巨大的差别。我们试图指出并强调这些差别。

通过将算法组合成其他算法，使用层次抽象来设计算法，以及将针对一个模型的算法转换成为针对其他模型的算法，我们尽量将我们的表达模块化。这有助于极大地降低设计思想的复杂性，使我们事半功倍。在实际的分布式系统设计中，相同种类的模块可以用于同样的目的。