Lecture 11: Time and Ordering — 物理时钟同步、Lamport 时钟与向量时钟

目录 · ← l10 · l12 →

Lecture 11: Time and Ordering — 物理时钟同步、Lamport 时钟与向量时钟

讲义对应：CS 425 FA2026 Lecture 11（9/29：Consistency Models + Time and Ordering 开始）与 Lecture 12（10/1：Time and Ordering — Lamport Timestamps / Vector Timestamps）。本章完整覆盖原始讲义 L12.FA25.pdf（共 60 页）的全部技术内容：Why Synchronization（公交车与云订票例子）、异步系统模型、Clock Skew vs Clock Drift、Maximum Drift Rate、External/Internal Synchronization、Cristian’s Algorithm、NTP、Happens-Before、Lamport Timestamps、Vector Timestamps；其中”一致性模型”部分归属 Ch.10，本章不重复。 教材对应：Coulouris 5th Ed. Ch. 14 Time and Global States（Sec 14.1–14.4）；补充：Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, CACM 1978；Fidge（1988）与 Mattern（1988）的向量时钟；Mills 的 NTP（RFC 5905）；Google Spanner TrueTime（OSDI 2012，Corbett et al.）；Kulkarni et al., Logical Physical Clocks and Consistent Snapshots（HLC, 2014）；Charron-Bost（1991）关于因果时钟维数下界的定理。 阅读材料：Lamport 1978 原文（全课程最值得精读的一篇，仅 8 页，本讲全部逻辑时钟部分的思想来源）；Dynamo 论文（SOSP 2007）中向量时钟检测并发写的一节；讲义提到的 Riak 键值存储的 sibling 冲突处理（见 Ch.9）。

11.1 概述

本章要回答一个看似幼稚、实则贯穿整门课的问题：在分布式系统里，事件 A 和事件 B 谁先发生？ 在单机上这个问题毫无难度——所有进程共享同一个系统时钟，读一次时间戳即可；但在互联网与云里，每台端主机有自己的晶振，它们以略微不同的频率走时，而消息延迟又没有任何上界。于是”读物理时钟来排序”这条最自然的路在原理上就是不可靠的：你可以把时钟调得足够准，但永远调不到准确。

本讲给出两条解决路线：第一条是把时钟调准——Cristian 算法与 NTP 通过测量往返时间（RTT）来估计偏移，把误差压到 RTT 的一半以内；第二条、也是更深刻的一条，是干脆不要物理时间——Lamport 在 1970 年代提出的 happens-before 关系 $\rightarrow$ 与 Lamport 逻辑时钟，让时间戳只服从因果性，不服从真实时间；随后向量时钟（Vector Timestamps）用 $O(N)$ 的空间把因果性刻画得精确而完整，连”两个事件并发”都能判定。

本章在课程中处于”时间与一致性“这一支柱的核心：它向前承接 Ch.9 中 Cassandra 用物理时间戳做 last-write-wins 的冲突解决（当时我们说”这是物理时钟不可靠性的直接代价”，本章会把它讲透），向后为 Ch.12 的 Chandy-Lamport 全局快照、Ch.13 的全序多播（total-order multicast）、Ch.14 的 Ricart-Agrawala 分布式互斥、Ch.15–Ch.17 的共识算法提供最底层的顺序基础设施。

一句话概括本章的哲学：

时间在分布式系统中不是被测量的，而是被构造的。 物理时钟给出”接近真实但永不可靠”的时间；逻辑时钟给出”不真实但绝对可靠”的因果顺序。选哪一个不取决于哪个更”对”，而取决于你要解决的问题究竟需要”真实时刻”还是只需要”先后关系”。

11.2 核心概念与分布式机制图解

11.2.1 为什么需要时间同步（Why Synchronization?）

定义与目的：时间同步（time synchronization）是指让分布式系统中多个进程的本地时钟在数值上彼此接近（或与某个外部权威时钟接近）的过程。它的目的不是”让时间精确”，而是让不同机器上的时间戳可以被合理地比较。
直观解释（”它是什么？”）：讲义用了一个极其朴素却精准的例子——你要赶 18:05 的公交车，但你手表的误差是 15 分钟：

   情况 1: 手表【慢】15 分钟
   ────────────────────────────────────────────────────────────────►
        真实 18:05  公交车到站、离站
        手表 17:50  你以为还有 15 分钟 → 慢悠悠走过去 → 车已经走了
        ✗ 后果: 你错过了车          → 损害【正确性 Correctness】

   情况 2: 手表【快】15 分钟
   ────────────────────────────────────────────────────────────────►
        真实 17:50  你按"18:05"赶到站台 → 车还没来
        手表 18:05
        ✗ 后果: 你在站台白白多等了 15 分钟 → 损害【公平性 Fairness】

关键结论：时间同步同时关系到正确性与公平性。讲义把这两点并列提出，是很有分量的：很多人直觉认为”时钟不准只是精度问题、慢一点没关系”，但实际上”慢”会让系统做出错误的判断（错过本该发生的事），”快”会让系统做出不公平的资源分配（某个进程多占了本不属于它的时间窗口）。在真实的分布式系统里，这两类后果都有对应物——

时间不同步的后果	真实系统中的例子
正确性受损（表慢了）	分布式锁的租约（lease）提前被另一个进程认为过期，两个进程同时进入临界区
正确性受损	日志时间戳错乱，导致运维/审计无法重建故障时间线（本章的云订票例子）
公平性受损（表快了）	令牌桶/限流器按本地时间放行，快时钟的机器获得更多配额
公平性受损	计费系统按本地时间切片，慢时钟的租户”少付钱”
两者都受损	TLS 证书有效期校验、Kerberos 票据有效期、跨集群事务的时间戳排序

机制图解：把”同步”画成两条各自走动的数轴，同步就是把它们的差值重新压小。

   进程 P1 的时钟: ────●────────────●───────────●────────►  (走得稍快)
   真实时间/UTC  : ────┼────────────┼───────────┼────────►
   进程 P2 的时钟: ──────●───────────●────────────●──────►  (走得稍慢)
                        ▲
                        └── skew: 同一真实时刻两个时钟读数之差
                            drift: 两条数轴斜率之差 → skew 随时间增大

关键假设与系统模型：我们假设存在一个”正确的”时间参照（UTC），但它只作为定义精度的基准，不假定任何进程真的拥有它；进程之间只能通过消息交换来互相校正。

11.2.2 云订票系统：被时钟颠倒的因果（Synchronization In The Cloud）

这是讲义给出的第一个、也是最重要的动机例子。它值得逐句还原并逐层解剖，因为它精准地展示了”物理时间戳排序”在分布式系统中的失效方式。

场景完整还原：

云上的机票预订系统。Server A 收到一个客户端请求：购买航班 ABC 123 上的最后一张机票。
Server A 用自己的本地时钟给这次购买打时间戳 9h:15m:32.45s，把它写进日志，然后回复客户端 ok。
卖出的是最后一张座位，所以 Server A 给 Server B 发一条消息：”flight full“。
Server B 收到后，把 "Flight ABC 123 full" 连同它自己的本地时钟读数（此时读到的是 9h:10m:10.11s）写进自己的日志。
Server C 出于某种目的（审计、对账、故障恢复、回答”这张票是谁买的”）查询了 A 与 B 两份日志，然后彻底困惑了：按照时间戳，客户是在航班已经满了之后（9:10:10.11）才在 A 处买到票的（9:15:32.45）——这在逻辑上不可能。
讲义最后一句是关键：”This may lead to further incorrect actions by C“——C 可能据此做出进一步的错误动作：把这张票退掉、把座位重新放出来卖（造成超售）、或者判定 A 的日志是伪造的而触发告警。

机制图解：注意两条时间轴——真实发生的顺序（物理事实，唯一且客观）与日志里呈现的顺序（由各自的本地时钟决定，被人为打乱）。

真实世界发生顺序（客观事实，C 看不到）:
   A: ① 卖出最后一张票 ABC123 ──► ② 发送 "flight full" 给 B
                                        │
                                        ▼
   B:                                ③ 收到并记录 "Flight ABC 123 full"
      真实时刻:  9:10:10 之前         全部发生在几毫秒之内
   ─────────────────────────────────────────────────────────────────────

C 从两份日志里"看到"的顺序（每个服务器用自己的钟打戳）:
   B 的日志:   9:10:10.11   "Flight ABC 123 full"      ← 时间戳更早
   A 的日志:   9:15:32.45   "sold last seat ABC123"    ← 时间戳更晚
   ⇒ C 的结论: "航班满了 5 分钟之后，还有人买到了票" ✗ 因果被彻底颠倒
   ─────────────────────────────────────────────────────────────────────
   额外观察: 这个错误【不可能被 C 自己发现】—— C 手里只有两个数字，
             没有任何信息能告诉它"哪个数字的钟更准"。

分析：错在哪里？ 把它拆成三层，一层比一层深刻：

表层原因：A 和 B 的时钟不同步（skew 约 5 分 22 秒）。A 的钟快、B 的钟慢，于是 A 的事件被推到”未来”，B 的事件被拉到”过去”。
中层原因：由消息 A → B "flight full" 建立的因果顺序（A 的售票 → A 发消息 → B 记录满员）被两个设备的物理时钟彻底抹掉了。物理时间戳表达的是”各自钟面上的读数”，与”谁导致了谁”毫无关系。
深层原因（最关键）：问题的本质不是时钟不准，而是我们缺少一种能反映因果关系的顺序机制。 即使把两个钟都调到误差 1 毫秒，这个系统在原理上依然是错的——因为
- 1 毫秒的误差仍然足以颠倒两个相隔几百微秒的事件，而”两件事在 1 毫秒内先后发生”在云上每时每刻都在发生；
- 更糟的是，误差的方向是随机的：同一份日志，今天看是”先满后卖”，明天看可能变成”先卖后满”，全凭漂移的脸色。一个会随机颠倒的系统，其审计结论是没有意义的；
- 而如果 A 与 B 恰好在这次操作中”看起来”顺序正确，那也只是运气，不是正确性——系统没有任何机制保证它。

补充说明（工程视角）：这就是为什么现代存储系统要么像 Cassandra 那样明确承认“用物理时间戳做 last-write-wins，因此可能静默丢弃因果上更晚的写”（见 Ch.9 的 LWW 与冲突解决），要么像 Dynamo/Riak 那样用向量时钟检测并发并把冲突交给应用解决。这个例子是 Ch.9 那句”物理时钟不可靠的直接代价”的完整展开。
关键假设与系统模型：本例中的三个服务器只通过各自的本地时钟和消息交互，没有任何共享内存或全局时钟；C 只能读取日志里已经写死的数字，无法在执行时”再问一次现在几点”。这正是异步系统模型的典型场景。

11.2.3 挑战的根源：异步系统模型（Asynchronous System Model）

定义与目的：异步系统模型（asynchronous system model）规定：进程之间的消息传递延迟没有上界，进程内部的处理延迟（从收到消息到处理完毕）也没有上界。这个模型不承诺”消息最多 100 ms 到达”，也不承诺”进程最多停 10 ms”。它是我们能为分布式系统建立的、最宽松也最诚实的模型。
直观解释（”它是什么？”）：把进程想象成几个在黑暗里靠纸条通信的人。你可以保证”纸条不会凭空消失”，但不能保证“纸条一定在 5 秒内送到”——收纸条的人可能正在洗手间、可能被别的事耽搁了、纸条可能被压在桌角一整天。于是任何依赖”等待时间有上限”的推理都站不住脚：你永远不知道对方是”暂时没空”还是”已经死掉了”（这正是 Ch.7 故障检测器要处理的核心困难）。
机制图解：讲义对比了两类系统。

 ┌─────────────────────────── 多处理器 / 并行系统 ───────────────────────────┐
 │  一个机箱 / 一块主板上的多个 CPU 或核                                       │
 │      CPU0 ─┐                                                              │
 │      CPU1 ─┼── 共享同一个系统时钟（同一个晶振）                              │
 │      CPU2 ─┘      共享内存 / 缓存一致性协议                                 │
 │  ⇒ 同步系统模型 (synchronous model): 有已知的时钟、已知的时间上界            │
 │  ⇒ 一个事件"在哪个时刻发生"是有确定答案的                                    │
 └──────────────────────────────────────────────────────────────────────────┘

 ┌────────────────────── 互联网 / 云：异步系统模型 ──────────────────────────┐
 │   主机 A ────[互联网]────► 主机 B ────[其它数据中心]────► 主机 C            │
 │   自己的晶振                自己的晶振                  自己的晶振           │
 │   ✗ 没有共享时钟   ✗ 消息延迟无上界   ✗ 处理延迟无上界                       │
 │  ⇒ 连"这两个事件的真实先后"都无法观测                                        │
 └──────────────────────────────────────────────────────────────────────────┘

讲义给出的形式化定义——这几个术语是全课程后续讨论的基础，必须记牢：

术语	定义
Process（进程）	执行计算的实体，拥有自己的状态（state）——即它所有变量的取值
State（状态）	进程全部变量在某一时刻的取值集合
Action（动作）	进程改变自己状态的操作。只有两类：instruction（本地指令）与 communication action（通信动作：send / receive）
Event（事件）	一个动作的发生（the occurrence of an action）
Local clock（本地时钟）	每个进程各自的时钟。同一进程内的多个事件可以按本地时钟线性排序

关键假设与系统模型：讲义最后一句点出了本讲的全部张力：“Each process has a local clock – events within a process can be assigned timestamps, and thus ordered linearly. But – in a distributed system, we also need to know the time order of events across different processes.” 也就是说，进程内排序是免费的，跨进程排序才是问题。
补充说明：异步模型是”最坏情况”的抽象，现实网络当然有实际上界（比如同机房内 RTT 通常几百微秒，广域网几十毫秒）。但算法必须在异步模型下正确，原因是：
1. 实际延迟分布有长尾——99.9 分位可能比中位数大 100 倍，”通常很快”不等于”一定有界”；
2. 拥塞、GC、虚拟机迁移、交换机缓冲区溢出会让某一次消息延迟任意长；
3. 如果算法的正确性依赖”消息一定在 Δ 内到达”，那它一定会在最不方便的时刻（故障时刻）出错。这也正是 Ch.15 的 FLP 不可能性、以及 CAP 定理中”分区”的根源。

11.2.4 时钟偏差与时钟漂移（Clock Skew vs. Clock Drift）

这是全课程最容易混淆的一对概念，讲义用”路上的两辆车”作了非常有效的类比。必须把”值”与”速率”这两个层次彻底分开。

定义与目的：
- Clock Skew（时钟偏差）：两个进程时钟值的相对差——在同一个真实时刻，两个钟面上读数的差距。类比：路上两辆车之间的距离。
- Clock Drift（时钟漂移）：两个进程时钟频率（速率）的相对差——两个钟”走得快慢”的差距。类比：两辆车的速度差。
直观解释（”它是什么？”）：
- skew 是位置差，是”当下这两个钟差多少秒”；
- drift 是速度差，是”这两个钟的差距正在以多快的速度变大（或变小）”。
- 两者是积分关系：$\text{skew}(t) = \text{skew}(t_0) + \displaystyle\int_{t_0}^{t} \text{drift}(u)\,du$。这解释了讲义的两条核心论断：

论断	含义	车的类比
非零 skew ⇒ 时钟未同步	两个钟的读数不同，此刻不能互相替代	两辆车不在一起
非零 drift ⇒ skew 最终会增大	速率不同，差距一定会被时间放大	速度不同的两辆车一定会越离越远

讲义特别强调的方向性分析（这是很多同学会答错的细节）：
- 若跑得快的车在前（快的钟读数更大）：它会持续跑远，skew 单调增大；
- 若跑得快的车在后（快的钟读数更小）：它会先追上，然后再跑远——所以 skew 会先减小、过零点、再反向增大。
机制图解：

   (a) 快时钟在前: skew 单调增大        (b) 快时钟在后: 先追上, 再拉开
   时钟值                               时钟值
     │              ↗ 快钟(C 大)          │          ↗ 快钟
     │            ↗                       │        ↗
     │          ↗   ← 距离(skew)不断变大   │      ↗
     │        ↗                           │    ↗ ← 追上的那一刻 skew = 0
     │      ↗                             │  ↗
     │    ↗ 慢钟                           │↗
     │  ↗                                 ●━━━━━━━━━━━ 慢钟
     └──────────────────► 真实时间         └──────────────────► 真实时间
      drift > 0, skew 单调增                drift > 0, skew 先减后增 (方向反转)

对比表（务必记住这张表，考试与面试都常问）：

维度	Clock Skew（时钟偏差）	Clock Drift（时钟漂移）
差的到底是什么	两个时钟的值（读数）	两个时钟的频率（速率）
类比	两辆车之间的距离	两辆车的速度差
量纲	时间（秒、毫秒、微秒）	无量纲比率（常写作 ppm，百万分之一）
能否瞬时观测	能（两个钟的读数相减）	不能（必须观测一段时间才能算出速率差）
非零的后果	此刻时钟不同步，跨机时间戳不可比	skew 会随时间（最终）增大
能否直接修正	能：直接调整钟的值	不能：只能靠提高同步频率、温度补偿、换更好的晶振
主要消除手段	时间同步算法（Cristian / NTP，见 11.2.7–11.2.8）	更频繁的同步 + 更好的硬件（TCXO/OCXO/GPS/原子钟）
本讲的量化工具	与”允许的最大 skew $M$”挂钩	用 MDR 描述（见 11.2.5）

关键假设与系统模型：我们假设每个进程的本地时钟的速率在短时间尺度上是稳定的（drift 是缓变量），因此”同步一次可以管一段时间”。如果 drift 剧烈抖动，任何同步策略都失效。

11.2.5 Maximum Drift Rate：多久需要同步一次？

定义与目的：最大漂移率（Maximum Drift Rate, MDR）指的是一个时钟相对”正确时间”的速率偏差的绝对值上界。“正确时间”就是 UTC（Coordinated Universal Time，协调世界时）——讲义的原话是”UTC is the correct time at any point of time”。
直观解释（”它是什么？”）：MDR 回答的是”这个钟走得最坏能有多歪”。它不是一个固定物理常数，而是依赖于环境的：
- 晶振质量：普通石英晶振、温度补偿晶振（TCXO）、恒温晶振（OCXO）的 MDR 差好几个数量级；
- 温度：这是最大的敌人——晶振的谐振频率随温度变化，温度变化会显著加剧漂移；
- 电压、老化（aging）、机械振动：都是次要但真实的影响因素。
两个关键公式（讲义的核心量化结论）：

\[\text{两个相似 MDR 的时钟之间的最大漂移率} \;=\; 2 \times \text{MDR}\] \[\text{给定允许的最大 skew } M \text{，必须至少每} \; \frac{M}{2 \times \text{MDR}} \; \text{个时间单位同步一次}\]

公式推导（讲义只用了一句”time = distance / speed”，这里补齐）：
1. 设两个时钟各自的速率相对 UTC 的偏差都不超过 MDR（一个最多快 MDR，一个最多慢 MDR）；
2. 那么它们相对彼此的速率差最多是 $\text{MDR} + \text{MDR} = 2\,\text{MDR}$（这正是”相似 MDR 的两个时钟之间是 $2\times$MDR”的含义）；
3. 现在把 skew 看成”距离”、把漂移率看成”速度”：已知速度 $v = 2\,\text{MDR}$，允许走过的距离 $d = M$，求时间 $t$；
4. 代入 $\text{time} = \text{distance} / \text{speed}$，得到两次同步之间最多能撑：

\[t_{\max} \;=\; \frac{M}{2\,\text{MDR}}\]

注意这是”上界”：必须在 skew 还没超过 $M$ 之前就完成下一次同步，所以同步周期的设计值应当严格小于 $M/(2\,\text{MDR})$（工程上常取一半，留出消息延迟与执行抖动的余量）。

真实数量级（必须形成直觉）：
- 普通石英晶振：$\text{MDR} \approx 10^{-6}$（百万分之一，即 1 ppm）。含义是每秒钟漂 1 微秒 ⇒ 每天漂 $86400 \times 10^{-6} \approx 0.0864$ 秒，约 0.1 秒/天。这正是”廉价服务器放一个月，时钟可能偏出好几秒”的来源。
- 温度变化可以把它显著推高：补充说明——没有温度补偿的普通晶振在宽温范围内（例如 0–70 °C）的频率漂移可达 $10^{-5}$ 量级甚至更差；TCXO（温度补偿）约 $10^{-6}\sim10^{-7}$；OCXO（恒温）约 $10^{-8}$；铷钟约 $10^{-11}$；铯原子钟约 $10^{-13}$。NTP 的 primary server 之所以要接 GPS/原子钟，就是因为只有这样才能把”权威时间”的 MDR 压到可以忽略。
一个具体的算例（用来建立工程直觉）：
- 若要求任意两台机器的时钟偏差不超过 $M = 1$ 毫秒，MDR $= 10^{-6}$： $t_{\max} = \frac{10^{-3}}{2 \times 10^{-6}} = 500 \text{ 秒} \approx 8.3 \text{ 分钟}$ 也就是说，要求 1 毫秒的精度，就必须每 8 分钟同步一次。
- 若把要求放宽到 $M = 10$ 毫秒：$t_{\max} = 5000$ 秒 $\approx 83$ 分钟。
- 若要求 10 微秒（典型的同机房 PTP 场景）：$t_{\max} = 10^{-5}/(2\times10^{-6}) = 5$ 秒——每 5 秒就要同步一次。这就是为什么高精度时间同步在工程上是一件”持续烧钱”的事：精度每提高一个数量级，同步频率就要提高一个数量级。
机制图解：

   skew
    M ┤                                    ╱ ← 不补: 超过允许上界
      │                                  ╱
      │                                ╱
      │                              ╱
    0 ┤────●────────────●────────────●──────────────────► 真实时间
          ↑            ↑            ↑
        同步点       同步点        同步点
          └── ≤ M/(2·MDR) ──┘
      每次同步把 skew 压回 0 附近 (step 或 slew),
      之后它以最多 2·MDR 的速度重新增长。

