原论文信息

Time, Clocks and the Ordering of Events in a Distributed System

Author: Leslie Lamport

以下为翻译及笔者注释


本文研究了分布式系统中一个事件在另一事件之前发生的概念，并表明这定义了事件的一个偏序。 文中给出了一种用于同步逻辑时钟系统(Synchronizing a system of logical clocks)的分布式算法，该算法可用于对事件进行排全序。 通过一种解决同步问题的方法展示了全序的用途。该算法随后被特化用于同步物理时钟，并导出了时钟可能不同步的最大界限。 关键词和短语： 分布式系统，计算机网络，时钟同步，多处理系统

引言

时间概念是我们思维方式的基础。它源自于事件发生顺序这一更基本的概念。如果某事件在我们的时钟读数为 3:15 之后、3:16 之前发生，我们就说它发生在 3:15。事件的时间排序概念渗透在我们对系统的思考中。例如，在航空订票系统中，我们规定如果在航班满员之前提出预订请求，则应予以批准。然而，我们将看到，在考虑分布式系统中的事件时，必须仔细重新审视这一概念。

分布式系统由一组空间上分离的、通过交换消息进行通信的不同进程组成。一个互连的计算机网络，如 ARPA 网，就是一个分布式系统。单个计算机也可以被视为一个分布式系统，其中中央控制单元、存储单元和输入输出通道是独立的进程。如果消息传输延迟与单个进程中事件之间的时间相比不可忽略，那么该系统就是分布式的。 我们将主要关注空间分离的计算机系统。然而，我们的许多论述将具有更广泛的适用性。特别地，单个计算机上的多处理系统会涉及与分布式系统类似的问题，因为某些事件可能以不可预测的顺序发生。 在分布式系统中，有时不可能确定两个事件中哪一个先发生。因此，”发生在…之前” 关系只是系统中事件的一个偏序。我们发现，问题常常源于人们没有充分意识到这一事实及其影响。 在本文中，我们讨论了由”发生在…之前”关系定义的偏序，并给出了一种分布式算法，用于将其扩展为所有事件的一致全序。该算法可以为实现分布式系统提供一种有用的机制。我们通过一种解决同步问题的简单方法来说明其用途。如果该算法获得的排序与用户感知的排序不同，则可能出现非预期的、不协调的行为。这可以通过引入真实的物理时钟来避免。我们描述了一种同步这些时钟的简单方法，并导出了它们可能漂移不同步的上界。

偏序

大多数人可能会说，如果一个事件 a 发生在比事件 b 更早的时间，则事件 a 发生在事件 b 之前。他们可能会根据物理时间理论来证明这一定义是合理的。然而，如果一个系统要正确满足规格（specification），那么该规格必须根据系统内可观察到的事件来给出。如果规范是基于物理时间的，那么系统必须包含真实的时钟。即使它确实包含真实时钟，仍然存在这样的问题：这些时钟并非完全准确，并且不能保持精确的物理时间。因此，我们将不使用物理时钟来定义”发生在…之前”关系。

系统内的关系定义（例如a发生在b之前）只能依赖系统内部的表达能力。可类比形式系统。

我们首先更精确地定义我们的系统。我们假设系统由一组进程组成。每个进程由一系列事件组成。根据应用的不同，计算机上子程序的执行可能是一个事件，或者单条机器指令的执行可能是一个事件。我们假设一个进程的事件形成一个序列，其中如果 a 发生早于 b，则 a 在此序列中位于 b 之前。换句话说，单个进程被定义为一个具有先验全序的事件集合。这似乎通常就是进程的含义。¹ 将我们的定义扩展到允许一个进程分裂成不同的子进程是微不足道的，但我们不打算这样做。 我们假设发送或接收消息是进程中的一个事件。然后我们可以如下定义”发生在…之前”关系，用”→”表示。 定义 在系统事件集合上的关系 “→” 是满足以下三个条件的最小关系：(1) 如果 a 和 b 是同一进程中的事件，并且 a 在 b 之前，则 a → b。(2) 如果 a 是一个进程发送消息，而 b 是另一个进程接收同一消息，则 a → b。(3) 如果 a → b 且 b → c，则 a → c。如果 a !→ b 且 b !→ a，则称两个不同的事件 a 和 b 是并发的。 我们假设对于任何事件 a，a → a 不成立。（事件发生在自身之前似乎没有物理意义。）这意味着 → 是系统所有事件集合上的一个非自反偏序。

