T01 Tutorial 1：两张时钟图和四条性质，练习事件排序与可靠广播

一句话版

这份 tutorial 只考两件事：给图机械算时钟，给场景点名性质。两件都靠熟练度，不靠灵感。

题目地图

五页题，三种题型，前三讲各考一遍。

题	考什么	主要失分点
选择题 1（p.1）	TOB 有哪四条标准性质	把 FIFO Order 当成 TOB 的性质
选择题 2（p.1）	RB 与 URB 的差别	选了 Agreement——两者都有，不构成差别
Figure 1（p.1–2）	Lamport 时钟手算，事件 a 到 z	max 的另一边取错；接收事件忘了 +1
Figure 2（p.2–3）	向量时钟手算，同样 a 到 z	只更新自己那一维，忘了逐分量 max
RB 两问（p.3）	哪条性质被违反	只答「出错了」，没点名性质
URB 三问（p.4）	数来源、判 Uniform Agreement	广播者自己那一份算不算来源
重画题（p.5）	改崩溃集合后重画执行图	漏掉 m2；给崩溃进程补上交付

答题时先点名性质，再引用定义说明是否违反；时钟题逐事件列值。

概念卡

1. 四条性质的准确表述（TOB Properties）

人话定义：Validity 管「自己广播的自己得交付」，Agreement 管「一个人交付了别人也得交付」，Integrity 管「不重不造」，Total Order 管「所有人看到的排列一样」。

例子：p.1 的选择题给了 Validity / Agreement / Total Order / FIFO Order 四选一问哪个不是 TOB 的标准性质，答 FIFO Order。它属于 FIFO Broadcast，和 Total Order 是两个独立维度——全序保证所有人顺序一致，但这个共同顺序不一定符合某个发送方自己的发送次序，两者都要满足的原语叫 FIFO Total Order Broadcast。Integrity 这次没进选项，它等于 No Duplication 加 No Creation，同样是四条之一。

常见误解

以为选项里没出现的性质就不在标准四条里 → Integrity 缺席只是出题时的取舍。这类题的排除法是：Validity 和 Agreement 是所有广播原语的公共底座，Total Order 是 TOB 的定义性性质，三个都排除，剩下那个排序名就是答案（p.1）。

2. Lamport 三条规则与「本地上一个事件」（Lamport Clock）

人话定义：每个进程一个计数器，本地事件和发送事件加 1，接收事件先和消息戳取 max 再加 1。

例子：规则只有三条——计数器初值 0；本地或发送事件 C ← C + 1，发送时把这个值附在消息上；接收事件 C ← max(C, 消息戳) + 1（p.1）。max 里的 C 指的是本进程上一个事件的时间戳，这是全题唯一的坑。Figure 1 里 f 收到时间戳 6 的消息，而 P1 上一个事件 e = 7，所以 f = max(7, 6) + 1 = 8，本地值比消息戳大，max 取本地。

常见误解

把接收事件算成「消息戳 + 1」→ 这在本地值更大时会给出完全不同的数，改卷时区分度最高的三个事件（i、s、t）全是这种情形（p.2）。另一处是接收事件忘了最后那个 +1，直接把 max 的结果当时间戳。

3. 向量时钟三条规则与因果判据（Vector Clock）

人话定义：规则和 Lamport 几乎一样，差别只有两处——max 是逐分量取的，加 1 只加自己那一维。

例子：进程 Pᵢ 维护长度为 n 的向量，初值全 0；本地或发送事件 V[i] ← V[i] + 1 之后再把整个向量附在消息上；接收事件先对所有 k 做 V[k] ← max(V[k], V′[k])，再 V[i] ← V[i] + 1（p.2）。第 k 维的含义是「本进程当前所知的 Pₖ 已发生的事件数」。因果判据：逐维 ≤ 且至少一维严格 < 等价于 happens-before，两个方向都不成立就是并发。

常见误解

接收时只给自己那一维加 1、跳过逐分量 max → 这是两个高频错误里的第一个，第二个是 max 做完忘了加 1（p.2）。还有一处在发送端：附在消息上的是自增之后的向量，先发再加会让接收方少算一格。

4. 正确进程还是故障进程（Correct vs Faulty）

人话定义：Agreement 只保护正确进程，Uniform Agreement 把前件扩到任何进程，所有判定题的第一问都是「这个进程属于哪一类」。

