FinCloud-
本文是读完Paper（本文中Paper特指《Time, Clocks and the Ordering of Events in a Distributed System》，下同）后的一些感想，不是译文（推荐阅读原文），感想也纯属一家之言，欢迎指正。
本文按照以下结构组织：首先简单总结下本次阅读的Paper的背景、主要内容和影响；其后介绍下本人读完paper后的一些感想。感想部分主要包含了
读过paper的可以直接跳到感想部分。
本Paper是 Leslie Lamport 老爷子在1978年的时候写的，虽然已经是41年前的Paper了，但是Paper挖掘了分布式系统中的时间的本质，并结合 狭义相对论 进行深入的分析，给人一种醍醐灌顶的感觉。Paper中提出的"happened before"，Logical Clocks，The Partial Ordering，Replicated State Machine等是目前整个分布式理论的基础。本Paper对于现代分布式理论的意义不亚于狭义相对论之于现代物理学。
本Paper在Google Scholar中的引用数为11231，最早发表于“Communication of ACM”，后分别获得了“2000 PODC Influential Paper Award”以及“ACM SIGOPS Hall of Fame Award in 2007” [1]
本Paper的几项重要贡献
本Paper大致分为如下几部分：
这部分提出了分布式系统中的时间问题。我们生活中感知的事件（Event）发生的先后是依赖于时钟的，而分布式系统 “A distributed system consists of a collection of distinct processes which are spatially separated, and which communicate with one another by exchanging messages.” 中很难包含一个实际的时钟（Wall Clock），同时在多个不同process中的时钟往往不够精确，因此在分布式系统中必须有一套独立的算法来解决时间问题。
分布式系统中如果没有实际的时钟，那么我们能依赖的就只有Happened Before了，即在某些条件下，我们可以确定event A一定在event B之前发生。这里有一个非常重要的理念： 在分布式系统中，我们能依赖的只有这种部分事件之间的Happened Before关系，也就是Partial Ordering 。在分布式系统中有2种情况是可以建立起Happened Before关系的：
Figure 1中由下往上是时间的流逝，自左往右是不同的空间中的process。Figure 1中的有些event之间是有直接（p1 -> q2）或者间接（p1 -> r3）的happened before关系的；而有些event之间是没有的（p3和q3），因此我们无法确定p3和q3之间的顺序，所以我们说p3和q3是并发的。
Happened Before的理论和 狭义相对论 中的物理世界中的观念十分的类似，即event的先后是相对的，在实际世界中的不同惯性坐标系下，2个event的先后关系可能发生变化。不过Paper中没有深入的对比，我会在 感想 部分中深入讨论下
其实对Happened Before和Partial Ordering的理解才是最重要和最难的，有了Partial Ordering的概念，我们很容易理解Logical Clocks。即我们指定一个全局的逻辑的时钟规则C(x)，以保证
这个时钟的规则也相对比较简单
以上规则分别体现了2个Happened Before关系。
既然知道了我们唯一能确定的就是Happened Before关系，但是我们在解决现实问题的时候，往往会用到全局序（Total Ordering）。那么我们可以预定义一个process之间的顺序，假设当event的逻辑时间相等时，process1的event永远先于process2的，那么我们就可以确定一个全局序。 这里要强调的是Partial Ordering是唯一的，而Total Ordering是不唯一的。
本章举了一个在没有Coordinator的情况下的，分布式临界资源算法。 注意这里的分布式临界资源是指没有统一协调者，没有统一等待队列的，需要多个process互相协商的算法。 这个算法非常重要，因为这是一个无中心的分布式算法（2PC是有中心的，才有block问题）。几乎所有的无中心分布式算法都是从这个算法演化而来的。同时我们可以通过状态机（State Machine）的思想，将该算法演变成一个完整的分布式系统。Lamport在这里提出的State Machine方案是一个被后人忽视的，但是却十分重要的贡献，甚至在很长时间内大家都没意识到paper中有这方面的贡献，老爷子后来的自述中也提到：
篇幅原因，这个分布式临界资源算法的细节大家参考原文的，有问题可以讨论。
上面定义的Logical Clocks有一些反常的行为，例如我们定义的Total Ordering是process 1 < process 2的，那么event a(from process 1)和event b(from process 2)的逻辑时间虽然相等，但是在Total Ordering中是C(a) < C(b)。但是现实生活中event a和event b可能是人操作产生的，而event b的操作员操作完成后打电话给event a的操作员操作的。那么Logical Clocks就显著违背了事实。其主要原因是b happened before a这个关系是在非本系统的外部系统中产生的，本系统不掌握这个情况，所以导致了反常。
为避免这种反常，有2中解法：
Paper中基于Logical Clock的整体理论，将逻辑时钟的产生替换为了物理时钟，并处理了2个主要时钟误差和其矫正方法：
从Lamport总结的分布式系统的时空观和狭义相对论中物理世界的时空观有着惊人的相似。
以上理论在所有的洛伦兹变换的惯性坐标系中都是成立的，我们可以以一下的方式直观的理解下：
Spanner中的True Time和本Paper中最后的Physical Clocks非常的相似。但是本文中的Physical Clocks是有一些限制的例如时钟不能倒退，同时通过系统内的message进行时钟修正，这也是在当时的硬件条件下的理想方案，而True Time通过系统外的消息进行修正（GPS），同时优化了协议。
同时根据狭义相对论，因为物理的时钟也是偏序的，只有可能在限制物理范围，并且保证event间间隔的情况下才有可能变成全局。 因此完整的True Time理论严格来说应该有这部分的论证。
由此想到的很多经典论文中的方案，可能当时来看是难以实现的，但是随着硬件的发展，稍加优化以后，可能会带来系统性的突破。
从本质上来说文章的Logical Clocks和Physical Clocks本质上是一样的都是 通过消息来产生Happened Before的偏序，再依赖这个偏序确定整个系统的因果序/全序 。虽然我们从狭义相对论中知道，“当2个事件只要在光可到达的时间差外先后发生，那么它们就有因果关系”，但是2个物理时钟并不能因此产生同步，还是需要有外部机制来产生同步，例如：NTP，GPS。可惜的是在1978年 NTP（1988年）和GPS（1989年商用）都还没发用，所以Lamport设计了这个时钟同步的雏形算法。
2者的不同是：
说到这里必须要提HLC了，HLC本质上是Logical Clocks而非Physical Clocks，这个下篇文章详细说吧
分享好知识！