关键假设与系统模型：该公式假设 MDR 是常数上界。现实中温度会周期性地改变速率（例如机房空调昼夜循环），所以工程上真正的做法是比公式算出的更频繁地同步，并监控 skew 的实际增长趋势。

11.2.6 外部同步 vs 内部同步（External vs. Internal Synchronization）

定义与目的：给定一组进程，同步有两种截然不同的语义目标。

	External Synchronization（外部同步）	Internal Synchronization（内部同步）
形式化定义	每个进程时钟 $C(i)$ 与组外一个公认时钟 $S$ 之差有界：$\lvert C(i) - S\rvert < D$ 在任何时刻成立	组内任意一对进程时钟之差有界：$\lvert C(i) - C(j)\rvert < D$ 对所有 $i,j$ 在任何时刻成立
参照物	组外的权威时钟 $S$（可接 UTC 或原子钟）	组内互相参照，不关心外部
讲义给出的例子	Cristian 算法、NTP	Berkeley 算法（讲义明确说明课程不讨论）
能否保证与 UTC 对齐	能（这正是它的目的）	不能（完全可能整体偏离 UTC）
典型适用场景	需要真实时刻的场合：审计日志、计费、证书有效期、跨数据中心的快照与事务、需要与外部世界对表的系统	只需要”组内事件可比较”的场合：组内全序多播、分布式互斥、局部一致性快照、监控指标聚合

两个重要定理（必须会推导）：

定理 A（外部同步 $\Rightarrow$ 内部同步，界翻倍）：若每个进程都满足 $\lvert C(i)-S\rvert < D$，则任意两个进程之间 $\lvert C(i)-C(j)\rvert < 2D$。

证明：对任意 $i,j$，由三角不等式 $\lvert C(i)-C(j)\rvert = \lvert (C(i)-S) + (S-C(j))\rvert \le \lvert C(i)-S\rvert + \lvert S-C(j)\rvert < D + D = 2D .$ （第二个等号是把 $S$ 插入后再拆开；第一个不等号是三角不等式；最后一个严格不等号来自两条假设。）$\blacksquare$

注意这个定理的实用含义：你用 NTP 把每台机器与 UTC 的偏差控制在 1 毫秒内，只能保证机器彼此之间的偏差在 2 毫秒内——界会翻倍，不能免费传递。

定理 B（内部同步 $\nRightarrow$ 外部同步）：内部同步不蕴含外部同步，而且极端情况下整个系统可以一起漂离外部时钟 $S$。

证明（反例构造）：设组内只有一个进程（或所有进程共用同一个参考），假设所有进程的时钟都以完全相同的速率 $1.001$ 倍于 UTC 走时，且它们之间没有任何偏差（内部 skew $\approx 0$，满足内部同步）。则对任意时刻 $t$，$C(i) = 1.001\,t$，组内任意两进程之差恒为 $0 < D$（内部同步成立），但与 UTC 的偏差为 $0.001\,t$，随时间无界增长（外部同步不成立，对任意给定的 $D$ 最终都会被突破）。 更一般地：内部同步只约束差分，而差分对”共同的偏移量”完全不敏感——所有钟一起快、一起慢、一起漂，内部同步的判据都毫无察觉。$\blacksquare$

机制图解：

   (a) 外部同步 (D)          ⇒     (b) 内部同步 (2D)
        ┌──────── S = UTC ────────┐        ┌──── 组内任意两点 < 2D ────┐
        │   ╷        ╷       ╷   │        │   ╷        ╷       ╷      │
        │  <D        <D      <D  │        │   └──<2D───┘  └──<2D──┘    │
        │   C1       C2      C3  │        │   C1       C2      C3      │
        └─────────────────────────┘        └──────────────────────────┘

   (c) 内部同步但整体漂离外部时钟 (定理 B 的反例)
        S = UTC ──────────────────────────────────────────────────►
        组内所有时钟 ─────────────────────────────────────────────►
                      \                                           \
                       \  大家一起快 0.1%, 内部 skew ≈ 0            \ 与 UTC 的
                        \                                          \ 偏差无界增长

关键假设与系统模型：外部同步需要一个被信任的外部时间源，这就引入了两个新问题：它是单点故障（它挂了，全组都失去校准能力），它也是攻击面（一个被攻陷或伪造的时间服务器可以让全组时钟任意跳变——详见 11.2.7 末尾与 Ch.25 安全）。
补充说明：Berkeley 算法（讲义说不讨论）是一种典型的内部同步算法：选出一个 master，它周期性地轮询所有从机的时钟读数，算出它们相对 master 的平均偏移，再把”你该调整多少”发回给每台机器（master 自己也按平均值调整）。它不需要任何外部时间源，代价是全体只能对齐到”组内平均值”而非 UTC。

11.2.7 Cristian 算法：把误差从”无界”压到”RTT 的一半”

定义与目的：Cristian 算法是一种外部时间同步算法：所有进程 $P$ 都向一个时间服务器（time server）$S$ 询问时间，并据此校正自己的时钟。
直观解释（”它是什么？”）：它就像你打电话问报时台”现在几点”。最朴素的做法是：你问，对方回答”9 点 15 分 32 秒”，你把表调到 9:15:32。问题在于——等你听完这句话把手表调好，真实时间已经又走了一两秒。你的表永远慢”你听话+动手”的那段时间。
朴素方案错在哪（讲义的核心提问）：

   P                                    S
   │ ──── "现在几点?" ─────────────────►│
   │                                    │ 查本地时钟, 得到 t
   │ ◄──── "现在是 t" ──────────────────│
   │                                    
   │ 收到后把自己的钟【设为 t】          
   ✗ 但从 S 读出 t 到 P 收到响应, 时间已经前进了 L2 (响应消息的单向延迟)
   ✗ 于是 P 的钟被设成了"过去"的某个时刻, 误差恰好是 L2 (+ S 的处理时间)
   ✗ 在异步系统中 L2 【没有上界】 ⇒ 这个方案的误差【无法有界】

Cristian 的洞察：既然单向延迟不可知，那就改成测量往返时间（Round-Trip Time, RTT）——P 在发请求前读一次自己的钟（$t_0$），收到响应后再读一次（$t_3$），于是 $\text{RTT} = t_3 - t_0 .$

为什么这个测量是”干净”的？ 因为 $t_0$ 与 $t_3$ 是同一个时钟读的，做差时该时钟自身的偏差被完全抵消——RTT 的测量与时钟偏差无关。这是一个非常重要、也非常优美的性质。反过来，为什么不能直接测量单向延迟？ 因为要算出 $L_1 = (\text{S 收到请求的真实时刻}) - (\text{P 发出请求的真实时刻})$，你必须同时知道两端的真实时刻——这要求两端时钟已经同步，也就是要求我们正在求的东西。这是一个循环依赖（circular dependency），所以单向延迟在原理上不可直接测量。这个”必须绕过循环依赖”的思想，是 Cristian 与 NTP 共同的精髓。

机制图解（两条时间轴 + 真实到达时刻的区间）：

         t0 发出请求                                              t3 收到响应

 P     --o------------------------------------------------------o------------>
            \                                               /
                \             M1  请求  P -> S            /
                   \                                /
                      \   M2  响应 t  S -> P     /
                          \                /
 S     ----------------------v---------^------------------------------------->
      S 收到请求时读表得 t ;  S 的时钟 = 真实时间(UTC)

      响应到达 P 时的真实时刻 T_recv = t + L2
      T_recv 落在区间 [ t + min2 ,  t + RTT - min1 ]
              |-------------------- RTT - min1 - min2 --------------------|
              t+min2                                                t+RTT-min1
                                         ^ P 取区间中点设钟: t + (RTT + min2 - min1)/2
                                         | 误差上界 (RTT - min1 - min2)/2

已知最小延迟时（讲义的关键一步）：设 $min_1$ 是 $P \to S$ 的最小单向延迟，$min_2$ 是 $S \to P$ 的最小单向延迟。讲义明确指出，这两个量取决于操作系统缓冲消息的开销、TCP 排队时间等等（因此它们是可以通过标定获得的工程常数，而不是物理常数）。记响应消息的实际单向延迟为 $L_2$：
- 因为 $L_2 \ge min_2$，所以响应到达 P 时的真实时刻 $T_{recv} = t + L_2 \ge t + min_2$；
- 又因为 $\text{RTT} = L_1 + L_2$（其中 $L_1 \ge min_1$ 是请求的单向延迟），所以 $L_2 = \text{RTT} - L_1 \le \text{RTT} - min_1$，即 $T_{recv} \le t + \text{RTT} - min_1$。
于是 $T_{recv}$ 一定落在区间 $T_{recv} \in \left[\, t + min_2, \;\; t + \text{RTT} - min_1 \,\right],$ 而 P 应该把钟设成这个区间里的哪一点？ 讲义的选择是取中点： $\text{新时钟值} \;=\; t + \frac{\text{RTT} + min_2 - min_1}{2}.$ 这样做的最大误差就是区间宽度的一半： $\text{误差} \;\le\; \frac{(\text{RTT} - min_1) - min_2}{2} \;=\; \frac{\text{RTT} - min_2 - min_1}{2}.$
关键结论：误差被有界了！ 这是 Cristian 算法相对朴素方案的本质改进：朴素的”直接设为 $t$”给出的误差是 $L_2$，在异步模型下无界；而取中点后，误差被可测量的 RTT 界定住了，而 RTT 是 P 自己掐表得到的、并且可以丢弃离群值（重传、异常抖动）后取最小值来收紧。
若 $min_1$ 与 $min_2$ 未知（讲义专门提问）：那就只能退化为把钟设成 $t + \text{RTT}/2$，误差界变成 $\pm \text{RTT}/2$——仍然有界，只是界变宽了一倍。这是一个很漂亮的鲁棒性：不知道 $min_1,min_2$ 并不会让算法失效，只会让精度变差。
Gotchas（讲义列出的三条，都是分布式系统的”黄金法则”）：
1. 允许增加时钟值，但绝不允许减少时钟值。 原因：把一个进程的时钟往回调，会让同一进程内先后发生的两个事件拿到逆序的时间戳——这直接违反了单调性，会破坏超时计时、租约、日志顺序，甚至让依赖”当前时间”的算法出现负数间隔。这是分布式系统里一条极其重要的工程戒律，值得记成”时钟只能前进，不能后退“。
2. 允许加快或减慢时钟的速率（slewing）来做渐进校正。 与其”跳变（step）”到目标值，不如在接下来的一段时间里让钟走得稍快一点或稍慢一点，平滑地逼近目标。Linux 的 adjtime/NTP 的 slewing 模式就是干这个的。
3. 误差太大时，取多次读数求平均。 单次读数受网络抖动影响很大；多次测量取平均（或取 RTT 最小的那几次）能显著提高精度——这正是 NTP 的 filtering 与 clustering 阶段做的事。
安全性问题（铺垫 Ch.25）：Cristian 算法把整个系统的时间正确性托付给单点的时间服务器 $S$：
- $S$ 是单点故障：它挂了，全组失去校准能力（NTP 用树形分层来缓解，见 11.2.8）；
- $S$ 是攻击目标：一个被攻陷或伪造的 $S$ 可以让你的时钟任意跳变。攻击者因此可以：把过期证书”变”成有效、把重放攻击的时间戳”变”成新鲜、让审计日志错乱、甚至让分布式锁的租约提前过期（配合”回拨”制造双主）。“你的时钟由谁决定，你的系统就由谁决定”——这也是现代系统为什么要给 NTP 加认证（symmetric key / Autokey），并最终走向 GPS/原子钟 + 签名时间源的原因。
关键假设与系统模型：异步模型（延迟无上界，但有下界 $min_1, min_2$）；$S$ 是正确（correct）的，即非恶意、非 Byzantine；通道是 fair-loss（消息可能丢，但重传最终能成功）。

11.2.8 NTP：把误差压到 RTT 的一半，并且永远留着非零误差

定义与目的：NTP（Network Time Protocol，网络时间协议）是互联网上事实标准的时间同步协议。它要做的事与 Cristian 算法相同（外部同步），但通过分层架构 + 多条测量 + 统计过滤 + 时钟disciplining把它做到了全球规模可用。
直观解释（”它是什么？”）：把 NTP 想成一个权威时间的分发树：树根是接 GPS/原子钟的服务器，中间节点逐级向下转发时间，叶子用户从自己的父节点取时间。每个节点只跟自己的父节点同步，于是”全球几十亿设备对表”这件事被分解成了”每个节点只跟一个上游对表”。
机制图解 1：NTP 的树形（分层）架构

              ┌───────────────────┐
              │  UTC 权威时源      │   GPS 卫星 / 铯原子钟 / 铷原子钟
              └─────────┬─────────┘
                        │  (直连外部时源)
        ┌───────────────┴───────────────┐
   ┌────┴─────┐                    ┌────┴─────┐
   │ Primary  │  stratum 1         │ Primary  │        ← 直连原子钟/GPS 的服务器
   └────┬─────┘                    └────┬─────┘
        │                               │
   ┌────┴─────┐                    ┌────┴─────┐
   │Secondary │  stratum 2         │Secondary │        ← 从 primary 取时间
   └────┬─────┘                    └────┬─────┘
        │                               │
   ┌────┴─────┐                    ┌────┴─────┐
   │ Tertiary │  stratum 3         │ Tertiary │        ← 从 secondary 取时间
   └────┬─────┘                    └────┬─────┘
        │                               │
     ┌──┴──┐                         ┌──┴──┐
     │Client│ 叶子                    │Client│          ← 普通主机/云主机
     └─────┘                         └─────┘

stratum（层级）是从权威时源往下数的”跳数”：stratum 1 = 直接接原子钟/GPS，stratum 2 = 从 stratum 1 取时间，依此类推。stratum 越大，累积误差通常越大（每一级都引入一次 RTT/2 量级的误差），所以工程上一般只用 stratum 1–4 的服务器。每个节点与它的树父节点（tree parent）同步，客户端是树的叶子——这正是讲义的原话。

机制图解 2：NTP 的四方时间戳交换（必须记住这四个时刻）

         t_s1 发出 M1                                           t_r2 收到 M2

 Child --o------------------------------------------------------o------------>
            \                                               /
                \   M1  Child -> Parent                 /
                   \                                /
                      \    M2  Parent -> Child /
                          \                /
 Parent----------------------v---------^------------------------------------->
                           t_r1 收到 M1              t_s2 发出 M2

      M2 把 t_r1 与 t_s2 带回 Child (真实 NTP 报文中还回显 t_s1)
      Child 只用四个时间戳算偏差:  o = ((t_r1 - t_r2) + (t_s2 - t_s1)) / 2

四个时间戳分别是：

$t_{s1}$：Child 发出 Message 1 时读自己的钟（send time）；
$t_{r1}$：Parent 收到 Message 1 时读自己的钟（receive time）；
$t_{s2}$：Parent 发出 Message 2 时读自己的钟（send time）；
$t_{r2}$：Child 收到 Message 2 时读自己的钟（receive time）。

注意这四个读数分别由两个不同的时钟产生——正是这一点让偏移可以被”挤”出来。计算偏移需要 $t_{r1}$（parent 的钟）与 $t_{s2}$（parent 的钟）回到 child 一侧，因此 Message 2 必须携带 parent 的这两个时间戳。（补充说明：真实 NTP 报文里，服务器的应答包含 T1 = 客户端发送时间（回显）、T2 = 服务器接收时间、T3 = 服务器发送时间，客户端本地记下 T4 = 接收时间；用 NTP 的记号 $\theta = \frac{(T_2-T_1)+(T_3-T_4)}{2}$，与讲义公式 $(t_{r1}-t_{r2}+t_{s2}-t_{s1})/2$ 完全等价。讲义在 Message 2 旁标注了它携带的时间戳，此处以讲义口径为准。）

偏移公式（讲义原式）： $\boxed{\;o \;=\; \frac{(t_{r1} - t_{r2}) + (t_{s2} - t_{s1})}{2}\;}$
完整的误差推导（讲义有，务必还原）：设 child 相对 parent 的真实偏移为 $o_{real}$，Message 1 的单向延迟为 $L_1$，Message 2 的单向延迟为 $L_2$。关键前提：没有任何人知道 $L_1$ 和 $L_2$。
按讲义的口径列方程： $t_{r1} = t_{s1} + L_1 + o_{real}, \qquad t_{r2} = t_{s2} + L_2 - o_{real}.$ 直观理解第一条：parent 在 child 发出读数 $t_{s1}$ 之后 $L_1$ 个时间单位收到消息，并且还要加上两台钟本身的偏移 $o_{real}$。第二条同理，符号相反。
把第二式从第一式中减去： $t_{r1} - t_{r2} = (t_{s1} - t_{s2}) + (L_1 - L_2) + 2o_{real},$ 移项并整理： $o_{real} = \frac{(t_{r1} - t_{r2}) + (t_{s2} - t_{s1})}{2} + \frac{L_2 - L_1}{2} \;=\; o + \frac{L_2 - L_1}{2}.$ 因此误差为 $\left\vert o_{real} - o \right\vert = \left\vert \frac{L_2 - L_1}{2} \right\vert < \left\vert \frac{L_2 + L_1}{2} \right\vert \;=\; \frac{\text{RTT}}{2}.$
结论：误差被往返时间（RTT）所界定。 这与 Cristian 算法得到的是同一个数量级的保证，但 NTP 的形式更优雅：它不需要事先知道 $min_1, min_2$，只用四个时间戳就自动得到 RTT/2 的界（因为 $\vert L_2-L_1\vert \le L_1+L_2$ 恒成立）。
补充说明（符号约定，容易绕晕的地方）：讲义把 $o_{real}$ 定义为”child 比 parent 领先的量”，但上面两条方程的符号对应的是相反的方向（若严格取 $o_{real} = C_{child} - C_{parent}$，则应写作 $t_{r1} = t_{s1} + L_1 - o_{real}$、$t_{r2} = t_{s2} + L_2 + o_{real}$）。两种约定给出的误差界完全相同，都是 $\lvert o_{real} - o\rvert = \lvert L_2 - L_1\rvert/2 < \text{RTT}/2$。工程实现里（RFC 5905）统一采用”$\theta$ = 需要加到本地钟上的校正量“这一约定：$\theta = \frac{(T_2-T_1)+(T_3-T_4)}{2}$，本地钟加上 $\theta$ 就对齐到服务器。
NTP 的实际精度：
- 局域网（LAN）内：通常达到亚毫秒级（同一数据中心内，配合好的硬件与频繁同步，几十微秒是可达的）；
- 广域网（WAN）内：通常在几毫秒到几十毫秒之间；
- 影响精度的两大因素：网络延迟的非对称性（$L_1 \ne L_2$，直接造成系统偏差）与路径延迟的抖动（造成随机误差）。前者无法靠多测几次消除——这是 NTP 精度的真正天花板。
- 用户态时间戳 vs 硬件时间戳：普通 NTP 的时间戳打在用户态，整条协议栈的排队延迟都会变成误差；PTP（IEEE 1588）通过网卡硬件打时间戳把这一项消掉，在局域网内可以做到亚微秒级。
安全问题（铺垫 Ch.25）：
- NTP 放大攻击（NTP amplification / reflection DDoS）：攻击者伪造受害者 IP 向大量 NTP 服务器发送 monlist 之类的查询，由于响应报文远大于请求，可以把攻击流量放大上百倍（经典案例是 2013 年的 CVE-2013-5211）。
- 伪造时间：没有认证的 NTP 响应可以被中间人篡改（”时间偏移攻击”），后果包括绕过证书有效期、重放攻击、破坏审计与计费、让租约语义失效。缓解手段是报文认证（对称密钥 / Autokey / NTS）。
- 所以高安全场景的时间源必须”可信且可验证”：GPS 信号本身也可能被欺骗（spoofing），这也促使了”多源交叉验证 + 签名”的架构。
更高精度与更现代的方案（补充说明）：
- PTP（Precision Time Protocol, IEEE 1588）：硬件时间戳 + 主从层次 + 路径延迟测量，局域网内亚微秒级，用于金融交易、工业控制、5G 前传。
- GPS/原子钟 + TrueTime（Google Spanner）：Spanner 的每个数据中心部署 GPS 接收机与原子钟，对外暴露的不是一个时间点，而是一个不确定区间 $[earliest, latest]$，其半宽 $\epsilon$ 通常小于 7 毫秒。Spanner 用 commit-wait 保证：提交事务时先等待”确定这段时间已经过去”，再做提交，从而获得外部一致性（external consistency）。这是”承认时钟不确定，并把不确定性显式地变成算法的一部分“的典范，与本讲的哲学完全一致。
- 混合逻辑时钟（Hybrid Logical Clock, HLC）：用一对 $(l, c)$，其中 $l$ 尽量贴近物理时间、$c$ 是逻辑计数器，既能像物理时钟一样”接近真实时间”（方便与用户的时间语义对齐、便于调试），又像逻辑时钟一样严格保证因果性。CockroachDB 用它做事务时间戳。见 11.5 的工程讨论。
讲义的核心结论（必须记住这句话）：

