Fidge–Mattern：分量时间戳怎样把并发从标量编号里认出来

破除误解：多一只计数器不是更准的时刻#

第一层误解把向量时钟听成「把兰波特的钟装成一排，于是更接近真实时间」。装置的要点不是提高对民用时的逼近，而是改比较方式。标量钟把全体事件投到一条数轴上，任何两个编号都能比出大小，于是并发被投影成先后。向量钟把每个进程自己的事件计数留在自己的分量里，比较改成乘积序：所有分量都不更大、且至少一处严格更小，才叫「早于」。两个向量谁也不小于谁，就停止比较。停下来不是校准失败，而是算法承认这两件事互不能影响。把本页读成授时手册，等于把「不可比」偷换成「还没对表」。

第二层误解看见某个分量更大，就读成「物理上更晚」。分量 \(i\) 只统计进程 \(Pi\) 已经执行过、并且已被当前事件所知的事件个数。\(Pj\) 的计数器狂跳，只说明 \(Pj\) 本地发生了许多事，或者沿某条消息路径听到了这些事；它不给 \(Pi\) 的沉默事件颁发物理时刻。两个不可比的向量可以在某一维上差很多。把「第三号分量是 17」当成法庭时间线，会把论文拒绝给出的全序物理意义重新塞回去。标量 逻辑时钟 已经警告过逆时钟条件不成立；向量钟并没有撤回那条警告，它只是换了一套不会强迫你排出先后的标记。

第三层误解把 1978 年的全序延拓提前写成「已经能检测并发」。兰波特很清楚：若要求 \(C(a)<C(b)\) 当且仅当 \(a\to b\)，则任意两个并发事件必须同一时刻发生，再与进程内部的先后一拼立刻自相矛盾。因此 1978 年的装置满足时钟条件就够了，全序靠进程名打破平局。菲奇的标题把缺的那一块写在纸面上：时间戳应当保持偏序，而不是只保持它的某个线性延拓。马特恩把同一事实说成虚拟时间本身是偏序。十年间隔不是同一篇论文的修订，是对象换了。

第四层误解把后来的副本版本向量、追踪插桩或冲突合并菜谱读回 1988 与 1989 年。菲奇的动机是调试消息传递程序时，不要在日志里发明本不存在的因果。马特恩的动机是给全局状态一个不靠墙钟的偏序坐标。二者都不规定生产系统里向量如何截断、如何随成员变动而伸缩、如何把两个购物车并成一单。那些是后代文献与工程合同。把本页读成「怎样给线上服务打点」或「怎样从交错里取出可利用的窗口」，类型就错了：它是观察者应当承认的潜在因果标记，不是一份操作指南。

装置：分量递增、接收取最大、不可比即并发#

装置仍从先于关系出发，本页不重推 1978 年的三条。同一进程里排在前面的事件先于后面的事件；发送先于对应的接收；关系传递。两个不同事件并发，当且仅当谁也不先于谁。标量钟给这条偏序一个单调编号；向量钟给它一个忠实编号。设进程集合固定为 \(P1,\ldots,Pn\)，每个进程 \(Pi\) 持有长度为 \(n\) 的整数向量 \(VTi\)，初值全零。比较采用乘积序：\(u\le v\) 当且仅当每个分量都有 \(u[k]\le v[k]\)；\(u<v\) 当且仅当 \(u\le v\) 且两者不等。两个向量不可比，当且仅当两边的 \(\le\) 都不成立。

局部规则只有三条，写的是计数器怎样动，不是报文格式怎样落地。进程 \(Pi\) 每发生一个内部事件或发送事件，先把 \(VTi[i]\) 加一；若是发送，把当前向量写入消息。接收时先做分量取最大：对每个 \(k\)，令 \(VTi[k]\) 为本地值与消息时间戳在第 \(k\) 位上的较大者；然后把 \(VTi[i]\) 再加一，接收事件发生在这次调整之后。自己的分量只由自己递增，别人无权改写你的计数；别人能做的，是经消息把「我已见到的各分量上界」送过来，由取最大并入。改变寄存器本身仍不构成事件。不同论文对「先加一再合并」的书写顺序略有出入，只要「每个事件都让本进程分量严格增加、接收吸收对方已知上界」这两条齐备，乘积序就与先于关系同向。

忠实性是装置的中心定理。对任意两个事件 \(e\) 与 \(f\)：\(e\to f\) 当且仅当 \(VT(e)<VT(f)\)；\(e\) 与 \(f\) 并发，当且仅当 \(VT(e)\) 与 \(VT(f)\) 不可比。还有一条常被用来少做几次全向量扫描的推论：若 \(e\) 发生在 \(Pi\)，则 \(e\to f\) 当且仅当 \(e\neq f\) 且 \(VT(e)[i]\le VT(f)[i]\)。直观很硬：\(VT(e)[i]\) 是 \(Pi\) 执行到 \(e\) 为止的本地事件数；任何先于 \(f\) 的 \(e\) 都必须已经被 \(f\) 那条因果路径「听说」，因而 \(f\) 的第 \(i\) 分量至少那么大。反过来，若 \(f\) 的第 \(i\) 分量已经不小于 \(e\) 的本地计数，则 \(e\) 已进入 \(f\) 的过去。标量钟给不出这句「当且仅当」。它可以保证先于则编号更小，但不能从两个整数读出不可比。