例子：RB 的 Agreement 前提是「某个正确进程交付了 m」，崩溃进程交付过什么不作数；URB 的 Uniform Agreement 前提是「任一进程交付了 m」，包含那些交付完立刻崩溃的（p.1）。Uniform 这个词在分布式文献里的固定含义就是把约束从正确进程扩展到所有进程。需要它的理由很实在：一个进程可能在崩溃前已经把交付结果暴露给外部——写了数据库、给用户发了确认，其他人最后都不交付的话，这个外部可见的结果就成了系统里的不一致（p.1、p.4）。

常见误解

把「有进程没交付」直接等同于「性质被违反」→ p.3 两问正是一对反例：正确进程 P5 永不交付违反 Agreement，故障进程 P4 不交付不违反。判定的第一步永远是分辨这个进程正确还是故障（p.3）。

逐题拆解

Figure 1（Lamport）的答案：P1 = 1, 2, 3, 6, 7, 8；P2 = 1, 2, 3, 4, 5, 6, 8；P3 = 1, 2, 3, [4], 5, 6, 7, 8, 9；P4 = 1, 2, 3, 6, 7。方括号那格是 P3 上未标注的黑点，按内部事件计。五个最容易错的：d = max(3, 5) + 1 = 6（收到 k 的 5，本地上一个是 c = 3）；m = max(6, 7) + 1 = 8；f = max(7, 6) + 1 = 8；y = max(3, 5) + 1 = 6；u = max(8, 7) + 1 = 9。另外三个本地值大于消息戳的：i = max(2, 1) + 1 = 3，s = max(6, 3) + 1 = 7，t = max(7, 3) + 1 = 8。

这张图还顺手给出了 Lamport 的局限：c = 3 和 p = 3 时间戳相同却毫无因果关系，f = 8 和 m = 8 也一样。不同事件的 Lamport 时间戳相等可推出并发，因为任一方向的因果都会要求严格增大；有序则不能反推因果，单向蕴含只有 e → e′ ⟹ C(e) < C(e′) 这一个方向。这正是下一题换向量时钟的理由。

Figure 2（向量）的关键值：c = (3, 4, 1, 0)，k = (1, 6, 6, 4)，p = (1, 1, 5, 4)，r = (4, 4, 8, 4)，s = (4, 4, 9, 7)，黑点 = (1, 1, 7, 4)。k 的第 3、4 维一下子跳到 6 和 4，说明那条消息链把 P3、P4 的历史整段带了过来。因果判断题拿这张图出：c = (3, 4, 1, 0) 与 p = (1, 1, 5, 4) 互不包含，c ∥ p 并发；a = (1, 0, 0, 0) 与 s 每一维都 ≤ 且有严格小于，a → s，图里确实存在 a → n → … → r → s 这条链。

RB 两问（p.3）。第一问：P1 广播 m，P2、P3、P4 交付了，正确进程 P5 因网络故障始终没收到。答 Agreement 被违反——定义是「若某个正确进程交付了 m，则所有正确进程最终都交付 m」，P5 是正确进程却永不交付。Validity 成立（广播者 P1 自己交付了），Integrity 成立（没有重复，没有凭空冒出的消息）。答完还要补一句模型前提：RB 建立在 perfect links 之上，只要收发双方都不崩溃消息最终必达，题目里的永久丢包超出了这个模型，协议本身没出 bug。

第二问：P4 收到 m 后在交付前崩溃。答 Agreement 依然满足，因为 P4 是故障进程，不在 Agreement 的约束范围内，P1、P2、P3、P5 都会交付。P2、P3 各自转发过一份，P5 至少有两条独立路径拿到 m——这就是「收到即转发」存在的理由：只靠广播者单点发送，它发到一半崩溃就会出现一部分人交付、一部分人永不交付，Agreement 立刻破。

URB 三问（p.4）。五个进程，P4、P5 在算法开始前就已崩溃，交付规则改成「收到来自至少 2 个不同进程的副本才交付」。数来源：P1 有三个（自己、P2 转发、P3 转发），P2 有两个（P1 原发、P3 转发），P3 有两个（P1 原发、P2 转发），三个正确进程全部达到阈值，都能交付。Uniform Agreement 满足——P4、P5 在崩溃前没交付过任何消息，「故障进程交付了而正确进程没交付」这种破坏情形不存在，而正确进程这一侧本来就全交付了。这是对这次固定执行的判断，不是对任意崩溃时序的证明。