“We still have a non-zero error! We just can’t seem to get rid of error — can’t, as long as message latencies are non-zero.” 我们仍然有非零误差！只要消息延迟非零，我们就永远无法消除误差。

这句话的分量在于：它不是”我们的算法还不够好”，而是”在异步系统里，物理时间同步的误差在原理上不可能为零“。于是讲义立刻抛出了全讲的转折问题：

Can we avoid synchronizing clocks altogether, and still be able to order events? 我们能不能完全不做时间同步，却仍然能给事件排序？

答案是肯定的——用逻辑时钟。接下来的所有内容（happens-before、Lamport 时间戳、向量时间戳）都是对这个问题的一个越来越好的回答。

11.2.9 Happens-Before 关系（$\rightarrow$）：本讲的理论基石

定义与目的：Happens-Before（先于发生）关系由 Leslie Lamport 在 1970 年代提出（“Used in almost all distributed systems since then”，讲义强调了它的普适性），它定义了两个事件之间的一种因果偏序，记作 $a \rightarrow b$，读作”$a$ 先于 $b$ 发生”或”$a$ 因果地先于 $b$”。
三条规则（必须逐字记住）：

$\text{(R1) 同一进程内：}\quad a \rightarrow b \quad \text{若} \quad time(a) < time(b) \;(\text{用本地时钟比较})$ $\text{(R2) 消息：}\quad \text{若 } p_1 \text{ 发送 } m \text{ 给 } p_2,\text{ 则 } send(m) \rightarrow receive(m)$ $\text{(R3) 传递性：}\quad \text{若 } a \rightarrow b \text{ 且 } b \rightarrow c,\text{ 则 } a \rightarrow c$

三条规则的含义分别是：

R1：同一个进程内的事件，按程序执行的先后顺序（本地时钟可以正确地给出这个顺序，因为它们是同一个钟读出来的值）；
R2：一条消息的发送必定先于它的接收——这是唯一能跨越进程建立因果的规则，也是全部跨进程顺序的来源；
R3：因果关系可以”接力”——这正是 $A \rightarrow F$ 这类非直接关系能够成立的原因。
关键性质：这创建的是偏序（partial order），不是全序（total order）。 也就是说，并非所有事件对都通过 $\rightarrow$ 相关联：
- 直觉解释（为什么这么定义）：$a \rightarrow b$ 的物理含义是”$a$ 有可能因果地影响 $b$“。如果两个事件之间既没有 $a \rightarrow b$、也没有 $b \rightarrow a$，那就意味着在它们之间不存在任何因果路径——它们互不知情、互不影响，无论真实时间上谁先谁后，系统里没有任何人能够观测到这个先后。这样的两个事件称为并发（concurrent），记作 $a \parallel b$。
- 这正是与物理时间的根本区别：物理时间对任意两个事件都给出一个先后（全序），但这个先后可能纯粹是钟表噪声；happens-before 只承认能被因果链证明的先后，因此它是客观的、不依赖任何时钟的。
机制图解（讲义的核心例子，必须精确还原）：三个进程 P1、P2、P3，事件分别是 $A\,B\,C\,D\,E$、$E^{\prime}\,F\,G$、$H\,I\,J$，四条消息分别对应 $\{H \to E^{\prime},\; B \to F,\; G \to D,\; E \to J\}$。

P1 -----------------oA------------oB------------oC--------------------oD----------oE------------------>
                                      \                              /             \
                                          \                         /               \
                                              \                    /                 \
                                                  v               ^                   \
P2 ------------------------------------oE'------------oF---------oG--------------------\-------------->
                                     /                                                  \
                                   /                                                     \
                                 /                                                        \
                               ^                                                           v
P3 --------------------------oH-----------------------oI------------------------------------oJ-------->

图中：横轴是时间（向右），三条横线是三个进程的时间轴（同一个进程的事件按 $P_1$ 上的水平位置从左到右发生），斜线是消息（$\backslash$ 表示向下传递、$/$ 表示向上传递，箭头尖端标出接收事件）。四条消息是：

消息	从	到	说明
$m_1$	$H$（P3）	$E^{\prime}$（P2）	P3 很早就发了一条消息给 P2
$m_2$	$B$（P1）	$F$（P2）	P1 发消息给 P2
$m_3$	$G$（P2）	$D$（P1）	P2 发消息回头给 P1
$m_4$	$E$（P1）	$J$（P3）	P1 在最后发消息给 P3

逐步推导（讲义要求的关系，逐个给出理由）：

关系	为什么成立	用到的规则
$A \rightarrow B$	同一进程 P1，$A$ 在 $B$ 之前（本地时钟）	R1
$B \rightarrow F$	$B$ 是消息 $m_2$ 的发送事件，$F$ 是它的接收事件	R2
$A \rightarrow F$	$A \rightarrow B$ 且 $B \rightarrow F$	R1 + R2 + R3
$H \rightarrow G$	$H \rightarrow E^{\prime}$（R2），$E^{\prime} \rightarrow F \rightarrow G$（R1），接力	R2 + R1 + R3
$F \rightarrow J$	$F \rightarrow G$（R1），$G \rightarrow D$（R2，消息 $m_3$），$D \rightarrow E$（R1），$E \rightarrow J$（R2，消息 $m_4$）	R1 + R2 + R3
$H \rightarrow J$	$H \rightarrow E^{\prime} \rightarrow F \rightarrow G \rightarrow D \rightarrow E \rightarrow J$，一条长达 7 个事件的因果链	R3 反复使用
$C \rightarrow J$	$C \rightarrow D$（R1），$D \rightarrow E$（R1），$E \rightarrow J$（R2）	R1 + R2 + R3

请特别注意 $H \rightarrow G$ 与 $C \rightarrow J$ 都是”传递性”产生的：$H$ 与 $G$ 之间、$C$ 与 $J$ 之间并没有直接的消息，是因果链把它们连起来的。这就是为什么 R3 不可省略。

并发对的分析（讲义提出的两个思考点）：
- $F$ 与 $J$？ 讲义特意在列出 $F \rightarrow J$ 之后追问”$F$ and $J$?”。答案是它们不是并发，而是因果相关：$F \rightarrow G \rightarrow D \rightarrow E \rightarrow J$ 存在一条完整的因果路径。“看起来在两个不同进程上”不等于并发——这是初学者最常见的误解。
- $F$ 与 $C$？ 这两个是并发的：$C$ 在 P1 上、$F$ 在 P2 上；从 $F$ 出发能不能走到 $C$？$F \rightarrow G \rightarrow D \rightarrow E$，而 $C$ 在 $D$ 之前，所以 $F$ 的因果未来里没有 $C$；反过来 $C \rightarrow D \rightarrow E$，而 $F$ 是 P2 上 $D$ 的因果过去的一部分吗？$C$ 的因果未来包含 $D$，但 $F$ 与 $D$ 之间只有 $F \rightarrow D$（$F$ 更早），所以也没有 $C \rightarrow F$。两条路都走不通 ⇒ $C \parallel F$。
- $H$ 与 $C$？ 同样并发：$H$ 在 P3 上、$C$ 在 P1 上，$H$ 的因果未来是 $\{E^{\prime},F,G,D,E,J\}$，不含 $C$；$C$ 的因果未来是 $\{D,E,J\}$，不含 $H$。所以 $H \parallel C$。
关键假设与系统模型：happens-before 完全不依赖物理时钟（R1 里的 time 只用于同一进程内的局部比较），因此它在异步模型中定义良好、在任何时钟偏差下都成立。它不要求 FIFO 通道，也不要求消息不丢失——它只描述”已经发生的事实之间的因果关系”。

11.2.10 Lamport 逻辑时钟（Lamport Timestamps）

定义与目的：Lamport 逻辑时钟的目标非常单纯：给每个事件分配一个逻辑时间戳，使这些时间戳遵守因果性（obey causality），即 $a \rightarrow b \;\Longrightarrow\; \text{timestamp}(a) < \text{timestamp}(b).$
四条规则（讲义原文的机械描述）：
1. 每个进程维护一个本地计数器（逻辑时钟），是一个整数，初始值为 0；
2. 进程在发生 send 或任何 instruction 时递增计数器，并把计数器的值作为该事件的时间戳；
3. send（消息）事件把它的时间戳附带在消息上；
4. 对于 receive 事件，计数器被更新为 $\max(\text{local clock},\ \text{message timestamp}) + 1$。
机制图解（讲义逐步演化的完整还原）：注意 P1 的第一个事件 $A$ 的时间戳是 1（不是 0）：计数器”加一后才作为时间戳”，所以初始值 0 表示”什么都还没发生”。

                 (初始) (0,0,0)     ← 三个进程的计数器都从 0 开始

P1 -----------------oA-1----------oB-2----------oC-3------------------oD-5--------oE-6---------------->
                                      \                              /             \
                                          \                         /               \
                                              \                    /                 \
                                                  v               ^                   \
P2 ------------------------------------oE'-2----------oF-3-------oG-4------------------\-------------->
                                     /                                                  \
                                   /                                                     \
                                 /                                                        \
                               ^                                                           v
P3 --------------------------oH-1---------------------oI-2----------------------------------oJ-7------>

逐步演化（这是讲义用多页幻灯片演示的过程，每一步都标出 $max$ 的计算）：

步骤	事件	进程	规则	计算	结果时间戳
1	$H$	P3	instruction/send：本地递增	$0+1$	1
2	$E^{\prime}$	P2	receive，消息携带 ts=1	$\max(0, 1)+1$	2（必须追上发送方！）
3	$A$	P1	instruction：本地递增	$0+1$	1
4	$B$	P1	send：本地递增，并把 2 放进消息	$1+1$	2
5	$F$	P2	receive，消息携带 ts=2，本地为 2	$\max(2, 2)+1$	3
6	$C$	P1	instruction	$2+1$	3
7	$G$	P2	send：本地递增，消息携带 4	$3+1$	4
8	$D$	P1	receive，消息携带 ts=4，本地为 3	$\max(3, 4)+1$	5（本地被”拉到”发送方的水平线之上）
9	$E$	P1	send：本地递增	$5+1$	6
10	$I$	P3	instruction	$1+1$	2
11	$J$	P3	receive，消息携带 ts=6，本地为 2	$\max(2, 6)+1$	7

回答讲义提出的 “Why Max?”：这是理解 Lamport 时钟的关键一问。为什么要取 $\max$，而不是简单地”本地加一”？
- 接收事件 $E^{\prime}$ 的时间戳必须大于发送事件 $H$ 的时间戳（规则 R2 要求 $send \rightarrow receive$，而时间戳必须遵守因果性）；
- 但接收方 P2 的本地计数器可能远远落后于发送方（P3 的钟已经走到 1，P2 还停在 0）。如果只用”本地加一”，就会得到 $ts(E^{\prime}) = 1$，与 $ts(H)=1$ 相等，从而在这一对因果事件上得不到严格大小关系，违反了因果性；
- 取 $\max(\text{local}, \text{msg}) + 1$ 的含义是：接收方必须”追上”发送方的因果历史——它要把自己的逻辑时钟跳到”至少和发送方一样新”，然后加一，从而保证自己的每个后续事件都排在发送方的事件之后；
- 更本质地说：消息携带的时间戳代表了发送方所见证的全部因果历史的一个”摘要”，取 max 就是把这段历史合并进接收方的时钟里（这一点在向量时钟里会被放大成”逐维取 max”）。
因果性的验证（讲义逐条列出，全部成立）：

因果对	时间戳比较	结论
$A \rightarrow B$	$1 < 2$	✓
$B \rightarrow F$	$2 < 3$	✓
$A \rightarrow F$	$1 < 3$	✓
$H \rightarrow G$	$1 < 4$	✓
$F \rightarrow J$	$3 < 7$	✓
$H \rightarrow J$	$1 < 7$	✓
$C \rightarrow J$	$3 < 7$	✓

Lamport 时钟不能推出因果性（最关键的限制）：反过来，时间戳更小并不意味着因果在先。讲义给出了两个漂亮的例子：
- $?\, C \rightarrow F\,?$：$3 = 3$ —— 两个时间戳相等，但它们并发；
- $?\, H \rightarrow C\,?$：$1 < 3$ —— 时间戳严格有序，但它们并发（$H$ 在 P3、$C$ 在 P1，两条因果路都不通）。
于是得到本讲的”黄金公式”： $\boxed{\;E_1 \rightarrow E_2 \;\Longrightarrow\; timestamp(E_1) < timestamp(E_2), \quad \text{BUT}}$ $\boxed{\;timestamp(E_1) < timestamp(E_2) \;\Longrightarrow\; \{E_1 \rightarrow E_2\} \;\text{OR}\; \{E_1 \text{ 与 } E_2 \text{ 并发}\}}$
必须明确记住：Lamport 时间戳不能区分并发事件。 当你看到 $ts(a) < ts(b)$ 时，你能确定的只有”$a$ 没有在 $b$ 之后发生”，但无法判断 $a$ 是 $b$ 的原因，还是它们俩根本互不相干。讲义对此的态度是宽容的：”Ok, since concurrent events are not causality related!”——既然并发事件本来就没有因果关系，分不清它们也无伤大雅。但有些场景就是需要分清（例如键值存储的冲突检测、需要把并发操作暴露给应用的系统），这就引出了向量时钟。
Lamport 时钟最重要的用途：把偏序扩展成全序（total order）。虽然 Lamport 时间戳不能判定因果，但它足以构造一个与因果一致的全局顺序：给每个事件配上二元组 $\text{key}(e) = \big(\,\text{Lamport}(e),\;\; pid(e)\,\big),$ 按字典序排序。由于”同一进程内的任意两个事件 Lamport 时间戳必然不同”（本地计数器严格递增），当时间戳相等时 $pid$ 必然不同，因此任意两个事件都能分出先后——这是一个全序（total order），而且它是原偏序的一个线性扩展（linear extension）：若 $a \rightarrow b$，则 $\text{Lamport}(a) < \text{Lamport}(b)$，所以字典序下 $a$ 必然排在 $b$ 前面。
这个构造是后续两讲的算法基础，务必点明这个连接：
- 全序多播（Ch.13，Lecture 15）：ISIS 的全序多播就是用 Lamport 时间戳给消息定序，保证所有接收者按同一顺序交付；
- 分布式互斥（Ch.14，Lecture 16）：Ricart-Agrawala 算法正是用 $(\text{ts}, pid)$ 来决定”谁的请求更早”，从而在 $2(N-1)$ 条消息内实现互斥；Lamport 自己的 bakery 算法也是同一思路。
代价是：这个全序在并发事件上的先后是人为的（由 pid 决定），不代表真实时间，也不代表因果。它只是”大家都同意的一个顺序”，而”大家都同意”恰恰是复制状态机所需要的。
关键假设与系统模型：Lamport 时钟不需要任何时钟同步，不需要预先知道进程数（计数器的大小与 $N$ 无关），也不需要 FIFO 或可靠通道；它唯一依赖的是”每个进程按顺序执行自己的事件”与”消息的发送发生在接收之前”这两条物理事实。因此它的适用面几乎是无条件的——这正是它”此后几乎所有分布式系统都在用”（讲义原话）的原因。

11.2.11 向量时钟（Vector Timestamps）：既能判因果，又能判并发

定义与目的：向量时钟是一种逻辑时间戳，它完整地刻画因果性： $a \rightarrow b \iff V(a) < V(b), \qquad a \parallel b \iff V(a) \text{ 与 } V(b) \text{ 不可比较}.$ 它解决了 Lamport 时钟的唯一缺陷——区分并发事件。讲义明确指出它的实际用武之地：“Used in key-value stores like Riak”（在 Riak 这类键值存储中用于检测并发写，见 Ch.9）。
直观解释（”它是什么？”）：一个向量时间戳就像给事件盖上一枚记录着”我见过的所有进程各发生了多少事”的邮戳。一个整数只能回答”我见过多少事”，一个向量才能回答”我分别从每个进程那里见过多少事”。正是这份”按进程拆开的历史清单”，让两个事件可以比较出”谁的历史包含了谁”——包含关系就是因果，互不包含就是并发。
机制：设组内有 $N$ 个进程，编号 $1 \ldots N$。
- 每个进程使用一个整数时钟向量，每个向量有 $N$ 个元素；
- 进程 $i$ 维护自己的向量 $V_i[1 \ldots N]$；
- $V_i[j]$ 的含义必须讲透：它是”进程 $i$ 所知道的、进程 $j$ 上已经发生的事件的最新数量“（讲义原话：“$V_i[j]$ is $i$’s knowledge of latest events at process $j$”）。换句话说，$V_i[j] = k$ 表示”$i$ 知道 $j$ 至少已经发生了 $k$ 个事件”。这里的”知道”是因果意义上的知道：只有当 $j$ 的事件（或关于它的信息）通过消息因果地传到 $i$，$i$ 才可能”知道”它。
更新规则（三条，按讲义口径）：
1. 在进程 $i$ 发生 instruction 或 send 事件时，$i$ 只递增自己那一维：$V_i[i] \mathrel{+}= 1$；
2. 每条消息携带发送事件的向量时间戳 $V_{message}[1 \ldots N]$；
3. 进程 $i$ 收到消息时： $V_i[i] = V_i[i] + 1 \qquad (\text{先递增自己那一维})$ $V_i[j] = \max\big(V_{message}[j],\; V_i[j]\big) \quad \text{对所有 } j \neq i \qquad (\text{再对其他维取 max})$
关于”先递增自己那维还是先合并”（讲义口径 vs 等价性）：讲义给的是”先递增自己那一维、再对其他维取 max“。那么顺序反过来（先 max 合并、再递增自己那维）会不一样吗？答案：不会，两种次序的结果完全相同。理由是一条恒成立的不等式——按接收规则，消息里关于 $i$ 的分量永远不超过 $i$ 当前的值：
\[V_{message}[i] \le V_i[i] \quad(\text{接收时刻}).\]
为什么？$V_{message}[i]$ 是发送方所知道的、$i$ 已经发生的事件数。发送方知道某个 $i$ 的事件 $e$，说明 $e \rightarrow send$；而 $send \rightarrow receive$（同一条消息），所以 $e \rightarrow receive$。由于 $e$ 与 receive 都在进程 $i$ 上，$e$ 必然发生在 receive 之前，因此”发送方所知道的 $i$ 的事件数” ≤ “$i$ 在 receive 之前已经发生的事件数” = $V_i[i]$。于是 $\max(V_{message}[i], V_i[i]) = V_i[i]$，先递增还是先合并得到的都是 $V_i[i]+1$。两种次序在因果判定上完全等价，讲义选择先递增只是写法上的方便。
机制图解（讲义逐步演化的完整还原）：仍然用同一个三进程例子，向量从 $(0,0,0)$ 演化到 $(5,3,1)/(2,3,1)/(5,3,3)$。

P1 -----------------oA-(1,0,0)----oB-(2,0,0)----oC-(3,0,0)------------oD-(4,3,1)--oE-(5,3,1)---------->
                                      \                              /             \
                                          \                         /               \
                                              \                    /                 \
                                                  v               ^                   \
P2 ------------------------------------oE'-(0,1,1)----oF-(2,2,1)-oG-(2,3,1)------------\-------------->
                                     /                                                  \
                                   /                                                     \
                                 /                                                        \
                               ^                                                           v
P3 --------------------------oH-(0,0,1)---------------oI-(0,0,2)----------------------------oJ-(5,3,3)>

逐步演化（每一步都标出 max 的来源）：

