背景
"时间"是我们平时思考问题时用到的一个基本概念，"时间"来源于一个更加基础的概念"事件发生顺序"。通常，如果事件发生在时钟显示为3:15之后并且尚未变为3:16, 我们会称这个事件发生在3:15。通过时间来为事件排序在系统中随处可见。比如在航线预定系统中，我们规定"如果一条航线尚未被预定，那么它应该被分配给接下来的航线预定请求"。需要注意的是，在分布式系统中我们需要对于事件的顺序进行重新的认识。
分布式系统由一组空间上相互独立、彼此间通过信息交换进行交互的进程组成。通过网络连接的一组计算机，是一个分布式系统。一台计算机也可以看做是由cpu、memory、disk等组成的分布式系统。因此，一般我们认为系统的不同进程间通信延迟相比进程内部通信延迟不可忽略时，那么这个系统就被认为是分布式系统。
我们关注的重点会聚焦在由多台计算机组成的分布式系统，但是其中的许多理论是普遍适用的。尤其，对于虽然运行在一台计算机上的多进程系统，由于事件发生的不确定性，其所面临的问题与多台计算机组成的的分布式系统是相似的。
在分布式系统中，有时候很难明确的说两个事件的发生顺序, 因此"happened before"只是系统中某些事件间的一个"偏序关系"(这里的概念是相对于系统中所有事件的按照时间排序的全序关系而言)。其实很多问题的发生都是因为认为没有认识到这种关系的本质和影响。
本文，我们会讨论由"happened before"关系所定义的"偏序关系"，并且会提出一种分布式算法来将这种某些事件间的"偏序关系"扩展为所有事件间的"全序关系"。这个分布式算法可以很好的帮助实现一个分布式系统，我们会通过解决一个同步问题，来说明它的用法。需要指出的是，如果通过该算法获得的事件顺序与用户所认为的顺序不同，可能会引起一些异常行为，我们会通过引入真实的物理时钟来避免这个问题。我们会提供一个简单的方式用于系统中不同时钟间的同步，并且会明确这些时钟间的最大偏差。
偏序关系
大部分人认为如果事件A的发生时间早于事件B，那么事件A "happened before" 事件B。他们是根据理论上的物理时间得出这个顺序的。但是，如果系统要正确的得到某种特定的事件顺序，那么这个事件顺序必须是系统观察到的。如果这种顺序是根据物理时钟定义的，那么系统中必须包含一个真实的时钟。问题在于，即使系统真的包含一个物理时钟，但是这样的时钟并不是完美的精确，并且不能跟真实的物理时间完全一致(时钟的误差,导致观察到的"时间"有误差，那么基于这种时钟的"时间"定义的顺序就有问题)。因此，我们并不依赖物理时钟去定义"偏序关系"。
接下来，我们开始准确的描述我们的系统。假设我们的系统由一组进程组成，每个进程包含一系列"事件"。"事件"的定义由应用程序决定，比如计算机上的一个子程序执行可以认为是一个"事件"，一个机器指令的执行也可以认为是一个"事件"(不同应用场景对于事件的定义不同，比如在数据库中一次dml可以认为是一个事件)。假设在一个进程中所有事件组成的序列中，如果事件A"happened before"事件B，那么事件A在事件B之前发生。换句话说，一个进程中事件有天然的全序关系，对于一个进程来说这种关系看起来顺理成章。当然我们也可以将我们的定义从进程扩展到子进程，但是我们并不打算这样去做。
假设进程中发送和接收消息是一个事件，那么可以这样定义"happened before"关系(通过"->"符号表示)：
定义：系统中事件间的"->"关系是满足以下三个条件的最基本关系)：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和事件B是并发的。
对于任意事件A，A!->A(在系统中一个事件可以"happened before"它自身，看起来是没有实际意义的)。这也表明"->"是一个系统中所有事件集合中的一个"反自反偏序关系"。(离散数学中的关系，自反和反自反)
类似Figure 1中的"时空图"，对于理解上述定义是有帮助的。时空图中，横向表示空间，纵向表示时间(越高表示时间越靠后)，小圆点表示事件，纵向的线表示进程，波浪线表示消息。显而易见，A->B表示在时空图中可以沿着表示进程的线或表示消息的波浪线，从A移动到B。比如Figure 1中的p1->r4。
另外一种理解上述定义的方式是，A->B意味着事件A和事件B之间可能存在因果关系。如果两个事件之间相互无影响，那么它们是并发的。比如Figure 1中的p3和q3是并发的，即使图中所画的q3先于p3发生，但是进程P无法知道进程Q中q3事件直到在p4事件中收到来自进程Q的消息。(在时间p4之前，进程P最多知道进程Q计划做事件q3)。
如果熟悉狭义相对论中的时空观，那么可以比较自然的理解上述定义。在狭义相对论中，时间的顺序是根据可能被发送的消息定义的。在我们的定义中，我们更加实用的只考虑实际发送的消息。我们根据实际发生的事件去判断系统是否正常工作，而不是根据可能发生的事件去判断。
逻辑时钟
现在我们将时钟引入到系统中。从抽象的角度看，"时钟"只是一种为事件分配编号的方式，其中编号代表事件发生的时间。具体的，我们为每一个进程Pi定义了一个时钟Ci，Ci的作用是为进程Pi中的每一个事件a分配一个序号Ci。整个系统中所有的时钟通过C表示，用来为每一个事件b分配一个序号C, 并且如果事件b发生在进程Pj中，那么C = Cj。截止现在，我们并没有对于序号Ci与物理时间之间的关系作出任何假设，因此我们可以认为Ci是"逻辑时钟"而非"物理时钟"。逻辑时钟的实现不需要任何真实的时间装置(比如原子钟)，可能仅仅是一个计数器。
现在，我们需要重新审视一下对于分布式系统，时钟的正确性意味着什么。我们不能基于真实的物理时间去定义分布式系统中时钟的正确性，因为这依赖完全与物理时间保持一致的时钟(之前提到，真实的时钟也是有误差的)。我们的定义必须是基于事件的发生顺序。需要满足的条件是，如果事件a在事件b之前发生，那么事件a的发生时间比事件b发生的时间早。我们通过以下的描述正式的定义这个条件：
时钟条件：对于任意事件a、b， 如果a->b, 那么C(a) < C(b)。
需要指出的是，上述时钟条件的反向条件是不成立的(也就是对于任意事件a、b，如果C(a) < C(b), 不能得出a->b), 因为如果反向条件成立，那么意味着任意两个并发的事件必须发生在相同的时间(这个推导应该比较简单，对于两个并发的事件a，b，那么a!->b && b!->a, 也就是C(a) !< C(b) && C(b)!p3是矛盾的。
显而易见，如果符合下面两个条件， 那么由"->"关系引出的上述时钟条件就会成立。
C1：如果事件a、b发生在相同的进程Pi中，并且事件a先于事件b发生，那么Ci(a) < Ci(b)。
C2：如果事件a是进程Pi中的发送消息事件，并且事件b是相应的进程Pj中的接收消息事件，那么Ci(a) < Cj(b)。
让我们根据时空图重新考虑"时钟"。我们想象一个进程的时钟的"滴答声"(这里的滴答声可以理解为逻辑时钟中时间的基本单位，比如物理时钟中的纳秒或者皮秒)是连续的，也就是进程中任意两个事件之间都有"滴答声"。举个例子，如果事件a、b是进程Pi中两个连续的事件，Ci = 4、Ci = 7, 那么时钟Ci的滴答声5、6、7就发生在事件a、b之间。我们在不同进程间接近的滴答声之间画虚的"滴答线"，那么Figure1中的时空图就会变成Figure2中的时空图。条件C1意味着，在一个进程中的任意两个事件间必须有至少一条"滴答线"；条件C2意味着， 每条消息线必须穿过至少一条"滴答线"。通过时空图的方式去说明"->"关系，可以简单的理解为什么条件C1和C2可以推导出"时钟条件"。
我们可以将滴答线看做是时空中的笛卡尔坐标系中时间坐标线。我们可以将Figure2中的时间坐标线拉直，就得到了Figure3。Figure3是另外一种方式去表示Figure2中的系统。在没有引入物理时间的系统中，没有办法去判断Figure2和Figure3哪一种是更好的表示方式。
现在，让我们假设进程就是一个算法，那么事件代表算法执行过程中具体的步骤。我们会介绍如何将时钟引入到进程中并且满足"时钟条件"。进程Pi的时钟通过Ci表示， 那么Ci就是在事件a发生时C中的"时间"。Ci的值会在不同的事件之间变化，因此Ci变化本身不被当作事件。
为了保证系统中的逻辑时钟满足"时钟条件"，我们要保证逻辑时钟满足条件C1和C2。条件C1容易满足，进程只需要遵守下面的实现规则(implementation rule)：
IR1：每一个进程Pi都需要在两个连续事件间增加Ci。
为了满足条件2，要求每一个消息m都需要包含一个时间戳Tm，Tm是消息m发送时的时间。当收到带有时间戳Tm的消息m时，接收消息的进程必须将它的时钟推进到Tm之后。具体的，需要满足下面的实现规则：
IR2：(a)如果事件a是进程Pi发送消息m的事件，那么消息m包含的时间戳Tm = Ci。
(b)当进程Pj收到消息m时，进程Pj将它的时钟Cj设置为大于等于其当前的值，并且这个值要大于Tm。
在IR2(b)中，我们认为接收消息m的事件发生在设置Cj之后。很明显，IR2保证条件C2被满足。因此，IR1和IR2可以通过简单的实现来保证"时钟条件"被满足，从而保证系统的逻辑时钟的正确性。
我们可以通过一个满足"时钟条件"的时钟去为系统中所有事件进行排序，从而得到一个系统中所有事件的全序关系。我们简单的通过事件发生的时间为它们排序。为了避免出现时间相等导致无法排序的情况，我们引入任意一种进程间的全序关系"<"来解决这个问题。具体的，我们定义了一种满足下面条件的新的关系"=>"：如果a是进程Pi中的事件，b是进程Pj中的事件，当且仅当满足1)Ci < Cj或者2) Ci = Cj && Pi < Pj时，a=>b关系成立。很明显，这里定义了一个全序关系，并且"时钟条件"表明如果a->b,那么a=>b。换句话说，关系"=>"是一种将基于"happened before"定义的偏序关系扩展为全序关系的方法。
基于"=>"关系的顺序取决于所选择的时钟系统，并非唯一的。选择不同的时钟(均满足时钟条件)会得出不同的"=>"关系。任意一个由"->"扩展而来的全序关系"=>"，都有一个满足时钟条件的时钟系统。只有偏序关系"->"是根据系统中的事件唯一确定的。
能够对所有事件进行排序在分布式系统的实现中是非常重要的。事实上，之所以实现一个正确的逻辑时钟系统也是为了获得这样一个全序。接下来，我们使用这种所有事件的全序关系来解决一个互斥问题，来说明它的用法。假设有一个由数目固定的若干进程组成的系统，这些进程共享一个资源R。某一时刻资源R只能被一个进程使用，因此进程间需要相互同步从而避免对资源R的使用冲突。我们期望找到一个算法可以按照如下三个条件去分配资源：1）在资源R被分配给一个进程之前，上一个获得资源R使用权的进程必须先释放资源R；2) 必须按照进程的请求顺序去分配资源R的使用权；3) 如果每个获得资源R使用权的进程最终都释放了资源R，那么所有资源R使用权的请求都最终被满足。
假设初始化时，资源R被分配给某一个进程。
上述的三个条件都是非常自然的需求，它们准确的描述了什么样的解决方案是正确的。注意这些条件跟事件间顺序的关系。条件2）并没有规定两个并发的请求(两个请求事件不存在偏序关系)被满足的先后关系。
意识到这个问题的不平凡性是非常重要的。除非加入其它假设(比如消息传递的时间恒定)，不然使用一个全局调度进程按照其收到请求的顺序去分配资源是不能满足上述条件的。举个例子，假设P0为全局调度进程，P1首先向P0发送了一个资源请求，然后P1向P2发送了一个消息，当P2收到来自P1的消息后，P2向P0发送一个资源请求，那么可能P2的资源请求先于P1的资源请求到达P0，那么P2的资源请求将会被先满足。这其实违反了上述条件2），因为实际上P1的资源请求与P2的资源请求之间存在"happened before"关系，并且P1->P2。
为了解决这个问题，我们实现了一个遵守IR1和IR2的时钟系统，并且通过它定义了所有事件的全序关系。它提供了所有请求资源和释放资源操作的全序关系。有了这个全序关系，解决方案就很明确了。该解决方案只需要每个进程可以知道所有其他进程的操作。
为了简化这个问题，我们做了一些假设。但这些假设不是必须，而是为了让我们更聚焦在解决方案本身，而非具体的实现细节。我们假设任意两个进程间，消息的接收顺序与消息的发送消息相同，也就是由Pi向Pj发送消息，Pj收到消息的顺序跟Pi发送消息的顺序相同(有了这个假设，我们可以不需要去介绍如果通过消息序列号和消息ack协议来保证这个顺序，这些是网络协议的事情)。同时，我们还假设进程间都可以互相直接通信(而不是需要进程P1和P3间的通信必须经过进程P2)。
每个进程管理它自己的私有请求队列，并且进程是无法获取其他进程的私有请求队列的内容。我们假设初始化时，每个请求队列中只有一个消息"T0:P0的资源请求", 其中P0是初始化时拥有资源R使用权的进程，T0小于所有时钟初始值。
该算法通过下面5条规则描述。为了方便，我们将每条规则对应的行为都视为一个单独的事件。
1）为了获取资源，进程Pi向所有其他进程发送消息"Tm:Pi的资源请求"，并且将这个消息放到它自己的请求队列中，其中Tm是该请求消息的时间戳。
2）当进程Pj收到消息"Tm:Pi的资源请求"时，将该消息放到自己的请求队列中，并且向进程Pi返回一个带有时间戳的ack消息。
3）为了释放资源，进程Pi从他的请求队列中删除所有"Tm:Pi的资源请求"消息， 并且向所有其他进程发送一个带有时间戳的Pi释放资源消息。
4）当进程Pj收到来自进程Pi的释放资源消息时，将其请求队列中的所有"Tm:Pi的资源请求"消息删除。
5）当满足下面两个条件时，进程Pi获得资源的使用权：a)进程Pi的请求队列中的所有请求按照关系"=>"排序后，消息"Tm:Pi的资源请求"排在最前面(为了确定消息间的关系"=>",我们通过其对应的发送事件来标识每一个消息)。b)进程Pi已经收到所有其他进程发来的时间戳大于Tm的消息。
需要指出的是，规则5）中的两个条件都是进程Pi通过自身状态进行判断(言外之意，不再需要与其他进程交互)。
可以非常简单的证明这个算法满足上述问题的三个条件。首先，规则5)中的条件b以及之前的消息按序接收的假设，可以保证进程Pi已经知道了所有早于Tm其他进程的资源请求。由于规则3)和规则4)是仅有的从请求队列中删除消息的事件，那么显而易见上述问题的条件1)是满足的(除非进程Pi释放了资源，否则消息"Tm:Pi的资源请求"就会一直占据着全序最小的位置，其他进程也就无法获得资源)。因为全序关系"=>"是通过偏序关系"->"扩展而来，那么根据全序关系分配资源也就不会违背偏序关系，那么上述问题的条件2)是满足的。规则2)保证了在进程Pi发出资源请求之后，规则5)中的条件b最终会被满足，因为收到请求的消息的进程都会回复一个带有时间戳的消息，而按照事件的偏序关系，这个时间戳肯定是大于请求资源消息中的时间戳的。规则3)和规则4)表明，如果每一个获取资源的进程最终都释放了资源，那么规则5)中的条件a最终都会被满足，这也证明了上述问题的条件3)被满足。
备注：
因为任一进程都要把自己的请求，不管是申请资源还是释放资源，通知到其他所有进程。如果规则5(ii)成立，说明Pi已经得知了其他所有进程至少在Tm之前的所有请求状态。假设此时不应该是Pi获得资源而应该是Pj获得资源，则Pj申请资源的事件的逻辑时钟序应该小于Tm，因此在Pi本地队列中有这一个消息，而且该消息在全序关系中比(Tm:Pi request resource)小，这跟规则5(i)矛盾。所以Pi仅根据本地判定自己获得资源是符合要求的。所以要求I是满足的。因为只有3和4会删除消息，所以除非Pi释放了资源，否则(Tm:Pi request resource)就会一直在消息队列中，且占据着全序最小的位置，其他进程是不会判定自己可以获得资源的。
因为我们是按照全序关系来判定的，而全序又是从偏序扩展来的，因此不会违背偏序定义的顺序。要求II因此满足。
规则3、4在删除了(Tm:Pi request resource)之后，必定有另外一个进程Pj的申请消息会占据全序的最小值位置，而ack消息也能保证5(ii)成立。因此III成立。
通常这里会有一个疑问，如果进程Pi和进程Pj并发的发起资源请求，那么这两个请求是不存在偏序关系，上述问题的条件2)对于并发请求的先后关系也没规定，所以哪个先被满足都可以，因为我们引入了进程间的全序关系，来将事件间的偏序关系扩展为全序关系，也就是说并发的两个请求在全序关系中是有顺序的，但是这并不违反事件间的偏序关系。为了理解这个关系，我们需要抛开固有的物理时间()，而是按照逻辑时间去理解，因为上面所说的排序也都是根据逻辑时间而非物理时间。
这是一个分布式算法。每一个进程相互独立的遵守这些规则，不存在中心化同步进程和中心化存储。这个算法对于在这样的多进程分布式系统中实现任何期望的同步都是适用的。这个算法还可以通过"状态机"描述, 状态机包括以下三部分：集合C包含所有可能执行的命令，集合S包含所有可能的状态，状态转移函数e: C X S -> S`表示在状态机处于状态S上执行命令C，状态机的状态变为S`。在我们的算法中，集合C包含进程Pi的所有请求资源和释放资源命令，集合S包含一个处于等待状态的请求资源队列，并且队列最前面的请求是将要被分配资源的。执行一个请求资源命令会在请求队列的尾部加入一个请求，执行一个释放资源命令会从队列中删除一个请求。
每一个进程通过执行所有进程发出的命令，独立的保持状态机的运转。进程间的同步通过执行相同顺序的命令序列来达到，因为所有命令顺序是通过全序关系指定的。当一个进程已经执行了所有小于等于时间T的命令后，它就可以执行时间戳为T的命令了。具体的算法已经很明确了，这里不再赘述。
上述方法可以用来在分布式系统实现任意形势的多进程间同步。但是，这个方法要求所有参与的进程都处于活跃状态。因为每个进程都需要知道其他进程发出的命令，因此任何进程的失败都会造成其他进程无法执行状态机中的命令，进而使整个系统停止。
解决进程失败导致系统停止的问题是比较困难的，并且这已经超出了本文的讨论范畴。并且失败的概念只有在物理时间的上下文才有意义。没有物理时间，我们无法判断系统是失败了还是只是在事件间隙。用户只能通过系统很长时间没有响应来判断系统crash了。在单个进程失败或通信出现问题的场景下，仍然可以工作的方法，我们在参考文献[3]中讨论。
我们的资源调度算法是根据全序关系来响应资源请求。这可能会导致下面这类"异常行为"，比如person1在计算机A上发起了请求a，然后他给在另外一个城市的朋友person2打电话，让person2在计算机B上发起请求b，很有可能请求b被分配了一个更小的时间戳，从而导致请求b排在请求a前面。之所以会出现这种情况，是因为系统内部没有办法知道请求a确实在请求b前面，因为这个时序信息是基于系统外部的消息(这个消息就是person1给person2打电话，让person2发起请求)。
让我们进一步去探究上述"异常行为"的根本原因。集合H包含系统中所有的事件，集合H`包含集合H和所有其他相关的事件，比如上面的例子中"打电话"事件。定义"->"(为了区别于之前的->关系，这里是加粗加斜的)关系为集合H`中的"happened before"。在上面的例子中，存在a->b(加粗加斜)，但是不存在a->b。显而易见，仅根据集合H中的事件，而不考虑H`中的任何其他事件，是无法设计出一个满足事件a肯定排在事件b之前的算法。
有两种方法去避免这个"异常行为"。第一个方法是显示的将与"->"(加粗加斜)关系相关的必要信息引入到系统中。对应于上面的例子，就是系统为person1发起的请求a分配一个时间戳Ta，当person2发起请求b时，他可以显示为请求b指定一个大于Ta的时间戳。这种方式是将避免"异常行为"的责任推给了用户。
第二种方法是构造一个满足下面条件的时钟系统：
加强时钟条件：对于集合H中的任意事件a、b，如果a->b(加粗加斜)，那么C(a) < C(b)。
这里可以返回去看一下之前的"时钟条件"，来看一下两者的区别。其实"->"(加粗加斜)是引入了外部序的"->"偏序关系。
假设集合H`包含的是物理时空中的真实事件，关系"->" (加粗加斜)是由狭义相对论定义的偏序关系，那么在我们所处的宇宙中，是有可能构造出一个物理时钟系统，其中的物理时钟相互之间独立运行但是满足"加强时钟条件"。因此我们可以通过使用物理时钟来避免上述"异常行为"，接下来我们重点关注这类时钟。
我们会将真实的物理时间引入到时空图中，Ci(t)代表时钟Ci在物理时间t时显示的值。为了计算方便，假设时钟是连续运转的而非离散的滴答运转。具体的，假设Ci(t)是时间t上的连续可微分函数，除非当时钟被重置时会导致的不连续情况。dCi(t)/dt表示时钟在时间t时的运行速度。
时钟Ci必须以一个相对正确的速率运行，才能被当作真实的物理时钟使用。也就是说dCi(t)/dt≈1。具体的，我们假设时钟Ci满足下面的条件：
PC1：必须存在一个远小于1的常量k，对所有的时钟i，|dCi(t)/dt - 1| < k。
通常石英钟的k <= 1/(10的6次方)。
要求每个独立的时钟以接近正确的速率运行是不够的。在时间t，不同的时钟显示的值应该相互接近，也就是Ci(t)。具体的，必须存在一个足够小的常量e满足下面的条件：
PC2：对于所有时钟i、j，|Ci(t) - Cj(t)| < e。
如果Figure2的纵向距离表示物理时间，那么PC2就要求每条滴答线的高度变化小于e。
因为两个不同的时钟永远不可能以相同的速率运行，那么他们之间的误差就会有越变越大的趋势。因此我们必须设计一个算法保证PC2永远满足。首先，我们需要明确k和e在多小的时候才能避免"异常行为"。我们必须保证有所有真实物理事件集合H`构成的系统满足"加强时钟条件"。我们假设我们的时钟系统满足之前的"时钟条件"，那么我们只需要要求那些H`集合中不满足a->b(加粗加斜)的事件间满足"加强时钟条件"。因此，我们只需要考虑那些发生在不同进程中的事件。
如果发生于物理时间t的事件a与发生在另一个进程中的事件b满足a->b(加粗加斜)关系，那么b发生的真实物理时间是在t + μ之后，μ要小于进程中传递消息的最小传递时间。通常我们将μ设置为(进程间距离）/ 光速。当然，μ可以设置为更大的值，这取决于事件间消息的传递方式。
为了避免"异常行为", 我们必须保证对于任意i、j、t，需要满足:Ci(t + μ) - Cj(t) > 0 (也就是说物理时间上靠后发生的事件，其逻辑时钟也靠后)。结合上面的两个条件PC1和PC2，当k、e、μ三个参数之间满足"e / (1 - k) <= μ "时，Ci(t + μ) - Cj(t) > 0成立。
也就是说上面的k、e、μ之间的不等式以及PC1和PC2，可以保证发生的物理时间点之间差值超过μ的事件，"加强时钟条件"成立，也就不会发生"异常行为"。从不等式"e / (1-k) <= μ"中可以发现，时钟间的误差e越大，"加强时钟条件"越不容易成立；时钟的速率与真实时间间的偏差k越大，"加强时钟条件"越不容易成立；两个事件间的间隔μ越大，"加强时钟条件"越容易成立。这与我们的直观感觉是相符的。
接下来，开始描述我们的算法如何保证PC2成立。m为在物理时间t被发送，在物理时间t`被接收的消息。定义Vm为消息m传递过程中的总延迟，当然对于接收消息m的进程是不知道这个延迟的。但是，我们假设接收消息的进程知道消息m传递的最小延迟μm，μm >= 0并且μm <= Vm。我们称ζm = Vm - μm为消息传递"不可预测的延迟"。
我们将逻辑时钟的实现规则IR1和IR2，为物理时钟特化为下面两条规则。
IR1`: 对于时钟i，如果Pi在物理时间t时没有收到消息，那么Ci是可微的并且dCi(t)/dt > 0。
IR2`: (a)如果Pi在物理时间t发送了带有时间戳Tm = Ci(t)的消息m。(b)当Pj在实际时间t1收到消息m时，进程Pj将其本地时钟Cj(t1)设置为max{Cj(t1 - 0), Tm + μm}。
虽然上述规则是根据物理时间作为参数来描述的，但是进程只需要知道他自身的时钟值以及收到的消息的时间戳。为了讨论方便，我们假设每个事件都发生在一个独立的物理时间，同一个进程的不同事件的发生时间不相同。因此上述条件IR1'和IR2'就是对于条件IR1和IR2的特化，因此我们的时钟系统是满足"时钟条件"的。实际上，真实环境中，事件都会持续一定时间，所以以上算法很容易实现。唯一需要注意的是，需要保证时钟的离散滴答声频率足够的快，以满足C1条件。
接下来我们介绍，这个分布式算法如何满足条件PC2。我们假设多进程分布式系统可以通过有向图来描述，其中从进程Pi到Pj的边表示一条通信线路，通过该通信线路消息可以在Pi和Pj之间直接传递。我们认为对于时间t，在t到t+ψ的时间内，都至少有一个消息在Pi和Pj之间传递。有向图的直径是任意两个不同进程Pj、Pk之间经过的边的最小边数d，也就是说存在一条Pj到Pj的路径经过最少d条边。
除了保证PC2条件的成立，下面的定理还说明了系统启动之后，可以进行时钟同步的下限。
定理：假设一个由多进程构成的强连通的直径为d的有向图遵守条件IR1'和IR2'。假设对于任意消息m，um <= μ，μ为常量，并且对于所有时间t(t >= t0): (a) 满足PC1. (b)存在常量ψ和常量ζ，每ψ秒一个消息会以小于ζ的"不可预期的延迟"在有向图的每条边上传递。当对于任意时间t ≥ t0 + ζd, e≈d(2kψ + ζ)时，满足PC2， 其中假设μ + ζ远小于ψ。
在这篇论文中，我们根据"happened before"概念定义了多进程分布式系统中不变的偏序关系。我们描述了一个算法将偏序关系扩展为一个任意的全序关系，并且展示了根据该全序关系可以解决一个简单的同步问题。未来我们会专门写一篇论文来说明这个方法可以用于解决任何的同步问题。
根据我们的算法得出的全序关系有点随意。当该顺序与系统用户所看到的顺序不一致时，会导致"异常行为"。这个问题可以通过正确的时钟同步来解决。我们的理论也表明了时钟同步的范围。
在一个分布式系统中，认识到事件发生的顺序只是一个偏序关系是非常重要的。它可以帮助我们去理解多进程系统中所遇到的一些基本问题。
http://loopjump.com/time_clock_order/
http://duanple.com/?spm=ata.13261165.0.0.7f356d086Cmhct&p=66