用”时空图”（如图 1）来理解这个定义是有帮助的。水平方向表示空间，垂直方向表示时间——较晚的时间比较早的时间更高。点表示事件，垂直线表示进程，波浪线表示消息。很容易看出，a → b 意味着可以从 a 出发，在图中沿着进程线和消息线向前移动到达 b。例如，在图 1 中我们有 p₁ → r₄。 看待这个定义的另一种方式是：a → b 意味着事件 a 有可能因果地影响事件 b。如果两个事件都不能因果地影响对方，则它们是并发的。例如，图 1 中的事件 p₃ 和 q₃ 是并发的。尽管我们绘制此图暗示了 q₃ 发生在比 p₃ 更早的物理时间，但进程 P 直到在 p₄ 处收到消息后才知道进程 Q 在 q₃ 处做了什么。（在事件 p₄ 之前，P 最多只能知道 Q 计划在 q₃ 做什么。） 对于熟悉狭义相对论中不变时空表述（例如在 [1] 或 [2] 的第一章中描述）的读者来说，这个定义会显得非常自然。在相对论中，事件的排序是根据可能发送的消息定义的。然而，我们采取了更务实的方法，只考虑实际发送的消息。我们应该能够仅通过知道那些确实发生的事件来确定系统是否正确运行，而无需知道哪些事件可能发生。

Fig 1 Fig 2
Fig 3  

逻辑时钟

现在我们向系统中引入时钟。我们从一个抽象的观点开始，其中时钟只是一种为事件分配数字的方式，该数字被认为是事件发生的时间。更精确地说，我们为每个进程 $P_i$ 定义一个时钟 $C_i$，它是一个函数，为该进程中的任何事件 a 分配一个数字 $C_i(a)$。整个系统的时钟由函数 C 表示，它为任何事件 b 分配数字 C(b)，其中如果 b 是进程 Pj 中的事件，则 C(b) = Cj(b)。目前，我们不假设数字 Ci(a) 与物理时间有任何关系，因此我们可以将时钟 Ci 视为逻辑时钟而非物理时钟。它们可以由没有实际计时机制的计数器来实现。

我们现在考虑使这样一个时钟系统正确意味着什么。我们不能基于物理时间来定义正确性，因为那将需要引入保持物理时间的时钟。我们的定义必须基于事件发生的顺序。最合理的强条件是：如果一个事件 a 发生在另一个事件 b 之前，那么 a 应该比 b 在更早的时间发生。我们将此条件更形式化地陈述如下。

时钟条件 对于任何事件 a, b： if $a → b$ then $C(a) < C(b)$

满足时钟条件的时钟是正确的时钟，即满足偏序 →。注意C、C_i 等，这里只是说整个系统的事件/某进程的事件都会分配一个对应的时间，但没有规定具体的如何分配。（下面IR1、IR2是具体的分配算法）。

注意，我们不能期望逆条件也成立，因为那将意味着任何两个并发事件必须发生在同一时间。在图 1 中，p₂ 和 p₃ 都与 q₃ 并发，所以这意味着它们都必须与 q₃ 发生在同一时间，这将与时钟条件矛盾，因为 p₂ → p₃。

从我们对关系 “→” 的定义很容易看出，如果满足以下两个条件，则时钟条件得到满足。

C1. 如果 a 和 b 是进程 Pi 中的事件，且 a 在 b 之前，则 $Ci(a) < Ci(b)$。

C2. 如果 a 是进程 Pi 发送消息，而 b 是进程 Pj 接收该消息，则 $Ci(a) < Cj(b)$。