步骤	事件	进程	操作	计算	结果向量
0	—	全部	初始	—	$(0,0,0)$
1	$A$	P1	instruction	第 1 维 +1	$(1,0,0)$
2	$H$	P3	send（消息 $m_1$ 携带 $(0,0,1)$）	第 3 维 +1	$(0,0,1)$
3	$E^{\prime}$	P2	receive $m_1$	$V_2[2]=0+1$；$V_2[1]=\max(0,0)$；$V_2[3]=\max(1,0)=1$	$(0,1,1)$
4	$B$	P1	send（消息 $m_2$ 携带 $(2,0,0)$）	第 1 维 +1	$(2,0,0)$
5	$F$	P2	receive $m_2$	$V_2[2]=1+1=2$；$V_2[1]=\max(2,0)=2$；$V_2[3]=\max(0,1)=1$	$(2,2,1)$
6	$C$	P1	instruction	第 1 维 +1	$(3,0,0)$
7	$G$	P2	send（消息 $m_3$ 携带 $(2,3,1)$）	第 2 维 +1	$(2,3,1)$
8	$D$	P1	receive $m_3$	$V_1[1]=3+1=4$；$V_1[2]=\max(3,0)=3$；$V_1[3]=\max(1,0)=1$	$(4,3,1)$
9	$E$	P1	send（消息 $m_4$ 携带 $(5,3,1)$）	第 1 维 +1	$(5,3,1)$
10	$I$	P3	instruction	第 3 维 +1	$(0,0,2)$
11	$J$	P3	receive $m_4$	$V_3[3]=2+1=3$；$V_3[1]=\max(5,0)=5$；$V_3[2]=\max(3,0)=3$	$(5,3,3)$

把这张表和 Lamport 那张表对照着看，能看出向量时钟的本质：$J$ 的向量 $(5,3,3)$ 一次性告诉了它在接收前”见过 P1 的 5 个事件、P2 的 3 个事件”；而 Lamport 只给出一个孤零零的 7。

比较规则（必须精确，一字不差）：
- 相等：$VT_1 = VT_2$ 当且仅当对所有 $i = 1,\ldots,N$，$VT_1[i] = VT_2[i]$；
- 小于等于：$VT_1 \le VT_2$ 当且仅当对所有 $i$，$VT_1[i] \le VT_2[i]$（逐维比较，这是一个偏序）；
- 因果相关：两个事件因果相关当且仅当 $VT_1 < VT_2$，即 $VT_1 \le VT_2 \quad \text{且} \quad \exists\, j,\ 1 \le j \le N,\ VT_1[j] < VT_2[j]$ （”至少有一维严格小于”——否则就相等了）；
- 并发：两个事件并发当且仅当 $\neg(VT_1 \le VT_2) \;\wedge\; \neg(VT_2 \le VT_1),$ 讲义把这个关系记作 $VT_2 \parallel\mid VT_1$（”不可比较”）。
验证示例（讲义逐条列出，全部成立）：

因果对	向量比较	为什么
$A \rightarrow B$	$(1,0,0) < (2,0,0)$	同一进程，第 1 维严格增
$B \rightarrow F$	$(2,0,0) < (2,2,1)$	第 2、3 维严格增（$F$ 接收了 $B$ 的消息）
$A \rightarrow F$	$(1,0,0) < (2,2,1)$	传递性在向量上的体现：逐维 ≤ 且至少一维 <
$H \rightarrow G$	$(0,0,1) < (2,3,1)$	经过 $H \to E^{\prime} \to F \to G$ 的因果链
$F \rightarrow J$	$(2,2,1) < (5,3,3)$	第 1、3 维严格增
$H \rightarrow J$	$(0,0,1) < (5,3,3)$	第 1、2、3 维都增
$C \rightarrow J$	$(3,0,0) < (5,3,3)$	第 1、2、3 维都增

识别并发事件（Lamport 做不到的事）：

并发对	向量比较	为什么不可比较
$C \;\&\; F$	$(3,0,0) \parallel\mid (2,2,1)$	第 1 维 $3 > 2$（$C$ 更大），第 2 维 $0 < 2$（$F$ 更大）——互不包含
$H \;\&\; C$	$(0,0,1) \parallel\mid (3,0,0)$	第 3 维 $1 > 0$，第 1 维 $0 < 3$——互不包含

核心结论（必须点明）：向量时钟精确刻画了因果性—— $a \rightarrow b \iff V(a) < V(b), \qquad a \parallel b \iff V(a),V(b) \text{ 不可比较}$ 这是 Lamport 时钟做不到的：Lamport 只保证 $\Rightarrow$ 方向，向量时钟两个方向都保证（双向等价）。代价是空间：Lamport 只需 $O(1)$（一个整数），向量时钟需要 $O(N)$（$N$ 个整数，且每条消息都要带上它们）。

关键假设与系统模型：向量时钟要求进程集合已知且固定（$N$ 是常数，每个向量长度固定）。这是它在实践中最大的痛点：动态成员变更、客户端也是参与者、$N$ 达数千时消息头会爆炸（见 11.5 的工程解法）。

11.2.12 本章的哲学：时间是被测量的，还是被构造的？

把 11.2 的全部内容压缩成一张对照图：

   需求: 给跨进程的事件排序
        │
        ├── 路线 A: 让物理时钟变准  ──►  Cristian / NTP / PTP / TrueTime
        │        工具: RTT 测量 + 区间取中点 + 分层树 + 统计过滤
        │        保证: 误差 < RTT/2   (有界!)
        │        但:   误差永远非零; 延迟非对称 ⇒ 系统性偏差;
        │              服务器是单点故障与攻击面
        │        适用: 需要"真实时刻"的场合 (审计/计费/证书/跨集群事务)
        │
        └── 路线 B: 干脆不要物理时间  ──►  Happens-Before / Lamport / 向量时钟
                 工具: 计数器 + max 合并 + 向量
                 保证: 因果性 100% 正确, 与时钟偏差、网络延迟完全无关
                 但:   给出的时间戳不是真实时间, 不能回答"这是几点"
                       向量时钟还要付 O(N) 空间
                 适用: 需要"先后/因果"的场合 (冲突检测/全序多播/互斥/快照)

时间在分布式系统中不是被测量的，而是被构造的。 物理时钟给出”接近真实但永不可靠”的时间；逻辑时钟给出”不真实但绝对可靠”的因果顺序。二者不是”更好/更差”的关系，而是回答两个不同问题的两套工具：
当你需要回答”这件事发生在几点“（审计、计费、证书、与外部世界对齐）时，你必须用物理时钟，并且必须接受”误差非零”这一事实，用 RTT/2 或 TrueTime 的不确定区间把误差显式地表达出来；
当你需要回答”这两件事谁先谁后、是否冲突“（冲突解决、全序多播、互斥、快照）时，你应该用逻辑时钟——它免费给你 100% 的因果正确性，而且不受任何时钟质量的影响。
最成熟的系统会同时用两者：用物理时钟给出”大致真实”的序（HLC、TrueTime），用逻辑分量保证因果不被时钟误差颠倒。这正是 11.5 中混合逻辑时钟（HLC）的设计动机。

11.3 算法伪代码与正确性分析

本节把 11.2 的机制写成可执行的伪代码，并给出它们的正确性论证（安全性 + 活性）与复杂度。六份伪代码分别是：Cristian、NTP、Lamport、向量时钟、向量比较、Lamport 全序构造。

算法 11.3.1：Cristian 算法（外部同步）

假设与系统模型

系统模型：异步（消息延迟无上界，但每个方向有下界 $min_1, min_2 > 0$）；
进程：客户端 $P$（任意多个）与单个时间服务器 $S$；
故障模型：$S$ 是 crash-stop 且非 Byzantine（correct）——它不会说谎，但可能崩溃、可能暂时不可达；
通道假设：fair-loss（消息可能丢失或重复，但只要持续重传，最终能送达）；不要求 FIFO；
时钟假设：$P$ 的本地时钟可以向前调整（step 或 slew），速率可以微调；不允许回拨；
已知量：$P$ 预先标定过两个方向的最小单向延迟 $min_1, min_2$（来源：OS 缓冲开销 + TCP 排队时间等）。

伪代码

── 客户端 P 的状态 ────────────────────────────────────────────────
    C_P        : P 的本地时钟 (可读、可向前调整、速率可微调)
    min1, min2 : 预先标定的两个方向的最小单向延迟
    K          : 标定次数 (取多次读数的中位数/平均以抗抖动)

── P 的同步例程 (每 T 个时间单位执行一次, 且 T < M/(2*MDR)) ────────
upon timer tick do
    samples <- []                                  # 收集多次读数
    repeat K times:
        t0  <- read(C_P)                           # ① 发送前读本地钟
        send <TIME_REQ> to S                       # ② 发出请求
        upon receive <TIME_REP, t> from S:         # ③ t = S 处理请求时读到的钟值
            t3  <- read(C_P)                       # ④ 收到后立刻读本地钟
            RTT <- t3 - t0                         # ⑤ 往返时间 (同一时钟做差, 与偏差无关)
            target <- t + (RTT + min2 - min1)/2    # ⑥ 区间中点 = 此刻应有的真实时刻
            err_bd <- (RTT - min1 - min2)/2        # ⑦ 本次读数误差上界
            samples.append( (target, err_bd) )
    (t_best, e_best) <- argmin over samples of err_bd      # 取误差界最小的一次
    -- 校正: 绝不回拨 --
    if t_best > read(C_P) then
        adjust_clock_forward_to(C_P, t_best)               # 向前 step
    else
        slew(C_P, rate = 1 + delta)                        # 向后不可跳跃, 只能放慢速率慢慢追上
    return t_best, e_best

── 服务器 S (第三方时间源, 接 UTC/原子钟) ─────────────────────────
upon receive <TIME_REQ> from P do
    t <- read(C_S)                                 # 记录"处理该请求"的瞬时读数
    send <TIME_REP, t> to P

算法逻辑解说（走一遍数值小例子） 设 $min_1 = 10$ ms、$min_2 = 10$ ms。某次交换中 $L_1 = 30$ ms、$L_2 = 20$ ms、$S$ 的处理时间为 0：

$P$ 读得 $t_0$，发出请求；$S$ 在 30 ms 后收到，读到 $t = 12{:}00{:}00.000$；
响应走 20 ms 回到 $P$，$P$ 读到 $t_3$，于是 $\text{RTT} = t_3 - t_0 = 30+20 = 50$ ms；
真实到达时刻是 $t + 20\text{ms}$，但 $P$ 不知道 20 这个数；它算出区间 $[\,t + min_2,\ t + \text{RTT} - min_1\,] = [\,t+10\text{ms},\ t+40\text{ms}\,]$；
取中点：$t + (50 + 10 - 10)/2 = t + 25$ ms，真实值 20 ms 与估计值 25 ms 相差 5 ms，误差上界 $(50-10-10)/2 = 15$ ms，$5 \le 15$ ✓。

正确性论证

定理 5（Cristian 误差界）：在算法 11.3.1 的假设下，$P$ 校正后的时钟与真实时间之差不超过 $\dfrac{\text{RTT} - min_1 - min_2}{2}$；若 $min_1, min_2$ 未知而使用 $t + \text{RTT}/2$，则误差不超过 $\dfrac{\text{RTT}}{2}$。

证明：记响应到达 $P$ 时的真实时刻为 $T_{recv}$，响应消息的单向延迟为 $L_2$，则 $T_{recv} = t + L_2 .$ （$t$ 是 $S$ 在收到请求那一刻读到的钟值；$S$ 的钟被假设为权威。若 $S$ 有处理时间 $proc$，则把 $proc$ 计入 $L_2$ 或从 RTT 中扣除即可，结论不变。）

由假设 $L_2 \ge min_2$ 得下界；由 $\text{RTT} = L_1 + L_2$ 且 $L_1 \ge min_1$ 得 $L_2 = \text{RTT} - L_1 \le \text{RTT} - min_1$，得上界。因此 $L_2 \in \left[\, min_2,\ \ \text{RTT} - min_1 \,\right].$ 算法把钟设成 $t + \dfrac{\text{RTT} + min_2 - min_1}{2}$，它恰好是上面这个区间的中点（区间中点为 $\frac{min_2 + \text{RTT} - min_1}{2}$）。于是误差就是 $L_2$ 到区间中点的偏差，而任何落在区间内的点到中点的距离不超过半宽： $\left\vert \text{设定值} - T_{recv} \right\vert = \left\vert \frac{\text{RTT} + min_2 - min_1}{2} - L_2 \right\vert \le \frac{(\text{RTT}-min_1) - min_2}{2} = \frac{\text{RTT} - min_1 - min_2}{2}.$ 这就证明了第一个结论。第二个结论是它的特例：若不知道 $min_1, min_2$，只能用最宽的可能区间 $[0, \text{RTT}]$（因为 $L_2 \ge 0$ 且 $L_2 \le \text{RTT}$），中点为 $\text{RTT}/2$，半宽为 $\text{RTT}/2$，故误差 $\le \text{RTT}/2$。$\blacksquare$

安全性（Safety）：三条。

误差有界（定理 5）：这是算法相对朴素方案的本质改进——朴素方案误差为 $L_2$，在异步模型下无界；本算法把误差锁死在可测量的 $\text{RTT}/2$ 之内。
单调性不被破坏：算法只在 $t_{best} > \text{read}(C_P)$ 时向前 step，否则只 slew（放慢速率）。因此进程 $P$ 的钟值永远不递减，同一进程内事件的先后顺序永远不会被校正动作颠倒。这是”时钟只能前进不能后退”这条黄金法则的算法化。
不依赖 $S$ 的连续性：每次同步都是”一问一答”的无状态交互，$S$ 崩溃只是让这一次同步失败，不会使 $P$ 的钟进入错误状态（$P$ 的钟仍在按本地晶振前进，只是逐渐漂离）。

活性（Liveness）：

每次同步最终终止：只要 fair-loss 假设成立且 $P$ 持续重传，请求-响应交换最终会完成（每次尝试有非零成功概率）；
误差不会无限增长（在 $S$ 可用的前提下）：若同步周期 $T < M/(2\,\text{MDR})$，则任意相邻两次同步之间 skew 的增长不超过 $M$，因此系统的 skew 被 $M + \text{RTT}/2$ 界定；
$S$ 崩溃时的降级行为：$P$ 仍然可用（不会阻塞），只是精度退化为”MDR × 距上次同步的时间”。这正是可用性与精度之间的取舍：时间同步不是硬依赖，而是精度依赖。

复杂度：每次同步 2 条消息（一次请求 + 一次响应），$P$ 侧 $O(1)$ 状态（$t_0, K$ 个样本）；时间上无等待（可以异步发起，不阻塞其它计算）；精度 $O(\text{RTT})$。

算法 11.3.2：NTP 的偏移计算与时钟校正

假设与系统模型

系统模型：异步；服务器组织成树（分层），每个节点只与自己的树父节点同步，客户端是叶子；
故障模型：父节点可能不可达（此时切换到备选父节点）；NTP 通过多源（多个服务器）+ Marzullo/交集算法来抵御单个服务器的错误读数（讲义未展开，属补充）；
通道假设：UDP，报文可能丢失；不要求对称（$L_1$ 与 $L_2$ 可以不同，这正是误差的来源）；
时钟假设：本地时钟可以 step（初始或偏差极大时）或 slew（常规）；需要周期性重复执行。

伪代码

── Child 侧状态 ────────────────────────────────────────────────
    C_child : 本地时钟
    peers   : 一组候选父节点 (stratum 更小者)

── 一次 NTP 测量 (与某一个 parent 之间) ────────────────────────
upon poll timer (每 2^k 秒, 自适应) do
    t_s1 <- read(C_child)                        # ① Child 发送 M1 的时刻
    send <M1, t_s1> to parent
    upon receive <M2, t_s1_echo, t_r1, t_s2> from parent:
        t_r2 <- read(C_child)                    # ② Child 收到 M2 的时刻
        RTT  <- (t_r2 - t_s1) - (t_s2 - t_r1)    # ③ 纯网络往返 = 总耗时 - 服务器停留时间
        o    <- ((t_r1 - t_r2) + (t_s2 - t_s1)) / 2      # ④ 偏移 (定理 6)
        d    <- RTT / 2                                   # ⑤ 单次测量的误差上界
        record (o, d) into filter[]

    -- 过滤 (filter): 对同一 parent 的最近 8 次测量按 o 排序, 取中位数 --
    -- 选择 (select/cluster): 在多个 parent 之间用交集算法挑出最可靠的一组 --
    o_best, d_best <- cluster(filter[], all_parents)

    -- 时钟纪律 (clock discipline): 用锁相环把本地钟平滑拉向 o_best --
    if |o_best| > STEP_THRESHOLD and not already_synced then
        step(C_child, by = o_best)               # 只在启动/偏差极大时跳变
    else
        slew(C_child, toward = o_best)           # 常规: 微调速率 (0.5 ms/s 量级), 绝不回拨
    return o_best, d_best

── Parent 侧 (同时又是它自己父节点的 child) ────────────────────
upon receive <M1, t_s1> from child do
    t_r1 <- read(C_parent)                       # 收到时刻
    t_s2 <- read(C_parent)                       # 发送时刻 (可与 t_r1 相同)
    send <M2, t_s1, t_r1, t_s2> to child         # 把父钟的两个读数带回 child

算法逻辑解说 Child 需要的是”我的钟比父钟差多少”。它手上只有四个数字，其中两个来自自己的钟（$t_{s1}, t_{r2}$）、两个来自父钟（$t_{r1}, t_{s2}$）。公式 $o = \frac{(t_{r1}-t_{r2})+(t_{s2}-t_{s1})}{2}$ 的直觉是：分子里两个括号分别度量”父钟往前走的路”与”子钟往前走的路”，两者之差再折半，就是两条时间线之间的系统性偏移。剩下的残差正是两次单向延迟之差的一半——它无法被消除，只能被 RTT 界定。

正确性论证

定理 6（NTP 误差界）：设 Message 1 与 Message 2 的单向延迟分别为 $L_1, L_2$，真实偏移为 $o_{real}$，则按上式计算出的 $o$ 满足 $\left\vert o_{real} - o \right\vert = \left\vert \frac{L_2 - L_1}{2} \right\vert \;<\; \frac{L_1 + L_2}{2} \;=\; \frac{\text{RTT}}{2}.$

证明：由定义列出两条方程（讲义口径，即 $o_{real}$ 度量”父钟相对子钟的超前量”）： $t_{r1} = t_{s1} + L_1 + o_{real}, \qquad t_{r2} = t_{s2} + L_2 - o_{real}.$ 两式相减： $t_{r1} - t_{r2} = (t_{s1} - t_{s2}) + (L_1 - L_2) + 2 o_{real}.$ 把 $(t_{s2}-t_{s1})$ 移到左边并两边除以 2： $o_{real} = \underbrace{\frac{(t_{r1}-t_{r2}) + (t_{s2}-t_{s1})}{2}}_{= \; o} + \frac{L_2 - L_1}{2}.$ 于是 $o_{real} - o = \frac{L_2-L_1}{2}$，取绝对值并用 $\lvert L_2 - L_1\rvert \le L_1 + L_2$（$L_1, L_2 \ge 0$）得到 $\lvert o_{real} - o\rvert = \left\vert \frac{L_2-L_1}{2}\right\vert \le \frac{L_1+L_2}{2} = \frac{\text{RTT}}{2}.$ （严格不等号在 $L_1 \ne L_2$ 时成立；$L_1 = L_2$ 时误差为 0。）$\blacksquare$

安全性（Safety）：

误差有界：$\lvert o_{real}-o\rvert < \text{RTT}/2$，且 RTT 可由 child 本地测得，不需要任何额外的同步假设；
不受时钟偏差污染：RTT 的计算 $(t_{r2}-t_{s1}) - (t_{s2}-t_{r1})$ 中，child 的偏差在 $t_{r2}-t_{s1}$ 中抵消、parent 的偏差在 $t_{s2}-t_{r1}$ 中抵消，因此 RTT 的测量是干净的；
时钟单调性：常规校正使用 slew 而非 step，保证本地钟永不回拨（NTP 会在偏差极大时才 step，且通常在启动阶段）。

活性（Liveness）：轮询周期自适应（同步稳定后指数退避到 1024 秒量级，误差增大时收紧），因此只要父节点最终可达，child 的偏差就不会无限增长。多层树的降级：父节点失效时切换到同层或更高层的其它服务器，整棵树不会因为一个节点崩溃而失去时间。

复杂度：每次测量 2 条消息；每次测量的状态 $O(1)$（但需要保留最近 8 次样本做过滤，仍是常数）；精度 WAN 内毫秒级、LAN 内亚毫秒级。

算法 11.3.3：Lamport 逻辑时钟

假设与系统模型

系统模型：异步，不需要任何时钟同步（这是它最大的优点）；
进程数：任意 $N$，无需事先知道 $N$；进程集合可以动态变化；
故障模型：无故障假设即可工作（崩溃的进程不再产生事件，不影响其它进程）；消息可丢失（丢失只意味着某个因果链路没被”传播”，不破坏正确性）；
通道假设：不要求 FIFO、不要求可靠（只需”已发生的因果关系不被错误地颠倒”）；
状态：每个进程一个整数计数器，初值 0。

伪代码

── 进程 i 的状态 ──────────────────────────────────────────────
    L : integer = 0                  # 本地逻辑时钟

── 事件处理 (三类) ────────────────────────────────────────────
upon (内部 instruction / 任意本地事件) at process i do
    L <- L + 1                       # 规则 1: 本地事件递增
    timestamp(e) <- L
    deliver_locally(e, L)