重画题（p.5）。原图里 P1 广播 m1、m2 后崩溃，m2 无人交付；P4 广播 m5、m6、m7 后立即崩溃；P5 广播 m8 后期崩溃。问题是把崩溃集合改成「P1 正确，P4 与 P5 崩溃」后重画。推导链条就是给分点：P1 变正确 ⟹ Validity 生效 ⟹ m1 和 m2 都必须被 P1 自己交付 ⟹ Uniform Agreement 生效 ⟹ P2、P3 也必须交付 m2 ⟹ 正确进程的交付集合统一拉齐为 {m1, m2, m3, m4}。m5 到 m8 仍可无人交付：广播它们的是故障进程，Validity 不保护，又确实没人交付过，Uniform Agreement 的前件不成立。

课件里的坑

• [课件留白] P3 的未标注黑点是否计作内部事件需注明假设；评分口径应向教师确认，不能保证哪种写法不扣分（p.1、p.3）。
• [课件留白] 不计那个黑点时的差异要能立刻说出：Figure 1 里 P3 从 q 起整体减 1（q = 4 … u = 8），连带 y = 5、z = 6，P1 与 P2 不受影响；Figure 2 里只有 r = (4, 4, 7, 4) 和 s = (4, 4, 8, 7) 两行变，因为 q 到 r 之间没有跨进程消息发出（p.1、p.3）。
• [课件留白] URB 那道阈值题没说广播者自己持有的那一份算不算来源。两种读法下 P1 都够 2 个，结论不变，但 P2、P3 的数法要在答卷上写明按哪种读法（p.4）。
• [口径差异] 重画题不止一种合法答案：让 P5 在崩溃前交付 {m1, m2, m3, m4} 同样不违反任何性质，因为它交付的都是正确进程也会交付的消息。代价是要求 P5 崩得更晚、画起来更麻烦，且顺手给 P5 画上 m8 的交付就会出错——给崩溃进程补交付会引入新的 Uniform Agreement 义务，整张图都得改（p.5）。
• [补充] 选择题 2 的四个选项里，Agreement 是最容易踩的那个。RB 与 URB 的 Validity、Integrity 完全相同，Agreement 两者都有，被加强的只有一致性那一条的主语，所以答 Uniform Agreement（p.1）。

课后 10 分钟：考点复习

这 10 分钟怎么用：合上页面，先默写三条——Lamport 的接收规则、向量时钟的接收两步、判定题的第一问；再把下面的「变式题」算一遍；最后回查两处最容易错的地方——max 的另一边取成了消息戳、逐分量 max 之后忘了给自己加 1。三步做完再往下看答案。

必背

1. TOB 四条标准性质：Validity、Agreement、Integrity（No Duplication + No Creation）、Total Order；FIFO Order 属于 FIFO Broadcast，不在其中。
2. Lamport 接收事件：C ← max(本地上一个事件, 消息戳) + 1，max 的另一边是本地上一个事件，不是本进程初值；本地事件与发送事件只做 +1。
3. 向量时钟接收事件先逐分量 max、再只给自己那一维 +1，两步都不能省；发送时先自增再把整个向量附在消息上。
4. 向量时钟判因果：逐维 ≤ 且至少一维严格 < 即 happens-before，互不包含即并发；不同事件的 Lamport 戳相等可判并发；戳较小却不能反推因果。
5. 判定题第一步永远是问「这个没交付的进程是正确进程还是故障进程」：正确进程不交付违反 Agreement，故障进程不交付不违反。
6. 正确进程永远收不到消息属于 perfect links 假设被打破，RB 协议本身没出错；「收到即转发」是为了广播者中途崩溃时其余正确进程仍能收到。
7. 本题固定执行中，三个正确进程都收到足够副本；不能把阈值 2 推广成任意故障模型下的 URB 充分条件，安全阈值还取决于故障上限和转发规则。
8. 重画题解法：先定崩溃集合 → 用 Validity 补出必须被交付的消息 → 用 Uniform Agreement 把正确进程的交付集合拉齐；崩溃进程广播的消息可以无人交付。

完整例题

把 Figure 2 里最长的那条线（P3，从 l 一路到 s）完整推一遍，向量按 (P1, P2, P3, P4) 排，初值全 0。这条线上有五个接收事件，正好把两个高频错误都踩一遍。

