分布式系统中的时间，时钟，以及事件顺序

原文：Time, Clocks, and the Ordering of Events in a Distributed System
作者：Leslie Lamport
发表日期：1978 年 07 月
译者：ou@https://ouonline.net/

摘要

本文研究了“分布式系统中一个事件在另一个事件之前发生”这个概念，并用它来定义事件的偏序关系。给出了用于同步逻辑时钟系统的分布式算法，该算法可以用来确定事件的全序关系。用解决同步问题的方法来说明全序的使用。这个算法被专门用来同步物理时钟，并得出时钟同步的最大偏离范围。

引言

时间的概念是我们思维的基础。它源自一个更基础的概念，即事件发生的顺序。如果某事发生在我们的时钟读数为 3:15 之后并且在其读数变为 3:16 之前，我们就说 3:15 发生了某事。事件的时间顺序概念充斥着我们对系统的思考。例如，在航空公司的预定系统中，我们指定如果在航班满员之前提出预定请求，那么应该允许该请求。然而，我们会看到，在考虑分布式系统中的事件时，必须仔细重新检查这个概念。

一个分布式系统由空间上分离的不同进程的集合组成，这些进程通过交换消息来互相通信。一个互相连接的计算机的网络，例如 ARPA，就是一个分布式系统。单个计算机也可以被看作是一个分布式系统，其中的中央控制单元，存储单元和输入输出通道都是独立的进程。如果消息传输延迟与单个进程中事件发生的间隔相比不能忽略，则这个系统就是分布式的。

我们将主要关注空间上分离的计算机系统。但是，我们的许多结论将会更通用。特别地，单台计算机上的多进程系统会遇到与分布式系统类似的问题，因为某些事件的发生顺序不可预测。

在分布式系统中，有时候无法决定两个事件中的哪一个先发生。因此，“先发生”关系只是系统中事件的偏序关系。我们发现这个问题经常出现，是因为人们没有完全意识到这个事实以及它的含义。

在本文中，我们讨论了由“先发生”关系定义的偏序，并给出了一种分布式算法，用于将偏序扩展为所有事件的一致全序。这个算法可以为实现分布式系统提供有用的机制。我们通过一个解决同步问题的简单方法来说明它的用法。如果由这个算法得到的顺序和用户感知的顺序不同，则可能会发生意外的异常行为。通过引入真实的物理时钟可以避免这种情况。我们介绍了一种用来同步这些时钟的简单的方法，并推导出它们漂移的不同步程度的上限。

偏序

如果事件 a 发生的时间早于事件 b，大部分人可能会说 a 在 b 之前发生。他们可能会根据时间物理理论证明这个定义是正确的。然而，如果系统要正确符合规范，则必须基于系统内可观察到的事件来给出该规范。如果规范是基于物理时间的，则系统必须包含真实的时钟。即使它确实包含真实的时钟，也会存在这样的问题，即这些时钟不够准确，并且不能保持精确的物理时间。因此，我们将在不使用物理时钟的情况下定义“先发生”的关系。

我们从更精确地定义我们的系统开始。假设系统由进程的集合组成。每个进程包含一系列事件。对不同的应用程序而言，在计算机上执行一个子程序或者执行单个机器指令，都有可能是一个事件。我们假设进程中的事件形成一个序列，如果 a 在 b 之前发生，则在序列中 a 出现在 b 之前。换句话说，单个进程被定义为先验全序的事件集合。这看起来就是“进程”的一般含义 ¹。很容易扩展我们的定义以允许将进程拆分成不同的子进程，但是我们不会这样做。

我们假设发送和接收消息是进程内的事件。然后我们就可以定义“先发生”的关系，用符号“$\rightarrow$”表示，像下面这样：

• 定义：系统中事件集合上的“$\rightarrow$”关系是指满足以下三个条件的最小关系：（1）如果 a 和 b 是同一进程中的事件，并且 a 在 b 之前，那么 a $\rightarrow$ b；（2）如果 a 表示“某个进程发送消息”，b 表示“另一个进程收到同一消息”，那么 a $\rightarrow$ b；（3）如果 a $\rightarrow$ b 并且 b $\rightarrow$ c，那么 a $\rightarrow$ c。如果两个不同的事件 a 和 b，其中 a $\nrightarrow$ b 并且 b $\nrightarrow$ a，那么 a 和 b 被称为“并行”。

