《分布式系统：为了乐趣和利益》是一本广受欢迎的资源，用于理解和学习分布式系统。该书由作者 Mikito Takada 撰写，介绍了构建分布式系统的基本概念、原则和挑战。

这本书涵盖了与分布式系统相关的广泛主题，包括网络、容错性、一致性模型、分布式算法、可扩展性等等。它旨在以清晰易懂的方式解释复杂的概念，适合初学者和有经验的分布式系统从业者阅读。

在整本书中，作者提供了各种实际案例和案例研究，以说明分布式系统的实际应用和实践方面。它还强调了构建分布式系统涉及的权衡和设计考虑，帮助读者全面理解这个主题。

《分布式系统：为了乐趣和利益》作为开源资源，可以免费在线获取，非常适合任何对学习分布式系统感兴趣的人。

原文链接：Distributed systems: for fun and profit

3. 时间及顺序

什么是顺序，为什么它很重要？

你说的“什么是顺序”是什么意思？

我的意思是，为什么我们对顺序如此着迷？为什么我们关心 A 是否发生在 B 之前？为什么我们不关心其他属性，比如“颜色”？

好吧，我的疯狂朋友，让我们回到分布式系统的定义来回答这个问题。

你可能还记得，我将分布式编程描述为使用多台计算机解决单台计算机可以解决的同一个问题的艺术。

事实上，这正是对顺序如此着迷的核心所在。任何只能一次执行一项任务的系统都会创建操作的总体顺序。就像人们通过一扇门一样，每个操作都有明确定义的前任和后继。这基本上是我们努力保留的编程模型。

传统的模型是：一个程序，一个进程，一个在一个 CPU 上运行的内存空间。操作系统抽象了可能存在多个 CPU 和多个程序的事实，以及计算机内存实际上是多个程序共享的。我并不是说线程编程和事件驱动编程不存在；只是它们是“一个/一个/一个”模型之上的特殊抽象。程序被编写成按照一定顺序执行：从上往下执行。

顺序作为一种属性受到了如此多的关注，是因为定义“正确性”的最简单方法是说“它的工作方式与单台计算机上的工作方式相同”。而通常这意味着 a）我们运行相同的操作，b）我们按照相同的顺序运行它们 - 即使有多台计算机。

保持顺序（如单个系统定义的顺序）的分布式系统的优点在于它们是通用的。你不需要关心操作是什么，因为它们将与在单台计算机上完全相同的方式执行。这很棒，因为你知道无论操作是什么，你都可以使用相同的系统。

实际上，分布式程序在多个节点上运行，具有多个 CPU 和多个操作流。你仍然可以分配一个总体顺序，但这需要准确的时钟或某种形式的通信。你可以使用完全准确的时钟为每个操作标记时间戳，然后利用它来确定总体顺序。或者你可以使用某种通信系统，使得可以分配类似总体顺序的连续编号。

全序和偏序

在分布式系统中，自然状态是偏序。网络和独立节点都不对相对顺序做出任何保证，但在每个节点上，你可以观察到一个局部顺序。

总序是一种二元关系，它为某个集合中的每个元素定义了一个顺序。

当两个不同的元素可比较时，其中一个大于另一个。在偏序集中，某些元素对不可比较，因此偏序并不指定每个项目的确切顺序。

总序和偏序都是传递性和反对称性的。对于集合 X 中的所有 a、b 和 c，以下陈述在总序和偏序中都成立：

If a ≤ b and b ≤ a then a = b (antisymmetry);
If a ≤ b and b ≤ c then a ≤ c (transitivity);

然而，总序是完全的：

a ≤ b or b ≤ a (totality) for all a, b in X

而偏序是自反的：

a ≤ a (reflexivity) for all a in X

注意，全序性蕴含自反性；因此，偏序是总序的一种较弱的变体。在偏序中的某些元素上，全序性不成立 - 换句话说，其中一些元素不可比较。

Git 分支是偏序的一个例子。正如你可能知道的，Git 版本控制系统允许你从单个基础分支（例如主分支）创建多个分支。每个分支表示基于共同祖先的源代码更改历史：

[ branch A (1,2,0)]  [ master (3,0,0) ]  [ branch B (1,0,2) ]
[ branch A (1,1,0)]  [ master (2,0,0) ]  [ branch B (1,0,1) ]
                  \  [ master (1,0,0) ]  /

