分布式系统中的时间、时钟与事件顺序

Leslie Lamport
Massachusetts Computer Associates, Inc.

摘要

本文考察分布式系统（distributed system）中一个事件发生在另一个事件之前这一概念，并说明它定义了事件的一种偏序（partial ordering）。文中给出一种分布式算法，用来同步一组逻辑时钟（logical clock）；这些逻辑时钟可用于对事件进行全序排列（total ordering）。随后通过一种求解同步问题的方法说明这种全序的用途。接着将该算法特化为物理时钟（physical clock）同步算法，并推导时钟之间可能偏离同步状态的上界。

关键词和短语： distributed systems，computer networks，clock synchronization，multiprocess systems

引言

时间概念是我们思维方式的基础。它源自一个更基本的概念：事件发生的先后顺序。我们说某件事发生在 3:15，是指它发生在我们的时钟读数为 3:15 之后、3:16 之前。事件的时间顺序概念贯穿了我们对系统的思考。例如，在航空订票系统中，我们会规定：如果一次订票请求是在航班订满之前提出的，就应当批准该请求。然而，我们会看到，在考虑分布式系统中的事件时，必须仔细重新审视这一概念。

分布式系统由一组相互区别、空间上分离的进程组成，这些进程通过交换消息彼此通信。由互联计算机构成的网络，例如 ARPA 网，就是一个分布式系统。单台计算机也可以看作一个分布式系统，其中中央控制单元、存储单元和输入输出通道是彼此分离的进程。如果消息传输延迟相对于单个进程中事件之间的时间不可忽略，那么这个系统就是分布式的。

我们主要关注由空间上分离的计算机组成的系统。不过，本文的许多论述也更一般地适用。特别是，单台计算机上的多处理系统也会涉及类似于分布式系统的问题，因为某些事件发生的顺序是不可预测的。

在分布式系统中，有时无法说两个事件中哪一个先发生。因此，“发生在……之前”（happened before）关系只是系统中事件的一种偏序。我们发现，问题常常产生于人们没有充分意识到这一事实及其含义。

本文讨论由“发生在……之前”关系定义的偏序，并给出一种分布式算法，将它扩展为所有事件的一致全序。该算法可以为实现分布式系统提供有用机制。我们通过一种求解同步问题的简单方法来说明它的用途。如果该算法得到的顺序不同于用户感知到的顺序，就可能发生意外的异常行为（anomalous behavior）。引入真实的物理时钟可以避免这种情况。我们描述一种同步这些时钟的简单方法，并推导它们可能偏离同步状态的上界。

偏序

大多数人也许会说，如果事件 \(a\) 发生的时间早于事件 \(b\)，那么事件 \(a\) 发生在事件 \(b\) 之前。他们可能会用关于时间的物理理论来说明这一定义。然而，如果一个系统要正确满足某个规约，那么该规约必须用系统内可观察到的事件来表述。如果规约用物理时间来表述，那么系统就必须包含真实时钟。即使系统确实包含真实时钟，仍然存在一个问题：这些时钟并不完全准确，也不会保持精确的物理时间。因此，我们将在不使用物理时钟的情况下定义“发生在……之前”关系。

我们先更精确地定义系统。假定系统由一组进程组成。每个进程由一个事件序列组成。根据应用不同，计算机上一个子程序的执行可以是一个事件，一条机器指令的执行也可以是一个事件。我们假定一个进程中的事件形成一个序列；如果在这个序列中 \(a\) 发生在 \(b\) 之前，就说 \(a\) 先于 \(b\)。换句话说，单个进程被定义为一组具有先验全序的事件。这似乎就是通常所说的进程含义。† 将定义扩展为允许一个进程分裂成不同子进程是很平凡的，但这里不再这样做。

我们假定发送消息或接收消息都是进程中的事件。于是可以如下定义“发生在……之前”关系，记作 \(\to\)。

定义。 系统事件集合上的关系 \(\to\) 是满足以下三个条件的最小关系：(1) 如果 \(a\) 和 \(b\) 是同一进程中的事件，并且 \(a\) 先于 \(b\)，则 \(a \to b\)。(2) 如果 \(a\) 是一个进程发送某条消息的事件，而 \(b\) 是另一个进程接收同一条消息的事件，则 \(a \to b\)。(3) 如果 \(a \to b\) 且 \(b \to c\)，则 \(a \to c\)。如果两个不同事件 \(a\) 和 \(b\) 满足 \(a \nrightarrow b\) 且 \(b \nrightarrow a\)，则称它们是并发的（concurrent）。

我们假定对任意事件 \(a\) 都有 \(a \nrightarrow a\)。（一个事件能够发生在自身之前的系统似乎没有物理意义。）这意味着 \(\to\) 是所有事件集合上的一种非自反偏序。

用图 1 这样的“时空图”（space-time diagram）来理解这一定义会很有帮助。水平方向表示空间，竖直方向表示时间，位置越高表示时间越晚。点表示事件，竖线表示进程，波浪线表示消息。† 很容易看出，\(a \to b\) 意味着可以在图中沿进程线和消息线从 \(a\) 向时间前进的方向走到 \(b\)。例如，在图 1 中有 \(p_{1} \to r_{4}\)。