一个最小画面就够把两者分开。\(P0\) 与 \(P1\) 从 \([0,0]\) 出发。\(P0\) 发送，时间戳 \([1,0]\)；\(P1\) 先做一次内部事件，得到 \([0,1]\)，再收到那条消息：取最大得 \([1,1]\)，本分量加一得 \([1,2]\)。发送与接收可比：\([1,0]<[1,2]\)。\(P0\) 发送之后又做一次内部事件，得 \([2,0]\)。\([2,0]\) 与 \([1,2]\) 谁也不小于谁：第一分量 2 不小于 1，第二分量 0 却小于 2。它们并发——\(P0\) 的第二次内部事件并未进入那条已发出的消息，\(P1\) 的接收也没有回到 \(P0\)。标量钟在同一段历史上完全可以给这两个事件贴上相同或任意先后的整数，再用进程名打破平局，于是日志里会出现一条系统从未承诺的「谁先谁后」。向量钟在这里停住，不发明那条边。

马特恩把同一只时间戳从成对事件抬到全局状态。一条割选取每个进程的一个前沿事件；它一致，当且仅当它在先于关系下左封闭：若 \(b\) 落在割里且 \(a\to b\)，则 \(a\) 也在割里。用向量写出：对所有 \(i,j\)，进程 \(j\) 前沿所携带的第 \(i\) 分量，不得超过进程 \(i\) 自己已经执行到的计数。直观是：割里不能出现「我已经收到你尚未发生的发送」。全体一致割在「前沿分量取最大 / 取最小」之下构成格。虚拟时间因此不是数轴上的一点，而是这座格里的一个元素；两个一致全局状态有上确界与下确界，观察者可以沿覆盖关系一格一格往前走，而不必先把并发投影成全序。这与 钱迪–兰波特快照 是相邻对象：快照算法用标记消息去构造一条一致割，向量时间用来判定一条已经写下的割是否一致。本页不把标记如何沿通道走写成步骤。

装置的代价也写在纸面上：每条消息携带 \(n\) 个整数，比较与取最大都随进程数增长。两文都假定进程集合事先已知且固定。成员加入、离开、计数器截断，属于后来的版本向量、点分版本向量与区间树钟文献，不是 1988 与 1989 年证明里的参数。菲奇 1991 年在 IEEE Computer 上又写过一篇面向实现者的综述，把时间戳规则讲得更顺；那是解说，不是把会议文换成另一套定理。

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

它表明：在固定有限的进程集合上，分量递增与接收取最大足以让时间戳的乘积序与先于偏序互推；并发因此是可判定的关系，判定依据是向量不可比，而不是「两个标量碰巧相等」。它表明标量 逻辑时钟 所放弃的那条逆命题，可以用更高维的标记收回，而不必引入墙钟。它表明（马特恩）一致全局状态不是一条时间线上的切片，它们构成格；「现在」若有意义，也只相对于一座格里的一个元素，而不是相对于全体进程共享的唯一时刻。它还表明两份独立的论文可以到达同一套计数器：调试痕迹的人要的是不要发明因果，研究全局状态的人要的是给割一个坐标，装置重合，问题意识并不重合。

它没有表明存在唯一的全局时刻，也没有把物理同时性送回系统。它没有给出崩溃后仍能选定单一值的共识算法，因而既不是 Paxos，也不是 钱德拉–图埃格 的检测器分级，更不是把 FLP 的完全异步模型改写成「有了向量就能终止」。向量在消息延迟任意、进程可能永久沉默时仍然可以局部推进；它不把「等太久」从「还在路上」里切开。它没有给出动态进程集合上的有界时间戳，没有给出矩阵钟、布隆钟或截断规则的正确性证明。它没有规定副本冲突该如何合并：检测「两写并发」与决定「并集还是取最小」是两件事，后者是业务语义，前者才是这套偏序所能说的全部。物理授时、闰秒、分层服务器与晶体频差仍在范围外。本页因此停在标记本身：先看见偏序，再看见一种不把不可比投影成先后的编号。编号是坐标，不是发现出来的历史。

跨域连接#