upon send(m) to Pj at process i do
    L <- L + 1                       # 规则 1': send 也是事件, 也要递增
    timestamp(e_send) <- L
    send <m, L> to Pj                # 规则 2: 消息携带发送事件的时间戳

upon receive(<m, Lm>) from Pj at process i do
    L <- max(L, Lm) + 1              # 规则 4: 先追上发送方, 再加一
    timestamp(e_recv) <- L
    deliver_locally(m, L)

── 查询 ──────────────────────────────────────────────────────
function lamport_of(e): return timestamp(e)
function total_order_key(e): return (timestamp(e), pid(e))       # 见算法 11.3.6

算法逻辑解说

每个事件都立即得到一个时间戳，无需与任何人通信——这是 Lamport 时钟在工程上如此流行的根本原因：它是零协调（coordination-free）的；
唯一需要网络配合的地方是 receive：把消息带来的时间戳与本地时钟取 max。取 max 意味着接收方的逻辑时钟只会被”拉高”，永远不会被”拉低”，这保证了它的单调性；
具体数值例子见 11.2.10 的 11 步演化表（$A{=}1, B{=}2, C{=}3, D{=}5, E{=}6$；$E^{\prime}{=}2, F{=}3, G{=}4$；$H{=}1, I{=}2, J{=}7$），其中第 8 步 $D = \max(3,4)+1 = 5$ 是最能说明问题的一步：本地钟明明只走到 3，但收到携带 4 的消息后必须跳到 5，否则 $D$ 就会小于发送事件 $G$，因果性被破坏。

正确性论证

定理 1（Lamport 逻辑时钟遵守因果性）：若 $a \rightarrow b$，则 $L(a) < L(b)$。

证明：关系 $\rightarrow$ 是由规则 R1、R2 生成、并在 R3 下封闭的最小关系，因此任何 $a \rightarrow b$ 都有一个有限的推导，我们对推导中使用的规则次数 $k$ 做归纳。

基础情形 $k = 1$（只用了一条规则）：

R1（同一进程）：设进程 $i$ 的事件按本地发生顺序为 $e_1, e_2, \ldots$。对每个 $m$，$e_{m+1}$ 要么是本地事件（$L \leftarrow L+1$），要么是 receive（$L \leftarrow \max(L, L_m)+1 \ge L+1$）。两种情形都有 $L(e_{m+1}) \ge L(e_m) + 1 > L(e_m)$。由归纳（对下标 $m$）可知同进程内任意靠后的事件时间戳都更大，故 $a$ 在 $b$ 之前 $\Rightarrow L(a) < L(b)$。
R2（send → receive）：设 $s$ 是 $i$ 的发送事件，携带时间戳 $L(s)$。接收方 $j$ 执行 $L(recv) = \max(L_j, L(s)) + 1 \ge L(s) + 1 > L(s)$。故 $L(s) < L(recv)$。

归纳步 $k > 1$：此时 $a \rightarrow b$ 必然是 R3 产生的，即存在事件 $c$ 使得 $a \rightarrow c$ 且 $c \rightarrow b$，而这两个推导分别只用了少于 $k$ 条规则。由归纳假设 $L(a) < L(c)$ 且 $L(c) < L(b)$；由整数严格序的传递性得到 $L(a) < L(b)$。$\blacksquare$

定理 2（定理 1 的逆命题不成立）：$L(a) < L(b) \not\Rightarrow a \rightarrow b$。并且任何只用 $O(1)$ 空间（单个整数）的逻辑时间戳方案都无法做到精确判定因果与并发。

证明（第一部分的两个反例，直接取自讲义的例子）：

取 11.2.10 中的 $H$ 与 $C$：$L(H) = 1 < L(C) = 3$，但 $H \parallel C$（$H$ 在 P3 的第一个事件，$C$ 在 P1 的第三个事件，两条因果路径都不通）。时间戳有序，事件却并发；
取 $C$ 与 $F$：$L(C) = L(F) = 3$，而它们并发。时间戳相等，事件却不同。

证明（第二部分的”为什么 $O(1)$ 做不到”——一个干净的结构性论证）：设某个时间戳方案使用全序的值域（整数就是全序的）并且精确刻画因果，即要求 $a \rightarrow b \iff T(a) < T(b), \qquad a \parallel b \iff T(a), T(b) \text{ 不可比较}.$ 在全序的值域里，两个值”不可比较”只有一种可能：它们相等。于是方案必须满足”并发 ⟺ 时间戳相等“。现在构造三个事件：进程 $P_1$ 上 $a \rightarrow c$（$a$ 发消息给 $P_3$ 得到 $c$），另有一个进程 $P_2$ 上的事件 $b$，使得 $b$ 与 $a$、$b$ 与 $c$ 都并发（例如 $P_2$ 独立执行，不与任何人有消息往来）。则由”并发 ⟺ 相等”必须同时有 $T(a) = T(b)$ 与 $T(b) = T(c)$，由等号传递性得 $T(a) = T(c)$；但 $a \rightarrow c$ 又要求 $T(a) < T(c)$——矛盾。$\blacksquare$

这个论证给出了一个很强的结论：想同时判定”因果”与”并发”，单靠一个全序的时间戳是不够的，时间戳的取值范围必须是一个偏序（且要与因果偏序同构）。接下来自然的问题是”至少要多大”：

补充说明（维数下界，Charron-Bost 1991）：一个事件的因果过去（causal past / 一致割）由 $N$ 个数字刻画——”每个进程各贡献了多少个事件”，而这 $N$ 个数字可以彼此独立地变化。可以证明：能精确刻画 $N$ 进程计算之因果关系的”有序向量空间”的最小维数恰好是 $N$（Charron-Bost, Concerning the size of logical clocks in distributed systems, IPL 1991）。因此向量时钟的 $O(N)$ 不是实现上的奢侈，而是理论下界——想要既判因果又判并发，$N$ 维信息是省不掉的。

安全性（Safety）：由定理 1，任何因果链上的两个事件都满足 $L$ 严格递增，因果顺序永远不会被逻辑时间戳颠倒；又因为 $L$ 在单个进程内严格递增（每步至少 +1），同一进程内的事件也永远不会拿到逆序的时间戳。这两条合起来，使 Lamport 时钟可以在任何”只要求因果不被违反”的场景里安全使用。它唯一不保证的是定理 2 指出的那件事——并发事件可能被排序或得到相等的时间戳，因此不能用它来判定两个事件是否真的相关。

活性（Liveness）：Lamport 时钟的活性论证异常简单而有力：每个事件在发生的瞬间就被打上时间戳，不需要等待任何消息、任何应答、任何协调。因此它永远不会阻塞，即使所有消息都丢失、所有其它进程都崩溃，本地系统仍然可以继续给事件打戳。这与外面世界的物理时钟形成了鲜明对照——物理时钟需要同步才有意义，逻辑时钟自己就是自己。

复杂度：空间 $O(1)$（每进程一个整数）；消息开销 每消息一个整数（$O(1)$）；时间开销 $O(1)$ per event。

算法 11.3.4：向量时钟

假设与系统模型

系统模型：异步，同样不需要时钟同步；
进程数：已知且固定为 $N$（这是向量时钟的核心假设，也是它最大的工程限制）；
故障模型：无故障假设即可；消息可丢失（丢失只导致”某些因果信息没传播”，不影响正确性，只影响精度——实际上会导致因果性判定的方向性问题，见 11.7 陷阱 6）；
通道假设：不要求 FIFO、不要求可靠；
状态：每个进程一个长度为 $N$ 的整数向量。

伪代码

── 进程 i 的状态 ──────────────────────────────────────────────
    V[1..N] : integer array = [0,0,...,0]        # V[i] 是"自己的事件计数"
                                                  # V[j] 是"我知道的 j 的事件数"
    me      : constant = i

── 事件处理 (三类) ────────────────────────────────────────────
upon (内部 instruction / 任意本地事件) at process i do
    V[i] <- V[i] + 1                     # 规则 1: 只递增自己那一维
    timestamp(e) <- copy(V)
    deliver_locally(e, copy(V))

upon send(m) to Pj at process i do
    V[i] <- V[i] + 1                     # 规则 1': send 也是本地事件
    timestamp(e_send) <- copy(V)
    send <m, copy(V)> to Pj              # 规则 2: 消息携带完整向量

upon receive(<m, Vm>) from Pj at process i do
    V[i] <- V[i] + 1                     # 规则 3a: 先递增自己那一维
    for each k in 1..N, k != i do
        V[k] <- max(Vm[k], V[k])         # 规则 3b: 再对其他维逐维取 max (合并因果历史)
    timestamp(e_recv) <- copy(V)
    deliver_locally(m, copy(V))

── 因果判定 (见算法 11.3.5) ───────────────────────────────────
function happens_before(V1, V2): return V1 != V2 and forall k: V1[k] <= V2[k]
function concurrent(V1, V2):     return not happens_before(V1,V2) and not happens_before(V2,V1)

算法逻辑解说

与 Lamport 的唯一结构性差别是：本地事件的递增只影响”自己那一维”，而接收事件的合并是逐维取 max。可以这样理解：Lamport 用一个整数表示”我见过多少事”；向量用 $N$ 个整数表示”我分别从每个进程见过多少事”。$max$ 从”合并一个数”变成了”合并一份清单”。
具体数值例子见 11.2.11 的 11 步演化表（$A(1,0,0) \to D(4,3,1) \to E(5,3,1)$ 等），其中第 8 步 $D$ 的合并最能说明问题：接收前 $V_1 = (3,0,0)$，消息携带 $(2,3,1)$，合并后得到 $(4,3,1)$——$D$ 一次性”继承”了 P2 的 3 个事件与 P3 的 1 个事件，这正是”接收方获得发送方全部因果历史”的体现。

正确性论证

先陈述三条不变量（invariant），它们是把”$V_i[j]$ 是什么”讲清楚的精确形式：

$I_1$（消息里关于接收方的分量不会超过接收方当前值）：对任意消息 $V_m$ 与接收进程 $j$，$V_m[j] \le (\text{接收前 } j \text{ 已发生的事件数})$；
$I_2$（自己那一维等于自己的事件计数）：在任何时刻，$V_i[i] = $ 进程 $i$ 已经发生的事件总数；
$I_3$（每一维都精确等于因果过去中该进程的事件数）：对任意事件 $e$， $V(e)[j] = \left\vert \downarrow e \;\cap\; \{ \text{进程 } P_j \text{ 的事件} \} \right\vert , \qquad \text{其中 } \downarrow e \triangleq \{f : f \rightarrow e\} \cup \{e\} \text{ 是 } e \text{ 的因果过去}.$ 这条不变量是向量时钟的灵魂：它说明 $V(e)$ 不是别的，就是把 $e$ 的因果过去按进程”数”了一遍。它也精确化了讲义那句 “$V_i[j]$ is $i$’s knowledge of latest events at process $j$”。

$I_3$ 的归纳证明（对事件的因果结构归纳）：

本地事件：$e$ 在 $i$ 上紧跟 $e_{prev}$，$\downarrow e = \downarrow e_{prev} \cup \{e\}$，只多了一个 $P_i$ 的事件；算法把 $V[i]$ 加 1、其它维不动，与 $I_3$ 一致；
send 事件：与本地事件相同（send 就是一个本地事件）；
receive 事件：$recv$ 在 $j$ 上收到来自 $i$ 的消息，$\downarrow recv = \downarrow send \,\cup\, \downarrow prev \,\cup\, \{recv\}$（其中 $prev$ 是 $j$ 上紧邻 $recv$ 之前的事件）。对 $k \ne j$：$V(recv)[k] = \max(V(send)[k], V(prev)[k])$，而两个被比较的量都是 $P_k$ 事件序列的前缀长度，前缀的并就是较长的那一个，所以 $\max$ 恰好等于 $\left\vert (\downarrow send \cup \downarrow prev) \cap P_k\right\vert $ ✓。对 $k = j$：$V(recv)[j] = V(prev)[j] + 1$；因为 $send \rightarrow recv$，$send$ 的因果过去中那些 $P_j$ 的事件必然都发生在 $recv$ 之前（它们与 $recv$ 同在 $P_j$ 上，且因果在先），所以它们都已经计入 $V(prev)[j]$，因此 $V(prev)[j]+1 = \left\vert \downarrow recv \cap P_j\right\vert $ ✓。$I_3$ 得证。$\square$

定理 3（向量时钟的精确性）：$a \rightarrow b \iff V(a) < V(b)$（对 $a \ne b$）。

证明（$\Rightarrow$，对 $\rightarrow$ 的推导长度归纳）：

R1（同进程）：$a$ 在 $b$ 之前同处进程 $i$。由算法规则，$i$ 上每个事件都使其第 $i$ 维 $+1$（且其它维只可能因 receive 而变大、绝不减小），所以在 $a$ 与 $b$ 之间第 $i$ 维严格增长，而所有维非减，故 $V(a) \le V(b)$ 且 $V(a)[i] < V(b)[i]$，即 $V(a) < V(b)$；
R2（send → receive）：设发送事件 $s$ 在 $i$、接收事件 $r$ 在 $j$，消息携带 $V(s)$。对 $k \ne j$：$V(r)[k] = \max(V(s)[k], V(prev)[k]) \ge V(s)[k]$；对 $k = j$：需要 $V(s)[j] \le V(r)[j] = V(prev)[j]+1$。由 $I_2$，$V(prev)[j]$ 是 $r$ 之前 $j$ 的事件数；而 $V(s)[j]$ 是 $s$ 的因果过去中 $j$ 的事件数。由于 $s \rightarrow r$ 且都在……（$s$ 在 $i$，$r$ 在 $j$）——$s$ 的因果过去里任何 $P_j$ 的事件 $f$ 都满足 $f \rightarrow s \rightarrow r$；又 $f$ 与 $r$ 同属 $P_j$，故 $f$ 必然发生在 $r$ 之前，于是被 $V(prev)[j]$ 计入。所以 $V(s)[j] \le V(prev)[j] < V(prev)[j]+1 = V(r)[j]$ ✓。合起来 $V(s) \le V(r)$ 且第 $j$ 维严格小，即 $V(s) < V(r)$；
R3（传递性）：若 $V(a) \le V(b) < V(c) \le \ldots$，逐维 $\le$ 的传递性加上”某维严格”在每一步都保留，故 $<$ 传递。

证明（$\Leftarrow$，即 $\neg(a \rightarrow b) \Rightarrow \neg(V(a) < V(b))$，用 $I_3$ 直接构造）：设 $V(a) < V(b)$，即对所有 $j$ 有 $V(a)[j] \le V(b)[j]$。由 $I_3$，$V(a)[j] = \lvert \downarrow a \cap P_j\rvert$、$V(b)[j] = \lvert \downarrow b \cap P_j \rvert$，而两者都是 $P_j$ 事件序列的前缀长度；前缀长度的大小关系就是包含关系： $\forall j:\ \downarrow a \cap P_j \;\subseteq\; \downarrow b \cap P_j .$ 对所有 $j$ 取并集（$j$ 遍历全部进程），得 $\downarrow a \subseteq \downarrow b$。由于 $a \in \downarrow a \subseteq \downarrow b = \{f : f \rightarrow b\}\cup\{b\}$，必有 $a \rightarrow b$ 或 $a = b$。若 $a = b$ 则 $V(a) = V(b)$，与严格小于矛盾，故 $a \rightarrow b$。$\blacksquare$

定理 4（并发判定）：对两个不同的事件 $a \ne b$，$a \parallel b \iff V(a)$ 与 $V(b)$ 不可比较（即 $\neg(V(a) \le V(b)) \wedge \neg(V(b) \le V(a))$）。

证明：由定义 $a \parallel b \iff \neg(a \rightarrow b) \wedge \neg(b \rightarrow a)$。由定理 3 的双向等价，$\neg(a \rightarrow b) \iff \neg(V(a) < V(b))$，$\neg(b \rightarrow a) \iff \neg(V(b) < V(a))$。由于 $a \ne b$ 时 $V(a) \ne V(b)$（若相等，则由定理 3 双向都会得出 $a \rightarrow b$ 与 $b \rightarrow a$，矛盾），$\neg(V(a)<V(b))$ 等价于 $\neg(V(a) \le V(b))$，故结论成立。$\blacksquare$

安全性（Safety）：定理 3 与定理 4 合起来给出的正是”因果性永不被颠倒，且并发永不被误判为因果“这一最强保证。特别地，与物理时钟形成鲜明对比：无论网络延迟多大、时钟多不准、消息何时到达，向量时钟给出的因果关系都是正确的——它不测量时间，所以时间无法伤害它。

活性（Liveness）：与 Lamport 时钟相同——每个事件在发生瞬间即被打戳，接收时的合并是纯本地计算（$O(N)$ 次比较），不需要等待任何第三方，永不阻塞。

复杂度：空间 $O(N)$ per process；每条消息携带 $N$ 个整数（这是最痛的开销）；每个事件 $O(N)$ 时间。

算法 11.3.5：向量时钟的比较函数

假设与系统模型：两个向量长度相同（都是 $N$）；纯函数，无副作用、无通信。

伪代码

function compare(V1[1..N], V2[1..N]):
    le1 <- true ; le2 <- true
    for k in 1..N do
        if V1[k] > V2[k] then le1 <- false
        if V2[k] > V1[k] then le2 <- false
        if not le1 and not le2 then break        # 提前退出: 已经互不包含
    if le1 and le2 then return EQUAL             # V1 == V2 (逐维相等)
    if le1        then return BEFORE             # V1 < V2  => 事件1 因果先于 事件2
    if le2        then return AFTER              # V2 < V1  => 事件1 因果后于 事件2
    return CONCURRENT                            # 不可比较 => 两事件并发

算法逻辑解说：函数名对应讲义的四条比较规则：

EQUAL ⟺ $VT_1 = VT_2$（逐维全等，对应同一个事件或”同一份因果历史”）；
BEFORE ⟺ $VT_1 < VT_2$ ⟺ $VT_1 \le VT_2$ 且存在 $j$ 使 $VT_1[j] < VT_2[j]$（因为已经排除了相等，le1 且非 le2 恰好等价于此）；
AFTER 对称；
CONCURRENT ⟺ $\neg(VT_1 \le VT_2) \wedge \neg(VT_2 \le VT_1)$，即讲义记作 $VT_2 \parallel\mid VT_1$ 的情形。

正确性论证

安全性（返回值正确）：容易对 $N$ 归纳验证：le1 为真当且仅当 $\forall k, V_1[k] \le V_2[k]$（即 $V_1 \le V_2$），le2 同理。四个分支互斥且穷尽：
- le1 ∧ le2 ⇒ 逐维双向 $\le$ ⇒ 逐维相等 ⇒ $V_1 = V_2$；
- le1 ∧ ¬le2 ⇒ $V_1 \le V_2$ 且 $V_1 \ne V_2$ ⇒ $V_1 < V_2$；
- 其余对称；¬le1 ∧ ¬le2 ⇒ 两个方向都不 $\le$ ⇒ 不可比较 ⇒ 并发。由定理 3/4，这四个返回值恰好对应”因果在前 / 因果在后 / 同一事件 / 并发”。
三分性（trichotomy）：对任意两个向量，上述四种情形恰有一种成立，不存在”既非相等、又非小于、又非大于、又非并发”的第五种情况。这正是”逐维乘积偏序”的结构性质。
活性：循环至多执行 $N$ 次（可提前 break），必然终止。

复杂度：时间 $O(N)$（最坏 $N$ 次比较/分支），空间 $O(1)$ 额外空间。在 “$N$ 个进程、$E$ 个事件”的系统中，全量两两比较的代价是 $O(E^2 N)$——这正是许多应用只做”局部比较”（例如只把新版本与已存版本比较）而不做全局排序的原因。

算法 11.3.6：用 Lamport 时间戳构造全序（total order）

假设与系统模型：已按算法 11.3.3 给每个事件打上 Lamport 时间戳；每个事件还携带发起它的进程标识 $pid$（$pid$ 是全序且互不相同的常数）；所有参与者对”如何比较 $pid$”有一致的约定（例如按数值大小）。

伪代码

── 每个事件 e 的排序键 ────────────────────────────────────────
function key(e): return (lamport(e), pid(e))       # 字典序: 先比 ts, 相等再比 pid

function less(e1, e2):                             # 严格全序关系 "<_T"
    if lamport(e1) != lamport(e2):
        return lamport(e1) < lamport(e2)
    else:
        return pid(e1) < pid(e2)                   # tie-break: 并发事件由 pid 定序

── 在任意进程上都能导出的全局顺序 ─────────────────────────────
function total_order(events):
    return sort(events, by = key)                  # 所有进程排序结果完全一致

