分布式经典论文之一：分布式系统中的时钟、时间以及事件时序[序：时间是一个很抽象的概念，爱因斯坦说时间是幻觉，马赫(Ernst Mach)说：我们根本沒有能力以时间來测量事物的变化，相反的，我们是透过事物的变化因而产生时间流动的抽象概念。

那么在分布式系统中是如何定义时序的呢？这篇论文进行了讨论，该论文首先通过定义一整套逻辑时钟系统对所有事件进行ordering，然后通过解决一个资源互斥访问问题说明了如何将此应用到分布式系统中，并引入了状态机复制的方法。

之后又由逻辑时钟所存在的一个问题引出了物理时钟的使用，由于物理时钟本身会存在偏差，又给出了一个物理时钟同步算法，并给出了一个关于物理时钟同步的定理。

该论文于1978年7月发表在”Communication of ACM”上，并于2000年获得了首届PODC最具影响力论文奖，于2007年获得了ACM SIGOPS Hall of Fame Award 。

关于该论文的贡献是这样描述的：本文包含了两个重要的想法，每个都成为了主导分布式计算领域研究十多年甚至更长时间的重要课题。

1. 关于分布式系统中事件发生的先后关系(又称为clockcondition)的精确定义和用来对分布式系统中的事件时序进行定义和确定的框架。

用于实现clock condition的最简单方式，就是由Lamport在本文中提出的”logical clocks”，这一概念在该领域产生了深远的影响，这也是该论文被引用地如此之多的原因。

同时它也开启了人们关于vector 和matrix clock ，consistent cuts概念(解决了如何定义分布式系统中的状态这一问题)，stable and nonstable predicate detection，认识逻辑(比如用于描述分布式协议的一些知识，常识和定理)的语义基础等方面的研究。

最后，最重要的是它非常早地指出了分布式系统与其他系统的本质不同，同时它也是第一篇给出了可以用来描述这些不同的数学理论基础(“happen before”relation)。

2. 状态机方法作为n-模块冗余的一种通用化实现，无论是对于分布式计算的理论还是实践来说，其非凡的影响力都已经被证明了。

该论文还给出了一个分布式互斥协议，以保证对于互斥区的访问权限是按照请求的先后顺序获取的。

更重要的是，该论文还解释了如何将该协议用来作为管理replication的通用方法。

从该方法还引出了如下问题：a)Byzantine agreement，那些用来保证所有的状态机即使在出错情况下也能够得到相同输入的协议。

很多工作都是源于这个问题，包括fast protocols, impossibility results, failure model hierarchies等等。

b)Byzantine clock synchronization 和ordered multicast protocols。

这些协议是用来对并发请求进行排序并保证得到相同的排序结果，通过与agreement协议结合可以保证所有状态机都具有相同的状态。

关于这篇论文，作者Leslie Lamport自己有这样的描述：“Jim Gray曾经告诉我他听到的关于该论文的两种观点，一种是觉得该论文太普通了，另一种则认为该论文太绝妙了。

对此，我并不想争辩什么。

这篇论文的灵感实际上是源自于Paul Johnson和Bob Thomas写的一篇名为”The Maintenance of Duplicate Databases”的文章。

他们在这篇文章中提出了在分布式系统中为消息使用时间戳的想法。

只是因为我本身恰巧对狭义相对论有比较深刻的理解，这使我敏锐地察觉到他们所做的工作的本质。

狭义相对论告诉我们时空中的事件并不存在一个始终如一的全序关系；不同的观察者对两个事件谁先发生可能具有不同的看法。

当且仅当事件e2是由事件e1引起的时候，事件e1和e2之间才存在一个先后关系。

我意识到Paul Johnson和Bob Thomas采用的算法的本质是通过时间戳来提供一个事件的全序关系，而这本质上与事件间的因果关系是一致的。

这个想法实在是太绝妙了，意识到这点后，其他的都显得很简单了。

由于Paul Johnson和Bob Thomas并没有理解他们真正所在做的事情，因此他们的算法并不完全正确，那个算法允许一些会打乱因果关系的异常行为的发生。

我赶紧记录下了关于这个问题的这些想法，并修正了他们的算法。

之后，我很快就意识到该定义事件全序关系的算法可以用来实现任意的分布式系统。

一个分布式系统可以描述为一个特殊的具有多个由网络互联的处理器的串行状态机。

如果能够对输入请求进行全排序，就能够实现任何由网络互联的处理器组成的状态机，因此也就可以实现任意的分布式系统。

为了表明这一点，论文采用了一个我能想到的最简单的分布式系统实例—分布式互斥算法作为例子。

该论文也是我的论文中被引用最多的。

很多计算机科学家都声称读过。

但是我碰到的人中，很少有人意识到该论文在说状态机相关的东西。

看起来他们认为该论文是在讲分布式系统中事件的时序关系，或者是分布式互斥算法。