1. l（本地）：只给第 3 维加 1 → (0, 0, 1, 0)。它随后被发往 P2，附带的就是这个向量。
2. m（收 t 的 (0, 0, 0, 1)）：本地上一个是 l = (0, 0, 1, 0)，逐分量 max → (0, 0, 1, 1)，第 3 维加 1 → (0, 0, 2, 1)。
3. n（收 a 的 (1, 0, 0, 0)）：max((0,0,2,1), (1,0,0,0)) = (1, 0, 2, 1)，加 1 → (1, 0, 3, 1)。
4. o（收 u 的 (0, 0, 0, 2)）：max → (1, 0, 3, 2)，加 1 → (1, 0, 4, 2)。
5. p（收 w 的 (0, 1, 0, 4)）：max((1,0,4,2), (0,1,0,4)) = (1, 1, 4, 4)，加 1 → (1, 1, 5, 4)。四维里有三维同时被推高，这是典型的「消息把别人的历史带过来」。
6. q（本地）→ (1, 1, 6, 4)；黑点（按内部事件计）→ (1, 1, 7, 4)。
7. r（收 d 的 (4, 4, 1, 0)）：本地上一个是黑点 (1, 1, 7, 4)，max → (4, 4, 7, 4)，加 1 → (4, 4, 8, 4)。注意第 3、4 维走的是本地值，第 1、2 维走的是消息值。
8. s（收 z 的 (2, 3, 1, 7)）：max((4,4,8,4), (2,3,1,7)) = (4, 4, 8, 7)，加 1 → (4, 4, 9, 7)。

自检：s 是这条线的末尾，它的第 1 维 4 表示该事件已获知的 P1 事件数，第 4 维 7 表示已获知的 P4 事件数，不是全知的全局实时计数——数一遍图上的黑点，对得上就说明中间没漏步。若不计那个未标注黑点，只有 r 和 s 两行变成 (4, 4, 7, 4) 与 (4, 4, 8, 7)，前面全不动，因为 q 到 r 之间没有任何跨进程消息发出。

变式题（先自己做）

三个进程，向量按 (P1, P2, P3) 排，初值全 0。事件序列：P1 上先有本地事件 a₁，再发消息 m 给 P3（发送事件 a₂）；P2 上先有本地事件 b₁，再发消息 m′ 给 P3（发送事件 b₂）；P3 上先有本地事件 c₁，然后先收到 m′（事件 c₂）、再收到 m（事件 c₃），最后回发一条给 P1（发送事件 c₄）；P1 收到它，记作 a₃。

(1) 写出全部九个事件的向量时钟。(2) a₁ 与 b₁ 是并发还是有因果关系？(3) 若 P3 上在 c₁ 之前还有一个未标注黑点，哪些值会变、变成多少？

提示

发送事件也要先给自己那一维加 1，附在消息上的是加完之后的值。c₄ 带走的向量和 c₃ 的不一样。第 (3) 问不必重算，只需想清楚「P3 那一维整体后移一格」会波及到谁——被 P3 发出去的消息带到哪，哪里就会变。

参考答案与自检（非官方评分标准）

自检要点：① 接收事件先逐分量 max 再只给自己加 1；② 发送事件附带的是自增之后的向量；③ 并发的判据是两个方向的 ≤ 都不成立，不能只看某一维。

(1) a₁ = (1, 0, 0)；a₂ = (2, 0, 0)，m 带 (2, 0, 0)。b₁ = (0, 1, 0)；b₂ = (0, 2, 0)，m′ 带 (0, 2, 0)。c₁ = (0, 0, 1)；c₂ = max((0,0,1), (0,2,0)) + 第 3 维加 1 = (0, 2, 2)；c₃ = max((0,2,2), (2,0,0)) + 加 1 = (2, 2, 3)；c₄ = (2, 2, 4)，带走的就是这个值。a₃ = max((2,0,0), (2,2,4)) + 第 1 维加 1 = (3, 2, 4)。

(2) 并发，a₁ ∥ b₁。a₁ = (1, 0, 0) 的第 1 维大，b₁ = (0, 1, 0) 的第 2 维大，互不包含，两个方向的 ≤ 都不成立。