算法逻辑解说：Lamport 时间戳本身不是全序的键——11.2.10 的例子里 $A$ 与 $H$ 都是 1、$B$、$E^{\prime}$、$I$ 都是 2、$C$ 与 $F$ 都是 3。加上 $pid$ 作为 tie-break 后，全序变成： $A \;<\; H \;<\; B \;<\; E^{\prime} \;<\; I \;<\; C \;<\; F \;<\; G \;<\; D \;<\; E \;<\; J .$ 这个顺序看起来有点”怪”——比如 $I$（P3 的第二个事件）排在了 $C$（P1 的第三个事件）前面，而画在图上 $C$ 的位置更靠左。这不是 bug：$C$ 与 $I$ 是并发事件，逻辑时间对它们的先后本来就是任意的，任何一致的约定都可以。请把这个例子和 11.2.10 的图对照看——逻辑时间不是物理时间。

正确性论证

定理 7（$(\text{Lamport}, pid)$ 是一个与因果一致的全序）：定义 $e_1 \prec e_2 \iff \big(L(e_1) < L(e_2)\big) \vee \big(L(e_1) = L(e_2) \wedge pid(e_1) < pid(e_2)\big)$。则 (a) $\prec$ 是事件集合上的全序（total order）； (b) $\prec$ 是 happens-before 偏序的一个线性扩展（linear extension），即 $a \rightarrow b \Rightarrow a \prec b$。

证明 (a)：

三分性：任取两个不同事件 $a \ne b$。若 $L(a) \ne L(b)$，则 $L$ 的整数序已判定先后；若 $L(a) = L(b)$，则 $a, b$ 必属于不同进程——因为同一进程内的事件时间戳严格递增（定理 1 证明中 R1 部分已证：每步至少 +1），故 $pid(a) \ne pid(b)$，仍可判定先后。不存在无法比较的事件对；
反对称性：$\prec$ 是字典序，由 $(\mathbb{Z}, <)$ 与 $(\text{pid}, <)$ 都是严格序保证；
传递性：字典序的传递性（按第一分量、再按第二分量分情形验证即可）。

证明 (b)：设 $a \rightarrow b$。由定理 1，$L(a) < L(b)$，于是按定义 $a \prec b$（第一分量就已判定，无需用到 $pid$）。因此 $\prec$ 保留了 $\rightarrow$ 的全部顺序关系，即 $\prec$ 是 $\rightarrow$ 的线性扩展。$\blacksquare$

注意 (b) 的证明只用到定理 1，完全不涉及 $pid$ 的选择——这说明任意能打破时间戳平局的确定性规则都能得到合法全序。因此全序是不唯一的，但所有合法的全序都满足”因果不被颠倒”。

安全性（Safety）：不会出现”$a \rightarrow b$ 但 $b$ 排在 $a$ 前面”的情况（定理 7b）。这是全序多播（Ch.13）与分布式互斥（Ch.14）所依赖的核心性质。

活性（Liveness）：只要消息携带时间戳就能在本地完成排序，无需共识、无需额外通信轮次。这是它相对于 Paxos/Raft 的巨大优势：总序的构造是免费的，代价是这个总序未必与真实时间一致，也不能保证所有进程都收到了同样的消息集合（而复制状态机需要的是”相同的交付顺序 + 相同的集合”，这也是为什么真正的全序多播还需要额外的机制，详见 Ch.13）。

复杂度：排序 $O(E \log E)$（$E$ 为事件数）；每个事件的键 $O(1)$ 空间；无额外消息开销（$pid$ 是常数，时间戳已随消息携带）。

11.4 代码示例与分布式实现

三个程序都只用 Python 标准库、自包含、固定随机种子（random.seed(425)）、可直接 python3 xxx.py 运行。程序 1 用真实线程 + queue.Queue 模拟三个并发进程（不是单线程顺序调用），并精确复现讲义的三进程例子。

11.4.1 程序 1：Lamport 时钟 + 向量时钟的线程级模拟器

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""CS425 Ch.11 程序 1: Lamport 时钟 + 向量时钟的线程级模拟器.
精确复现讲义 P1/P2/P3 与事件 A..J 的例子, 并断言讲义给出的所有因果/并发关系。
3 个真实线程通过 queue.Queue 互相收发消息; 只用标准库。"""
import queue, random, threading, time

random.seed(425)
NPROC = 3


class LamportClock:
    """Lamport 逻辑时钟: 一个整数, 三条规则 (本地事件 / send / receive)。"""

    def __init__(self):
        self.value = 0

    def local_event(self):
        self.value += 1
        return self.value

    def send_event(self):                       # send 也是一个本地事件
        return self.local_event()

    def receive_event(self, msg_ts):            # 规则: max(本地, 消息) + 1
        self.value = max(self.value, msg_ts) + 1
        return self.value


class VectorClock:
    """向量时钟: N 维整数向量, 三条规则。"""

    def __init__(self, nproc, me):
        self.nproc, self.me, self.v = nproc, me - 1, [0] * nproc

    def local_event(self):                      # 规则 1: 只递增自己那一维
        self.v[self.me] += 1
        return tuple(self.v)

    def send_event(self):
        return self.local_event()

    def receive_event(self, msg_v):             # 规则 3: 先递增自己, 再对其余维取 max
        self.v[self.me] += 1
        for j in range(self.nproc):
            if j != self.me:
                self.v[j] = max(msg_v[j], self.v[j])
        return tuple(self.v)


class Process(threading.Thread):
    """每个进程 = 一个线程 + 一个信箱 (queue.Queue), 顺序执行自己的脚本。"""

    def __init__(self, pid, script, inboxes, trace, lock):
        super().__init__(daemon=True)
        self.pid, self.script, self.inboxes = pid, script, inboxes
        self.trace, self.lock = trace, lock
        self.lc, self.vc, self.box = LamportClock(), VectorClock(NPROC, pid), inboxes[pid]

    def mark(self, name, kind, lts, vts, extra=""):     # 记录一次事件
        with self.lock:
            self.trace.append(dict(pid=self.pid, name=name, kind=kind,
                                   lamport=lts, vector=vts, extra=extra))

    def run(self):
        for step in self.script:
            time.sleep(random.uniform(0.0, 0.002))   # 制造真实的并发交错
            kind, name = step[0], step[1]
            if kind == "local":
                self.mark(name, "local", self.lc.local_event(), self.vc.local_event())
            elif kind == "send":
                target, msg_id = step[2], step[3]
                vts, lts = self.vc.send_event(), self.lc.send_event()
                self.mark(name, "send", lts, vts, "->P%d" % target)
                self.inboxes[target].put((msg_id, name, lts, vts, self.pid))
            else:                                     # recv: 阻塞等待消息 (真实的消息传递)
                _, sname, lts_m, vts_m, src = self.box.get()
                lts = self.lc.receive_event(lts_m)
                vts = self.vc.receive_event(vts_m)
                self.mark(name, "recv", lts, vts, "<-P%d(%s)" % (src, sname))


# 讲义原例: P1: A,B(send->P2),C,D(recv),E(send->P3); P2: E'(recv),F(recv),G(send->P1)
#           P3: H(send->P2),I,J(recv)
SCRIPT = {1: [("local", "A"), ("send", "B", 2, "m2"), ("local", "C"), ("recv", "D"),
              ("send", "E", 3, "m4")],
          2: [("recv", "E'"), ("recv", "F"), ("send", "G", 1, "m3")],
          3: [("send", "H", 2, "m1"), ("local", "I"), ("recv", "J")]}


def happens_before(v1, v2):
    """定理 3: v1 -> v2 当且仅当 v1 <= v2 (逐维) 且 v1 != v2。"""
    return v1 != v2 and all(a <= b for a, b in zip(v1, v2))


def concurrent(v1, v2):
    """定理 4: 不可比较 <=> 并发。"""
    return not happens_before(v1, v2) and not happens_before(v2, v1)


def relation(v1, v2):
    if v1 == v2:
        return "="
    if happens_before(v1, v2):
        return "->"
    return "<-" if happens_before(v2, v1) else "||"


def main():
    inboxes = {i: queue.Queue() for i in range(1, NPROC + 1)}
    trace, lock = [], threading.Lock()
    procs = [Process(i, SCRIPT[i], inboxes, trace, lock) for i in range(1, NPROC + 1)]
    [p.start() for p in procs]
    [p.join(timeout=5) for p in procs]
    ev = {e["name"]: e for e in trace}
    order = ["A", "B", "C", "D", "E", "E'", "F", "G", "H", "I", "J"]

    print("=" * 76)
    print("1) 每个事件的 Lamport 时间戳与向量时间戳 (讲义原例)")
    print("=" * 76)
    print("%-5s %-5s %-9s %-13s %s" % ("事件", "进程", "Lamport", "向量时间戳", "类型"))
    for nm in order:
        e = ev[nm]
        print("%-6s P%-4d %-9d %-13s %s %s" % (nm, e["pid"], e["lamport"],
                                               str(e["vector"]), e["kind"], e["extra"]))

    exp_l = {"A": 1, "B": 2, "C": 3, "D": 5, "E": 6, "E'": 2, "F": 3, "G": 4, "H": 1, "I": 2, "J": 7}
    exp_v = {"A": (1, 0, 0), "B": (2, 0, 0), "C": (3, 0, 0), "D": (4, 3, 1), "E": (5, 3, 1),
             "E'": (0, 1, 1), "F": (2, 2, 1), "G": (2, 3, 1), "H": (0, 0, 1),
             "I": (0, 0, 2), "J": (5, 3, 3)}
    for nm in order:
        assert ev[nm]["lamport"] == exp_l[nm], (nm, ev[nm]["lamport"])
        assert ev[nm]["vector"] == exp_v[nm], (nm, ev[nm]["vector"])
    print("\n[OK] 11 个事件的 Lamport 值与向量值与讲义逐一对齐")

    causal = [("A", "B"), ("B", "F"), ("A", "F"), ("H", "G"), ("F", "J"), ("H", "J"),
              ("C", "J"), ("H", "E'"), ("E'", "F"), ("F", "G"), ("G", "D"), ("D", "E"),
              ("E", "J"), ("A", "C"), ("C", "D"), ("C", "E"), ("H", "I"), ("I", "J"), ("F", "D")]
    conc = [("C", "F"), ("H", "C"), ("A", "H"), ("A", "E'"), ("B", "E'"), ("B", "H"),
            ("C", "G"), ("C", "I"), ("D", "I"), ("E", "I"), ("F", "I"), ("G", "I")]
    for a, b in causal:
        assert happens_before(ev[a]["vector"], ev[b]["vector"]), ("应因果", a, b)
    for a, b in conc:
        assert concurrent(ev[a]["vector"], ev[b]["vector"]), ("应并发", a, b)
    print("[OK] 讲义的因果对 (A->B, B->F, A->F, H->G, F->J, H->J, C->J) 全部成立")
    print("[OK] 讲义的并发对 (C||F, H||C) 及另外 %d 对并发对判定正确" % (len(conc) - 2))

    viol = [(a, b) for a, b in causal if not ev[a]["lamport"] < ev[b]["lamport"]]
    assert not viol, viol
    print("\n[定理1] %d 个因果对全部满足 Lamport(a) < Lamport(b): 0 反例" % len(causal))
    fake, seen = [], set()
    for a in order:
        for b in order:
            if ev[a]["lamport"] < ev[b]["lamport"] and concurrent(ev[a]["vector"], ev[b]["vector"]):
                key = tuple(sorted((a, b)))
                if key not in seen:
                    seen.add(key)
                    fake.append((a, b))
    print("[定理2] Lamport(a) < Lamport(b) 却并发的反例 (共 %d 对), 前 5 个:" % len(fake))
    for a, b in fake[:5]:
        print("        Lamport(%s)=%d < Lamport(%s)=%d, 但 %s || %s"
              % (a, ev[a]["lamport"], b, ev[b]["lamport"], a, b))
    tie = [(a, b) for i, a in enumerate(order) for b in order[i + 1:]
           if ev[a]["lamport"] == ev[b]["lamport"]]
    print("        时间戳相等的事件对 (讲义: C 与 F :: 3 = 3):", tie)

    total = sorted(order, key=lambda nm: (ev[nm]["lamport"], ev[nm]["pid"]))
    print("\n[(Lamport, pid) 全序] " + " < ".join(total))
    pos = {nm: i for i, nm in enumerate(total)}
    assert all(pos[a] < pos[b] for a, b in causal)
    print("[OK] 该全序是偏序 -> 的线性扩展: %d 个因果对的先后全部被保持" % len(causal))

    print("\n向量时钟的完整两两关系矩阵 (行 vs 列): -> 行先于列,  <- 行后于列,  || 并发")
    print("      " + "".join("%-5s" % nm for nm in order))
    for a in order:
        print("%-6s%s" % (a, "".join("%-5s" % relation(ev[a]["vector"], ev[b]["vector"])
                                     for b in order)))
    nc = sum(1 for i, a in enumerate(order) for b in order[i + 1:]
             if concurrent(ev[a]["vector"], ev[b]["vector"]))
    print("\n统计: %d 个事件, %d 个事件对; 因果相关 %d 对, 并发 %d 对"
          % (len(order), len(order) * (len(order) - 1) // 2,
             len(order) * (len(order) - 1) // 2 - nc, nc))


if __name__ == "__main__":
    main()

运行输出（节选，完全可复现）：

事件    进程    Lamport   向量时间戳        类型
A      P1    1         (1, 0, 0)    local
B      P1    2         (2, 0, 0)    send ->P2
C      P1    3         (3, 0, 0)    local
D      P1    5         (4, 3, 1)    recv <-P2(G)
E      P1    6         (5, 3, 1)    send ->P3
E'     P2    2         (0, 1, 1)    recv <-P3(H)
F      P2    3         (2, 2, 1)    recv <-P1(B)
G      P2    4         (2, 3, 1)    send ->P1
H      P3    1         (0, 0, 1)    send ->P2
I      P3    2         (0, 0, 2)    local
J      P3    7         (5, 3, 3)    recv <-P1(E)

[OK] 11 个事件的 Lamport 值与向量值与讲义逐一对齐
[OK] 讲义的因果对 (A->B, B->F, A->F, H->G, F->J, H->J, C->J) 全部成立
[OK] 讲义的并发对 (C||F, H||C) 及另外 10 对并发对判定正确
[定理1] 19 个因果对全部满足 Lamport(a) < Lamport(b): 0 反例
[定理2] Lamport(a) < Lamport(b) 却并发的反例 (共 11 对), 前 5 个:
        Lamport(A)=1 < Lamport(E')=2, 但 A || E'
        Lamport(A)=1 < Lamport(I)=2, 但 A || I
        Lamport(C)=3 < Lamport(G)=4, 但 C || G
        Lamport(E')=2 < Lamport(C)=3, 但 E' || C
        Lamport(H)=1 < Lamport(B)=2, 但 H || B
        时间戳相等的事件对 (讲义: C 与 F :: 3 = 3): [('A','H'), ('B',"E'"), ('B','I'), ('C','F'), ("E'",'I')]

[(Lamport, pid) 全序] A < H < B < E' < I < C < F < G < D < E < J
[OK] 该全序是偏序 -> 的线性扩展: 19 个因果对的先后全部被保持

统计: 11 个事件, 55 个事件对; 因果相关 39 对, 并发 16 对

【代码做什么？】

LamportClock / VectorClock 把 11.3.3 与 11.3.4 的伪代码逐条实现为三个方法：local_event() / send_event() / receive_event(msg_ts \| msg_v)；
Process 继承 threading.Thread，每个进程一个真实线程，它们的”程序”是一串脚本化的动作（local / send / recv）；
main() 为进程两两建立 queue.Queue 作为信箱；send 时把 (消息号, 发送事件名, Lamport 戳, 向量戳, 源进程) 投入目标信箱，recv 时阻塞在 self.box.get() 上——这就是真实的（进程内）消息传递语义；
每个线程在动作之间 time.sleep(random.uniform(0, 0.002))，让操作系统自由调度，制造真实的时间交错；
全部事件结束后收集 trace，逐条断言讲义给出的 Lamport 数值、向量数值、因果对与并发对（与本笔记 11.2.9–11.2.11 的表格一一对应）；
最后打印完整的两两关系矩阵（$11 \times 11$）与统计（39 对因果、16 对并发）。

【分布式机制透视】

消息通道：queue.Queue 扮演网络。它是可靠、FIFO、阻塞的（比真实网络好得多），但这一点不影响结论——因为 Lamport/向量时钟的正确性从不依赖通道的可靠性或 FIFO 性，它们只依赖”发送先于接收”这一事实；
并发：三个线程是真正并发的（操作系统调度），但程序的最终结果确定：因为脚本中每个 recv 都阻塞等待对应的 send，事件之间的因果依赖强制了唯一的执行顺序（$H$ 必须先于 $E^{\prime}$，$B$ 必须先于 $F$，$G$ 必须先于 $D$，$E$ 必须先于 $J$，而这个依赖图是无环的，所以不会死锁）；
每个进程的状态：lc（一个整数）与 vc（一个长度为 3 的列表）就是该进程的全部”时间状态”；没有任何共享变量（除锁保护的 trace，那只是日志），这正是分布式系统”无共享内存”的真实写照；
消息携带时间戳：inboxes[target].put((msg_id, name, lts, vts, self.pid)) 这一行同时对应伪代码里的 send <m, L> 与 send <m, copy(V)>——时间戳随消息一起在网络中旅行，这是逻辑时钟能跨进程传递因果信息的唯一途径。

【与理论的对应】

代码	理论	位置
`LamportClock.receive_event`: `max(self.value, msg_ts) + 1`	算法 11.3.3 规则 4；”Why Max?” 的机械化	11.2.10 / 11.3.3
`VectorClock.local_event`: 只增 `v[me]`	算法 11.3.4 规则 1	11.2.11 / 11.3.4
`VectorClock.receive_event`: 先增自己、再对其余维 `max`	算法 11.3.4 规则 3；且验证了”先增/先合并在因果判定上等价”	11.2.11
`happens_before` / `concurrent`	定理 3（精确性）与定理 4（并发判定）	11.3.4
`assert ev[nm]["lamport"] == exp_l[nm]`	讲义 11.2.10 的 11 步演化表	11.2.10
`assert ev[nm]["vector"] == exp_v[nm]`	讲义 11.2.11 的 11 步演化表	11.2.11
`[定理2] ... 却并发的反例`	定理 2（逆命题不成立）	11.3.3
`[(Lamport, pid) 全序]` + `assert pos[a] < pos[b]`	定理 7（全序 + 线性扩展）	11.3.6
关系矩阵	讲义的两条比较规则（因果 vs 并发）	11.2.11

11.4.2 程序 2：物理时钟 vs Lamport 时钟 vs 向量时钟的对比实验

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""CS425 Ch.11 程序 2: 三种时钟的对比实验.

用同一个随机执行, 分别给事件打上
  (1) 物理时钟时间戳 (带 skew 与 drift)   (2) Lamport 时间戳   (3) 向量时间戳
然后检查: 谁违反因果性? 谁能识别并发? 谁会丢写?
"""
import heapq
import random

random.seed(425)


class PhysicalClock:
    """物理时钟: C(t) = t*(1+rate) + offset, t 为真实时间(秒), rate 为漂移率。"""

    def __init__(self, rate, offset):
        self.rate = rate
        self.offset = offset

    def read(self, real_t):
        return real_t * (1.0 + self.rate) + self.offset


def simulate(nproc, steps_per_proc, p_send, skew_amp, drift_amp):
    """离散事件仿真: 返回事件列表 (含三种时间戳) 与真实时间。"""
    pc = [PhysicalClock(random.uniform(-drift_amp, drift_amp),
                        random.uniform(-skew_amp, skew_amp)) for _ in range(nproc)]
    lam = [0] * nproc
    vec = [[0] * nproc for _ in range(nproc)]
    steps = [0] * nproc
    seq = 0
    events = []
    heap = [(i * 0.001, 0, i, "step", None) for i in range(nproc)]

    while heap:
        t, _, i, kind, payload = heapq.heappop(heap)
        if kind == "step":
            if steps[i] >= steps_per_proc:
                continue
            steps[i] += 1
            seq += 1
            lam[i] += 1
            vec[i][i] += 1
            if random.random() < p_send and steps[i] < steps_per_proc - 1:
                j = random.choice([k for k in range(nproc) if k != i])
                events.append(dict(id=len(events), proc=i, kind="send", real=t,
                                   phys=pc[i].read(t), lamport=lam[i],
                                   vector=tuple(vec[i]), peer=j, msg=seq))
                delay = random.uniform(0.02, 0.25)
                heapq.heappush(heap, (t + delay, seq, j, "recv", (seq, lam[i], tuple(vec[i]))))
            else:
                events.append(dict(id=len(events), proc=i, kind="local", real=t,
                                   phys=pc[i].read(t), lamport=lam[i],
                                   vector=tuple(vec[i]), peer=None, msg=None))
            heapq.heappush(heap, (t + random.uniform(0.01, 0.06), seq, i, "step", None))
        else:
            msg, lam_m, vec_m = payload
            seq += 1
            lam[i] = max(lam[i], lam_m) + 1
            vec[i][i] += 1
            for k in range(nproc):
                if k != i:
                    vec[i][k] = max(vec_m[k], vec[i][k])
            events.append(dict(id=len(events), proc=i, kind="recv", real=t,
                               phys=pc[i].read(t), lamport=lam[i],
                               vector=tuple(vec[i]), peer=None, msg=msg))
    return events