我们假设对于任意事件 a，a $\nrightarrow$ a。（某个事件在自身发生之前发生的系统似乎没有物理意义。）这表明“$\rightarrow$”是一个在系统所有事件集合上的不自反偏序。

像图 1 这样的“时空图”的形式对理解这个定义很有帮助。水平方向表示空间，垂直方向表示时间——晚一点的时间比早一点的时间高。点表示事件，垂线表示进程，波浪线表示消息 ²。容易看到 a $\rightarrow$ b 表示，在时间中沿着进程和消息的线移动，可以从图中的 a 到达 b。例如，在图 1 中，我们有 p1 $\rightarrow$ r4。

（图 1 见原文）

另一个理解这个定义的方法是：a $\rightarrow$ b 表示可能是事件 a 导致了事件 b 的发生。如果两个事件互相之间没有因果关系，那么它们是并行的。例如，图 1 中的 p3 和 q3 是并行的。尽管图示中 q3 发生的时刻在物理时间上比 p3 早，进程 P 直到在 p4 收到消息才知道进程 Q 在 q3 做了什么。（在事件 p4 之前，P 最多知道 Q 在 q3 打算做什么。）

对于熟悉狭义相对论的不变时空公式的读者来说，这个定义显得很自然，就像 [1] 或者 [2] 中的第一章描述的那样。在相对论中，事件的顺序是由可被发送的消息来定义的。然而，我们采用了更实用的方法，即只考虑实际被发送的消息。通过只了解那些实际上发生了的事件，即使不知道可能已经发生了的事件，我们也能够判断系统是否正确运行。

逻辑时钟

现在我们将时钟引入到系统中。我们从一个抽象的观点开始，即时钟只是给事件分配编号的一种方式，这些编号被认为是事件发生的时间。更精确地说，我们为每个进程 $P_i$ 定义一个时钟 $C_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。我们将这个条件更正式地表述如下：

• 时钟条件：对任意事件 a 和 b，如果 a $\rightarrow$ b，那么 $C(a)$ < $C(b)$。

注意，我们不能认为这个条件反过来也成立，因为这意味着任意两个并行的事情必须同时发生。在图 1 中，p2，p3 都和 q3 并行，因此这意味着它们必须和 q3 同时发生，这与时钟条件冲突，因为 p2 $\rightarrow$ p3。

从我们对“$\rightarrow$”关系的定义很容易可以看出，如果以下两个条件成立，则满足时钟条件。

• 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)$。

让我们从时空图的角度来考虑时钟。我们设想进程的时钟“嘀嗒”经过每个编号，“嘀嗒”发生在进程的事件之间。例如，如果 a 和 b 是进程 Pi 中的连续事件，其中 $C_i(a)$ = 4，$C_i(b)$ = 7，那么时钟“嘀嗒” 5，6 和 7 发生在这两个事件之间。我们画一条“刻度线”（用虚线表示）经过不同进程的所有相同编号的“嘀嗒”点。图 1 的时空图可能会生成图 2。条件 C1 表示进程线上的任意两个事件之间一定会有一条刻度线，条件 C2 表示每条消息线一定会穿过一条刻度线。从“$\rightarrow$”的图形定义中很容易看出为什么这两个条件可以推导出时钟条件。

（图 2 见原文）

我们可以将刻度线看作是时空上某些笛卡尔坐标系中的时间坐标线。我们可以重新绘制图 2 来拉直这些坐标线，从而得到图 3。图 3 是展示与图 2 相同的事件系统的有效替代方法。不向系统引入物理时间的概念（这需要引入物理时钟），就无法确定哪个图是更好的展示方法。

（图 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 包含一个时间戳 $T_m$，其中 $T_m$ 是 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) 中，在设置了 $C_j$ 之后，我们认为“收到消息 m”这个事件就发生了。（这只是表达上的啰嗦，与任何实际的实现无关。）很明显，IR2 保证满足条件 C2。因此，简单的实现规则 IR1 和 IR2 意味着满足时钟条件，因此它们保证了逻辑时钟系统的正确性。