• 时间哲学：麦塔加特的 B 系列是「先于 / 后于」的固定关系，A 系列才是过去—现在—未来的流逝。标量逻辑钟把 B 系列延拓成一条全序，看起来像给了每个事件一个「更早 / 更晚」的位置，却仍不生产 A 系列里那个全体共享的「现在」。向量钟连这条延拓也拒绝：并发事件在 B 系列里根本没有先后，标记必须把缺口留在纸面上。马特恩的格比数轴更接近一种不流逝的时间观——格的元素是一致全局状态，覆盖关系是「再收入一个事件」，没有一个元素配得上「全世界的此刻」。奥古斯丁问「现在」有没有厚度；这里的现在甚至不必是一条横切线，它只是观察者选中的一个一致割。把向量里较大的那个分量读成「已经进入未来」，是把 B 系列的缺口重新填成 A 系列的流逝。
• 狭义相对论：兰波特已经提醒读者去看不变的时空表述，并划开「可能发出的信号」与「实际发出的消息」。向量钟把这张图的类空部分写进了可计算的标记：两个不可比的时间戳，对应消息图上互不进入对方过去的一对事件，正如类空间隔上没有信号能把谁变成谁的原因。光锥给出物理上的不可能影响；消息图给出这次运行里实际发生的影响。乘积序不是闵可夫斯基度规，分量也不是时空坐标，但几何同构是清楚的——同时性不是世界里的物件，不可比才是。把所有事件排成全序，等于强行选一张同时面，再把类空事件投影到面上假装有先后。菲奇要保持的偏序，正是拒绝这张假装。
• 因果：休谟盯住台球，说我们看见的是先后相随，看不见那根力。先于关系比休谟更窄：没有送达的消息，就不许画那条边。向量钟把「不许画边」做成两个向量的不可比，于是因果在这里不是恒常连接，也不是必须在日志里找到的传递物，而是潜在影响的闭包。检测并发不是发现隐藏的力，而是承认规格里本来就没有这条边。电话那则系统外因果的旧例子对向量钟同样有效：系统没看见的先后，不会因为多了 \(n-1\) 个分量就自动出现。把不可比读成「其实有因果，只是钟还不够密」，是把装置的否定判断误当成测量误差。
• 集合论：乘积序是偏序集上最普通的构造之一：\(n\) 个全序的笛卡尔积，按分量同时比较。不可比不是缺陷，是积序相对全序多出来的结构。马特恩的一致割在包含关系下构成格，有限偏序集的格论在这里不再是习题：上确界对应「两边都已发生的那些事件再并起来」，且并完仍左封闭。线性延拓定理保证任何偏序都能被补成全序，1978 年的标量钟加进程名就是在做一次延拓；保持偏序的时间戳要的是同构，不是延拓。读者若只记住「向量比整数更细」，会把格收缩回全序，装置最贵的那一笔就白付了。
• 认识论：进程 \(Pi\) 的第 \(j\) 分量是一份局部知识：我目前所知的 \(Pj\) 至多执行到第几号事件。取最大是知识的并，不是发现一个外在的全局事实。没收到消息之前，\(Pi\) 不能把 \(Pj\) 的沉默翻译成「什么也没发生」，只能翻译成「我不知道」。向量不可比意味着两份局部知识谁也不能覆盖谁，任何一方把对方的事件写进自己的过去都是越权。公共知识更远：全体向量两两可比，也不等于每个人都知道别人已经知道。本页的装置停在「我是否可能被你影响」，不把私人证据提升为大家都知道的时刻表。

参考文献#

• Colin J. Fidge, "Timestamps in Message-Passing Systems That Preserve the Partial Ordering", Proceedings of the 11th Australian Computer Science Conference, University of Queensland, 1988, pp. 56–66. Also Australian Computer Science Communications 10(1), 1988. —— 本文对象之一：保持偏序的消息时间戳。
• Friedemann Mattern, "Virtual Time and Global States of Distributed Systems", in M. Cosnard et al. (eds.), Parallel and Distributed Algorithms, North-Holland, 1989, pp. 215–226. —— 本文对象之二：向量虚拟时间、一致割与全局状态的格。
• 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. —— 标量逻辑时钟与先于偏序；向量钟要收回的是其逆时钟条件。
• Colin Fidge, "Logical Time in Distributed Computing Systems", IEEE Computer 24(8), 1991, pp. 28–33. DOI: 10.1109/2.84874. —— 作者本人对时间戳规则的后续解说，不是 1988 年会议文的替换。
• K. Mani Chandy & Leslie Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems", ACM Transactions on Computer Systems 3(1), 1985, pp. 63–75. DOI: 10.1145/214451.214456. —— 用标记消息构造一致割，对象页见 分布式快照；与马特恩的判定性坐标相邻，不是同一份装置。
• Reinhard Schwarz & Friedemann Mattern, "Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail", Distributed Computing 7(3), 1994, pp. 149–174. DOI: 10.1007/BF02278855. —— 因果检测后续综述，用来标明本页停在 1988/1989 的计数器本身。