分支 A 和分支 B 是从一个共同的祖先派生出来的，但它们之间没有确定的顺序：它们代表不同的历史，不能简化为单一的线性历史而不经过额外的工作（合并）。当然，你可以按某种任意顺序放置所有提交（例如，首先按祖先排序，然后按照 A 在 B 之前或 B 在 A 之前的顺序排序），但这会通过强制存在不存在的总序来丢失信息。

在由一个节点组成的系统中，总序是必然产生的：指令在单个程序中以特定的可观察顺序执行，消息以特定的顺序处理。我们已经依赖于这个总序 - 它使程序的执行可预测。在分布式系统中可以维护这种顺序，但代价很大：通信是昂贵的，时间同步是困难且脆弱的。

时间是什么？

时间是一种秩序的来源，它允许我们定义操作的顺序，而这个顺序也有人们可以理解的解释（秒、分钟、天等）。

从某种意义上说，时间就像任何其他整数计数器一样。它只是因为太重要，以至于大多数计算机都有一个专用的时间传感器，也称为时钟。它非常重要，以至于我们已经找出了如何使用一些不完善的物理系统（从蜡烛到铯原子）合成同一个计数器的近似值。我所说的“合成”，是指我们可以通过某些物理属性在物理上相距较远的地方近似计算整数计数器的值，而不需要直接进行通信。

时间戳实际上是一个简写值，用于表示从宇宙起源到当前时刻的世界状态 - 如果某个事物发生在特定的时间戳上，那么它可能受到之前发生的一切事物的影响。这个想法可以推广为一个因果时钟，它明确跟踪原因（依赖关系），而不仅仅假设前一个时间戳之前的一切都是相关的。当然，通常的假设是我们只关心特定系统的状态，而不是整个世界。

假设时间在任何地方以相同的速度流逝 - 这是一个很大的假设，我一会儿会回到这个问题上 - 时间和时间戳在程序中使用时有几种有用的解释。这三种解释分别是：

• 顺序

• 持续时间

• 解释

顺序。当我说时间是秩序的来源时，我的意思是：

• 我们可以将时间戳附加到无序事件上以对它们进行排序。
• 我们可以使用时间戳来强制执行操作的特定顺序或消息的传递（例如，如果操作到达的顺序错误，则延迟该操作）。
• 我们可以使用时间戳的值来确定某件事在时间上是否发生在另一件事之前。

解释 - 时间作为可普遍比较的值。时间戳的绝对值可以解释为日期，对人类来说很有用。通过日志文件中停机开始的时间戳，你可以知道那是上个星期六，当时有一场雷暴。

持续时间 - 以时间为单位测量的持续时间与现实世界有一定的关系。算法通常不关心时钟的绝对值或其作为日期的解释，但它们可能使用持续时间进行某些判断。特别是，等待的时间长度可以提供有关系统是否分区或仅遇到高延迟的线索。

由于分布式系统的特性，其组件的行为并不可预测。它们不保证任何特定的顺序、前进速度或无延迟。每个节点都有一些局部顺序 - 因为执行是（大致上）顺序执行的 - 但这些局部顺序彼此独立。

强加（或假设）顺序是减少可能执行和可能发生情况空间的一种方式。当事物可以以任何顺序发生时，人们很难推理事物 - 要考虑的排列组合太多了。

时间在任何地方都以相同的速度前进吗？

我们每个人都根据自己的个人经验对时间有一种直观的概念。不幸的是，这种直观的时间观念更容易想象出完全顺序而不是部分顺序。我们更容易想象事物一个接一个地发生的顺序，而不是同时发生。对于消息的单一顺序进行推理比推理以不同顺序和不同延迟到达的消息更容易。

然而，在实施分布式系统时，我们希望避免对时间和顺序做出强烈的假设，因为假设越强，系统对于“时间传感器”或内部时钟的问题就越脆弱。此外，强加一种顺序是有代价的。我们能够容忍的时间非确定性越多，就越能充分利用分布式计算的优势。

对于“时间是否在任何地方以相同的速率流逝”的问题，有三种常见的回答。它们分别是：

• “全局时钟”：是的
• “本地时钟”：不是，但是
• “无时钟”：不是！

这些大致对应于我在第二章中提到的三种时间假设：同步系统模型具有全局时钟，部分同步模型具有本地时钟，在异步系统模型中根本不能使用时钟。让我们更详细地看看这些。

具有“全球时钟”假设的时间