事件的全序

我们用满足时钟条件的时钟系统来对所有系统事件集合进行全排序。我们仅按事件发生的时间来排序。为了打破平衡，我们使用所有进程的一个任意全序关系 $\prec$。更精确地说，我们定义关系 $\Rightarrow$ 如下：如果 a 是进程 $P_i$ 中的事件，b 是进程 $P_j$ 中的事件，当且仅当（i）$C_i(a)$ < $C_j(b)$，或者（ii）$C_i(a)$ = $C_j(b)$ 并且 $P_i \prec P_j$ 时，有 a $\Rightarrow$ b 。很容易看出这定义了一个全序，并且由时钟条件可以得到：如果 a $\rightarrow$ b 那么 a $\Rightarrow$ b。换句话说，关系 $\Rightarrow$ 是将“先发生”这种偏序关系变为全序关系的一种方法。³

$\Rightarrow$ 的顺序取决于时钟系统 $C_i$，并且不是唯一的。选择不同的满足时钟条件的时钟会产生不同的关系 $\Rightarrow$。给出一个任意的扩展 $\rightarrow$ 的全序关系 $\Rightarrow$，存在一个可以产生这个关系的满足时钟条件的时钟系统。事件系统中唯一确定的只是偏序关系。

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

我们假设初始状态的资源只被授予给一个进程。这些是非常自然的要求。它们精确地指出了正确解决方案的含义。观察条件如何影响事件的顺序。条件 II 没有说明两个并行发起的请求中的哪一个应该被授予资源。

意识到这是一个不简单的问题很重要。除非有额外的假设，否则使用中央调度进程按接收到请求的顺序授予资源这个方法行不通。为了证明这点，我们令 $P_0$ 作为调度进程。假设 $P_1$ 向 $P_0$ 发起请求，然后向 $P_2$ 发一条消息。$P_2$ 收到 $P_1$ 的消息后向 $P_0$ 发起请求。$P_2$ 的请求有可能在 $P_1$ 的请求之前到达 $P_0$。如果先批准了 $P_2$ 的请求则违反了条件 II。

为了解决这个问题，我们使用规则 IR1 和 IR2 实现时钟系统，并用它们来定义所有事件的全序关系 $\Rightarrow$。这提供了所有请求和释放操作的一个全序关系。有了这个全序，找到解决方案变得很直截了当。这只需要保证每个进程都了解其它所有进程的操作。

为了简化问题，我们做一些假设。它们不是必需的，引入它们是为了避免分散实现细节。首先，我们假设对任意两个进程 $P_i$ 和 $P_j$，从 $P_i$ 发送到 $P_j$ 的消息的接收顺序与它们被发出的顺序相同。此外，我们假设每条消息最终都会被接收到。（可以通过引入消息编号和消息确认协议来避免这些假设。）我们还假设一个进程可以向其它每个进程直接发送消息。

每个进程都维护各自的请求队列，其它任何进程都不会看到这个队列。我们假设请求队列最初包含单个请求资源的消息 $T_0$:$P_0$，其中 $P_0$ 表示最初被授予资源的进程，$T_0$ 是小于任何时钟的初始值。

然后，算法由以下 5 条规则定义。为了方便，假设每条规则定义的行为都构成一个事件。

1. 为了请求资源，进程 Pi 向其它所有进程发送请求资源的消息 $T_m$:$P_i$，并将该消息放入自己的请求队列，其中 $T_m$ 是消息的时间戳；
2. 当进程 $P_j$ 收到请求资源的消息 $T_m$:$P_i$，它将消息放入自己的请求队列，并发送（带有时间戳的）确认消息给 $P_i$；⁵
3. 为了释放资源，进程 Pi 从它的请求队列中删除所有请求资源的消息 $T_m$:$P_i$，并且发送一条（带有时间戳的）释放资源的消息 $P_i$ 给其它所有进程；
4. 当进程 $P_j$ 收到释放资源的消息 $P_i$ 时，它从它的请求队列中删除所有请求资源的消息 $T_m$:$P_i$；
5. 当以下两个条件被满足时，进程 $P_i$ 将被授予资源：（i）在它的请求队列中有一条请求资源的消息 $T_m$:$P_i$，如果按照关系 $\Rightarrow$ 排序，该消息排在队列中的其它任何请求之前；（为了定义消息的 $\Rightarrow$ 关系，我们用发送消息的事件来标识它。）（ii）$P_i$ 收到来自其它所有进程的时间戳晚于 $T_m$ 的消息。⁶

