2025 期末真题解析(一)|Q16–Q18:逻辑时钟、URB 与 CO-URB
非官方参考解答:2025 年期末卷 Part C 的 Q16 Lamport 时钟与向量时钟填表、Q17 URB 重画流程图、Q18 CO-URB 交付顺序与 m.past,题面中文转述,解析附讲义页码和歧义说明。
手机上宽表格可左右滑动;自测答案默认收起,点击题目下方按钮查看。
非官方参考解答,不是讲师给的标准答案;今年的考试安排与范围以讲师通知为准。 先自己在纸上做一遍,再展开对照。
范围与作答约定
本页收 2025 年期末卷 Part C 的前三题,题目按卷面原题中文转述,关键术语保留英文;三张图截自 Final Review 课件。后面五题见真题解析(二)和真题解析(三),卷子的整体形式见期末复习资料。
这三题都是填表计算,一格算错会连着错一串。解析里的数是按图上读出的消息箭头逐事件推出来的,图上读不准的地方单独写「此处按 X 读;若按 Y 读,结果变为 Z」。考场上遇到这类地方,在答案旁写一句自己的假设。
题目与解析
Q16 · Lamport clock and vector clock
(1) Figure 1 有四个进程 P1–P4,事件 a 到 z,初始时钟都是 0。填出每个带字母事件的 Lamport timestamp。
(2) Figure 2 同样是四个进程、事件 a 到 z,初始向量 (0,0,0,0)。填出每个事件的 vector timestamp。这一问 5 分,每错一格扣 0.5 分,扣完为止。
Q16 · 查看答案与解析
参考解答,非官方答案。 先列出从图上读到的消息(发送 → 接收),再按规则逐个事件推。
Figure 1 的 13 条消息:a→h、b→j、g→p、n→i、v→o、c→s、k→d、w→r、q→y、x→t、e→m、l→f、z→u。
Figure 2 的 13 条消息:a→n、f→v、l→g、t→m、u→o、h→x、i→c、b→y、w→p、d→r、j→e、q→k、z→s。
规则:Lamport 时钟本地事件加 1,收消息取「本地值和消息时间戳的较大者」再加 1(L02 p.19)。向量时钟本地事件只给自己那一位加 1,收消息再和消息向量逐位取较大者(L02 p.22)。
(1) Lamport:
| 进程 | 时间戳 |
|---|---|
| P1 | a 1, b 2, c 3, d 6, e 7, f 8 |
| P2 | g 1, h 2, i 3, j 4, k 5, l 6, m 8 |
| P3 | n 1, o 2, p 3, 黑点 4, q 5, r 6, s 7, t 8, u 9 |
| P4 | v 1, w 2, x 3, y 6, z 7 |
容易错的四格:d 收 k 的 5,本地 3,得 6;m 收 e 的 7,本地 6,得 8;f 收 l 的 6,本地 7,得 8;u 收 z 的 7,本地 8,得 9。
(2) 向量:
| 进程 | 时间戳 |
|---|---|
| P1 | a (1,0,0,0), b (2,0,0,0), c (3,4,1,0), d (4,4,1,0), e (5,5,1,0) |
| P2 | f (0,1,0,0), g (0,2,1,0), h (0,3,1,0), i (0,4,1,0), j (0,5,1,0), k (1,6,6,4) |
| P3 | l (0,0,1,0), m (0,0,2,1), n (1,0,3,1), o (1,0,4,2), p (1,1,5,4), q (1,1,6,4), r (4,4,8,4), s (4,4,9,7) |
| P4 | t (0,0,0,1), u (0,0,0,2), v (0,1,0,3), w (0,1,0,4), x (0,3,1,5), y (2,3,1,6), z (2,3,1,7) |
P3 上 q 和 r 之间的黑点算出来是 (1,1,7,4),题目没让填它,但它会让 r、s 的第三位各加 1。
黑点的歧义。 两张图的 P3 上都有一个没标字母的黑点。此处按「它是一个内部事件」读(图上画了点就是事件)。若按「不是事件」读,结果变为:Figure 1 的 q 4、r 5、s 6、t 7、u 8,连带 P4 的 y 5、z 6;Figure 2 的 r (4,4,7,4)、s (4,4,8,7);其余格不变。答题时在表旁写一句「the unlabeled dot on P3 is treated as an internal event」。
这两张图和 Tutorial 1 的两张图相同,结果和 Tutorial 1 的答案一致。
Q17 · Redraw the URB diagram
5 个节点运行 Uniform Reliable Broadcast(URB),原流程图如下:P1 广播 m1、m2,交付 m1、m3 后崩溃;P2 广播 m3,交付 m1、m3、m4;P3 广播 m4,交付 m1、m3、m4;P4 广播 m5、m6、m7 后崩溃,什么也没交付;P5 广播 m8,交付 m1、m3、m4 后崩溃。
(1) 假设 P1 没有崩溃,P4、P5 照原图崩溃,重画这张图。
(2) 假设 P1、P5 都没有崩溃,只有 P4 照原图崩溃,重画这张图。
Q17 · 查看答案与解析
参考解答,非官方答案。 重画只需要把每个节点最后交付了哪些消息画对,交付先后 URB 不管。要用的两条性质(L03 p.12–19):Validity,正确进程广播的消息自己一定交付;Uniform Agreement,任何进程交付过的消息(哪怕它后来崩溃了),所有正确进程都要交付。
(1) 正确进程是 P1、P2、P3。
| 节点 | 交付 |
|---|---|
| P1 | m1, m2, m3, m4 |
| P2 | m1, m2, m3, m4 |
| P3 | m1, m2, m3, m4 |
| P4 | 无,广播 m5、m6、m7 后崩溃 |
| P5 | m1, m3, m4,之后崩溃 |
P1 变成正确进程,Validity 要求它交付自己的 m1、m2;Uniform Agreement 再把 m2 带到 P2、P3,也要求 P1 补交付 P2、P3 交付过的 m4。m5 到 m8 的广播者都崩溃了,Validity 不保护,又没有任何人交付过,所以可以无人交付。P5 不能画成交付了 m8,否则 P1、P2、P3 也必须交付 m8。
(2) 正确进程是 P1、P2、P3、P5。
| 节点 | 交付 |
|---|---|
| P1、P2、P3、P5 | m1, m2, m3, m4, m8 |
| P4 | 无 |
P5 变成正确进程,Validity 要求它交付自己的 m8,Uniform Agreement 把 m8 带到另外三个正确进程,也把 m2 带到 P5。m5、m6、m7 仍可无人交付。
「crashed as above」的歧义。 此处按「崩溃时刻和原图一样」读:(1) 里 P5 保留原图的交付 m1、m3、m4 再崩溃(它多交付一个 m2 也合法)。若按 Tutorial 1 的简化读法,P4、P5 在收到任何消息之前就崩溃,(1) 里 P5 的交付栏为空,同样合法。两种读法下正确进程的交付集合都是 {m1, m2, m3, m4},失分点只会出在正确进程上。
Q18 · CO-URB delivery order and m.past
4 个节点运行 CO-URB(causal order URB),执行轨迹如下图,M1 旁标的是它的 m.past = (0,0,0,0)。每次广播都有一条回到自己的弯箭头,表示自交付。
(1) 在 P2 上,M1 和 M5 谁先交付?
(2) 在 P4 上,M3 和 M4 谁先交付?
(3) 写出 m.past:P2 发 M3 时、P3 发 M4 时、P4 发 M5 时。
(4) 写出 delivered 向量:P1 交付 M3 之后、P2 交付 M5 之后、P3 交付 M2 之后。
复习课课件的截图只截到第 (3) 问,第 (4) 问在卷子原件上。
Q18 · 查看答案与解析
参考解答,非官方答案。 规则(L03 p.37–41):delivered 第 k 位是本节点已交付的 Pk 消息数;广播时把当前 delivered 拷一份当 m.past;收到消息时,只有自己的 delivered 每一位都不小于 m.past 才交付,交付后发送者那一位加 1,否则先缓存,每交付一条再回头看缓存。
从图上读到的到达顺序:
| 节点 | 时间顺序 |
|---|---|
| P1 | 广播 M1,收 M3,收 M4,收 M5,广播 M2 |
| P2 | 广播 M3,收 M4,收 M5,收 M2,最后收 M1 |
| P3 | 收 M1,收 M3,广播 M4,收 M5,收 M2 |
| P4 | 收 M1,收 M4,收 M3,广播 M5,收 M2 |
逐事件推出各消息的 m.past:M1 (0,0,0,0),M3 (0,0,0,0),M4 (1,1,0,0),M5 (1,1,1,0),M2 (1,1,1,1)。
P2 的过程:交付自己的 M3,变 (0,1,0,0);M4 到达,要求第一位 ≥ 1,缓存;M5、M2 到达,同样缓存;M1 最后到达,交付后 (1,1,0,0),接着放出 M4、M5、M2。P2 的交付顺序是 M3、M1、M4、M5、M2。
P4 的过程:交付 M1,变 (1,0,0,0);M4 到达,要求第二位 ≥ 1,缓存;M3 到达并交付,变 (1,1,0,0),放出 M4。
(1) At P2, M1 is delivered before M5. M5 先到,但它的 m.past 要求已经交付过 P1、P2、P3 各一条,P2 得等 M1 和 M4。
(2) At P4, M3 is delivered before M4. M4 先到,被缓存到 M3 交付之后。
(3) M3.past (0,0,0,0);M4.past (1,1,0,0);M5.past (1,1,1,0)。
(4) P1 交付 M3 后 (1,1,0,0);P2 交付 M5 后 (1,1,1,1);P3 交付 M2 后 (2,1,1,1)。
四个节点最后都停在 (2,1,1,1),可以拿来自查。图上 P1 附近箭头较密,就算把 P1 收到的某条读错,(4) 的第一格也还是 (1,1,0,0),因为 M3.past 全是 0,P1 收到就能交付,此时它只交付过自己的 M1。
回讲义:L03b-2 因果序
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。