有些人还坚持声称该论文根本跟状态机无关，搞得我甚至重新回头读下这篇文章来确定我确实记得我写了什么。

该论文中描述了逻辑时钟的同步方法。

之后我又开始思考另一个问题，即真实时钟的同步问题，并由此引入了一个关于真实时钟同步的理论。

同时我也惊奇地发现要提供证明太困难了，当然这也为后面的Byzantine clock synchronization{!即论文Byzantine clock synchronization}提供了一些基础，只是那已经是另一个故事了。

”另外在一次采访中，当提问者问到“你认为你的哪个贡献对现代计算机科学与产业具有最大的影响力？”，Leslie Lamport 是这样回答的“我的引用量最多的文章是“Time, Clock, and Ordering of Events in a Distributed System”，我不知道这和你说的影响是不是一回事，因为我并不能从该文章直接指导出许多工作，但可能它影响了人们思考分布式系统的方法。

我认为我在工业界还没有太多影响，虽然我期望Paxos 和状态机方法将在分布式系统设计上有重要影响。

在微软内部已经可以看到这一点(Lamport 目前在微软研究院工作)”。

这个回答还是很谦虚的，随着海量数据处理需求的增加，在各种分布式系统大行其道的今天，Paxos及各种分布式算法已经发挥着越来越重要的作用，感觉也该给Lamport一个图灵奖了，只是不知道还要等几年。

除了这篇，Leslie Lamport还发表了其他一些关于time,clock 在分布式系统中应用的文章，”The Implementation ofR eliable Distributed Multiprocess Systems”(1978),”Using Time Instead of Timeout for Fault-Tolerant Distributed Systems”(1984),“Byzantine clock synchronization”(1984), “Synchronizing Clocks in the Presence of Faults”(1985)等。

另外看时钟同步这个问题，在该论文中也涉及了时钟同步技术的原理，方法及应用。

在该论文发表后的1981年，人们提出了Internet Clock Protocol(RFC 778)，这是最早提出的Internet时间同步协议；1983年提出了Time Protocol(RFC 868)，该协议可以精确到1s；1988年提出了NTP协议(Network Time Protocol RFC 1059)，在广域网内使用NTP 协议进行同步，可以达到几十毫秒的精度，在局域网内精度可以达到0.1毫秒；1996年，又提出了NTP协议的简化版SNTP(RFC 2030)，它可以用于对时间精度要求比较低的场景。

2000年11月，IEEE成立网络精密时钟同步委员会，2002年9月通过了IEEE 1588标准，IEEE 1588 PTP协议借鉴了NTP技术，具有容易配置·、快速收敛以及对网络带宽和资源消耗少等特点。

IEEE1588标准的全称是“网络测量和控制系统的精密时钟同步协议标准(IEEE 1588 Precision Clock Synchronization Protocol)”，简称PTP(Precision Timing Protocol)，基本构思是通过硬件和软件将网络设备（客户机）的内时钟与主控机的主时钟实现同步，提供同步建立时间小于10μs的运用(应该是单链路内的)，与未执行IEEE1588协议的以太网延迟时间1000μs相比，整个网络的定时同步指标有显著的改善。

近来Google发表的Spanner中提到的TrueTime API，这也是实现该系统各重要feature的基础。

要真正理解TrueTime API在这篇论文中的重要意义，就得了解为何要得到事件的一个全序关系，得到这样的关系可以做什么，以及如何得到这样的一个关系。

读完这篇论文，就能发现其实早在30多年前Leslie Lamport就开始考虑这些问题，而且当时的思考已经非常深刻，即使是在今天看来，这些思考依然是如此深刻和富有远见。

而关于时钟同步这个问题，实际上历史要更为悠久，即使是在Leslie Lamport发表这篇论文时，人们已经进行了非常多的研究。

]摘要在本文中我们审视了分布式系统中，某事件发生在另一事件之前这一概念，并展示了如何用它来定义事件间的偏序关系(partial order)。

给出了一个可以对具有逻辑时钟的系统进行同步的算法，通过逻辑时钟可以得到事件的全序关系(total ordering)。

通过作为解决同步(synchronizing)问题的一种方法，我们展示了total ordering的使用方法。

进一步地，该算法还可以被特化用来解决物理时钟的同步问题，同时我们推导出了时钟可能达到的不同步的一个误差范围。

关键词：分布式系统计算机网络时钟同步多进程系统导引对于我们的思维来说，时间是一个非常基础的概念。

它实际上源于更基础的概念--事件发生的顺序。

如果某件事情在我们的时钟指示在3:15且还未指示3:16之前，我们就是这件事发生在3:15。

事件的时序概念遍布在我们对系统的思考中。

比如，在一个航线预订系统中，我们会这样表述，如果预订请求是在该航线被分配出去之前发出的，那么该请求应该得到授权。

但是，我们将看到对于分布式系统中的事件来说，需要对这个概念重新仔细地进行审视。