注意规则 5 中的条件（i）和（ii）由 $P_i$ 在本地判断。

很容易验证由这些规则定义的算法是否满足条件 I-III。首先，观察到规则 5 中的条件（ii）和“消息按顺序接收”这个假设，确保了 $P_i$ 已经了解了在它当前请求之前的所有请求。由于规则 3 和 4 是仅有的从请求队列中删除消息的规则，因此很容易看到条件 I 成立。条件 II 源自全序关系 $\Rightarrow$ 扩展了偏序关系 $\rightarrow$ 这个事实。规则 2 确保了在 $P_i$ 请求了资源之后，规则 5 中的条件（ii）最终成立。规则 3 和 4 表明，如果每个被授予资源的进程最终会释放它，那么规则 5 中的条件（i）最终将成立，从而证明条件 III。

这是一种分布式算法。每个进程独立遵循这些规则，并且没有中央调度进程或者中央存储。这种方法可以被推广来实现这种分布式多进程系统所需的任何同步。同步是由状态机指定的，该状态机由一个可能的命令集合 $C$，一个可能的状态集合 $S$，以及一个函数 $e$：$C \times S \rightarrow S$。关系 $e(C,S)=S'$ 表示在状态为 $S$ 的机器上执行命令 $C$ 会导致机器状态变为 $S'$。在我们的例子中，集合 $C$ 包括 $P_i$ 中请求资源和释放资源的所有命令，状态包括等待请求命令的队列组成，其中队列头的请求是当前已被授权的请求。执行请求命令会把请求添加到队列的尾部，执行释放命令会从队列中删除命令。⁷

每个进程使用所有进程发出的命令来独立地模拟状态机的执行。由于所有进程都根据命令的时间戳对命令排序（使用关系 $\Rightarrow$），因此每个进程都是用同样的命令序列，从而实现同步。当一个进程已经知道所有其它进程发出的时间戳小于或等于 T 的命令时，它就可以执行时间戳为 T 的命令。精确的算法很直截了当，我们不再介绍它。

这种方法允许在分布式系统中实现任何所需的形式的多进程同步。然而，最终的算法要求所有进程的积极参与。一个进程必须知道其它进程发出的所有命令，这样单个进程的出错会使其它任何进程无法执行状态机命令，从而使系统停止运行。

出错问题是一个难题，任何详细的讨论都超出了本文的范围。我们将观察到，出错的整个概念只在物理事件的背景下才有意义。没有物理时间，就无法区分出错的进程和仅在事件之间暂停的进程。用户判断系统“崩溃”只是因为他等待响应的时间太长。[3] 中描述了一个方法，在单个进程或者通信线路出错的情况下仍然可以工作。

异常行为

我们的资源调度算法使用全序关系 $\Rightarrow$ 对请求进行排序。这允许以下类型的“异常行为”。考虑一个全国范围内的互相连接的计算机系统。假设某人在计算机 A 上发起请求 A，然后打电话给另一个程是的朋友，让他在另一台不同的计算机 B 上发起请求 B。请求 B 可能会得到一个较低的时间戳并且排在请求 A 之前。会发生这种情况，是因为系统无法知道 A 实际上早于 B，因为该优先级信息基于系统外部的消息。

让我们更仔细地研究问题的根源。令 $\mathcal{S}$ 表示所有系统事件的集合。让我们引进一组事件 $\underline{\mathcal{S}}$，其中包含 $\mathcal{S}$ 中的事件以及所有其它相关的外部事件，例如我们的例子中的打电话。令 -> 表示 $\underline{\mathcal{S}}$ 中的“先发生”关系。在我们的例子中，我们有 A -> B，但是 A $\nrightarrow$ B。很明显，没有算法可以只基于 $\mathcal{S}$ 中的事件，但是不会以任何方式将这些事件与集合 $\underline{\mathcal{S}}$ 中的其它事件关联起来，就能保证请求 A 排在请求 B 之前。