让我们根据时空图来考虑时钟。我们想象一个进程的时钟通过每一个数字”滴答”前进，滴答发生在进程的事件之间。例如，如果 a 和 b 是进程 Pi 中的连续事件，且 Ci(a) = 4 和 Ci(b) = 7，那么时钟滴答 5, 6 和 7 发生在两个事件之间。我们通过所有不同进程的相同编号的滴答画一条虚线”滴答线”。图 1 的时空图可能产生图 2 的图片。条件 C1 意味着在进程线上任何两个事件之间必须有一条滴答线，条件 C2 意味着每条消息线必须穿过一条滴答线。从 → 的图像意义来看，很容易看出为什么这两个条件蕴含时钟条件。

我们可以将滴答线视为时空上某个笛卡尔坐标系的时间坐标线。我们可以重画图 2 以拉直这些坐标线，从而得到图 3。图 3 是表示与图 2 相同事件系统的一种有效的替代方式。如果不将物理时间概念引入系统（这需要引入物理时钟），就无法判断这些图片中哪一个是更好的表示。

读者可能会发现，将进程想象成一个二维空间网络是有帮助的，它会产生一个三维时空图。进程和消息仍用线表示，但滴答线变成了二维曲面。

现在让我们假设进程是算法，事件代表其执行过程中的某些动作。我们将展示如何在进程内引入满足时钟条件的时钟。进程 Pi 的时钟由寄存器 Ci 表示，因此 Ci(a) 是事件 a 期间 Ci 包含的值。Ci 的值将在事件之间变化，因此改变 Ci 本身并不构成一个事件。

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

IR1. 每个进程 Pi 在任何两个连续事件之间递增 Ci。

为了满足条件 C2，我们要求每条消息 m 包含一个时间戳 Tm，等于消息发送时的时间。在收到带有时间戳 Tm 的消息时，进程必须将其时钟前进到晚于 Tm。更精确地说，我们有以下规则。

IR2. (a) 如果事件 a 是进程 Pi 发送消息 m，则消息 m 包含时间戳 Tm = Ci(a)。 (b) 在收到消息 m 时，进程 Pj 将 Cj 设置为大于等于其当前值且大于 Tm。

在 IR2(b) 中，我们认为表示接收消息 m 的事件发生在设置 Cj 之后。（这只是一个记号上的小麻烦，在任何实际实现中都无关紧要。）显然，IR2 确保了 C2 得到满足。因此，简单的实现规则 IR1 和 IR2 意味着时钟条件得到满足，因此它们保证了正确的逻辑时钟系统。

给事件排全序

我们可以使用满足时钟条件的时钟系统对所有系统事件集合进行全排序。我们只需按事件发生的时间对它们进行排序。为了打破平局，我们任选进程的某个全序 $\prec$ 。更精确地说，我们定义关系 ⇒ 如下：如果 a 是进程 Pi 中的事件，b 是进程 Pj 中的事件，则 a ⇒ b 当且仅当 (i) Ci(a) < Cj(b) 或 (ii) Ci(a) = Cj(b) 且 Pi < Pj。很容易看出这定义了一个全序，并且时钟条件蕴含如果 a → b 则 a ⇒ b。换句话说，关系 ⇒ 是将”发生在…之前”偏序扩展为全序的一种方式。

排序 ⇒ 依赖于时钟系统 Ci，并且不是唯一的。满足时钟条件的不同时钟选择会产生不同的关系 ⇒。给定任何扩展了 → 的全序关系 ⇒，都存在一个满足时钟条件的时钟系统，它产生该关系。只有偏序 → 是由事件系统唯一确定的。

偏序 → -> 时钟系统 -> 全序 ⇒：构造一个始终系统，使其满足偏序关系，然后利用该始终系统排全序。我们就得到了一个满足偏序关系的全序。 偏序关系是系统本身的逻辑要求，因此必须满足；全序关系用来实现分布式系统。

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

我们假设资源最初恰好授予一个进程。

这些是非常自然的要求。它们精确地指定了解决方案正确的含义。⁴ 注意条件是如何涉及事件排序的。条件 II 对两个同时发出的请求中哪个应被首先授予没有说明。

