逻辑时钟：Lamport 时间与向量时钟

不同机器的物理时钟存在偏差，即使通过时间同步减小误差，也不能把时间戳比较直接当成所有事件的因果证明。本文从课程笔记整理，讨论协议如何描述事件顺序。

Happens-before 是偏序

同一进程中先发生的事件，先于后发生的事件；发送消息先于接收该消息；这个关系具有传递性。记作 \(a\rightarrow b\)。

若两个事件之间没有任何方向的因果关系，就称它们并发。这里的并发表示因果不可比较，不要求物理时间完全相同。

Lamport 时钟保留因果顺序

每个进程维护整数计数器。本地事件递增；发送消息附带时间戳；接收时间戳 \(T_m\) 时：

\[C_j\leftarrow\max(C_j,T_m)+1\]

该规则保证：

\[a\rightarrow b\;\Rightarrow\;C(a)<C(b)\]

反过来不成立。两个没有通信联系的进程，也可以分别拥有 2 和 10 这样的时间戳，不能据此推出前一个事件导致了后一个。

把进程标识加在时间戳后面，按字典序比较，可以构造全序。它保留已有的因果先后，并给并发事件安排确定次序；这个额外次序是协议选择。

经典起点是 Lamport 的 Time, Clocks, and the Ordering of Events in a Distributed System。

向量时钟保留更多信息

固定成员系统中，每个进程维护一个向量。每个分量记录所知的相应进程事件进度。接收消息时逐分量取最大值，再递增接收者自己的分量。

若 \(V(a)\) 的所有分量不大于 \(V(b)\)，且至少一个更小，记作 \(V(a)<V(b)\)。在标准模型下，这能刻画 happens-before。

两个向量	判断
\((1,0)\) 与 \((2,1)\)	前者因果先于后者
\((2,0)\) 与 \((1,2)\)	分量互有大小，事件并发

向量增长带来存储和通信开销，成员加入退出也需要额外设计。

时间戳不是完整协议

给消息排序并不意味着接收方已经知道所有更早消息都到齐。全序交付、故障恢复和成员管理仍需要协议机制。

阅读日志或复制算法时，应区分三个问题：时间戳保留什么顺序、节点如何获知缺失消息，以及何时可以安全地应用更新。