另一种理解定义的方式是：\(a \to b\) 意味着事件 \(a\) 有可能因果地影响事件 \(b\)。如果两个事件彼此都不能因果影响对方，则它们是并发的。例如，图 1 中的事件 \(p_{3}\) 和 \(q_{3}\) 是并发的。尽管我们在图中画得像是 \(q_{3}\) 的物理时间早于 \(p_{3}\)，但进程 \(P\) 在事件 \(p_{4}\) 接收到消息之前，不可能知道进程 \(Q\) 在 \(q_{3}\) 做了什么。（在事件 \(p_{4}\) 之前，\(P\) 最多只能知道 \(Q\) 计划在 \(q_{3}\) 做什么。）

熟悉狭义相对论中不变时空表述的读者会觉得这个定义很自然，例如 \[1\] 或 \[2\] 第一章中描述的那种表述。在相对论中，事件的顺序是根据可能发送的消息来定义的。不过，我们采取了更务实的做法，只考虑实际发送的消息。我们应当能够仅凭已经发生的事件来判断系统是否正确执行，而不必知道哪些事件本来可能发生。

逻辑时钟

现在把时钟引入系统。我们先从抽象角度出发：时钟只是给事件赋予一个数的一种方式，这个数被看作事件发生的时间。更精确地说，我们为每个进程 \(P_{i}\) 定义一个时钟 \(C_{i}\)，它为该进程中的任意事件 \(a\) 赋予一个数 \(C_{i}(a)\)。整个系统的时钟由函数 \(C\) 表示；它为任意事件 \(b\) 赋值 \(C(b)\)，其中如果 \(b\) 是进程 \(P_{j}\) 中的事件，则 \(C(b) = C_{j}(b)\)。目前我们不假定数字 \(C_{i}(a)\) 与物理时间有任何关系，因此可以把这些时钟 \(C_{i}\) 视为逻辑时钟，而不是物理时钟。它们可以用计数器实现，不需要任何实际计时机制。

现在考虑这样的时钟系统怎样才算正确。我们不能基于物理时间来定义正确性，因为那会要求引入保持物理时间的时钟。我们的定义必须基于事件发生的顺序。最强的合理条件是：如果事件 \(a\) 发生在另一个事件 \(b\) 之前，那么 \(a\) 应该发生在比 \(b\) 更早的时刻。更形式化地说：

时钟条件（Clock Condition）。 对任意事件 \(a\)、\(b\)：

\[ a \to b \Longrightarrow C(a) < C(b) \]

注意，我们不能期望反向条件也成立，因为那会意味着任意两个并发事件必须发生在同一时刻。在图 1 中，\(p_{2}\) 和 \(p_{3}\) 都与 \(q_{3}\) 并发，所以这会意味着它们都必须与 \(q_{3}\) 同时发生；但这会和时钟条件矛盾，因为 \(p_{2} \to p_{3}\)。

根据我们对关系 \(\to\) 的定义，很容易看出，如果下列两个条件成立，时钟条件就成立。

C1。 如果 \(a\) 和 \(b\) 是进程 \(P_{i}\) 中的事件，并且 \(a\) 先于 \(b\)，则 \(C_{i}(a) < C_{i}(b)\)。

C2。 如果 \(a\) 是进程 \(P_{i}\) 发送某条消息的事件，而 \(b\) 是进程 \(P_{j}\) 接收该消息的事件，则 \(C_{i}(a) < C_{j}(b)\)。

让我们用时空图来考察时钟。我们想象一个进程的时钟会逐一经过每个数值的“时钟刻度”（tick），而这些刻度出现在该进程的事件之间。例如，如果 \(a\) 和 \(b\) 是进程 \(P_{i}\) 中的连续事件，且 \(C_{i}(a) = 4\)、\(C_{i}(b) = 7\)，那么时钟刻度 5、6、7 出现在这两个事件之间。我们通过不同进程中编号相同的时钟刻度画出一条虚线“时钟刻度线”（tick line）。图 1 的时空图可能得到图 2 所示的图形。条件 C1 意味着进程线上任意两个事件之间必须有一条时钟刻度线，条件 C2 意味着每条消息线都必须穿过一条时钟刻度线。根据 \(\to\) 的图形含义，很容易看出为什么这两个条件会推出时钟条件。

我们可以把时钟刻度线看作时空中某个笛卡尔坐标系的时间坐标线。可以重画图 2，把这些坐标线拉直，从而得到图 3。图 3 是表示同一事件系统的另一种有效方式。只要没有把物理时间概念引入系统（这要求引入物理时钟），就没有办法判定这两幅图中哪一幅是更好的表示。

读者也许会发现，想象一个二维空间中的进程网络很有帮助；它会产生三维时空图。进程和消息仍由线表示，但时钟刻度线会变成二维曲面。

现在假定进程是算法，事件表示算法执行过程中的某些动作。我们将说明如何在进程中引入满足时钟条件的时钟。进程 \(P_{i}\) 的时钟由寄存器 \(C_{i}\) 表示，因此 \(C_{i}(a)\) 是事件 \(a\) 期间 \(C_{i}\) 中保存的值。\(C_{i}\) 的值会在事件之间改变，所以改变 \(C_{i}\) 本身并不构成事件。

为了保证时钟系统满足时钟条件，我们将确保它满足条件 C1 和 C2。条件 C1 很简单；进程只需遵守以下实现规则：

IR1。 每个进程 \(P_{i}\) 在任意两个连续事件之间递增 \(C_{i}\)。

