← COMP5567 全部讲次
Q04

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。

Figure 1:四条水平进程线 P1 到 P4,P1 上有事件 a 到 f,P2 上有 g 到 m,P3 上有 n 到 u 以及 p 和 q 之间一个没标字母的黑点,P4 上有 v 到 z,进程之间有 13 条斜向消息箭头
图片来源:COMP5567 Final-Review-5567-2026.pdf, p.22(2025 期末卷 Q16(1) 截图)

(2) Figure 2 同样是四个进程、事件 a 到 z,初始向量 (0,0,0,0)。填出每个事件的 vector timestamp。这一问 5 分,每错一格扣 0.5 分,扣完为止。

Figure 2:四条水平进程线 P1 到 P4,P1 上有事件 a 到 e,P2 上有 f 到 k,P3 上有 l 到 s 以及 q 和 r 之间一个没标字母的黑点,P4 上有 t 到 z,进程之间有 13 条斜向消息箭头
图片来源:COMP5567 Final-Review-5567-2026.pdf, p.23(2025 期末卷 Q16(2) 截图)
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 的答案一致。

回讲义:L02b-2 Lamport 时钟、L02b-3 向量时钟、T01a 时钟填表习题课

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 后崩溃。

Q17 原流程图:五条进程线 P1 到 P5,标出每个节点广播的消息 m1 到 m8 和交付的消息,P1、P4、P5 线末画了崩溃标记
图片来源:COMP5567 Final-Review-5567-2026.pdf, p.24(2025 期末卷 Q17 截图)

(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},失分点只会出在正确进程上。

回讲义:L03a-2 URB 协议、L03a-1 可靠性分三级、T01b 广播性质习题课

Q18 · CO-URB delivery order and m.past

4 个节点运行 CO-URB(causal order URB),执行轨迹如下图,M1 旁标的是它的 m.past = (0,0,0,0)。每次广播都有一条回到自己的弯箭头,表示自交付。

Q18 执行轨迹:四条进程线 P1 到 P4,P1 先广播 M1 后广播 M2,P2 广播 M3,P3 广播 M4,P4 广播 M5,各消息斜向到达其他节点,M1 到 P2 的那条线最长
图片来源:COMP5567 Final-Review-5567-2026.pdf, p.25(2025 期末卷 Q18 截图)

(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 因果序

下一页 →
Q05 2025 期末真题解析(二)|Q19–Q20:3PC 与 VR 时序图

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。