重要的是要意识到这是一个不平凡的问题。使用一个按接收顺序授予请求的中央调度进程将无法工作，除非做出额外的假设。为了看到这一点，让 P₀ 成为调度进程。假设 P₁ 向 P₀ 发送一个请求，然后向 P₂ 发送一条消息。在收到后一条消息后，P₂ 向 P₀ 发送一个请求。P₂ 的请求有可能在 P₁ 的请求之前到达 P₀。如果 P₂ 的请求被首先授予，则条件 II 被违反。

为了解决这个问题，我们使用规则 IR1 和 IR2 实现一个时钟系统，并用它们定义所有事件的全序 ⇒。这提供了所有请求和释放操作的全序。有了这个排序，寻找解决方案就变成了一项简单的练习。它只涉及确保每个进程了解所有其他进程的操作。

为了简化问题，我们做出一些假设。这些假设不是本质性的，但引入它们是为了避免分散注意力的实现细节。我们首先假设对于任意两个进程 Pi 和 Pj，从 Pi 发送到 Pj 的消息按发送顺序被接收。此外，我们假设每条消息最终都被接收。（这些假设可以通过引入消息编号和消息确认协议来避免。）我们还假设一个进程可以直接向其他每个进程发送消息。

每个进程维护其自己的请求队列，其他任何进程都看不到该队列。我们假设请求队列最初包含单条消息 T₀:P₀ requests resource，其中 P₀ 是最初被授予资源的进程，T₀ 小于任何时钟的初始值。

TODO: 什么是事件？实际的场景下，如何决定把哪些操作当作一个事件？（下面的算法可能有启发）

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

  1. 为了请求资源，进程 Pi 向其他每个进程发送消息 Tm:Pi requests resource，并将该消息放入其请求队列，其中 Tm 是消息的时间戳。
  2. 当进程 Pi 收到消息 Tm:Pj requests resource 时，将其放入其请求队列，并向 Pj 发送一条（带时间戳的）确认消息。⁵
  3. 为了释放资源，进程 Pi 从其请求队列中移除任何 Tm:Pi requests resource 消息，并向其他每个进程发送一条（带时间戳的）Pi releases resource 消息。
  4. 当进程 Pi 收到一条 Pj releases resource 消息时，从其请求队列中移除任何 Tm:Pj requests resource 消息。
  5. 当满足以下两个条件时，进程 Pi 被授予资源：(i) 其请求队列中存在一条 Tm:Pi requests resource 消息，该消息通过关系 ⇒ 排序在其队列中任何其他请求之前。（为了定义消息的”⇒”关系，我们将消息与其发送事件等同。）(ii) Pi 已从其他每个进程收到一条时间戳晚于 Tm 的消息。⁶

注意，规则 5 的条件 (i) 和 (ii) 由 Pi 本地测试。

⁵ 这个确认消息如果 Pi 已经向 Pi 发送了一条时间戳晚于 Tm 的消息，则无需发送。 ⁶ 如果 Pi $\prec$ Pj，那么 Pi 只需要从 Pj 收到一条时间戳 ≥ Tm 的消息。

很容易验证由这些规则定义的算法满足条件 I–III。首先，观察规则 5 的条件 (ii)，结合消息按顺序接收的假设，保证了 Pi 已经了解到其当前请求之前的所有请求。 由于规则 3 和 4 是仅有的从请求队列中删除消息的规则，因此很容易看出条件 I 成立。条件 II 源自全序 ⇒ 扩展了偏序 → 这一事实。规则 2 保证了在 Pi 请求资源后，规则 5 的条件 (ii) 最终将成立。规则 3 和 4 意味着如果每个被授予资源的进程最终都释放它，那么规则 5 的条件 (i) 最终将成立，从而证明条件 III。

这是一个分布式算法。每个进程独立地遵循这些规则，没有中央同步进程或中央存储。这种方法可以推广到为此类分布式多处理系统实现任何所需的同步。同步用一个状态机来指定，该状态机由一组可能的命令 C、一组可能的状态 S 和一个函数 e: C × S → S 组成。关系 e(C, S) = S’ 表示在机器处于状态 S 时执行命令 C 会导致机器状态变为 S’。在我们的例子中，集合 C 由所有命令 Pi requests resource 和 Pi releases resource 组成，状态由一个等待请求命令的队列组成，其中队列头部的请求是当前被授予的请求。执行一个请求命令将请求添加到队列尾部，执行一个释放命令从队列中移除一个命令。