有两种方法可以避免这样的异常行为。第一种方法是把与 -> 顺序有关的必要信息明确引入系统。在我们的例子中，发出请求 A 的人可以从系统接收该请求的时间戳 $T_A$。在发出请求 B 时，他的朋友可以指定 B 的时间戳晚于 $T_A$。这把避免异常行为的责任交给了用户。

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

• 强时钟条件：对于 $\mathcal{S}$ 中的任意事件 a 和 b，如果 a -> b 那么 $C(a)$ < $C(b)$。

这比普通的时钟条件强，因为 -> 是一个比 $\rightarrow$ 更强的关系。我们的逻辑时钟通常不能满足要求。

让我们用物理时空中的“真实”事件集合来定义 $\underline{\mathcal{S}}$，并且令 -> 表示由狭义相对论定义的事件的偏序关系。宇宙其中一个神秘之处是存在这样的可能：构造一个物理时钟系统，该系统彼此完全独立地运行，也能够满足强时钟系统。因此我们可以使用物理时钟来消除异常行为。我们现在将注意力转向这类时钟。

物理时钟

让我们在时空图中引入引入物理时间坐标，并且令 $C_i(t)$ 表示在物理时间 t 处时钟 $C_i$ 的读数。⁸ 为了数学上的方便，我们假设时钟连续运行，而不是离散地“嘀嗒”。（离散的时钟可以被认为是连续的时钟，其中读取时钟的误差可以达到 1/2 “嘀嗒”。）更精确地说，我们假设 $C_i(t)$ 是对 t 的连续可微函数，除了在时钟重置时的孤立不连续的跳变点。那么 $dC_i(t)/dt$ 表示时钟在时间 t 的运行速率。

为了使时钟 $C_i$ 成为真正的物理时钟，它必须以接近正确的速率运行。也就是说，对于所有的 t，我们必须有 $dC_i(t)/dt \approx 1$。更精确地说，我们假设满足以下条件：

• PC1. 存在一个常数 $\kappa \ll 1$，使得对于所有的 i，有 $|dC_i(t)/dt - 1|< \kappa$。

对于典型的石英钟，$\kappa \leq 10^{-6}$。

时钟独立地以接近正确的速率运行还不够。它们必须同步，以便对于所有的 i，j 和 t，都有 $C_i(t) \approx C_j(t)$。更精确地说，一定存在一个足够小的常数 $\epsilon$ 使得以下条件成立：

• PC2. 对于所有的 i 和 j，有 $|C_i(t) - C_j(t)| < \epsilon$。

如果我们认为图 2 中的垂直距离表示物理时间，那么 PC2 说明单个刻度线的高度变化小于 $\epsilon$。

由于两个不同的时钟永远不会以完全相同的速率运行，它们往往会漂移得越来越远。我们必须设计一种算法来确保 PC2 一直成立。但是，首先让我们检查 $\kappa$ 和 $\epsilon$ 必须要多小才能防止异常行为。我们必须确保相关物理事件的系统 $\underline{\mathcal{S}}$ 满足强时钟条件。我们假设我们的时钟满足普通的时钟条件，因此我们只需要在 a 和 b 都是 $\underline{\mathcal{S}}$ 中的事件且 a $\nrightarrow$ b 时满足强时钟条件。因此，我们只考虑在不同进程中发生的事件。