全球时钟假设是存在一个完全精确的全球时钟，并且每个人都可以使用该时钟。这就是我们思考时间的方式，因为在人类互动中，时间上的微小差异并不重要。

全局时钟基本上是总序的来源（即使这些节点从未进行过通信，也能精确确定所有节点上每个操作的顺序）。

然而，这是对世界的理想化观点：实际上，时钟同步只能以有限的精度进行。这受限于商品计算机时钟的准确性不足，受限于使用诸如 NTP 的时钟同步协议时的延迟，以及基本上受限于时空的本质。

假设分布式节点上的时钟完全同步意味着假设时钟从相同的值开始，永远不会漂移。这是一个很好的假设，因为你可以自由使用时间戳来确定全局总序 - 以时钟漂移为界限，而不是延迟 - 但这是一个非平凡的操作挑战和潜在的异常源。存在许多不同的情况，其中简单的故障 - 比如用户意外更改机器上的本地时间，或者过时的机器加入集群，或者同步的时钟以稍微不同的速率漂移等等 - 可能会导致难以追踪的异常。

尽管如此，有一些现实世界的系统做出了这种假设。Facebook 的 Cassandra 就是一个假设时钟同步的系统示例。它使用时间戳来解决写入冲突 - 具有较新时间戳的写入操作获胜。这意味着如果时钟漂移，新数据可能会被旧数据忽略或覆盖；同样，这是一个操作上的挑战（据我所听说的，人们对此非常清楚）。另一个有趣的例子是 Google 的 Spanner：该论文描述了他们的 TrueTime API，它同步时间但也估计最坏情况下的时钟漂移。

“本地时钟”假设的时间

第二个也许更合理的假设是每台机器都有自己的时钟，但没有全局时钟。这意味着您无法使用本地时钟来确定远程时间戳是发生在本地时间戳之前还是之后；换句话说，您无法有意义地比较两台不同机器的时间戳。

本地时钟假设更接近于现实世界。它建立了一个部分顺序：每个系统上的事件被排序，但通过仅使用时钟无法对跨系统的事件进行排序。

然而，在单个机器上，您可以使用时间戳对事件进行排序；只要小心不允许时钟跳动，您可以在单个机器上使用超时。当然，在由最终用户控制的机器上，这可能假设得太多了：例如，用户在使用操作系统的日期控件查找日期时可能会意外更改日期为其他值。

在实际的分布式系统中，仅依靠本地时钟来对跨不同机器的事件进行排序可能导致不一致性，并且在实现对系统状态的全局视图方面存在挑战。为了解决这些问题并在系统间建立事件的部分顺序，使用各种同步机制和算法，例如逻辑时钟或向量时钟。这些机制通常利用节点之间的消息交换和协调来实现对分布式系统的一致视图。

“无时钟”假设的时间

最后，还有逻辑时间的概念。在这种情况下，我们根本不使用时钟，而是以某种其他方式跟踪因果关系。请记住，时间戳只是对该时刻之前世界状态的一种简写 - 因此，我们可以使用计数器和通信来确定某个事件是在另一个事件之前、之后还是同时发生。

通过这种方式，我们可以确定不同机器之间事件的顺序，但无法对时间间隔进行任何说明，也无法使用超时（因为我们假设没有"时间传感器"）。这是一个部分顺序：在单个系统上，可以使用计数器而无需通信来对事件进行排序，但在系统间对事件进行排序则需要进行消息交换。

在分布式系统中，Lamport 关于时间、时钟和事件排序的论文是最被引用的之一。向量时钟是该概念的推广（我将更详细地介绍它），它是一种在不使用时钟的情况下跟踪因果关系的方法。Cassandra 的近亲产品 Riak（Basho）和 Voldemort（Linkedin）使用向量时钟而不是假设节点具有完全准确的全局时钟。这使得这些系统能够避免之前提到的时钟准确性问题。

当不使用时钟时，跨远程机器对事件进行排序的最大精度受到通信延迟的限制。

分布式系统中的时间是如何使用的？

时间的好处在于：

1. 定义系统中的顺序（无需通信）：时间可以在系统中定义事件的顺序，即使没有直接的通信。通过时间戳或逻辑时钟，可以将事件按照它们发生的顺序进行排序。
2. 为算法定义边界条件：时间可以用来划定算法的边界条件，特别是区分“高延迟”和“服务器或网络连接断开”。这是非常重要的应用场景；在大多数现实世界的系统中，超时用于确定远程机器是否失败，或者它是否仅仅是遇到了高网络延迟。用于进行此类判断的算法称为故障检测器（failure detectors）。