每个进程使用所有进程发出的命令，独立模拟状态机的执行。同步之所以能实现，是因为所有进程都根据其时间戳（使用关系 ⇒）对命令进行排序，因此每个进程使用相同的命令序列。当进程了解到所有其他进程发出的时间戳小于或等于 T 的所有命令时，它可以执行时间戳为 T 的命令。精确的算法很简单，我们就不描述了。

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

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

我们的资源调度算法根据全序 ⇒ 对请求进行排序。这允许以下类型的”异常行为”。考虑一个全国互联的计算机系统。假设一个人在计算机 A 上发出请求 A，然后打电话给另一个城市的朋友，让他在不同的计算机 B 上发出请求 B。请求 B 很有可能获得更早的时间戳并在请求 A 之前被排序。这可能发生，因为系统无法知道 A 实际上在 B 之前，因为这种先后信息是基于系统外部的消息。

让我们更仔细地研究问题的根源。让 S 是所有系统事件的集合。让我们引入一个事件集合S’，它包含 S 中的事件以及所有其他相关的外部事件，例如我们例子中的电话呼叫。让 ⟼ 表示 S’ 的”发生在…之前”关系。在我们的例子中，我们有 A ⟼ B，但 A → B 不成立。显然，任何完全基于 S 中事件、并且不以任何方式将这些事件与 S’ 中其他事件关联起来的算法，都无法保证请求 A 在请求 B 之前被排序。

有两种可能的方法来避免这种异常行为。第一种方法是明确地将关于排序 ⟼ 的必要信息引入系统。在我们的例子中，发出请求 A 的人可以从系统获得该请求的时间戳 TA。当发出请求 B 时，他的朋友可以指定给 B 一个晚于 TA 的时间戳。这使用户承担了避免异常行为的责任。

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

强时钟条件 对于 S’ 中的任何事件 a, b： 如果 a ⟼ b 那么 C(a) < C(b)。

这比普通时钟条件更强，因为 ⟼ 是比 → 更强的关系。它通常不被我们的逻辑时钟满足。

让我们将 S’ 与物理时空中的某些”真实”事件集合等同，让 ⟼ 是由狭义相对论定义的事件偏序。 宇宙的神奇之一是，有可能构建一个物理时钟系统，这些时钟彼此独立运行，却能满足强时钟条件。因此，我们可以使用物理时钟来消除异常行为。我们现在将注意力转向这样的时钟。

物理时钟

让我们在时空图中引入一个物理时间坐标，并用 Ci(t) 表示物理时间 t 时时钟 Ci 的读数。为了数学上的方便，我们假设时钟连续运行，而不是离散地”滴答”。（离散时钟可以被视为一个连续时钟，在读取时存在最多半个”滴答”的误差。）更精确地说，我们假设 Ci(t) 是 t 的连续、可微函数，除了时钟重置时的孤立跳跃间断点外。那么 dCi(t)/dt 表示时钟在时间 t 的运行速率。

为了使时钟 Ci 成为一个真正的物理时钟，它必须以近似正确的速率运行。也就是说，对于所有 t，我们必须有 dCi(t)/dt ≈ 1。更精确地说，我们将假设满足以下条件：

PC1. 存在常数 κ « 1，使得对于所有 i： $|dCi(t)/dt - 1| < κ$

对于典型的晶体控制时钟，κ ≤ 10⁻⁶。

仅凭时钟各自以近似正确的速率运行是不够的。它们必须同步，使得对于所有 i, j 和 t，Ci(t) ≈ Cj(t)。更精确地说，必须存在一个足够小的常数 ε，使得以下条件成立：

PC2. 对于所有 i, j： $|Ci(t) - Cj(t)| < ε$。

