Lamport 1978：先于关系怎样把分布式事件收成不靠墙钟的偏序

破除误解：编号不是时刻，全序也不是唯一历史#

第一层误解把逻辑时钟听成「把各机器的墙钟调准」。论文给分布式系统下的定义是：空间上分开的一集进程，靠交换消息通信；当消息传输延迟相对于单进程内事件间隔不可忽略，系统就是分布式的。ARPA 网被当作例子，一台计算机内部的控制器、存储器与通道也可以被看成进程。规格若用物理时间来写，系统里就必须有真实的钟，而真实的钟并不精确守时。于是先于关系被故意定义成不使用物理时钟。后来的网络时间协议处理的是另一件事：把振荡器读数约束到协调世界时附近。那份工程合同可以失败、可以分层、可以靠往返时延估计偏差，全部不进入 1978 年的时钟条件。把本页读成授时手册，等于把「事件的序」偷换成「此刻几点」。

第二层误解看见编号就读成「物理上更晚」。时钟条件只要求单向：若 \(a \to b\)，则 \(C(a) < C(b)\)。论文明确说，不能指望逆命题也成立，否则任意两个并发事件必须发生在同一时刻；再与进程内部的先后一拼，立刻自相矛盾。因此更大的逻辑时间戳不是「墙上更晚发生」，只是算法分配的编号。两个互不能因果影响的事件，编号谁大谁小并不携带物理先后。把编号当法庭时间线，会把论文拒绝给出的全序物理意义重新塞回去。

第三层误解把后来的向量时钟提前写进 1978 年。标量时钟满足时钟条件，足以把偏序延拓成全序，并拿这全序去排队。它不能精确刻画并发：你不能从 \(C(a)\) 与 \(C(b)\) 的大小读出「二者不可比」。1988 年 Colin Fidge、1989 年 Friedemann Mattern 各自给出 向量时间戳，使「先于」与时间戳上的偏序互相刻画。那是后文，不是本页的装置。本页若开始教人怎么维护 \(n\) 维计数器、怎么检测写冲突，就把对象换成另一篇论文。

第四层误解把全序听成「系统里真正发生过的那条唯一历史」，或听成共识协议已经选出的日志。论文写得很清楚：由时钟条件得到的全序依赖于这组时钟，并不唯一；不同的、都满足时钟条件的时钟给出不同的全序。任意一个延拓了先于关系的全序，都存在一组满足时钟条件的时钟把它实现出来。唯一由事件系统本身决定的，是那条偏序。资源互斥的例子只说明全序能用来陈述「请求按发出次序被授予」，对并发发出的请求，规格本身不指定谁先。把这例子读成可上线的锁，或读成 Paxos 的两阶段，类型就错了。把先于关系读成一份用来寻找交错漏洞的操作指南，同样错了：它是观察者应当承认的潜在因果，不是一份攻击步骤。

装置：先于、逻辑时钟与全序#

装置从进程开始。每个进程是一列事先全序的事件：子程序一次执行可以算一个事件，一条机器指令也可以算一个事件。发送与接收各是进程里的事件。先于关系 \(\to\) 是满足下面三条的最小关系。同一进程里 \(a\) 排在 \(b\) 前面，则 \(a \to b\)。\(a\) 是发送一条消息、\(b\) 是另一进程收到同一条消息，则 \(a \to b\)。传递性：若 \(a \to b\) 且 \(b \to c\)，则 \(a \to c\)。两个不同事件并发，当且仅当 \(a \not\to b\) 且 \(b \not\to a\)。关系被假定为反自反：一个事件先于自己，在物理上没有意义。于是 \(\to\) 是全体事件上的反自反偏序。论文给的第二种读法是：\(a \to b\) 意味着事件 \(a\) 有可能因果地影响事件 \(b\)；二者并发，则谁也不能影响谁。时空图画成进程竖线、消息波浪线。从 \(a\) 沿着进程与消息往「以后」走到 \(b\)，当且仅当 \(a \to b\)。

与狭义相对论的对照被写进正文，界限也写进正文。熟悉不变时空表述的读者会觉得这个定义自然，因为相对论里事件的序由可以发送的信号来定义。兰波特采取更实用的路线：只考虑实际发出的消息。判断系统是否按规格运行，应当只靠已经发生的事件，不必知道哪些事件本来可能发生。消息允许乱序到达。进程的粒度会改变接收事件的次序——中断置位与处理中断的子程序不是同一件事——因而「一个进程」本身已是建模选择。这些句子把装置钉在可观察历史上，而不是钉在光速锥的几何上。