令 $\mu$ 表示一个整数，使得如果事件 a 在物理时间 t 发生，并且另一个进程中的事件 b 满足 a $\rightarrow$ b，那么 b 发生在物理时间 $t+\mu$ 之后。换句话说，$\mu$ 小于进程间消息的最短传输时间。我们可以总是令 $\mu$ 等于进程间的最短距离除以光速。然而，取决于 $\underline{\mathcal{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$。如果不等式 $\epsilon/(1-\kappa) \leq \mu$ 成立，那么使用 PC2 很容易推导出 $C_i(t+\mu) - C_j(t) > 0$。这个不等式和 PC1 以及 PC2 结合起来意味着异常行为不可能发生。

现在我们介绍了确保 PC2 成立的算法。令 m 表示在物理时间 t 发送并在时间 t' 接收到的消息。我们定义 $\nu_m$ = t' - t 表示消息 m 的总延迟。当然，这个延迟对于接收到 m 的进程是未知的。然而，我们假设接收进程知道某个最小延迟 $\mu_m \geq 0$，使得 $\mu_m \leq \nu_m$。我们把 $\xi_m = \nu_m - \mu_m$ 称为消息的不可预测的延迟。

现在我们针对物理时钟特化规则 IR1 和 IR2 如下：

• IR1'. 对于每个 i，如果 $P_i$ 在物理时间没有收到消息，那么 $C_i$ 在 t 可微，并且 $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')$ 设为 $C_j(t'-0)$ 和 $T_m+\mu_m$ 两者之间的最大值。⁹

尽管规则使根据物理时间参数正式指定的，但是进程只需要知道它自己的时钟读数以及收到的消息的时间戳。为了数学上的方便，我们假设每个事件都在物理时间的精确时刻发生，这样相同进程中的不同事件在不同的时间发生。这些规则就是规则 IR1 和 IR2 的特化，因此我们的时钟系统满足时钟条件。真实事件具有有限的持续时间这个事实不会给算法的实现带来任何困难。在实现过程中，唯一真正关心的是确保离散的时钟“嘀嗒”足够频繁，以便保证满足 C1。

现在我们证明时钟同步算法可以用来满足条件 PC2。我们假设进程系统由有向图来描述。在有向图中，从进程 $P_i$ 到 $P_j$ 的一条弧线表示一条通信线路，$P_i$ 可以通过该线路直接向 $P_j$ 发送消息。如果对于任意 t，在物理时间 t 和 $t + \tau$ 之间 $P_i$ 至少向 $P_j$ 发送一条消息，我们说在这条弧线上每 $\tau$ 秒发送一条消息。对于任何一对不同的进程 $P_i$ 和 $P_k$，如果存在一条从 $P_j$ 到 $P_k$ 的路径，路径上最多有 d 条弧，那么有向图的直径就是最小的 d 值。

除了确立 PC2 外，下面的定理还限制了系统首次启动时同步时钟所需的时长。

• 定理：假设直径为 d 的进程的强连通图始终遵守规则 IR1' 和 IR2'。假设对任意消息 m，对某个常数 $\mu$，其中 $\mu_m \leq \mu$，那么对于所有 $t \geq t_0$：（a）PC1 成立。（b）存在常数 $\tau$ 和 $\xi$，使得每 $\tau$ 秒中，每条弧上都会发送一条消息，该消息的不可预测的延迟小于 $\xi$。那么对于所有的 $t \geq t_0 + \tau d$，当 $\epsilon \approx d(2\kappa\tau + \xi)$ 时满足 PC2，其中的近似值假设满足 $\mu + \xi \ll \tau$。

该定理的证明非常困难，已在附录中给出。关于同步物理时钟的问题已经做了很多工作。我们向读者推荐 [4] 来获得关于这个主题的介绍。对于估算消息延迟 $\mu_m$ 和调整时钟频率 $dC_i/dt$（对于允许这种调整的时钟），文献中描述的方法很有帮助。然而，时钟永远不能倒退的要求似乎和我们之前研究的情况有所不同，我们相信这个定理是一个新的成果。

总结

我们已经看到“先发生”这个概念定义了分布式多进程系统中事件的不变偏序关系。我们描述了一种用来将偏序扩展为有些随意的全序的算法，并展示了怎样使用全序来解决简单的同步问题。未来的论文将展示如果扩展这种方法来解决任意的同步问题。

该算法定义的全序有些随意。如果它与系统用户所感知的顺序不一致，则可能会产生异常行为。这可以通过正确使用同步的物理时钟来避免。我们的定义表明了时钟可以同步的误差程度。

在分布式系统中，重要的是意识到事件发生的顺序只是偏序关系。我们认为这种想法对理解任何多进程系统很有帮助。它可以帮助人们独立地理解多进程的基本问题以及用来解决它们的机制。

附录

见原文。

参考文献

[1] Schwartz, J.T. Relativity in lllustrations. 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. 1EEE Trans. Comm. Com-23, 5 (May 1973), 605-624.

脚注