在分布式系统中，事件的顺序非常重要，因为许多分布式系统的性质是通过操作/事件的顺序来定义的：

• 正确性取决于（对事件顺序的）正确一致性，例如在分布式数据库中的可串行化性。
• 当资源争用发生时，顺序可以用作决定性因素，例如如果有两个对于一个小部件的订单，可以满足第一个订单并取消第二个订单。

全局时钟将允许在两台不同的机器上的操作进行排序，而无需这两台机器直接通信。没有全局时钟，我们需要通过通信来确定顺序。

因此，时间在分布式系统中具有重要的作用，可以帮助实现事件的顺序确定、算法的边界条件划定以及故障检测等关键功能。

矢量时钟（因果顺序的时间）

之前我们讨论了分布式系统中时间进展速率的不同假设。假设我们无法实现准确的时钟同步，或者以系统不对时间同步问题敏感为目标，我们如何对事件进行排序呢？

Lamport 时钟和向量时钟是替代物理时钟的解决方案，它们依靠计数器和通信来确定分布式系统中事件的顺序。这些时钟提供了一个可在不同节点之间进行比较的计数器。

Lamport 时钟很简单。每个进程使用以下规则来维护一个计数器：

• 每当进程执行工作时，增加计数器的值。
• 每当进程发送消息时，将计数器的值包含在消息中。
• 当接收到消息时，将计数器设置为max(local_counter, received_counter) + 1。

以下是用代码表达的示例：

function LamportClock() {
  this.value = 1;
}

LamportClock.prototype.get = function () {
  return this.value;
};

LamportClock.prototype.increment = function () {
  this.value++;
};

LamportClock.prototype.merge = function (other) {
  this.value = Math.max(this.value, other.value) + 1;
};

Lamport 时钟允许在系统之间比较计数器，但有一个限制：Lamport 时钟定义了一个偏序关系。如果 timestamp(a) < timestamp(b)：

• a 可能在 b 之前发生，或者
• a 与 b 不可比较

这被称为时钟一致性条件：如果一个事件在另一个事件之前发生，则该事件的逻辑时钟在其他事件之前。如果 a 和 b 来自同一因果历史，例如两个时间戳值都来自同一个进程，或者 b 是对 a 发送的消息的响应，那么我们知道 a 在 b 之前发生。

直观上讲，这是因为 Lamport 时钟只能携带关于一个时间线/历史的信息；因此，将从未相互通信的系统的 Lamport 时间戳进行比较可能导致并发事件在没有顺序关系的情况下被排序。

想象一个系统，在初始阶段之后分为两个永不相互通信的独立子系统。

对于每个独立系统中的所有事件，如果 a 在 b 之前发生，则 ts(a) < ts(b)；但是，如果你从不同的独立系统中选择两个事件（即彼此无因果关系的事件），则无法对它们的相对顺序做出有意义的判断。虽然系统的每个部分已经为事件分配了时间戳，但这些时间戳之间没有关联。即使两个事件无关，它们可能看起来是有序的。

然而，从单台机器的角度来看，仍然有一个有用的性质：以 ts(a)发送的任何消息都会收到一个 ts(b) > ts(a)的响应。

向量时钟是 Lamport 时钟的扩展，它维护了一个包含 N 个逻辑时钟（每个节点一个）的数组[t1, t2, …]。每个节点在每个内部事件中不是递增一个公共计数器，而是递增向量中表示该节点的逻辑时钟的值。因此，更新规则如下：

• 当一个进程执行工作时，增加向量中节点的逻辑时钟值。

• 当一个进程发送消息时，包括完整的逻辑时钟向量。

• 当接收到一条消息时：

  • 将向量中的每个元素更新为本地和接收到的值的最大值。

  • 增加表示当前节点的逻辑时钟值的向量中的元素。

以下是相应的代码实现：

function VectorClock(value) {
  // expressed as a hash keyed by node id: e.g. { node1: 1, node2: 3 }
  this.value = value || {};
}

VectorClock.prototype.get = function () {
  return this.value;
};

VectorClock.prototype.increment = function (nodeId) {
  if (typeof this.value[nodeId] == "undefined") {
    this.value[nodeId] = 1;
  } else {
    this.value[nodeId]++;
  }
};