逻辑时钟先被定义成抽象赋值：进程 \(Pi\) 的时钟 \(Ci\) 给该进程的每个事件一个数，系统时钟 \(C\) 在事件 \(b\) 上取值 \(C_j(b)\)。暂时不假设这些数与物理时间有关，计数器即可，不必有计时机构。正确性不能建立在物理时间上，否则又要把守时的钟偷运进来。最强而仍合理的条件是：若一事先于另一事，它应拿到更早的编号。正式写出即时钟条件。它由两条更局部的条件推出。C1：同一进程内的先后，编号严格递增。C2：一条消息的发送编号小于接收编号。时空图上，C1 说进程线上任意两事件之间必须夹一条「滴答线」，C2 说每条消息线必须穿过一条滴答线。滴答线可以被看成某种笛卡尔坐标的时间轴；把它们扳直，得到另一张看起来更「同时」的图。没有把物理时间引入系统之前，没有办法判决哪一张图更好。这正是同时性在本页里的位置：它是作图选择，不是测量结果。

把抽象钟安装成寄存器，论文给出两条充分规则。IR1：每个进程在相继两事件之间递增自己的 \(Ci\)。IR2：发送事件把当时的 \(Ci\) 写入消息时间戳；接收进程把 \(C_i\) 调到不小于当前值、并且严格大于该时间戳，接收事件发生在这次调整之后。规则保证 C1、C2，因而保证时钟条件。它们不是生产环境里如何处理溢出、落盘、闰秒或分层服务器的配方，只是使编号成为偏序的单调标记。改变寄存器本身不构成事件。

全序用编号加上进程之间任意预先约定的次序来打破平局。若 \(a\) 在 \(Pi\)、\(b\) 在 \(Pj\)，则 \(a \Rightarrow b\) 当且仅当 \(Ci(a) < Cj(b)\)，或者编号相等且 \(Pi\) 排在 \(Pj\) 前面。时钟条件立刻给出：若 \(a \to b\)，则 \(a \Rightarrow b\)。于是 \(\Rightarrow\) 是把先于偏序补全后的全序。补全不是发现「真正的历史」，只是选出一种与潜在因果相容的讲法。资源互斥被用来说明这种讲法能做什么。规格有三条：获准者必须先释放才能让给别人；不同请求按发出次序授予；若获准者终将释放，则每个请求终将被授予。中央调度按到达次序授权不够：\(P1\) 先请求再通知 \(P2\)，\(P_2\) 的请求仍可能先到达调度者。全序把「发出」从「到达」里救出来。每个进程本地维护请求队列，用 \(\Rightarrow\) 比较带时间戳的请求；一个进程可以取得资源，仅当自己的请求在该序下最早，并且已经从每个其他进程收到时间戳更晚的消息——从而知道所有先于自己这次请求的操作。论文随即把同一想法写成状态机：命令按时间戳排成同一序列，各进程独立模拟。它同时划出界限：这种方法要求每个进程知道别人发出的全部命令，单个进程停住就会让状态机无法继续。失败问题被明确标成超出本文范围。

异常行为来自系统外的因果。全国联网的计算机上，一人发出请求 \(A\)，再打电话让另一座城市的朋友发出请求 \(B\)。电话不在系统的消息集合里，逻辑时钟可能给 \(B\) 更小的编号。任何只看见系统内事件的算法，都无法保证把这条外部先后翻译进去。论文给出两条出路：把外部次序显式送回系统；或者构造满足强时钟条件的物理钟——对包含外部事件的更强先于关系，编号仍然严格递增。逻辑时钟一般不满足强时钟条件。物理时钟一节引入牛顿时空坐标作为证明用的背景时间，要求每只钟的速率接近一（PC1），彼此读数之差有界（PC2），并且只向前拨、永不回拨。它证明：在强连通、直径为 \(d\) 的进程图上，若每条弧上周期性发出不可预测延迟有界的消息，则同步误差可被写成直径、速率误差与延迟的乘积型上界。本页记录这个存在性界，不把 \(\mu\)、\(\tau\)、晶体频差写成可执行参数。1978 年也还没有后来的网络时间协议；论文引用的是更早的系统时间传播文献，用来标明物理同步是另一个题目。

它证明了什么，以及它没有证明什么#

它证明：系统内可观察事件上的先于关系是反自反偏序；并发就是互不能影响；逻辑时钟若服从 IR1 与 IR2，就满足时钟条件；满足时钟条件的编号加上进程次序，给出一条延拓了偏序的全序，而这样的全序并不唯一。它证明全序足以陈述一类不靠中央调度者到达次序的同步规格，并指出把全体命令排成同一序列的状态机图景。它证明物理钟在所述速率与通信假设下可被保持在一个与直径成正比的误差带内，从而使强时钟条件在外部因果足够慢时成为可能。它还留下一句后来被 FLP 写严的观察：失败这个概念只有在物理时间里才有意义；没有物理时间，停机与两次事件之间的停顿无法区分。用户觉得系统「崩溃」，往往只是等得太久。

它没有证明存在唯一的全局时刻，也没有证明逻辑编号的逆时钟条件。它没有给出向量时间戳，没有检测并发写的判定程序。它没有给出崩溃后仍能选定单一值的共识算法，因而既不是 Paxos，也不是 钱德拉–图埃格 的故障检测器，更不是 分布式系统 里某次超时怎么设。物理时钟定理假定牛顿坐标、强连通与周期性消息，不是相对论性授时，也不是把民用时拷进机房的步骤。互斥五条规则是课堂尺度的存在性说明，要求消息终达、同通道保序、进程集合固定、全体参与；缺一条就把「失败」从范围外放进来。本页因此停在序本身：先看见偏序，再看见一种不与偏序打架的编号，最后看见编号可以被补成全序。补全是约定，不是发现。