为了满足条件 C2，我们要求每条消息 \(m\) 都包含时间戳（timestamp）\(T_{m}\)，它等于该消息被发送时的时间。进程收到时间戳为 \(T_{m}\) 的消息时，必须把自己的时钟推进到晚于 \(T_{m}\)。更精确地说，有如下规则。

IR2。 (a) 如果事件 \(a\) 是进程 \(P_{i}\) 发送消息 \(m\)，则消息 \(m\) 包含时间戳 \(T_{m} = C_{i}(a)\)。(b) 收到消息 \(m\) 时，进程 \(P_{j}\) 将 \(C_{j}\) 设置为大于或等于当前值，并且大于 \(T_{m}\)。

在 IR2(b) 中，我们认为表示接收消息 \(m\) 的事件发生在设置 \(C_{j}\) 之后。（这只是记号上的麻烦，在任何实际实现中都无关紧要。）显然，IR2 保证 C2 成立。因此，简单的实现规则 IR1 和 IR2 蕴含时钟条件成立，从而保证得到正确的逻辑时钟系统。

对事件进行全序排列

可以用满足时钟条件的一组时钟来给所有系统事件组成的集合赋予全序。我们只需按照事件发生的时间来排序。为了打破并列，我们使用进程上的任意全序 \(<\)。更精确地说，定义关系 \(\Rightarrow\) 如下：如果 \(a\) 是进程 \(P_{i}\) 中的事件，\(b\) 是进程 \(P_{j}\) 中的事件，则 \(a \Rightarrow b\) 当且仅当 (i) \(C_{i}(a) < C_{j}(b)\)，或者 (ii) \(C_{i}(a) = C_{j}(b)\) 且 \(P_{i} < P_{j}\)。很容易看出，这定义了一个全序，并且时钟条件蕴含：如果 \(a \to b\)，则 \(a \Rightarrow b\)。换句话说，关系 \(\Rightarrow\) 是把“发生在……之前”偏序补全为全序的一种方式。†

排序 \(\Rightarrow\) 依赖于时钟系统 \(C_{i}\)，并不是唯一的。选择不同的、满足时钟条件的时钟，会得到不同的关系 \(\Rightarrow\)。给定任意一个扩展 \(\to\) 的全序关系 \(\Rightarrow\)，都存在一个满足时钟条件的时钟系统会产生该关系。唯一由事件系统本身决定的是偏序。

能够对事件进行全序排列，对实现分布式系统非常有用。事实上，实现正确逻辑时钟系统的原因就是获得这样的全序。我们将通过求解下面这个互斥问题（mutual exclusion problem）的版本来说明事件全序的用途。考虑一个由固定进程集合组成的系统，它们共享一个资源。一次只能有一个进程使用该资源，因此这些进程必须彼此同步以避免冲突。我们希望找到一种向进程授予资源的算法，满足以下三个条件：(I) 已被授予资源的进程必须释放该资源之后，资源才能授予另一个进程。(II) 对资源的不同请求必须按照提出请求的顺序被授予。(III) 如果每个获得资源的进程最终都会释放资源，那么每个请求最终都会被授予。

我们假定资源初始时恰好授予一个进程。

这些都是完全自然的要求。它们精确说明了解法正确的含义。† 注意这些条件怎样涉及事件的顺序。条件 II 并没有规定两个并发提出的请求中哪一个应当先被授予。

必须认识到，这不是一个平凡问题。使用一个中央调度进程按照收到请求的顺序授予请求并不可行，除非再作额外假设。为说明这一点，令 \(P_{0}\) 为调度进程。假设 \(P_{1}\) 向 \(P_{0}\) 发送一个请求，然后向 \(P_{2}\) 发送一条消息。\(P_{2}\) 收到后一条消息后，向 \(P_{0}\) 发送一个请求。\(P_{2}\) 的请求完全可能先于 \(P_{1}\) 的请求到达 \(P_{0}\)。如果先授予 \(P_{2}\) 的请求，就违反了条件 II。

为了解决这个问题，我们用规则 IR1 和 IR2 实现一个时钟系统，并用它们定义所有事件上的全序 \(\Rightarrow\)。这为所有请求和释放操作提供了一个全序。有了这个顺序，构造解法就相当直接。它只涉及确保每个进程都获知所有其他进程的操作。

为简化问题，我们作一些假设。它们并非本质要求，只是为了避免分散注意力的实现细节。首先假定，对任意两个进程 \(P_{i}\) 和 \(P_{j}\)，从 \(P_{i}\) 发送给 \(P_{j}\) 的消息按发送顺序被接收。此外，假定每条消息最终都会被接收。（这些假设可以通过引入消息编号和消息确认协议来避免。）我们还假定一个进程可以直接向其他每个进程发送消息。

每个进程维护自己的请求队列，其他进程永远看不到该队列。我们假定请求队列初始时包含唯一一条消息 T0:P0 requests resource，其中 \(P_{0}\) 是初始获得资源的进程，\(T_{0}\) 小于任何时钟的初值。

算法由以下五条规则定义。为方便起见，每条规则定义的动作都假定构成单个事件。

1. 为请求资源，进程 \(P_{i}\) 向其他每个进程发送消息 Tm:Pi requests resource，并把该消息放入自己的请求队列，其中 \(T_{m}\) 是该消息的时间戳。

