此文是分布式系统领域的经典论文，定义了分布式系统中事件的偏序关系，并且提出了一种分布式系统的时间同步算法。
在多进程通信时，独立的计算机也可能是分布式系统，换句话说，只要不同进程之间的通信时延不能忽略都可以算作分布式系统。 在分布式系统的运行过程中，事件的执行顺序非常重要，论文首先明确定义了事件的 happened before 关系， 进而阐明了事件的偏序关系（不叫全序的原因是有些事件不能以物理时钟的视角进行排序，可以看做是并行的，没有绝对的先后顺序）， 为了实现对分布式系统中所有事件排序，又定义了全序关系，在偏序关系的基础上用进程的逻辑时钟对没有先后顺序的事件进行排序。
happened before（a $→$ b）： 偏向对事件的逻辑关系进行排序，事件 a 会对事件 b 造成潜在的影响，称 a happened before b。
- 对于单进程，只要 a 的执行顺序是在 b 之前，即为 a $→$ b。
- 对于多个进程，一个进程发送事件（a）给另一个进程，并且另一个进程收到这个事件（b），也算是 a $→$ b。
- happened before 有传递性，若 a $→$ b，b $→$ c，也有 a $→$ c。如果 a $↛$ b，并且 b $↛$ a，则表明 a 和 b 是并发的。
The Partial Ordering（偏序关系）： $→$ 本身就是一个定义在系统全部事件上的不自反偏序，不存在「另一个范围更大的偏序」把它包在里面。说它是偏序，指的就是它满足这几条：
- 不自反：任何事件都不会有 a $→$ a。
- 传递：a $→$ b 且 b $→$ c 则 a $→$ c。
- 不完全：存在事件对既不满足 a $→$ b 也不满足 b $→$ a。
「偏」的含义正是第 3 条——不是任意两个事件都可比。比如 a $→$ b 且 a $→$ c，而 b 和 c 之间没有 $→$ 关系，那 b 和 c 就是并发的，谁先谁后无所谓。
为了在分布式系统中实现对所有事件进行排序，论文引入了逻辑时钟，我们能将其看做是一个自增的 id，可以不依赖物理时钟，只需要为每个进程定义事件顺序即可，我们可以用 $C_i(a)$ 定义为第 i 个进程的事件 a 的逻辑时钟。
对于任意事件 a 和 b，如果 a $→$ b，则 C(a) < C(b)，那么需要满足：
- IR1：对于单进程，每个进程定义的逻辑时钟需要自增。
- IR2：对于多进程，进程 i 发送消息 m（事件 a）时附带自己的逻辑时钟 $T_m = C_i(a)$；进程 j 收到 m（事件 b）时，必须把自己的时钟设成不小于当前值、并且严格大于 $T_m$。这里必须是严格大于，否则 $C_j(b)$ 可以等于 $T_m$，就推不出 $C(a) < C(b)$ 了。
通过逻辑时钟，我们就可以定义全序关系 $⇒$。设 a 发生在进程 i、b 发生在进程 j，则 a $⇒$ b 当且仅当满足下面任意一条：
- $C_i(a) < C_j(b)$；
- $C_i(a) = C_j(b)$ 并且 $process_i < process_j$——逻辑时钟撞了，就拿进程编号这个事先固定的全序来破平。
可以知道的是，$⇒$ 关系最终构成的事件顺序是不唯一的，受到逻辑时钟的影响；$→$ 则是唯一的。 那么如何才能定义全序关系，并且实现呢？对于一个资源互斥的使用场景，全序关系的算法实现需要满足三个条件：
- 同一时间只能有一个进程持有某个资源，进程持有资源的时候，前一个使用此资源的进程需要释放资源。
- 对同一个资源的不同请求，必须按它们被发出的顺序依次批准。
- 如果每个已经使用的资源最终被释放，那么每个资源的请求都会被通过。
具体来说，可以用五个规则来实现：
- 进程 $P_i$ 请求资源时，把带时间戳 $T_m$ 和进程 id 的请求消息发给其他所有进程，同时在自己的请求队列里也放一条这个请求。
- 进程 $P_j$ 收到这条请求后，把它放进自己的请求队列，并给 $P_i$ 回一条带时间戳的 ack。
- $P_i$ 释放资源时，从自己的请求队列里删掉自己那一条 $T_m:P_i$ 请求，再把带时间戳的释放消息发给其他所有进程。
- $P_j$ 收到 $P_i$ 的释放消息后，从自己的请求队列里删掉 $P_i$ 那一条请求——只删这一条，别人的请求不动。
- 进程持有资源需要满足以下两个条件：① 自己那条请求按 $⇒$ 排在队列中所有其他请求之前；② $P_i$ 已经从其他每一个进程都收到过时间戳晚于 $T_m$ 的消息。
但是假如用户 A 发送了一个请求到服务器，告知用户 B 之后用户 B 也发送了同样的请求，如果全序关系分配了较大的逻辑时钟给 B 的请求，那么服务器返回的结果可能与期望的结果不符。
这个问题，并不是系统内部能够控制的，虽然定义的全序关系可以组成一个多个进程统一的命令队列，每个机器按照队列执行可以保证分布式系统的一致性，但是，集群无法感知外界的“happened before”关系，可能会得到违反自觉的结果。
因此，本文的作者引入了物理时钟解决这个问题。注意这里要的不是前面那条时钟条件（a $→$ b 则 $C(a) < C(b)$，写成这样只是把已有结论重复一遍），而是更强的强时钟条件：判据换成物理时间的先后——只要 a 在物理时间上早于 b，就要求 $C(a) < C(b)$，哪怕 a 和 b 在系统内部完全没有消息链、因果是通过系统外的渠道（比如 A 打电话告诉 B）传过去的。系统内的 $→$ 看不见这种外部因果，只有把时钟锚到物理时间上才能覆盖它。
对于时钟约束，我们假设每个机器的速率可以用 $dC_i(t)/dt$ 表示，现实的物理时钟的速率为 1，集群的时钟有两个限制：
- PC1： $| dC_i(t)/dt -1| < \kappa$ $\kappa$ 常 $ \leq 10^{-6}$
- PC2： $|C_i(t) - C_j(t)| < \epsilon$
因为两个机器的时钟不可能以同一个速率运行，那么两者的差值会越来越大，我们必须设计一个时钟同步算法来保证 $a \nrightarrow b$ 的时候满足以上两个约束（现实世界的强限制）。
首先需要考虑的问题是如何设定 $κ$ 和 $ϵ$ 的值。先澄清一个容易记反的点：PC1 是双向的界，机器时钟的走速既可以略快于物理时间也可以略慢；真正单调的是校准动作——下文 IR2’ 用 $\max$ 取值，只会把时钟往前拨，永远不会往回拨。
首先想到的是这两个值与集群进程间通信的时延有关，如果进程间通信的最小时延为 $μ$，由 PC1 给出的下界 $dC_i(t)/dt > 1-κ$，我们可以得到 $C_i(t+μ) - C_i(t) > (1-κ)μ$，左边是同一机器在经过 $μ$ 物理时间后自己时钟走过的量，理想情况下应该等于 $μ$；右边是 PC1 允许的最慢走速下这段时间的下界；由限制 2，我们可以得到 $C_i(t+μ)-C_j(t)>0$，化简可知 $ϵ/(1-κ)≤μ$。
在真正的物理世界，我们由上面的 逻辑时钟限制 衍生出了以下两个限制：
- IR1’：对于每个进程 i，如果在物理时间 t 的时候没收到请求，在时间 t 的时候 $C_i$ 是连续可导的，并且 $dC_i(t)/dt > 0$
- IR2’：进程 i 发送信息 m 的时候需要附带自己的时间戳 $T_m = C_i(t)$，进程 j 接收到 m 的时候为 t’，那么 j 需要设置自己的时钟为 $max{C_j(t’-0),T_m+μ_m}$。
基于以上的两个限制，论文通过两页纸的证明得出结论：把节点之间的通信看成有向图的边，设这个强连通图的直径为 $d$。前提是所有时钟都满足 PC1、每条边每隔 $\tau$ 秒发一条消息、消息的不可预测延迟小于 $\xi$、并且对每条消息 m 有 $μ_m≤μ$；那么在 IR1’ 和 IR2’ 之下，从所有时钟启动后 $\tau d$ 时间起，系统满足 PC2，其中 $ϵ \approx d(2κτ+ξ)$，适用条件是 $μ+ξ\ll τ$。
别把 PC1 当成结论：PC1 是对单机石英钟走速的假设，是这套推导的输入；同步算法要争取的是 PC2，也就是任意两台机器读数之差有界。