VectorClock.prototype.merge = function (other) {
  var result = {},
    last,
    a = this.value,
    b = other.value;
  // This filters out duplicate keys in the hash
  Object.keys(a)
    .concat(b)
    .sort()
    .filter(function (key) {
      var isDuplicate = key == last;
      last = key;
      return !isDuplicate;
    })
    .forEach(function (key) {
      result[key] = Math.max(a[key] || 0, b[key] || 0);
    });
  this.value = result;
};

此图（来源）显示了矢量时钟：

每个节点（A、B、C）都跟踪向量时钟。随着事件发生，它们会被标记上当前向量时钟的值。通过检查向量时钟，例如{ A: 2, B: 4, C: 1 }，我们可以准确地确定（可能）影响该事件的消息。

向量时钟的问题主要在于它们需要每个节点一个条目，这意味着对于大型系统来说，它们可能会变得非常庞大。为了减小向量时钟的大小，已经应用了各种技术（例如定期进行垃圾回收，或通过限制大小来降低准确性）。

我们已经看过如何在没有物理时钟的情况下跟踪顺序和因果关系。现在，让我们看看如何使用时间持续期进行截止。

故障检测器（截止时间）

如我之前所述，等待的时间量可以提供关于系统是分区还是仅遇到高延迟的线索。在这种情况下，我们不需要假设一个完全准确的全局时钟，只需要有一个足够可靠的本地时钟即可。

给定在一个节点上运行的程序，它如何判断远程节点是否失败？在没有准确信息的情况下，我们可以推断在经过一段合理的时间后，无响应的远程节点已经失败。

但是，什么是“合理的时间”？这取决于本地和远程节点之间的延迟。与其明确地指定具有特定值的算法（在某些情况下不可避免地是错误的），最好处理一个合适的抽象概念。

故障检测器是一种用于抽象化准确计时假设的方法。故障检测器使用心跳消息和定时器实现。进程交换心跳消息。如果在超时之前未收到消息响应，则进程怀疑其他进程。

基于超时的故障检测器存在过于激进（宣布节点失败）或过于保守（需要很长时间才能检测到崩溃）的风险。故障检测器需要多准确才能使用？

Chandra 等人（1996）在解决共识问题的背景下讨论了故障检测器，这是一个特别相关的问题，因为它是大多数复制问题的基础，其中副本需要在具有延迟和网络分区的环境中达成一致。

他们使用两个属性来描述故障检测器：完整性和准确性：

• 强完整性。每个崩溃的进程最终被每个正确的进程怀疑。
• 弱完整性。每个崩溃的进程最终被某个正确的进程怀疑。
• 强准确性。没有正确的进程被怀疑。
• 弱准确性。某个正确的进程从未被怀疑。

完整性比准确性更容易实现；事实上，所有重要的故障检测器都可以达到它 - 你所需要做的就是不永远等待来怀疑某人。Chandra 等人指出，具有弱完整性的故障检测器可以转化为具有强完整性的故障检测器（通过广播有关被怀疑进程的信息），从而使我们可以集中关注准确性属性的范围。

除非您能够假设消息延迟存在硬上限，否则很难避免错误地怀疑非故障进程。这个假设可以在同步系统模型中进行 - 因此，在这种系统中，故障检测器可以是强准确的。在不对消息延迟施加硬限制的系统模型下，故障检测最多只能是最终准确的。

Chandra 等人表明，即使是非常弱的故障检测器 - 最终弱故障检测器 ⋄W（最终弱准确性+弱完整性） - 也可以用于解决共识问题。下面的图表（来自论文）说明了系统模型和问题可解性之间的关系：

正如您上面所看到的，在异步系统中，如果没有故障检测器（或对时间边界的强假设，例如同步系统模型），就无法确定远程节点是崩溃了还是仅仅遇到了高延迟。对于任何追求单一副本一致性的系统来说，这种区分是重要的：故障节点可以被忽略，因为它们不会导致数据的分歧，但分区节点则不能被安全地忽略。

如何实现故障检测器呢？从概念上讲，一个简单的故障检测器并没有太多复杂的内容，它只是在超时后检测到失败。最有趣的部分涉及如何判断远程节点是否失败。