2. 当进程 \(P_{j}\) 收到消息 Tm:Pi requests resource 时，它将该消息放入自己的请求队列，并向 \(P_{i}\) 发送一条带时间戳的确认消息。†

3. 为释放资源，进程 \(P_{i}\) 从自己的请求队列中移除任意 Tm:Pi requests resource 消息，并向其他每个进程发送一条带时间戳的 Pi releases resource 消息。

4. 当进程 \(P_{j}\) 收到一条 Pi releases resource 消息时，它从自己的请求队列中移除任意 Tm:Pi requests resource 消息。

5. 当满足以下两个条件时，进程 \(P_{i}\) 被授予资源：(i) 它的请求队列中存在一条 Tm:Pi requests resource 消息，根据关系 \(\Rightarrow\)，该消息排在队列中任何其他请求之前。（为了定义消息上的关系 \(\Rightarrow\)，我们把一条消息等同于发送该消息的事件。）(ii) \(P_{i}\) 已经从其他每个进程收到一条时间戳晚于 \(T_{m}\) 的消息。†

注意，规则 5 的条件 (i) 和 (ii) 都由 \(P_{i}\) 在本地测试。

很容易验证，这些规则定义的算法满足条件 I-III。首先，注意规则 5 的条件 (ii) 连同消息按序接收这一假设，保证 \(P_{i}\) 已经获知所有先于其当前请求的请求。由于只有规则 3 和 4 会从请求队列中删除消息，因此很容易看出条件 I 成立。条件 II 来自这样一个事实：全序 \(\Rightarrow\) 扩展了偏序 \(\to\)。规则 2 保证在 \(P_{i}\) 请求资源之后，规则 5 的条件 (ii) 最终会成立。规则 3 和 4 蕴含：如果每个获得资源的进程最终都释放资源，那么规则 5 的条件 (i) 最终会成立，从而证明条件 III。

这是一个分布式算法。每个进程独立遵循这些规则，不存在中央同步进程或中央存储。这种方法可以推广，用于实现这类分布式多处理系统中任何期望的同步。同步用一个状态机（State Machine）来规定，状态机由可能命令的集合 \(C\)、可能状态的集合 \(S\)，以及函数 \(e: C \times S \to S\) 组成。关系 \(e(C, S) \to S'\) 表示在机器处于状态 \(S\) 时执行命令 \(C\)，会使机器状态变为 \(S'\)。在我们的例子中，集合 \(C\) 包含所有命令 Pi requests resource 和 Pi releases resource；状态由等待请求命令组成的队列表示，队首的请求就是当前被授予的请求。执行一个请求命令会把该请求加入队尾，执行一个释放命令会从队列中移除一个命令。†

每个进程独立地模拟该状态机的执行，使用所有进程发出的命令。同步之所以实现，是因为所有进程都按照命令的时间戳（使用关系 \(\Rightarrow\)）来排序，因此每个进程都使用相同的命令序列。当一个进程已经获知其他所有进程发出的、时间戳小于或等于 \(T\) 的全部命令后，它就可以执行时间戳为 \(T\) 的命令。精确算法很直接，这里不再描述。

这种方法允许在分布式系统中实现任何期望形式的多处理同步。然而，所得算法要求所有进程积极参与。一个进程必须知道其他进程发出的所有命令，因此单个进程发生故障就会使任何其他进程都无法执行状态机命令，从而使系统停顿。

故障问题很困难，详细讨论它超出了本文范围。我们只指出，整个故障概念只有在物理时间的语境中才有意义。没有物理时间，就无法区分一个发生故障的进程和一个只是在事件之间暂停的进程。用户能判断系统已经“崩溃”，只是因为他等待响应的时间太长了。\[3\] 描述了一种即使个别进程或通信线路发生故障也能工作的办法。

异常行为

我们的资源调度算法按照全序 \(\Rightarrow\) 对请求排序。这允许出现以下类型的“异常行为”。考虑一个全国范围内的互联计算机系统。假设某人在计算机 \(A\) 上发出请求 \(A\)，然后给另一个城市的朋友打电话，让他在另一台计算机 \(B\) 上发出请求 \(B\)。请求 \(B\) 完全可能获得较小的时间戳，并被排在请求 \(A\) 之前。这会发生，是因为系统无法知道 \(A\) 实际上先于 \(B\)，因为这种先后信息基于系统外部的消息。

让我们更仔细地考察问题来源。令 \(S\) 为所有系统事件的集合。再引入一个事件集合 \(S^*\)，它包含 \(S\) 中的事件，以及所有其他相关外部事件，例如我们例子中的电话。令 \(\to^*\) 表示 \(S^*\) 上的“发生在……之前”关系。在例子中，我们有 \(A \to^* B\)，但没有 \(A \to B\)。显然，任何完全基于 \(S\) 中事件、并且不以任何方式将这些事件同 \(S^*\) 中其他事件关联起来的算法，都无法保证请求 \(A\) 排在请求 \(B\) 之前。

有两种可能方式可以避免这种异常行为。第一种方式是把关于顺序 \(\to^*\) 的必要信息显式引入系统。在我们的例子中，发出请求 \(A\) 的人可以从系统获得该请求的时间戳 \(T_{A}\)。他的朋友在发出请求 \(B\) 时，可以指定 \(B\) 应当获得晚于 \(T_{A}\) 的时间戳。这把避免异常行为的责任交给了用户。