跨域连接#

• 时间哲学：兰波特把时间从「现在几点」还原成事件的次序，这与把时间看成关系而非容器的路线同构。麦塔加特的 B 系列正是「先于 / 后于」的固定关系，A 系列才是过去—现在—未来的流逝。逻辑时钟只实现 B 系列里那条可观察的「能影响」，并不生产一个全体共享的「现在」。并发事件没有谁在先，不是因为钟没校准，而是因为关系本身没有把它们排进去。把滴答线扳直得到另一张图，等于承认同时性是坐标选择。奥古斯丁问「现在」有没有厚度；本页的现在甚至不必存在：进程只保存一个整数，整数在事件之间被改写，改写本身不是事件。
• 狭义相对论：论文要读者去看不变的时空表述，随即划开界限。相对论的因果是光速信号可能连接的事件；兰波特的先于只统计实际发出的消息。光锥给出的是物理上的不可能影响，消息图给出的是这次运行里实际发生的影响。没有物理钟，两张时空图哪一张更「正」无法判决，这与同时性的相对性是同一类几何：横切的同时面不是世界里的物件。物理时钟一节为了写出速率与误差，仍借用牛顿坐标，并加脚注说若相对运动或引力不可忽略，必须从固有时变换到任意选定的时间坐标。装置因此不是把狭义相对论搬进机房，而是借用其序观念，再把「可能」收成「实际」。
• 因果：先于被定义成潜在因果，不是休谟要你在接球瞬间看见的那根力。你看见的是进程内部的排列，加上一条已经送达的消息。没有送达，就没有这条边；尚未送达的消息不能把接收端尚未发生的事件提前写进过去。并发不是「其实有隐藏的力，只是我们没测到」，而是规格承认的不可比。电话那则异常例子说明：系统外的因果不会自动成为系统内的边。把潜在因果读成必须在日志里找到的传递物，会把偏序误当成物证链；物证链要求实际留下痕迹，偏序只禁止「无路径却声称在先」。
• 认识论：进程 \(P\) 在收到消息之前，至多知道 \(Q\) 计划做什么，不知道 \(Q\) 已经做了什么。局部观察不是全局历史的知识。时钟条件保证的是：凡是已经进入潜在因果的事，编号不会颠倒；它不保证每个参与者都持有那条全序的抄本。全序是事后给观察者的一种补全，不是每个进程在每个时刻都已经知道的事实。把「我这边的计数器更大」当成「我已经知道世界的次序」，是把私人证据提升为公共知识。1978 年的装置拒绝这一跃。
• 知识：状态机图景看起来像所有人终于共享同一条命令序列，但它的前提是每个进程都知道别人发出的全部命令。一人缺席，知识闭包就拆开，模拟无法继续。这不是共识协议的安全性质，而是「全序要靠全体到场才能被本地核验」。失败与知识在这里绑在一起：若你不能用物理时间把「等太久」从「还在路上」里切开，你就不能把缺席写成已经确证的事实。后来的不可能性结果把这句观察写成定理；本页只把它当作序装置的边界，不把检测器或超时阈值提前安装进来。

参考文献#

• Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System", Communications of the ACM 21(7), 1978, pp. 558–565. DOI: 10.1145/359545.359563. —— 本文对象：先于偏序、逻辑时钟、全序延拓、互斥说明与物理时钟误差界。
• J. T. Schwartz, Relativity in Illustrations, New York University Press, 1962. —— 论文参考文献 [1]，用以对照不变时空表述与「只统计实际消息」的实用路线。
• Edwin F. Taylor & John Archibald Wheeler, Space-Time Physics, W. H. Freeman, 1966. —— 论文参考文献 [2]，狭义相对论时空图的教科书来源。
• Michael J. Fischer, Nancy A. Lynch & Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM 32(2), 1985, pp. 374–382. DOI: 10.1145/3149.214121. —— 把「失败相对物理时间才有意义」写成完全异步下的不可能性。
• Colin J. Fidge, "Timestamps in Message-Passing Systems That Preserve the Partial Ordering", Proceedings of the 11th Australian Computer Science Conference, 1988, pp. 56–66. —— 向量时间戳，用以标明本页标量钟不刻画并发。
• Friedemann Mattern, "Virtual Time and Global States of Distributed Systems", in Parallel and Distributed Algorithms, North-Holland, 1989, pp. 215–226. —— 与 Fidge 独立的向量时间，同样不是 1978 年的装置。
• C. Ellingson & R. J. Kulpinski, "Dissemination of System Time", IEEE Transactions on Communications 21(5), 1973, pp. 605–624. DOI: 10.1109/TCOM.1973.1091674. —— 论文参考文献 [4]，物理时钟文献入口；用来把本页与后来的网络授时协议分开。