def hb(v1, v2):
    return v1 != v2 and all(a <= b for a, b in zip(v1, v2))


def conc(v1, v2):
    return not hb(v1, v2) and not hb(v2, v1)


def analyse(tag, skew_amp, drift_amp):
    ev = simulate(nproc=4, steps_per_proc=6, p_send=0.4,
                  skew_amp=skew_amp, drift_amp=drift_amp)
    causal, conc_pairs = [], []
    for i, a in enumerate(ev):
        for b in ev[i + 1:]:
            if hb(a["vector"], b["vector"]):
                causal.append((a, b))
            elif conc(a["vector"], b["vector"]):
                conc_pairs.append((a, b))

    print("=" * 78)
    print("%s  (skew 幅度=%.1e s, drift 幅度=%.1e)" % (tag, skew_amp, drift_amp))
    print("=" * 78)
    print("事件数 %d, 消息数 %d, 因果相关事件对 %d, 并发事件对 %d"
          % (len(ev), sum(1 for e in ev if e["kind"] == "send"), len(causal), len(conc_pairs)))

    # ---- (1) 物理时钟 ----
    bad = [(a, b) for a, b in causal if not a["phys"] < b["phys"]]
    by_msg = {}
    for e in ev:
        if e["kind"] in ("send", "recv") and e["msg"] is not None:
            by_msg.setdefault(e["msg"], {})[e["kind"]] = e
    msg_bad = [(d["send"], d["recv"]) for _, d in sorted(by_msg.items())
               if "send" in d and "recv" in d and not d["send"]["phys"] < d["recv"]["phys"]]
    print("\n[物理时钟] 违反因果性的事件对: %d / %d   (%.1f%%)"
          % (len(bad), len(causal), 100.0 * len(bad) / max(1, len(causal))))
    for a, b in msg_bad[:4]:
        print("   * 消息 m%-3d: P%d 发送物理戳 %.4f  >  P%d 接收物理戳 %.4f  <-- 接收早于发送!"
              % (a["msg"], a["proc"], a["phys"], b["proc"], b["phys"]))
    print("   => 若用 LWW(最大物理时间戳获胜) 解决冲突, 会静默丢弃 %d 个因果上更晚的写" % len(bad))

    # ---- (2) Lamport ----
    lam_bad = [(a, b) for a, b in causal if not a["lamport"] < b["lamport"]]
    assert not lam_bad
    print("\n[Lamport  ] 违反因果性的事件对: %d / %d   (定理 1: 必为 0)"
          % (len(lam_bad), len(causal)))
    fake = [(a, b) for a, b in conc_pairs if a["lamport"] != b["lamport"]]
    tie = [(a, b) for a, b in conc_pairs if a["lamport"] == b["lamport"]]
    print("   并发对中被 Lamport 时间戳强行排了先后: %d / %d (%.1f%%) —— 无法识别并发"
          % (len(fake), len(conc_pairs), 100.0 * len(fake) / max(1, len(conc_pairs))))
    print("   并发对中时间戳恰好相等: %d 对 (相等不代表因果, 也不代表同一事件)" % len(tie))

    # ---- (3) 向量时钟 ----
    vec_bad = [(a, b) for a, b in causal if not hb(a["vector"], b["vector"])]
    vec_false = [(a, b) for a, b in conc_pairs if hb(a["vector"], b["vector"])]
    print("\n[向量时钟 ] 违反因果性: %d ; 把并发误判为因果: %d  (定理 3: 两者必为 0)"
          % (len(vec_bad), len(vec_false)))
    assert not vec_bad and not vec_false
    return len(ev), len(by_msg), len(causal), len(conc_pairs), len(bad), len(fake)


def main():
    print("CS425 Ch.11 实验: 物理时钟 vs Lamport 时钟 vs 向量时钟")
    print("说明: 为了让违规在有限仿真中显现, 场景 A 用了被放大的 skew/drift;")
    print("      场景 B 用频繁同步后的小 skew/drift (但漂移仍最终会累积)。\n")
    A = analyse("场景 A: 时钟几乎未同步", skew_amp=0.60, drift_amp=0.05)
    print()
    B = analyse("场景 B: 刚刚同步过 (skew 很小)", skew_amp=0.0005, drift_amp=1e-5)
    print("\n" + "=" * 78 + "\n对比汇总\n" + "=" * 78)
    rows = [("物理(A)", A[4], "不能", A[4], "不可靠"),
            ("物理(B)", B[4], "不能", B[4], "暂时可用, 但会漂"),
            ("Lamport", 0, "不能", 0, "因果安全, 无法判并发"),
            ("向量", 0, "可以", 0, "既安全又精确")]
    print("时钟       违反因果性   识别并发   丢失因果更晚的写   结论")
    for name, v1, v2, v3, v4 in rows:
        print("%-10s %-12s %-10s %-18s %s" % (name, v1, v2, v3, v4))
    print("\n场景 A 的并发对被 Lamport 强行排序: %d 对; 场景 B: %d 对" % (A[5], B[5]))


if __name__ == "__main__":
    main()

运行输出（节选）：

场景 A: 时钟几乎未同步  (skew 幅度=6.0e-01 s, drift 幅度=5.0e-02)
事件数 32, 消息数 8, 因果相关事件对 159, 并发事件对 337

[物理时钟] 违反因果性的事件对: 8 / 159   (5.0%)
   * 消息 m12 : P1 发送物理戳 0.3818  >  P2 接收物理戳 0.2740  <-- 接收早于发送!
   * 消息 m16 : P3 发送物理戳 0.4179  >  P0 接收物理戳 -0.0666  <-- 接收早于发送!
   => 若用 LWW(最大物理时间戳获胜) 解决冲突, 会静默丢弃 8 个因果上更晚的写

[Lamport  ] 违反因果性的事件对: 0 / 159   (定理 1: 必为 0)
   并发对中被 Lamport 时间戳强行排了先后: 292 / 337 (86.6%) —— 无法识别并发

[向量时钟 ] 违反因果性: 0 ; 把并发误判为因果: 0  (定理 3: 两者必为 0)
...
时钟       违反因果性   识别并发   丢失因果更晚的写   结论
物理(A)    8            不能       8                  不可靠
物理(B)    0            不能       0                  暂时可用, 但会漂
Lamport    0            不能       0                  因果安全, 无法判并发
向量       0            可以       0                  既安全又精确

【代码做什么？】

PhysicalClock 用 $C(t) = t\,(1+rate) + offset$ 建模一个带漂移率与初始偏差的物理钟；
simulate() 是一个离散事件仿真器：用最小堆按真实时间推进，每个进程按自己的节奏产生事件；发出消息时按随机延迟把接收事件插进堆——这真实地模拟了”消息在飞行中”；
同一个执行里，每个事件同时被盖上三种时间戳（物理 / Lamport / 向量）；
analyse() 用向量时钟的结果作为”因果真相“的裁判，然后分别检查三种时钟：物理时钟有多少因果对被颠倒、Lamport 有多少并发对被强行排序、向量时钟是否两者都正确；
最后在两个场景（几乎未同步 / 刚刚同步）之间对比，输出汇总表。

【分布式机制透视】

离散事件仿真：heapq 维护全局事件队列，堆里的时间就是真实时间；这正是仿真分布式系统最标准的做法（比真起多机更可控、可复现）；
“因果真相”的获取：程序用向量时钟的判定当作 ground truth——这在工程上也是常见做法（Riak/Dynamo 就是靠向量时钟知道自己面对的是并发写）；
物理时钟的建模：read(t) = t*(1+rate) + offset 精确对应 11.2.4 的定义——offset 就是 skew，rate 就是 drift，两者是独立参数，正好演示了”skew 是值差、drift 是速率差”；
场景 A vs B 的对照：场景 B 里物理时钟的违反次数是 0——但这并不意味着物理时钟安全，它只说明”刚刚同步过、且仿真时间跨度还太短，漂移还没积累起来”；把仿真时间拉长，场景 B 必然退化成场景 A。这正是”物理时钟给出接近真实但永不可靠的时间”的定量演示。

【与理论的对应】

物理时钟违反因果性（接收时间戳 < 发送时间戳）⇒ 直接验证了 11.2.2 云订票例子中”因果被颠倒”的机制；也解释了 Ch.9 中 Cassandra LWW 会静默丢弃因果上更晚的写；
assert not lam_bad ⇒ 定理 1（Lamport 时钟永远不违反因果性）；
fake 与 tie 的统计 ⇒ 定理 2（Lamport 无法区分并发：86.6% 的并发对被强行排序、另有大量并发对时间戳相等）；
assert not vec_bad and not vec_false ⇒ 定理 3 与定理 4（向量时钟既判因果又判并发，两个方向都对）。

11.4.3 程序 3：Cristian 与 NTP 的误差模拟

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""CS425 Ch.11 程序 3: Cristian 与 NTP 的误差模拟.

验证两条误差界:
  Cristian: |误差| <= (RTT - min1 - min2)/2          (定理 5)
  NTP     : |o - o_真实校正量| < (L1 + L2)/2 = RTT/2  (定理 6)