第二种方法是构造满足以下条件的时钟系统。

强时钟条件（Strong Clock Condition）。 对 \(S^*\) 中任意事件 \(a\)、\(b\)：

\[ a \to^* b \Longrightarrow C(a) < C(b) \]

它比普通时钟条件更强，因为 \(\to^*\) 是比 \(\to\) 更强的关系。一般来说，我们的逻辑时钟并不满足它。

让我们把 \(S^*\) 等同于物理时空中的某个“真实”事件集合，并令 \(\to^*\) 为由狭义相对论定义的事件偏序。宇宙中的一个神秘之处是：可以构造一组物理时钟，它们彼此相当独立地运行，却会满足强时钟条件。因此，我们可以使用物理时钟来消除异常行为。现在转向这类时钟。

物理时钟

把物理时间坐标引入我们的时空图，并令 \(C_{i}(t)\) 表示时钟 \(C_{i}\) 在物理时间 \(t\) 的读数。† 为了数学上的方便，假定时钟连续运行，而不是以离散“时钟刻度”运行。（离散时钟可以看作一种连续时钟，只是在读取时可能有最多 1/2 个“时钟刻度”的误差。）更精确地说，假定 \(C_{i}(t)\) 是 \(t\) 的连续、可微函数，除了时钟被重置处存在孤立跳跃不连续点。于是 \(\frac{dC_i(t)}{dt}\) 表示时钟在时间 \(t\) 的运行速率。

为了让时钟 \(C_{i}\) 成为真正的物理时钟，它必须以近似正确的速率运行。也就是说，对所有 \(t\)，必须有 \(\frac{dC_i(t)}{dt} \approx 1\)。更精确地说，我们假定满足以下条件：

PC1。 存在常数 \(\kappa \ll 1\)，使得对所有 \(i\)：

\[ \left|\frac{dC_i(t)}{dt} - 1\right| < \kappa \]

对典型的晶体控制时钟，\(\kappa \le 10^{-6}\)。

仅仅让各个时钟分别以近似正确的速率运行还不够。它们必须同步，使得对所有 \(i\)、\(j\) 和 \(t\)，\(C_{i}(t) \approx C_{j}(t)\)。更精确地说，必须存在足够小的常数 \(\epsilon\)，使得以下条件成立：

PC2。 对所有 \(i\)、\(j\)：

\[ \left|C_i(t) - C_j(t)\right| < \epsilon \]

如果把图 2 中的竖直距离看作物理时间，那么 PC2 表示一条时钟刻度线的高度变化小于 \(\epsilon\)。

由于两个不同的时钟永远不会以完全相同的速率运行，它们会趋于相互漂移得越来越远。因此，必须设计一种算法来确保 PC2 始终成立。不过，先考察 \(\kappa\) 和 \(\epsilon\) 必须小到什么程度才能防止异常行为。我们必须确保相关物理事件系统 \(S^*\) 满足强时钟条件。我们假定时钟满足普通时钟条件，因此只需要求当 \(a\) 和 \(b\) 是 \(S\) 中事件且 \(a \to^* b\) 时，强时钟条件成立。所以只需要考虑发生在不同进程中的事件。

令 \(\mu\) 为一个数，满足：如果事件 \(a\) 发生在物理时间 \(t\)，而另一个进程中的事件 \(b\) 满足 \(a \to^* b\)，则 \(b\) 发生在晚于物理时间 \(t + \mu\) 的时刻。换句话说，\(\mu\) 小于进程间消息的最短传输时间。总可以把 \(\mu\) 取为进程之间最短距离除以光速。不过，取决于 \(S^*\) 中消息的传输方式，\(\mu\) 可能显著更大。

为了避免异常行为，必须确保对任意 \(i\)、\(j\) 和 \(t\)：\(C_{i}(t + \mu) - C_{j}(t) > 0\)。将这一点与 PC1 和 PC2 结合起来，可以把 \(\kappa\) 和 \(\epsilon\) 需要多小同 \(\mu\) 的值联系起来。我们假定时钟被重置时，总是向前设置而不是向后设置。（向后设置可能导致 C1 被违反。）于是 PC1 蕴含 \(C_{i}(t + \mu) - C_{i}(t) > (1 - \kappa)\mu\)。利用 PC2 很容易推出，如果以下不等式成立，则 \(C_{i}(t + \mu) - C_{j}(t) > 0\)：

\[ \frac{\epsilon}{1 - \kappa} \le \mu \]

该不等式连同 PC1 和 PC2 蕴含异常行为不可能发生。

现在描述确保 PC2 成立的算法。令 \(m\) 为一条在物理时间 \(t\) 发送并在时间 \(t'\) 接收的消息。定义 \(\nu_m = t' - t\) 为消息 \(m\) 的总延迟。当然，接收 \(m\) 的进程并不知道这个延迟。不过，我们假定接收进程知道某个最小延迟 \(\mu_m \ge 0\)，且 \(\mu_m \le \nu_m\)。称 \(\xi_m = \nu_m - \mu_m\) 为该消息的不可预测延迟（unpredictable delay）。

现在将规则 IR1 和 IR2 特化为适用于物理时钟的规则：

IR1’。 对每个 \(i\)，如果 \(P_{i}\) 在物理时间 \(t\) 没有收到消息，则 \(C_{i}\) 在 \(t\) 处可微，且 \(\frac{dC_i(t)}{dt} > 0\)。

