形式陈述

在含 $n$$n$ 个进程的标准消息传递模型中，每个进程 $i$$i$ 维护初始为全零的向量 $V_i\in\mathbb N^n$$V_i\in {\mathbb{N}}^n$。本地或发送事件前递增自身分量；消息携带向量；进程 $i$$i$ 收到向量 $W$$W$ 时先取逐分量最大值，再递增自身分量：

$$ V_i\leftarrow\max(V_i,W),\qquad V_i[i]\leftarrow V_i[i]+1. $$$$V_i\leftarrow max(V_i,W),V_i[i]\leftarrow V_i[i]+1.$$

定义 $u\le v$$u\le v$ 为逐分量不大于，$u<v$$u<v$ 为 $u\le v$$u\le v$ 且 $u\ne v$$u\ne v$。对事件时间戳 $V(a),V(b)$$V(a),V(b)$，在该模型及规则下

$$ a\to b\quad\Longleftrightarrow\quad V(a)<V(b). $$$$a\to b⟺V(a)<V(b).$$

两个向量不可比当且仅当相应事件并发。

直觉

向量的第 $j$$j$ 个分量记录当前事件已知的进程 $j$$j$ 历史进度。逐分量比较因而能判断一份因果知识是否完整包含另一份，而单个整数只能保序、不能反推因果。

例子与边界

若 $V(a)=(2,0)$$V(a)=(2,0)$、$V(b)=(0,3)$$V(b)=(0,3)$，二者不可比，表示并发；若 $V(c)=(2,4)$$V(c)=(2,4)$，则前两者都先于 $c$$c$。精确等价依赖固定进程身份、可靠事件规则和标准 happened-before 模型；动态成员、压缩时钟或共享内存变体需重新陈述保证。

推论与应用

向量时钟用于因果广播、版本向量、冲突检测和分布式调试。其主要代价是时间戳通常含每个进程一个分量，即 $\Theta(n)$$\mathrm{\Theta }(n)$ 空间；稀疏表示和矩阵时钟在不同工作负载下作进一步权衡。

参考资料

• Friedemann Mattern, “Virtual Time and Global States of Distributed Systems,” in Proceedings of the Workshop on Parallel and Distributed Algorithms, 1989, pp. 215–226，Full paper。
• Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996，Ch. 6。