并展示非对称延迟如何造成系统性偏差。
"""
import random

random.seed(425)
TRIALS = 20000


def delays(mode, min1, min2, scale, proc=0.0):
    """返回一次消息交换的 (L1, L2, proc)。"""
    if mode == "constant":                      # 完全固定的对称延迟
        l1 = l2 = min1
    elif mode == "uniform":                     # 对称的均匀抖动
        l1 = min1 + random.uniform(0, scale)
        l2 = min2 + random.uniform(0, scale)
    elif mode == "exponential":                 # 对称的指数抖动 (重尾)
        l1 = min1 + random.expovariate(1.0 / scale)
        l2 = min2 + random.expovariate(1.0 / scale)
    elif mode == "asymmetric":                  # 非对称: 上行快、下行慢 (WAN 常见)
        l1 = min1 + random.expovariate(1.0 / scale)
        l2 = min2 + random.expovariate(1.0 / (3.0 * scale))
    else:
        raise ValueError(mode)
    return l1, l2, proc


def cristian(mode, min1, min2, scale, known_mins=True, proc=0.0):
    """完整走一遍 Cristian 算法, 返回 (误差, 误差上界)。"""
    l1, l2, proc = delays(mode, min1, min2, scale, proc)
    send_real = 100.0                            # 真实发送时刻 (任意基准)
    recv_real = send_real + l1 + proc + l2       # 响应真正到达 P 的真实时刻
    t = send_real + l1                           # 服务器读表得到的值 (服务器 = 真实时间)
    rtt = l1 + proc + l2                         # 用本地时钟两端做差, 与时钟偏差无关
    if known_mins:                               # 已知 min1, min2: 取区间中点
        estimate = t + (rtt + min2 - min1) / 2.0
        bound = (rtt - min1 - min2) / 2.0
    else:                                        # 未知 min1, min2: 退化为 t + RTT/2
        estimate = t + rtt / 2.0
        bound = rtt / 2.0
    return estimate - recv_real, bound


def ntp(mode, min1, min2, scale, proc=0.0):
    """NTP 四方时间戳交换, 返回 (误差, 真实所需校正量, RTT)。"""
    l1, l2, proc = delays(mode, min1, min2, scale, proc)
    o_real = random.uniform(-1.0, 1.0)           # child 时钟相对 parent 的真实偏差
    r1 = 100.0                                   # 真实发送 M1 的时刻
    t_s1 = r1 + o_real                           # child 读表
    t_r1 = r1 + l1                               # parent 读表 (= 真实时间)
    t_s2 = r1 + l1 + proc                        # parent 发 M2
    t_r2 = r1 + l1 + proc + l2 + o_real          # child 收到 M2 时读表
    o = (t_r1 - t_r2 + t_s2 - t_s1) / 2.0        # 讲义/NTP 的偏移公式
    true_correction = -o_real                    # child 真正需要加上的量
    rtt = (t_r2 - t_s1) - (t_s2 - t_r1)          # 纯网络往返 + 处理时间
    return o - true_correction, true_correction, rtt


def report_cristian(mode, min1, min2, scale, known=True):
    errs = [cristian(mode, min1, min2, scale, known) for _ in range(TRIALS)]
    worst = max(abs(e) for e, _ in errs)
    worst_bound = max(b for _, b in errs)
    tag = "已知 min1,min2" if known else "未知 min1,min2"
    print("  Cristian[%-12s %-14s min1=%.3f min2=%.3f]  最大|误差|=%.5f  "
          "最大上界=%.5f  违界次数=%d"
          % (mode, tag, min1, min2, worst, worst_bound,
             sum(1 for e, b in errs if abs(e) > b)))
    assert max(abs(e) - b for e, b in errs) <= 1e-12, "误差界被突破!"


def report_ntp(mode, min1, min2, scale, hist=False):
    res = [ntp(mode, min1, min2, scale) for _ in range(TRIALS)]
    errs = [e for e, _, _ in res]
    viol = sum(1 for e, _, rtt in res if abs(e) >= rtt / 2.0)
    print("  NTP[%-12s min1=%.3f min2=%.3f]  平均偏差=%+.5f  最大|误差|=%.5f  "
          "越界(|e|>=RTT/2)次数=%d"
          % (mode, min1, min2, sum(errs) / len(errs), max(abs(e) for e in errs), viol))
    assert viol == 0
    if hist:
        print("        误差分布 (单位: 毫秒; 非对称延迟造成的系统性偏差):")
        lo, hi, bins = min(errs), max(errs), 21
        counts = [0] * bins
        for e in errs:
            counts[min(bins - 1, int((e - lo) / (hi - lo + 1e-12) * bins))] += 1
        for k, c in enumerate(counts):
            x = (lo + (k + 0.5) * (hi - lo) / bins) * 1000.0
            print("        %+8.1f |%s %d" % (x, "#" * int(60.0 * c / max(counts)), c))


def main():
    print("=" * 78)
    print("实验 1: Cristian 算法 —— 误差是否真的被 (RTT-min1-min2)/2 界定?")
    print("=" * 78)
    for mode, s in [("constant", 0.05), ("uniform", 0.10), ("exponential", 0.08)]:
        report_cristian(mode, 0.01, 0.01, s, known=True)
    print("  非对称延迟 (上行 min1=10ms, 下行 min2=50ms): 区间中点估计仍正确, 只是区间更宽")
    report_cristian("asymmetric", 0.01, 0.05, 0.02, known=True)
    print("  若 min1, min2 未知, 退化为 t + RTT/2, 界变成 RTT/2:")
    report_cristian("uniform", 0.01, 0.01, 0.10, known=False)
    report_cristian("asymmetric", 0.01, 0.05, 0.02, known=False)

    print("\n" + "=" * 78)
    print("实验 2: NTP —— 偏差公式 o = ((t_r1 - t_r2) + (t_s2 - t_s1))/2 的误差")
    print("=" * 78)
    print("  对称延迟: 误差无系统偏差, |误差| 远小于 RTT/2")
    report_ntp("constant", 0.01, 0.01, 0.0)
    report_ntp("uniform", 0.01, 0.01, 0.10)
    print("  非对称延迟 (上行 10ms, 下行 50ms): 出现约 (L1-L2)/2 的固定系统偏差")
    report_ntp("asymmetric", 0.01, 0.05, 0.02, hist=True)
    print("\n  结论: 误差界 < RTT/2 永远成立 (定理 6), 但 RTT 本身无法告诉我们")
    print("        偏差落在区间里的哪一边 —— 非对称延迟是 NTP 精度的真正天花板。")


if __name__ == "__main__":
    main()

运行输出（节选）：

  Cristian[constant     已知 min1,min2   min1=0.010 min2=0.010]  最大|误差|=0.00000  最大上界=0.00000  违界次数=0
  Cristian[uniform      已知 min1,min2   min1=0.010 min2=0.010]  最大|误差|=0.04969  最大上界=0.09944  违界次数=0
  Cristian[exponential  已知 min1,min2   min1=0.010 min2=0.010]  最大|误差|=0.40706  最大上界=0.51563  违界次数=0
  Cristian[asymmetric   已知 min1,min2   min1=0.010 min2=0.050]  最大|误差|=0.31829  最大上界=0.34286  违界次数=0
  Cristian[uniform      未知 min1,min2   min1=0.010 min2=0.010]  最大|误差|=0.04948  最大上界=0.10959  违界次数=0

  NTP[uniform      min1=0.010 min2=0.010]  平均偏差=-0.00004  最大|误差|=0.04931  越界(|e|>=RTT/2)次数=0
  NTP[asymmetric   min1=0.010 min2=0.050]  平均偏差=-0.03972  最大|误差|=0.39128  越界(|e|>=RTT/2)次数=0
        误差分布 (单位: 毫秒; 非对称延迟造成的系统性偏差):
         -136.3 |# 213
         -114.2 |### 484
          -92.0 |####### 1119
          -69.8 |############## 2067
          -47.7 |############################### 4553
          -25.5 |############################################################ 8547
           -3.3 |################# 2496
          +18.8 |## 295

【代码做什么？】

delays() 提供四种延迟模型：固定对称、均匀抖动、指数重尾、非对称（上行与下行服从不同的分布）；
cristian() 完整实现 11.3.1 的算法：算出 RTT、取区间中点、给出误差上界，并返回真实误差（仿真知道 $L_1, L_2$，因此可以算出真值——真实系统做不到这一点）；
ntp() 完整实现 11.3.2 的四方时间戳交换与偏移公式，并把它与”真实需要校正的量”比较；
每个配置跑 20000 次，检查是否曾经突破误差界（违界次数 必须为 0，否则 assert 直接报错）；
最后为非对称场景画出误差直方图。

【分布式机制透视】

真实时间基准：程序用”真实时间”作为仿真世界的坐标，实际系统中这个量不可知——所有算法都只能看到各自时钟的读数，这正是仿真要还原的核心困难；
RTT 的测量：rtt = l1 + proc + l2 由两个本地读数做差得到（代码里体现为”两端都用同一个时钟”），因此与偏差 $o_{real}$ 无关——这一点是 Cristian 与 NTP 能工作的关键；
$min_1, min_2$ 的角色：代码把 known_mins=False 与 True 两种情形都跑了一遍，展示”未知最小值”只是让界从 $(RTT-min_1-min_2)/2$ 退化为 $RTT/2$；
非对称延迟：asymmetric 模式下 $E[L_1] = 30$ ms、$E[L_2] = 110$ ms，算出的偏移会产生约 $-(110-30)/2 = -40$ ms 的系统性偏差（代码里”平均偏差 = -0.03972 s”正是这个值）——这是 NTP 精度的真正天花板：多测几次取平均不能消除它，因为它是偏差不是随机误差。

【与理论的对应】

assert max(abs(e) - b for e, b in errs) <= 1e-12 ⇒ 定理 5（Cristian 的误差界从未被突破，20000 次实验零违界）；
assert viol == 0 ⇒ 定理 6（NTP 的 $\lvert o_{real}-o\rvert < \text{RTT}/2$ 从未被突破）；
对称 vs 非对称的对比 ⇒ 11.2.8 中”$\lvert o_{real}-o\rvert = \lvert L_2-L_1\rvert/2$”这一等式：延迟越不对称，系统性偏差越大；
constant 模式下误差恒为 0 ⇒ 式子的特例：当 $L_1 = L_2$ 时偏差被完全消除——这也是为什么同机房、路径对称的场景下 NTP 精度最好。

11.5 性能与可扩展性分析

11.5.1 逻辑时间戳的开销对比

维度	Lamport 时间戳	向量时间戳
每个进程的空间	$O(1)$（一个整数）	$O(N)$（$N$ 个整数）
每条消息的开销	$O(1)$（一个整数，通常 4–8 字节）	$O(N)$（$N$ 个整数，可能几百字节到几 KB）
每个事件的时间	$O(1)$	$O(N)$（接收时要逐维取 max）
遵守因果性	是（定理 1），且是单向的：$a \rightarrow b \Rightarrow L(a) < L(b)$	是（定理 3），且是双向等价的：$a \rightarrow b \iff V(a) < V(b)$
能否识别并发	不能（定理 2：大量并发对被强行排序或得到相同时间戳）	能（定理 4：不可比较 ⟺ 并发）
与真实时间的关系	无（只是计数器）	无（只是计数器向量）
进程数变化	无影响（$N$ 可以动态变化，甚至不需要知道 $N$）	必须预先知道且固定 $N$（向量长度固定）
典型用途	全序多播、分布式互斥（Ricart-Agrawala）、Lamport bakery、日志的粗排序	冲突检测（并发写）、因果一致性、调试与溯源、快照的一致性判定
真实系统	ISIS 全序多播；Ricart-Agrawala 互斥；CockroachDB 的 HLC 逻辑分量	Riak（DVV）、Dynamo（version vector + siblings）、部分版本控制与同步工具
判定的强度	偏序的单向近似（会”多报”因果）	因果关系的精确刻画

一句话总结：向量时钟用 $O(N)$ 的空间，买到了”识别并发”这一 Lamport 时钟买不到的能力（定理 2 的维数下界说明这份空间是省不掉的）。

11.5.2 向量时钟的”大小爆炸”与工程解法

向量时钟在真实系统里的核心问题是：消息头会随进程数线性膨胀。

$N$ 小时的甜蜜区：$N \le 10$ 时，一个向量 40 字节，完全可接受；
$N$ 中等（几十到几百）：如果参与者是”副本”（每个分片 3–5 个副本），仍然可以接受——关键在于把 $N$ 定义为”副本数”而不是”客户端数/节点数”；
$N$ 巨大（上千个节点、上亿客户端）：每条消息都要带一个上千维的向量，完全不可接受（消息头几百字节到几 KB，网络与存储成本爆炸）。

工程上的六类解法：

解法	思路	代表系统 / 场景
版本向量（Version Vector）+ 每对象一份	向量只在每个数据对象上维护（记录该对象被哪些副本改过、改到第几版），而不是给系统里每个事件打戳；$N$ = 副本数（通常 3）而非节点总数	Dynamo、Riak
稀疏向量（Sparse Vector）	只记录非零（有更新）的分量，用 `(进程id, 计数)` 的列表表示；大多数对象只被少数几个副本写过，因此实际长度远小于 $N$	大量生产实现
Dotted Version Vectors (DVV)	把”向量”与”一个点（dot = 具体的 (进程, 计数) 对）”分开：向量描述因果上下文，dot 描述本次写本身。解决了经典版本向量”同一客户端连续写两次数值看起来像并发”的假冲突问题	Riak 2.0
哈希/有界向量（Hash-based / Bounded）	对向量做哈希并只保留摘要，或对向量维数设上界（超过则丢弃最旧的分量）——牺牲精确性换空间，需要接受误判风险	学术方案，少见于生产
Interval Tree Clocks (ITC)	用一棵区间树表示”我负责的进程 ID 区间”，支持进程的动态增加与删除，空间与”当前活跃的进程数”相关而不是与历史最大 $N$ 相关	Torres-Rojas & Ahamad (1999)；适合 P2P/动态成员系统
混合逻辑时钟（HLC）	放弃”判并发”，改用 $(l, c)$：$l$ 尽量贴近物理时间、$c$ 是逻辑计数器；保留因果性、把开销压回 $O(1)$，同时得到”接近真实时间”的时间戳	CockroachDB、MongoDB 的部分场景

HLC 的更新规则（值得记住，它是”物理 + 逻辑”折中的标准答案）：设本地为 $(l, c)$，收到消息携带 $(l_m, c_m)$： $l' = \max(l, l_m), \qquad c' = \begin{cases} \max(c, c_m) + 1, & l' = l = l_m \quad(\text{物理时间相同, 只能靠计数器打破平局})\\ c + 1, & l' = l \ne l_m\\ c_m + 1, & l' = l_m \ne l\\ 0, & \text{否则（物理时间前进, 计数器归零）} \end{cases}$ HLC 的性质：$e \rightarrow f \Rightarrow \text{HLC}(e) < \text{HLC}(f)$（因果性被严格保持），同时 $l$ 与物理时间的偏差有界（只要时钟偏差有界）。它用物理时钟来”压缩”逻辑时间戳的大小，用逻辑分量来兜住物理时钟的错误——正好呼应 11.2.12 的哲学：两者不是竞争关系，而是互补关系。

11.5.3 真实系统中的用法：Riak / Dynamo vs Cassandra

系统	用什么判顺序	遇到并发写怎么办	代价
Cassandra（Ch.9）	物理时间戳 + last-write-wins	时间戳大的赢，小的被静默丢弃（即使它因果上更晚）	简单、开销极小；但依赖时钟同步，时钟偏差会丢数据
Dynamo / Riak	向量时钟（版本向量）	检测到并发版本（不可比较）时，保留多个版本作为 siblings（兄弟）返回给应用，由应用决定如何合并	需要应用层处理冲突逻辑；向量会随历史膨胀（用 DVV 缓解）

这正是 11.2.2 云订票例子的现实版：Cassandra 选择了”简单但可能错”，Riak/Dynamo 选择了”复杂但因果正确”。讲义提到”vector timestamps used in key-value stores like Riak”就是在说后一条路线。值得注意的是，向量时钟在客户端直连的键值存储里还有一个隐藏问题：如果客户端也算作”进程”，$N$ 会随着客户端数量爆炸——这就是为什么 Riak 1.x 的经典版本向量会被 DVV 取代（DVV 把”客户端的一次写”建模成一个 dot，而不是给每个客户端分配一个永久维度）。

11.5.4 Lamport 时钟在真实系统里的用法

Lamport 时钟的价值不在于它有多强，而在于它几乎没有成本：

全序多播（Ch.13，Lecture 15）：给每条消息打 Lamport 时间戳，接收方按 $(\text{ts}, pid)$ 排序后交付，从而让所有接收者看到相同的顺序。这是复制状态机的顺序基础设施；
分布式互斥（Ch.14，Lecture 16）：Ricart-Agrawala 用 $(\text{ts}, pid)$ 做请求的优先级——时间戳更小的请求优先获得进入临界区的权利，配合”每个请求者必须收到所有其他进程的回复”实现互斥，消息复杂度 $2(N-1)$；
数据库与日志的粗排序：不要求精确因果、只需要一个全局一致且稳定的顺序时，Lamport 时间戳足够；
CockroachDB / MongoDB 等：用 HLC 兼顾”接近物理时间”与”因果正确”。

11.5.5 物理时钟路线的工程精度对照

方案	典型精度	关键机制	主要瓶颈
裸晶振（不同步）	每天漂 0.1 秒量级	无	MDR $\approx 10^{-6}$
NTP over WAN	几毫秒 ~ 几十毫秒	RTT/2 界定 + 过滤 + slew	路径延迟非对称 + 抖动
NTP over LAN	亚毫秒（几十 μs ~ 几百 μs）	同上，RTT 小	用户态时间戳 + 交换机排队
PTP（IEEE 1588）	亚微秒（LAN）	网卡硬件打时间戳 + 主从层次	需要硬件支持与网络配置
GPS/原子钟 + TrueTime	不确定区间半宽 $\epsilon$ 通常 $< 7$ ms	每机房 GPS+原子钟，显式暴露不确定区间 + commit-wait	成本、部署复杂度
Cristian（单服务器）	$\text{RTT}/2$	区间中点	单点故障 + 易被攻击

共同的物理规律：精度越高，成本（硬件 + 同步频率 + 部署复杂度）越高，而且误差永远非零。这正是 11.2.8 那句”只要消息延迟非零，我们就永远无法消除误差”的工程印证。

11.5.6 容错能力对照

机制	能容忍什么故障	不能容忍什么
Cristian（单时间服务器）	客户端崩溃、消息丢失（重传）	服务器崩溃（降级为无同步）、服务器作恶/被攻陷
NTP 树	单个服务器失效（切换到备选）、网络抖动（过滤）	大范围欺骗攻击（无认证时）、根时源失效、路径长期不对称
Lamport 时钟	任意消息丢失、任意进程崩溃、任意时钟偏差	无（它不依赖任何外部条件）
向量时钟	同上	无（但消息丢失会让某些因果关系变得不可见，见 11.7 陷阱 6）
TrueTime	本地 GPS/原子钟失效（区间自动变宽）	区间宽度超过业务可接受范围时会阻塞提交（可用性下降）

设计教训：物理时间同步把”正确性”绑定在”基础设施的健康”上；逻辑时钟把”正确性”绑定在”算法本身”上。 这就是为什么本讲最后会强调：逻辑时钟不是物理时钟的”低配替代品”，而是在没有可信时间源时唯一能保证因果正确的方案。

11.6 关键要点

时间同步同时关乎正确性与公平性，但它永远无法做到零误差。 表慢会错过事件（正确性），表快会白等或占便宜（公平性）；而只要消息延迟非零，物理时钟的误差就不可能为零——NTP 能给你的最好保证是”误差被 RTT 界定”（$\lvert o_{real}-o\rvert < \text{RTT}/2$），而不是”误差为零”。
“多久同步一次”是一个可以算出来的工程常数：$M/(2\times\text{MDR})$。 两个相似时钟之间的相对漂移率是 $2\times$MDR，把 skew 当”距离”、漂移率当”速度”，$\text{time} = \text{distance}/\text{speed}$ 就给出同步周期。要求 1 毫秒精度、MDR $=10^{-6}$，就必须每 8 分钟同步一次。
外部同步蕴含内部同步（界从 $D$ 变成 $2D$），但内部同步不蕴含外部同步——整个系统可以一起漂走。 三角不等式给出前者；”所有钟一起快”这一反例给出后者。所以”NTP 对得很好”不等于”我和 UTC 对得很好”。
happens-before 是分布式系统里唯一客观的”先后”，因为它不依赖任何时钟。 它只承认能被因果链证明的顺序，因此是偏序而非全序；两个既无 $a \rightarrow b$ 也无 $b \rightarrow a$ 的事件就是并发，它们的真实先后在系统内不可观测。
Lamport 时间戳保证”因果一定有序”，但不保证”有序一定因果”；向量时间戳两个方向都保证。 前者 $O(1)$ 空间、无法识别并发；后者 $O(N)$ 空间、精确刻画因果与并发，且这个 $O(N)$ 是理论下界（Charron-Bost），不是实现偷懒。
$(\text{Lamport}, pid)$ 把偏序免费升级成全序。 这是全序多播（Ch.13）与 Ricart-Agrawala 互斥（Ch.14）的地基：不需要共识、不需要额外通信，只需要一个一致的 tie-break 规则。
时间是构造出来的，不是测量出来的。 需要”几点”时用物理时钟并显式承认误差；需要”谁先谁后”时用逻辑时钟并享受 100% 的正确性；两者兼具需求的系统用 HLC / TrueTime 把二者缝合起来。

11.7 常见陷阱与注意事项

把”时钟准”当成”顺序对”。 为什么错：即使把 skew 压到 1 微秒，两个相隔几百纳秒的事件仍可能被颠倒，而且误差方向是随机的——同一份日志今天读是一个结论、明天读可能是另一个，这种”随机正确的系统”毫无意义。正确做法：需要跨进程排序时用逻辑时间戳（或 HLC）；只有当问题真正需要”真实时刻”时才依赖物理时钟，并把不确定区间显式地传播出去（像 Spanner 那样）。
回拨时钟（把时钟值往回调）。 为什么错：回拨会让同一进程内先后发生的两个事件拿到逆序的时间戳，直接破坏单调性：超时计时出现负间隔、租约提前过期（可能造成双主）、日志顺序错乱。正确做法：遵守”允许增加、绝不允许减少“的黄金法则——只能向前 step，或者用 slew 放慢速率渐进逼近。
以为可以测量单向延迟（把 Cristian/NTP 的 RTT 换成单向）。 为什么错：测单向延迟需要知道两端的真实时刻，而这要求时钟已经同步——循环依赖。正确做法：只能测 RTT，然后用区间 + 取中点把误差压到 $\text{RTT}/2$；接受”误差非零但可界定”这个现实。
把并发事件误判为因果事件（或反过来）。 为什么错：在 Lamport 时钟下，$L(a) < L(b)$ 完全不意味着 $a \rightarrow b$（讲义的反例：$H(1) < C(3)$ 但两者并发）；$L(a) = L(b)$ 也不意味着是同一个事件。正确做法：把黄金公式贴在墙上——$E_1 \rightarrow E_2 \Rightarrow ts(E_1) < ts(E_2)$，但反过来只能推出”因果或并发”。要精确判定就用向量时钟。
在向量时钟里把”合并”写成逐维相加或逐维取较小值。 为什么错：向量时钟的合并必须是逐维取 max（把对方的因果历史并进来）；相加会虚构出从未发生的事件，取小会丢失因果信息。正确做法：V[i] += 1（只增自己那一维）+ 其余维 max(V_msg[k], V[k])。
以为逻辑时钟在消息丢失时也永远正确。 为什么错：向量时钟的正确性依赖”因果信息被传播”。若一条消息在网络上丢失（且没有被重传），那么”接收方继承发送方历史”这一步就没有发生——此时存储系统如果只看到接收方后续的写，就可能把一个本应因果在先的写误判为并发（产生假冲突）甚至丢失它。正确做法：因果信息必须与数据一起被可靠地存储与传播（这正是 Dynamo/Riak 用”读时反熵 + 读修复”来补齐因果元数据的原因）；逻辑时钟解决的是顺序问题，不解决可靠性问题。
向量时钟的维数用错（把客户端/会话也当成一个维度）。 为什么错：$N$ 一旦包括所有客户端，向量会无限膨胀，消息头无法承受。正确做法：$N$ 只包含副本（replica）；客户端的”一次写”用一个 dot（Dotted Version Vector）表示，而不是分配一个永久维度。
忽略 $min_1 \ne min_2$ 造成的系统性偏差。 为什么错：非对称延迟造成的偏差是系统偏差（$\lvert o_{real}-o\rvert$ 的期望约为 $\lvert E[L_2]-E[L_1]\rvert/2$），多测几次取平均完全无法消除它——程序 3 的实验里平均偏差稳定在 $-39.7$ ms 就是这个道理。正确做法：把时间服务器放在网络拓扑上对称的位置（同机房、同交换机），或使用硬件时间戳（PTP）与多源交叉验证。
把 Lamport 时间戳当成”事件的真实发生次数/时刻”。 为什么错：它既不是真实时间，也不是事件计数（$D$ 的 Lamport 值是 5，但 $D$ 只是 P1 的第 4 个事件）。正确做法：把它理解为”因果高度的一个上界近似”——它只对比较大小负责，不对数值含义负责。

11.8 思考题（带答案）

题目 1（计算题）：某系统要求任意两台机器的时钟偏差始终小于 $M = 1$ ms。机器使用普通石英晶振，$\text{MDR} = 5 \times 10^{-6}$。 (a) 至少多久同步一次？ (b) 若使用 NTP，实测 RTT 为 20 ms，那么即使按 (a) 的频率每秒同步，实际能达到的偏差是多少？这个要求可满足吗？ (c) 若要把该要求变为可满足，有哪些可行的工程手段？

答案： (a) 两个相似时钟之间的最大相对漂移率是 $2\,\text{MDR} = 10^{-5}$。由 $t_{\max} = M/(2\,\text{MDR})$： $t_{\max} = \frac{10^{-3}}{2 \times 5\times 10^{-6}} = \frac{10^{-3}}{10^{-5}} = 100\ \text{秒}.$ 即最多每 100 秒同步一次（工程上应更频繁，例如每 50 秒）。

(b) 不可满足。 每次 NTP 同步本身就把时钟设到一个误差不超过 $\text{RTT}/2 = 10$ ms 的值上——单次同步的残留误差（10 ms）已经是要求（1 ms）的 10 倍。同步再频繁也无法把这个误差变小，因为它是”消息延迟的不确定性”造成的，与同步周期无关。系统的实际偏差上界约为 $\underbrace{\text{RTT}/2}_{10\ \text{ms}} + \underbrace{M}_{1\ \text{ms}} \approx 11\ \text{ms} \gg 1\ \text{ms}.$ (c) 可行手段（任答两条即可）：

缩短 RTT：把时间服务器放到同一台机器/同一个机架（RTT 从 20 ms 降到几十微秒），误差界随之降到微秒级；
使用 PTP + 硬件时间戳：消除协议栈排队延迟与非对称性，局域网可达亚微秒；
部署本地权威时源：GPS/原子钟（TrueTime 路线），把”网络不确定性”换成”本地硬件不确定性”，并把不确定区间显式暴露给上层；
放宽 $M$：如果业务其实只需要 10 ms 的一致性，那就不必强求 1 ms——先问清楚精度是不是真的需要，这往往是最便宜的优化。

题目 2（”某个直观但错误的想法”）：某同学说：”我们在所有服务器上部署了 NTP，每台机器与 UTC 的偏差都不超过 1 ms，那么日志里的事件顺序就一定是真实的因果顺序了。”这个想法错在哪？请给出两层反驳。

答案：

第一层（误差方向随机）：1 ms 的偏差虽然小，但它的符号是随机的。对于两个真实间隔小于 2 ms 的事件（在云上极其常见），时间戳的先后完全可能是反的——而且今天是这个结论，明天可能是另一个。一个”有时正确”的顺序机制在生产环境里等同于”不可靠”。
第二层（更根本）：即使时间戳顺序恰好正确，那也只是运气，因为物理时间戳与因果关系没有任何必然联系。例如 A 卖票后发消息给 B、B 记录满员：这个因果链在时间戳上完全不可见——B 的钟哪怕与 A 的钟误差为零，我们也只是”碰巧”看到正确顺序，系统里没有任何机制保证它。要保证，就必须把因果信息（逻辑时间戳）随消息一起传播，这正是 Lamport/向量时钟做的事。
补充：还有一个常被忽略的点——物理时间同步把系统的正确性外包给了 NTP 基础设施，而 NTP 服务器是单点故障、也是攻击面（一个被伪造的时间源可以让整个日志系统的顺序任意变）。

题目 3（设计题）：你要为一个多副本键值存储设计冲突解决策略，两个候选方案是 (A) Cassandra 式”物理时间戳 + last-write-wins”，(B) Dynamo/Riak 式”向量时钟 + 检测并发 + 把 siblings 交给应用”。请分别写出它们在一个”客户端先 put(x=1) 再 put(x=2)（两次写打到了不同副本）”场景下的行为，并说明各自的代价。

答案：

场景：客户端跨副本写两次，第一个副本收到 x=1，第二个副本收到 x=2，两个副本事后做反熵。
方案 A（LWW）：两个副本各自用本地物理时钟给写打戳。若客户端确实先写 x=1、后写 x=2，正常情况下 $ts_2 > ts_1$，LWW 保留 x=2 ✓。但若接收 x=2 的副本时钟偏慢（比如慢 5 毫秒而两次写只隔 1 毫秒），就会出现 $ts_1 > ts_2$，LWW 会静默丢弃 x=2——用户明明后写了 2，读回来的却是 1，而且系统不会报任何错。代价：正确性依赖时钟同步，且错误是静默的；收益：实现极其简单，元数据只有 8 字节。
方案 B（向量时钟）：每个副本维护一个版本向量。客户端先写 x=1 得到版本 $V_1$，再写 x=2 得到 $V_2$；因为是同一个客户端/同一条因果链，若版本元数据被正确传播（客户端第二次写时必须带上第一次写的版本，或用 DVV 的 dot 表示”紧接着的那次写”），则 $V_1 < V_2$，系统正确地判定 x=2 更新 ✓。只有当客户端真的并发写（例如两个离线客户端各写一次）时，两个版本才不可比较，此时返回 siblings，由应用层合并（也许 x 应该相加而不是覆盖，也许应该让用户选）。代价：元数据膨胀（向量 + dot），需要可靠传播因果元数据（陷阱 6），需要应用层实现合并逻辑；收益：永远不会因时钟偏差丢写。
结论：选择取决于业务——“计数器/购物车”这类可合并的数据适合 B（丢一次加购是真实损失），“最后一次配置覆盖”这类语义本身就以覆盖为准的数据适合 A。Cassandra 之所以选 A，是因为它把简单性、可用性与低开销排在”绝对不丢写”之前；Riak 之所以选 B，是因为它把正确性排在前面并愿意把复杂度推给应用。

题目 4（概念题）：为什么 Lamport 时钟的 $O(1)$ 空间不可能同时做到”精确判断因果与并发”？请给出论证，并说明向量时钟为什么必须花 $O(N)$。

答案：

第一步：如果要求精确判断，方案必须满足 $a \rightarrow b \iff T(a) < T(b)$ 且 $a \parallel b \iff T(a), T(b)$ 不可比较。
第二步：整数（或任何全序值域）中，两值”不可比较”的唯一方式是相等。所以方案必须满足”并发 ⟺ 时间戳相等”。
第三步（反例）：构造三个事件：$P_1$ 上 $a \rightarrow c$（$a$ 发消息给 $P_3$ 得到 $c$），$P_2$ 上的 $b$ 与 $a$、$b$ 与 $c$ 都并发。由第二步必须同时有 $T(a) = T(b)$ 与 $T(b) = T(c)$，于是 $T(a) = T(c)$；但 $a \rightarrow c$ 又要求 $T(a) < T(c)$，矛盾。故单个整数做不到。
第四步：既然时间戳的值域必须是偏序，那它至少要能区分”每个进程各发生了多少事件”这 $N$ 个相互独立的量——因为事件的因果过去（一致割）正是由这 $N$ 个计数确定的，而它们可以独立变化。Charron-Bost（1991）证明了能精确刻画 $N$ 进程计算之因果关系的向量空间最小维数恰好是 $N$。向量时钟的 $N$ 维正是这个下界的紧的实现。
结论：$O(N)$ 不是工程上的将就，而是理论上必须付的价。想要 $O(1)$，就必须放弃某种能力——Lamport 放弃了”识别并发”，HLC 也放弃了”识别并发”（它只保证因果性），这正是它们能回到 $O(1)$ 的原因。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li