如果我们认为图 2 中的垂直距离代表物理时间，那么 PC2 说明单条滴答线的高度变化小于 ε。

由于两个不同的时钟永远不会以完全相同的速率运行，它们会趋向于漂移得越来越远。因此，我们必须设计一种算法来确保 PC2 始终成立。然而，首先让我们计算一下 κ 和 ε 必须多小才能防止异常行为。我们必须确保相关物理事件系统 S’ 满足强时钟条件。我们假设我们的时钟满足普通时钟条件，因此我们只需要在 a 和 b 是 S’ 中的事件且满足 a !→ b 的事件时，强时钟条件成立。因此，我们只需要考虑发生在不同进程中的事件。

让 μ 是一个数，使得如果事件 a 发生在物理时间 t，且另一进程中的事件 b 满足 a ⟼ b，则 b 发生在晚于物理时间 t + μ 的时间。换句话说，μ 小于进程间消息的最短传输时间。我们总是可以选择 μ 等于进程间的最短距离除以光速。然而，根据 S 中消息的传输方式，μ 可能会显著更大。

为了避免异常行为，我们必须确保对于任何 i, j 和 t：$Ci(t + μ) - Cj(t) > 0$。

物理时间t是什么：本节的物理时间是基于牛顿绝对时空观的。 j 在时刻t给 i 发消息(事件a)，i在时刻T收到（事件b）。因为a ⟼b，因此需要Cj(a) < Ci(b) 才能满足正确性，即需要Cj(t) < Ci(T)。 i 收到消息时，有T> t+u，因此Ci(T) > Ci(t+u)， 在确保 Cj(t) < Ci(t+u) 之后，有Cj(t) < Ci(T)，得证。

如果扩展到相对论时空，在实际的地球附近的物理条件下，可以选取一个参考系q的时间作为物理时间。 事件a在j的视角为时间t’，时间戳Cj(t’)，事件b在i的视角为时间T’，时间戳Ci(T’)；它们在q的视角时间分别为t和T。 μ也定义为在参考系q中观察到的时间。因此有T>t+u。 η定义为其他进程与q在物理时间上的最大偏移。在现实中，η « u。 PC2: Ci(t-η)<Ci(t_q)<Ci(t+η) –> ε需要放大2η 要求 Cj(t) < Ci(t+u-2η) – 实质上等价于u变小一点； Cj(a) = Cj(t’) < Cj(t+η) < Ci(t+u-η) < Ci(T-η) < Ci(T’) = Ci(b)

正确性要求: 对S’中的任意a ⟼ b，需要Cj(a) < Ci(b) 实际重要的只是时钟，而不是物理时间，因为我们只能观察到时钟。设想一种情境，系统中所有进程全都步调一致地变快或者变慢，其实无所谓。 最终，我们需要的是对系统中的事件能够根据时钟读数排全序的同时不违背（我们关心的）因果关系。 例如spanner的思想，假如我们能知道不同进程之间时钟读数差异的范围，我们可以把事件延迟一定的时间来保证满足正确性要求。

关心物理时间是因为物理时间关系到实际体验。例如S中的事件加上物理时间派生出的事件组成S’。 例如进程1在01分写入数据库，进程2在02分读取。进程之间没有同步的情况下，进程2读取到写入前或后的数据都不违背时钟条件。 但现实中合理的方式显然是读取写入后的数据。

将此与 PC1 和 PC2 结合，我们可以将 κ 和 ε 所需的小的程度与 μ 的值联系起来，如下。 我们假设当时钟被重置时，它总是被向前设置，从不向后。（向后设置可能导致 C1被违反。） PC1 则蕴含 Ci(t + μ) - Ci(t) > (1 - κ)μ。使用 PC2，然后很容易推导出，如果$ε/(1 - κ) ≤ μ$成立，则 Ci(t + μ) - Cj(t) > 0：

这个不等式与 PC1 和 PC2 一起意味着异常行为是不可能的。