(3) 黑点 = (0, 0, 1) 之后，P3 那一维整体后移一格：c₁ = (0, 0, 2)，c₂ = (0, 2, 3)，c₃ = (2, 2, 4)，c₄ = (2, 2, 5)。P1 的 a₃ 因为收了 c₄ 也跟着变成 (3, 2, 5)。a₁、a₂ 与 P2 的两个事件全不变——P3 的变化只能通过它发出的消息传播出去。

闪卡自测

1. TOB 的四条标准性质是什么？FIFO Order 为什么不在其中？

Validity、Agreement、Integrity（No Duplication + No Creation）、Total Order（p.1）。FIFO Order 属于 FIFO Broadcast，和 Total Order 是两个独立维度；全序保证所有人顺序一致，但这个共同顺序不一定符合发送方自己的发送次序。两者都要满足的原语叫 FIFO Total Order Broadcast。

2. 一句话说出 Agreement 与 Uniform Agreement 的唯一差别。

前件的主语：Agreement 写「某个正确进程交付了 m」，Uniform Agreement 写「任一进程交付了 m」，包含交付完立刻崩溃的那些。后件都是「所有正确进程最终交付 m」（p.1）。

3. 为什么需要 Uniform Agreement？

进程可能在崩溃前已经把交付结果暴露给外部——写了数据库、给用户发了确认。其他人最后都不交付的话，这个外部可见的结果就成了系统里的不一致（p.1、p.4）。

4. 写出 Lamport 接收事件的公式，指出 max 的两个操作数分别是什么。

C ← max(C, 消息时间戳) + 1。其中 C 是本进程上一个事件的时间戳，不是初值也不是消息戳。Figure 1 里 f = max(7, 6) + 1 = 8 就是本地值更大的情形（p.1）。

5. 向量时钟接收事件的两步是什么？哪一步最容易漏？

先对所有 k 做逐分量 V[k] ← max(V[k], V′[k])，再只给自己那一维加 1（p.2）。两个高频错误是只更新自己那一维、跳过逐分量 max，以及 max 做完忘了加 1。

6. Figure 2 里 c 与 p 是什么关系？判据是什么？

c = (3, 4, 1, 0)，p = (1, 1, 5, 4)。c 的第 1、2 维大，p 的第 3、4 维大，互不包含，所以 c ∥ p 并发。判据是逐维 ≤ 且至少一维严格 < 才构成 happens-before（p.3）。

7. 正确进程 P5 因网络故障永不交付，违反了哪条性质？这算协议出 bug 吗？

违反 Agreement——P2、P3、P4 这些正确进程交付了，同为正确进程的 P5 却永不交付。不算协议 bug：RB 建立在 perfect links 之上，永久丢包超出了这个模型（p.3）。

8. RB 里「收到即转发」这一步能防住什么？

防广播者中途崩溃。只靠广播者单点发送，它发到一半崩溃就会出现一部分人交付、一部分人永不交付，Agreement 立刻被破坏；转发让传播不再依赖任何单个进程（p.3）。

9. URB 那题里 P1、P2、P3 各有几个来源？阈值改成 1 会怎样？

P1 有三个（自己、P2 转发、P3 转发），P2 与 P3 各两个，都达到阈值 2（p.4）。在题设 P4、P5 已预先崩溃、其余进程正确的执行里，阈值降到 1 不会凭空制造后续崩溃。若换成动态崩溃模型，必须结合广播与转发规则另证 Uniform Agreement。

10. 重画题里 m2 为什么在原图可以无人交付、在新图必须被交付？

原图 P1 崩溃，Validity 只保护正确进程的广播，且没人交付过 m2，Uniform Agreement 的前件不成立。新图 P1 变正确，Validity 要求它交付自己广播的 m1 和 m2，再由 Uniform Agreement 把 P2、P3 的交付集合一起拉齐到 {m1, m2, m3, m4}（p.5）。

下一步

两张图各重算一遍，不看答案——这是这门课唯一能靠熟练度稳拿分的题型，错也只错在机械步骤上，盯住「本地上一个事件」和「先 max 再 +1」两处，练三遍就不会再错。再把「图里出现无标签事件先在答卷上写一句假设」写进自己的答题模板。性质那一侧背准四条定义，简答题全是点名性质加套定义，定义背不准就写不出得分点。按课程进度，下一次课堂时段是 Project 介绍，组队和选题从那时开始。