理想情况下，我们希望故障检测器能够自适应不断变化的网络条件，并避免将超时值硬编码到其中。例如，Cassandra 使用了一种称为累积故障检测器的方法，它会输出一个怀疑级别（介于 0 和 1 之间的值），而不是二进制的“上”或“下”判断。这使得使用故障检测器的应用程序可以根据准确性和早期检测之间的权衡做出自己的决策。

累积故障检测器的实现方式可以根据具体的算法和系统需求而有所不同。它通常基于心跳机制，使用心跳消息和定时器来检测节点的存活状态。具体的实现可能涉及超时时间的选择、可疑级别的计算方法以及如何根据累积的信息进行判断等。

通过使用累积故障检测器或类似的方法，可以使故障检测器能够根据网络条件的变化进行动态调整，并提供更灵活的判断结果，以满足系统的需求。这样的故障检测器可以帮助系统在异步环境中实现更可靠的一致性。

时间、顺序和表现

之前，我提到了需要为顺序付出代价，您想知道这是什么意思？

如果您正在编写一个分布式系统，那么您可能拥有多台计算机。在这种情况下，对于事件的自然（也是现实）观点是部分顺序而不是总顺序。您可以将部分顺序转化为总顺序，但这需要通信、等待，并且会施加限制，限制了在任何特定时间点上可以工作的计算机数量。

所有时钟都只是近似值，受网络延迟（逻辑时间）或物理限制。即使在多个节点之间保持一个简单的整数计数器同步也是一个挑战。

尽管时间和顺序经常一起讨论，但时间本身并不是一个非常有用的属性。算法关心的不是时间，而是更抽象的属性：

• 事件的因果顺序
• 故障检测（例如，消息传递的上界近似）
• 一致快照（例如，在某个时间点上检查系统状态的能力；此处不讨论）

强制施加总顺序是可能的，但代价很高。这要求您以最常见（最低）的速度进行操作。通常，确保事件按某种定义的顺序传递的最简单方法是指定一个单一（瓶颈）节点，所有操作都通过该节点进行。

时间/顺序/同步真的是必需的吗？这取决于情况。在某些用例中，我们希望每个中间操作将系统从一个一致状态移动到另一个一致状态。例如，在许多情况下，我们希望数据库的响应表示所有可用的信息，并且希望避免处理系统可能返回不一致结果的问题。

但在其他情况下，我们可能不需要那么多的时间/顺序/同步。例如，如果您正在运行一个长时间运行的计算，并且在最后阶段之前并不关心系统的操作，那么只要能够保证答案正确，就不需要太多的同步。

同步通常被作为一种粗糙的工具应用于所有操作，而实际上只有一部分情况对最终结果真正重要。何时需要顺序来保证正确性？CALM 定理提供了一个答案，我将在最后一章中讨论。

在其他情况下，接受只表示最佳已知估计的答案是可以接受的，也就是说，它只基于系统中包含的总信息的一个子集。特别是在网络分区期间，可能需要使用系统的部分来回答查询。在其他用例中，最终用户实际上无法区分相对较新且可以廉价获取的答案与保证正确且计算成本高昂的答案。例如，Twitter 用户 X 的关注者数量是 X 还是 X+1？或者对于某个查询，电影 A、B 和 C 是否是绝对最佳的答案？进行更便宜、基本正确的“尽力而为”可能是可以接受的。

在接下来的两章中，我们将研究容错强一致性系统的复制——这些系统在提供强保证的同时，对故障具有越来越强的韧性。这些系统提供了第一种情况的解决方案：当您需要保证正确性并愿意为此付出代价时。然后，我们将讨论具有弱一致性保证的系统，这些系统可以在分区的情况下保持可用，但只能给出之力求最佳的答案。

进一步阅读

兰波特时钟，矢量时钟

• Time, Clocks and Ordering of Events in a Distributed System - Leslie Lamport, 1978

故障检测

• Unreliable failure detectors and reliable distributed systems - Chandra and Toueg
• Latency- and Bandwidth-Minimizing Optimal Failure Detectors - So & Sirer, 2007
• The failure detector abstraction, Freiling, Guerraoui & Kuznetsov, 2011

快照

• Consistent global states of distributed systems: Fundamental concepts and mechanisms, Ozalp Babaogly and Keith Marzullo, 1993
• Distributed snapshots: Determining global states of distributed systems, K. Mani Chandy and Leslie Lamport, 1985

因果关系

• Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail - Schwarz & Mattern, 1994
• Understanding the Limitations of Causally and Totally Ordered Communication - Cheriton & Skeen, 1993