我们现在描述我们的算法，以确保 PC2 成立。让 m 是一条在物理时间 t 发送、在时间 t’ 接收的消息。 我们定义 $ν_m = t’ - t$ 为消息 m 的总延迟。当然，接收 m 的进程不会知道这个延迟。 然而，我们假设接收进程知道某个最小延迟 $μ_m ≥ 0$，使得 $μ_m ≤ ν_m$。我们称 $ξm = ν_m - μ_m$ 为消息的不可预测延迟。

我们现在将规则 IR1 和 IR2 专门针对我们的物理时钟，如下所示：

IR1’. 对于每个 i，如果 Pi 在物理时间 t 没有接收到消息，则 Ci 在 t 处可微，且 dCi(t)/dt > 0。

IR2’. (a) 如果 Pi 在物理时间 t 发送消息 m，则 m 包含一个时间戳 Tm = Ci(t)。 (b) 在时间 t’ 接收到消息 m 时，进程 Pj 将 Cj(t’) 设置为 $max(Cj(t’ - 0), T_m + μ_m)$。⁹

尽管规则是根据物理时间参数正式指定的，但一个进程只需要知道它自己的时钟读数和它接收到的消息的时间戳。为了数学上的方便，我们假设每个事件都发生在物理时间的精确瞬间，并且同一进程中的不同事件发生在不同时间。这些规则是规则 IR1 和 IR2 的特化，因此我们的时钟系统满足时钟条件。实际事件具有有限持续时间这一事实在实现算法时不会造成困难。实现中唯一真正需要关心的是确保离散时钟滴答足够频繁，以维持 C1。

我们现在证明这个时钟同步算法可以用来满足条件 PC2。我们假设进程系统由一个有向图描述，其中从进程 Pi 到进程 Pj 的弧代表一条直接发送消息的通信线路。如果对于任何 t，Pi 在物理时间 t 和 t + τ 之间至少向 Pj 发送一条消息，则称每隔 τ 秒通过此弧发送一条消息。有向图的直径是最小的数 d，使得对于任何一对不同的进程 Pj, Ph，存在一条从 Pj 到 Ph 的路径，该路径最多有 d 条弧。

除了建立 PC2 外，以下定理还限制了系统首次启动时时钟达到同步所需的时间。

定理. 假设一个强连通的进程图，直径为 d，始终遵守规则 IR1’ 和 IR2’。假设对于任何消息 m，$μ_m ≤ μ（μ 为某常数）$，并且对于所有 t ≥ t₀：(a) PC1 成立。(b) 存在常数 τ 和 ξ，使得每隔 τ 秒，通过每条弧发送一条不可预测延迟小于 ξ 的消息。那么对于所有 $t ≥ t₀ + τd$，PC2 以 $ε ≈ d(2κτ + ξ)$ 满足，其中近似假设 $μ + ξ \ll τ$。

这个定理的证明出奇地困难，在附录中给出。关于同步物理时钟的问题已经做了大量工作。我们请读者参阅 [4] 作为该主题的入门。文献中描述的方法对于估计消息延迟 μm 和调整时钟频率 dCi/dt（对于允许此类调整的时钟）是有用的。然而，要求时钟从不向后设置似乎将我们的情况与之前研究的情况区分开来，我们相信这个定理是一个新的结果。

结论

我们已经看到，”发生在…之前”的概念定义了分布式多处理系统中事件的一个不变偏序。我们描述了一种将该偏序扩展为某种程度上任意的全序的算法，并展示了如何使用这种全序来解决一个简单的同步问题。未来的论文将展示如何扩展这种方法来解决任何同步问题。

该算法定义的全序在某种程度上是任意的。如果它与系统用户感知的排序不一致，它可能会产生异常行为。这可以通过使用适当同步的物理时钟来防止。我们的定理展示了时钟可以同步到多接近的程度。

在分布式系统中，重要的是要意识到事件发生的顺序只是一个偏序。我们相信这个想法对于理解任何多处理系统都是有用的。 它有助于人们理解并发的基本问题时不需考虑解决问题的具体机制。

省略附录对定理的证明

参考文献

  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, G., and Kulpinski, R.J. Dissemination of system-time. IEEE Trans. Comm. Com-23, 5 (May 1973), 605–624.