IR2’。 (a) 如果 \(P_{i}\) 在物理时间 \(t\) 发送消息 \(m\)，则 \(m\) 包含时间戳 \(T_{m} = C_{i}(t)\)。(b) 在时间 \(t'\) 收到消息 \(m\) 时，进程 \(P_{j}\) 将 \(C_{j}(t')\) 设置为 \(\max(C_{j}(t' - 0), T_{m} + \mu_m)\)。†

虽然这些规则在形式上用物理时间参数规定，但进程只需要知道自己的时钟读数和所收到消息的时间戳。为了数学上的方便，我们假定每个事件发生在一个精确的物理时间瞬间，且同一进程中的不同事件发生在不同时间。这些规则于是就是规则 IR1 和 IR2 的特化，因此我们的时钟系统满足时钟条件。真实事件具有有限持续时间这一事实不会给实现算法造成困难。实现中唯一真正需要关心的是，必须确保离散时钟刻度足够频繁，从而维持 C1。

现在说明该时钟同步算法可以用来满足条件 PC2。假定进程系统由有向图（directed graph）描述，其中从进程 \(P_{i}\) 到进程 \(P_{j}\) 的一条弧表示一条通信线路，消息可沿这条线路直接从 \(P_{i}\) 发送到 \(P_{j}\)。如果对任意 \(t\)，\(P_{i}\) 在物理时间 \(t\) 到 \(t + \tau\) 之间至少向 \(P_{j}\) 发送一条消息，则称每 \(\tau\) 秒有一条消息沿这条弧发送。有向图的直径（diameter）是最小数 \(d\)，使得对任意一对不同进程 \(P_{j}\)、\(P_{k}\)，都存在一条从 \(P_{j}\) 到 \(P_{k}\)、至多包含 \(d\) 条弧的路径。

除建立 PC2 外，下面的定理还给出了系统初始启动时时钟达到同步可能需要的时间上界。

定理。 假设有一个直径为 \(d\) 的强连通（strongly connected）进程图，它始终遵守规则 IR1’ 和 IR2’。假设对任意消息 \(m\)，有 \(\mu_m \le \mu\)，其中 \(\mu\) 为某个常数，并且对所有 \(t \ge t_{0}\)：(a) PC1 成立。(b) 存在常数 \(\tau\) 和 \(\xi\)，使得每 \(\tau\) 秒都有一条不可预测延迟小于 \(\xi\) 的消息沿每条弧发送。那么，对所有 \(t \ge t_{0} + \tau d\)，PC2 以 \(\epsilon \approx d(2\kappa\tau + \xi)\) 成立，其中这些近似假定 \(\mu + \xi \ll \tau\)。

该定理的证明出人意料地困难，见附录。关于物理时钟同步问题已经有大量工作。我们建议读者参见 \[4\] 对该主题的介绍。文献中描述的方法可用于估计消息延迟 \(\mu_m\)，并用于调整时钟频率 \(\frac{dC_i}{dt}\)（对于允许这种调整的时钟）。然而，时钟永远不能被向后设置这一要求似乎把我们的情形同以前研究过的情形区分开来，我们认为该定理是一个新的结果。

结论

我们已经看到，“发生在……之前”这一概念定义了分布式多处理系统中事件的一种不变偏序。我们描述了一种算法，把该偏序扩展为某种有些任意的全序，并说明这种全序可以怎样用于求解一个简单的同步问题。后续论文会说明如何把这种方法扩展到解决任意同步问题。

算法定义的全序有些任意。如果它不同于系统用户感知到的顺序，就可能产生异常行为。使用正确同步的物理时钟可以防止这种情况。我们的定理给出了时钟可以同步到何种精度。

在分布式系统中，认识到事件发生的顺序只是一种偏序非常重要。我们相信，这一思想有助于理解任何多处理系统。它应当帮助人们独立于用于解决问题的具体机制，理解多处理的基本问题。

附录

定理证明

对任意 \(i\) 和 \(t\)，定义 \(C_{i}^t\) 为这样一个时钟：它在时间 \(t\) 被设置为等于 \(C_{i}\)，随后以与 \(C_{i}\) 相同的速率运行，但永远不被重置。换句话说，

\[ C_i^t(t') = C_i(t) + \int_t^{t'} [dC_i(u)/du]du \tag{1} \]

对所有 \(t' \ge t\) 成立。注意：

\[ C_i(t') \ge C_i^t(t') \quad \text{for all } t' \ge t. \tag{2} \]

假设进程 \(P_{1}\) 在时间 \(t_{1}\) 向进程 \(P_{2}\) 发送一条消息，该消息在时间 \(t_{2}\) 被接收，其不可预测延迟 \(\le \xi\)，其中 \(t_{0} \le t_{1} \le t_{2}\)。那么对所有 \(t \ge t_{2}\) 有：

\[ \begin{aligned} C_2^{t_2}(t) &\ge C_2^{t_2}(t_2) + (1-\kappa)(t-t_2) && \text{[by (1) and PC1]} \\ &\ge C_1(t_1) + \mu_m + (1-\kappa)(t-t_2) && \text{[by IR2' (b)]} \\ &= C_1(t_1) + (1-\kappa)(t-t_1) - [(t_2-t_1)-\mu_m] + \kappa(t_2-t_1) \\ &\ge C_1(t_1) + (1-\kappa)(t-t_1) - \xi. \end{aligned} \]

因此，在这些假设下，对所有 \(t \ge t_{2}\) 有：

\[ C_2^{t_2}(t) \ge C_1(t_1) + (1-\kappa)(t-t_1) - \xi. \tag{3} \]

现在假设对 \(i = 1, ..., n\) 有 \(t_{i} \le t_{i}' < t_{i+1}\)、\(t_{0} \le t_{1}\)，并且在时间 \(t_{i}'\)，进程 \(P_{i}\) 向进程 \(P_{i+1}\) 发送一条消息，该消息在时间 \(t_{i+1}\) 被接收，且不可预测延迟小于 \(\xi\)。那么反复应用不等式 (3)，对 \(t \ge t_{n+1}\) 得到以下结果：

\[ C_{n+1}^{t_{n+1}}(t) \ge C_1(t_1') + (1-\kappa)(t-t_1') - n\xi. \tag{4} \]

由 PC1、IR1’ 和 IR2’ 可推出：

\[ C_1(t_1') \ge C_1(t_1) + (1-\kappa)(t_1'-t_1). \]

将它与 (4) 结合，并使用 (2)，得到

\[ C_{n+1}(t) \ge C_1(t_1) + (1-\kappa)(t-t_1) - n\xi \tag{5} \]

对 \(t \ge t_{n+1}\) 成立。

对任意两个进程 \(P\) 和 \(P'\)，都可以找到一个进程序列 \(P = P_{0}, P_{1}, ..., P_{n+1} = P'\)，其中 \(n \le d\)，并且从每个 \(P_{i}\) 到 \(P_{i+1}\) 都有通信弧。根据假设 (b)，可以找到时间 \(t_{i}\)、\(t_{i}'\)，使得 \(t_{i}' - t_{i} \le \tau\) 且 \(t_{i+1} - t_{i}' \le \nu\)，其中 \(\nu = \mu + \xi\)。因此，当 \(t \ge t_{1} + d(\tau + \nu)\) 时，形如 (5) 的不等式以 \(n \le d\) 成立。于是对任意 \(i\)、\(j\) 以及任意 \(t\)、\(t_{1}\)，若 \(t_{1} \ge t_{0}\) 且 \(t \ge t_{1} + d(\tau + \nu)\)，则有：

\[ C_i(t) \ge C_j(t_1) + (1-\kappa)(t-t_1) - d\xi. \tag{6} \]

现在令 \(m\) 为任意一条带时间戳 \(T_{m}\) 的消息，并假设它在时间 \(t\) 发送、在时间 \(t'\) 接收。设想 \(m\) 有一个时钟 \(C_{m}\)，该时钟以常速运行，使得 \(C_{m}(t) = T_{m}\) 且 \(C_{m}(t') = T_{m} + \mu_m\)。于是 \(\mu_m \le t' - t\) 蕴含 \(\frac{dC_m}{dt} \le 1\)。规则 IR2’ (b) 只是把 \(C_{j}(t')\) 设置为 \(\max(C_{j}(t' - 0), C_{m}(t'))\)。因此，时钟只会通过把它们设置为等于其他时钟来重置。

对任意时间 \(t_{x} \ge t_{0} + \mu/(1 - \kappa)\)，令 \(C_{x}\) 为时间 \(t_{x}\) 处具有最大值的时钟。由于所有时钟的运行速率都小于 \(1 + \kappa\)，对所有 \(i\) 以及所有 \(t \ge t_{x}\)，有：

\[ C_i(t) \le C_x(t_x) + (1+\kappa)(t-t_x). \tag{7} \]

现在考虑以下两种情形：(i) \(C_{x}\) 是进程 \(P_{q}\) 的时钟 \(C_{q}\)。(ii) \(C_{x}\) 是进程 \(P_{q}\) 在时间 \(t_{1}\) 发送的一条消息的时钟 \(C_{m}\)。在情形 (i) 中，(7) 直接变为：

\[ C_i(t) \le C_q(t_x) + (1+\kappa)(t-t_x). \tag{8i} \]

在情形 (ii) 中，由于 \(C_{m}(t_{1}) = C_{q}(t_{1})\) 且 \(\frac{dC_m}{dt} \le 1\)，有：

\[ C_x(t_x) \le C_q(t_1) + (t_x-t_1). \]

因此，(7) 得到：

\[ C_i(t) \le C_q(t_1) + (1+\kappa)(t-t_1). \tag{8ii} \]

由于 \(t_{x} \ge t_{0} + \mu/(1 - \kappa)\)，得到：

\[ \begin{aligned} C_q(t_x-\mu/(1-\kappa)) &\le C_q(t_x)-\mu && \text{[by PC1]}\\ &\le C_m(t_x)-\mu && \text{[by choice of }m\text{]}\\ &\le C_m(t_x)-(t_x-t_1)\mu_m/\nu_m && [\mu_m \le \mu,\ t_x-t_1 \le \nu_m]\\ &= T_m && \text{[by definition of }C_m\text{]}\\ &= C_q(t_1) && \text{[by IR2'(a)]}. \end{aligned} \]

因此，\(C_{q}(t_{x} - \mu/(1 - \kappa)) \le C_{q}(t_{1})\)，所以 \(t_{x} - t_{1} \le \mu/(1 - \kappa)\)，从而 \(t_{1} \ge t_{0}\)。

在情形 (i) 中令 \(t_{1} = t_{x}\)，即可把 (8i) 和 (8ii) 结合起来，推出：对任意 \(t\)、\(t_{x}\)，若 \(t \ge t_{x} \ge t_{0} + \mu/(1 - \kappa)\)，则存在一个进程 \(P_{q}\) 和一个时间 \(t_{1}\)，使得 \(t_{x} - \mu/(1 - \kappa) \le t_{1} \le t_{x}\)，并且对所有 \(i\)：

\[ C_i(t) \le C_q(t_1) + (1+\kappa)(t-t_1). \tag{9} \]

选取满足 \(t \ge t_{x} + d(\tau + \nu)\) 的 \(t\) 和 \(t_{x}\)，可以将 (6) 和 (9) 结合，得出存在某个 \(t_{1}\) 和某个进程 \(P_{q}\)，使得对所有 \(i\)：

\[ C_q(t_1) + (1-\kappa)(t-t_1) - d\xi \le C_i(t) \le C_q(t_1) + (1+\kappa)(t-t_1). \tag{10} \]

令 \(t = t_{x} + d(\tau + \nu)\)，得到

\[ d(\tau+\nu) \le t-t_1 \le d(\tau+\nu) + \mu/(1-\kappa). \]

将它与 (10) 结合，得到

\[ \begin{aligned} C_q(t_1) + (t-t_1) - \kappa d(\tau+\nu) - d\xi &\le C_i(t) \\ &\le C_q(t_1) + (t-t_1) + \kappa[d(\tau+\nu)+\mu/(1-\kappa)]. \end{aligned} \tag{11} \]

利用假设 \(\kappa \ll 1\) 且 \(\mu \le \nu \ll \tau\)，可以把 (11) 改写为以下近似不等式：

\[ C_q(t_1) + (t-t_1) - d(\kappa\tau+\xi) \lesssim C_i(t) \lesssim C_q(t_1) + (t-t_1) + d\kappa\tau. \tag{12} \]

由于它对所有 \(i\) 成立，得到：

\[ |C_i(t) - C_j(t)| \lesssim d(2\kappa\tau+\xi), \]

并且它对所有 \(t \ge t_{0} + d\tau\) 成立。

注意，如果假设 \(\mu + \xi \ll \tau\) 不成立，证明中的关系 (11) 给出了 \(|C_{i}(t) - C_{j}(t)|\) 的精确上界。考察这个证明会提示一种快速初始化时钟的方法，或者在时钟由于任何原因脱离同步时重新同步（resynchronize）的方法。每个进程发送一条消息，该消息被转发给其他每个进程。这个过程可以由任何进程发起；假设每条消息的不可预测延迟小于 \(\xi\)，那么同步完成所需时间少于 \(2d(\mu + \xi)\) 秒。

致谢

使用时间戳给操作排序，以及异常行为这一概念，归功于 Paul Johnson 和 Robert Thomas。

Received March 1976; revised October 1977

References

1. Schwartz, J.T. Relativity in Illustrations. New York U. Press, New York, 1962.
2. Taylor, E.F., and Wheeler, J.A. Space-Time Physics, W.H. Freeman, San Francisco, 1966.
3. Lamport, L. The implementation of reliable distributed multiprocess systems. To appear in Computer Networks.
4. Ellingson, C., and Kulpinski, R.J. Dissemination of system-time. IEEE Trans. Comm. Com-23, 5 (May 1973), 605-624.

† 构成事件的内容会影响进程中事件的排序。例如，接收一条消息可以表示计算机中某个中断位被置位，也可以表示处理该中断的子程序被执行。由于中断不一定按其发生顺序被处理，这种选择会影响一个进程中消息接收事件的顺序。

† 注意，消息可能不按发送顺序被接收。我们允许发送多条消息构成一个单个事件，但为方便起见，假定接收单条消息不会与发送或接收任何其他消息同时发生。

† 排序 \(<\) 在进程之间建立优先级。如果希望采用“更公平”的方法，可以令 \(<\) 成为时钟值的函数。例如，如果 \(C_{i}(a) = C_{j}(b)\) 且 \(j < i\)，则当 \(j < C_{i}(a) \bmod N \le i\) 时令 \(a \Rightarrow b\)，否则令 \(b \Rightarrow a\)；其中 \(N\) 是进程总数。

† “最终”一词应当被精确定义，但那会使我们偏离主题太久。

† 如果 \(P_{j}\) 已经向 \(P_{i}\) 发送过一条时间戳晚于 \(T_{m}\) 的消息，则无需发送这条确认消息。

† 如果 \(P_{j} < P_{i}\)，则 \(P_{i}\) 只需已经从 \(P_{j}\) 收到一条时间戳 \(\ge T_{m}\) 的消息。

† 如果每个进程并不严格交替执行请求命令和释放命令，那么执行一个释放命令可能会从队列中删除零个、一个或多个请求。

† 我们将假定牛顿时空。如果时钟的相对运动或引力效应不可忽略，那么必须通过从固有时间变换到任意选定的时间坐标，从实际时钟读数推导出 \(C_{i}(t)\)。

† \(C_{j}(t' - 0) = \lim_{\delta \to 0} C_{j}(t' - |\delta|)\)。