← COMP5567 全部讲次
T01a · 第 3 周

T01a Tutorial 1(上):两张时钟图,一步不漏地手算

Lamport 和向量时钟手算的三处失分点,以及那个没标字母的黑点。

一句话版

这一半只考一件事:给图机械算时钟。靠熟练度,不靠灵感。

先认识这几个词

读之前最好先懂逻辑时钟:Lamport 时钟见 L02b-2,向量时钟见 L02b-3。

词 全称 / 读法 一句人话
内部事件 local event 进程自己做的一件事,不收也不发消息
发送 / 接收事件 send / receive event 发出或收到一条消息,各算一个事件
Lamport 时钟 Lamport clock 每个进程一个整数计数器,用来给事件排先后
向量时钟 vector clock 每个进程记一串数,第 k 个数是它知道的 Pₖ 已发生的事件数
e → e′ / e ∥ e′ 读「e 先于 e′」/「e 与 e′ 并发」 → 是 happens-before,有因果先后;∥ 是谁也不影响谁

题目地图

整份 tutorial 五页题,三种题型,前三讲各考一遍。本页拆两张时钟图,选择题和广播判定题在 T01b。

题 考什么 主要失分点
Figure 1 Lamport 时钟手算,事件 a 到 z max 的另一边取错;接收事件忘了 +1
Figure 2 向量时钟手算,同样 a 到 z 只更新自己那一维,忘了逐分量 max

时钟题逐事件列值,图里有没标字母的事件,先在答卷上写一句假设。

概念卡

1. Lamport 三条规则与「本地上一个事件」(Lamport Clock)

人话定义:它用一个数给每个事件编号,让有因果关系的事件编号一定变大。本地事件和发送事件加 1,接收事件先和消息戳取 max 再加 1。

例子:规则只有三条。计数器初值 0。本地或发送事件 C ← C + 1,发送时把这个值附在消息上。接收事件 C ← max(C, 消息戳) + 1。

max 里的 C 指的是本进程上一个事件的时间戳,这是全题唯一的坑。Figure 1 里 f 收到时间戳 6 的消息,P1 上一个事件 e = 7。本地值比消息戳大,max 取本地:

f = max(7, 6) + 1 = 8

常见误解

把接收事件算成「消息戳 + 1」→ 本地值更大时会给出完全不同的数。改卷时区分度最高的三个事件(i、s、t)全是这种情形。

另一处是接收事件忘了最后那个 +1,直接把 max 的结果当时间戳。

回讲义:L02b-2 Lamport 时钟:给每个事件发一个号

2. 向量时钟三条规则与因果判据(Vector Clock)

人话定义:它能反过来从时间戳判断两个事件有没有因果关系,Lamport 时钟做不到。规则和 Lamport 几乎一样,差别只有两处:max 逐分量取,加 1 只加自己那一维。

例子:进程 Pᵢ 维护长度为 n 的向量,初值全 0。本地或发送事件 V[i] ← V[i] + 1,之后再把整个向量附在消息上。接收事件先对所有 k 做 V[k] ← max(V[k], V′[k]),再 V[i] ← V[i] + 1。意思是先把对方知道的历史并进来,再给自己记一笔。

第 k 维的含义是「本进程当前所知的 Pₖ 已发生的事件数」。判因果:逐维 ≤ 且至少一维严格 < 就是 happens-before;两个方向都不成立就是并发。

常见误解

接收时只给自己那一维加 1、跳过逐分量 max → 这是两个高频错误里的第一个,第二个是 max 做完忘了加 1。

发送端也有一处:附在消息上的是自增之后的向量,先发再加会让接收方少算一格。

回讲义:L02b-3 向量时钟:每台机器记一位,就能判出并发

3. 那个没标字母的黑点(Unlabeled Event)

人话定义:两张图的 P3 上各有一个没有字母的黑点。按分布式系统的惯例,它是一个内部事件,要占一个计数。

例子:下面的答案默认把它算作内部事件。不计它的话,Figure 1 里 P3 从 q 起整体减 1,连带 P4 的 y、z 也变;Figure 2 只有 r、s 两行变,因为 q 到 r 之间没有跨进程消息发出。

常见误解

以为黑点没字母就可以跳过 → 计不计它会改动后面一串数字。两种算法都可能被接受,但评分口径要向教师确认,答卷上先写一句假设。

回讲义:L02b-1 事件、割与 happens-before:没有统一的表,怎么排先后

逐题拆解

Figure 1(Lamport 时钟)

Tutorial 1 的 Figure 1:P1 到 P4 四条进程横线,时间向右。P1 上依次是 a、b、c、d、e、f,P2 上 g、h、i、j、k、l、m,P3 上 n、o、p、一个未标字母的黑点、q、r、s、t、u,P4 上 v、w、x、y、z;箭头表示消息:a→h、b→j、n→i、g→p、v→o、k→d、c→s、e→m、l→f、w→r、x→t、q→y、z→u
图片来源:COMP5567 2026-5567-tutorial-1.docx, Figure 1

答案如下,方括号那格是 P3 上未标注的黑点,按内部事件计:

  • 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

最容易错的五个:

  • 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 1 每个事件的 Lamport 值,重点看接收时 max 什么时候取本地值。

图里事件按时钟值排横坐标,只是示意。每一步只算「所需消息已经到了」的事件,空心点是还没算的。

  1. 先算不收消息的事件:P1 的 a、b、c,P2 的 g,P3 的 n,P4 的 v、w、x,各自在上一个值上 +1。

    第 1 步:四条进程线上,a、b、c 得 1、2、3,g、n、v 都得 1,w、x 得 2、3,青绿标出,其余事件是空心灰点

  2. P2 收到 a、n、b:h = max(1, 1) + 1 = 2,i = max(2, 1) + 1 = 3,j = max(3, 2) + 1 = 4,之后 k = 5,l = 6。P3 收到 v、g:o = 2,p = 3,黑点 = 4,q = 5。

    第 2 步:P2 的 h、i、j、k、l 得 2 到 6,P3 的 o、p、黑点、q 得 2 到 5,青绿标出,收 a、n、b、v、g 的五条消息画成实线箭头

  3. k 和 q 的值送达:d = max(3, 5) + 1 = 6,e = 7;y = max(3, 5) + 1 = 6,z = 7。

    第 3 步:P1 的 d 收 k 得 6、e 得 7,P4 的 y 收 q 得 6、z 得 7,青绿标出,两处都是消息戳 5 大于本地值 3

  4. P3 依次收 w、c、x:r = max(5, 2) + 1 = 6,s = max(6, 3) + 1 = 7,t = max(7, 3) + 1 = 8。三次都取本地值。

    第 4 步:P3 的 r、s、t 依次收 w、c、x 得 6、7、8,青绿标出,三次 max 取的都是本地上一个事件的值

  5. 最后三个接收事件:f = max(7, 6) + 1 = 8,m = max(6, 7) + 1 = 8,u = max(8, 7) + 1 = 9。全图算完。

    第 5 步:P1 的 f 收 l 得 8,P2 的 m 收 e 得 8,P3 的 u 收 z 得 9,青绿标出,全部事件都已有值

Figure 2(向量时钟)

Tutorial 1 的 Figure 2:P1 到 P4 四条进程横线,时间向右。P1 上 a、b、c、d、e,P2 上 f、g、h、i、j、k,P3 上 l、m、n、o、p、q、一个未标字母的黑点、r、s,P4 上 t、u、v、w、x、y、z;箭头表示消息:l→g、f→v、a→n、t→m、u→o、h→x、i→c、b→y、w→p、j→e、q→k、d→r、z→s
图片来源:COMP5567 2026-5567-tutorial-1.docx, 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 这条链。

一步一步看

目标:分五批算出 Figure 2 每个事件的向量,看接收时逐维 max 怎样把别人的历史带进来。

同样按时间先后分五批算,每个事件先逐维取 max(只有接收事件需要),再给自己那一维 +1。

  1. 先算发送事件:a = (1, 0, 0, 0),b = (2, 0, 0, 0),f = (0, 1, 0, 0),l = (0, 0, 1, 0),t = (0, 0, 0, 1),u = (0, 0, 0, 2)。

    第 1 步:P1 的 a、b,P2 的 f,P3 的 l,P4 的 t、u 只给自己那一维加 1,六个向量青绿标出,其余事件是空心灰点

  2. g 收 l:逐维 max 得 (0, 1, 1, 0),第 2 维 +1 得 (0, 2, 1, 0)。h、i、j 依次加到 (0, 5, 1, 0)。v 收 f 得 (0, 1, 0, 3),w = (0, 1, 0, 4)。

    第 2 步:P2 的 g 收 l 得 (0,2,1,0),h、i、j 依次加 1 到 (0,5,1,0);P4 的 v 收 f 得 (0,1,0,3),w 得 (0,1,0,4),青绿标出

  3. P3 依次收 t、a、u、w: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),黑点 = (1, 1, 7, 4)。

    第 3 步:P3 的 m、n、o、p 依次收 t、a、u、w,q 和黑点各加 1,六个向量从 (0,0,2,1) 到 (1,1,7,4) 青绿标出

  4. P1 收 i、j:c = (3, 4, 1, 0),d = (4, 4, 1, 0),e = (5, 5, 1, 0)。P4 收 h、b:x = (0, 3, 1, 5),y = (2, 3, 1, 6),z = (2, 3, 1, 7)。

    第 4 步:P1 的 c、d、e 和 P4 的 x、y、z 算出,c 收 i 得 (3,4,1,0),y 收 b 得 (2,3,1,6),青绿标出

  5. 最后三个接收事件:k 收 q,max((0, 5, 1, 0), (1, 1, 6, 4)) 后第 2 维 +1,得 (1, 6, 6, 4)。r 收 d 得 (4, 4, 8, 4),s 收 z 得 (4, 4, 9, 7)。

    第 5 步:P2 的 k 收 q 得 (1,6,6,4),P3 的 r 收 d 得 (4,4,8,4),s 收 z 得 (4,4,9,7),青绿标出,全图算完

课件里的坑

  • [课件留白] 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)。

课后 10 分钟:考点复习

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

必背

  1. Lamport 接收事件:C ← max(本地上一个事件, 消息戳) + 1,max 的另一边是本地上一个事件,不是本进程初值;本地事件与发送事件只做 +1。
  2. 向量时钟接收事件先逐分量 max、再只给自己那一维 +1,两步都不能省;发送时先自增再把整个向量附在消息上。
  3. 向量时钟判因果:逐维 ≤ 且至少一维严格 < 即 happens-before,互不包含即并发;不同事件的 Lamport 戳相等可判并发;戳较小却不能反推因果。
  4. 图里没标字母的黑点默认按内部事件计一格,答卷上先写一句假设。
  5. 不计 P3 那个黑点时:Figure 1 里 P3 从 q 起整体减 1,连带 y = 5、z = 6;Figure 2 只有 r、s 两行变。

完整例题

把 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. 写出 Lamport 接收事件的公式,指出 max 的两个操作数分别是什么。

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

2. Figure 1 里 d 收到 k(时间戳 5),P1 上一个事件是 c = 3。d 是多少?

d = max(3, 5) + 1 = 6。不是 5 + 1 碰巧对,也不是 3 + 1(p.1)。

3. Figure 1 里 c 和 p 的 Lamport 戳都是 3,说明什么?

两者并发、毫无因果关系。不同事件的戳相等可以推出并发,因为有因果就一定严格增大;但戳有大小也不能反推因果(p.1)。

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

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

5. 发送事件附在消息上的向量,是自增之前还是之后的?

之后。先给自己那一维加 1,再把整个向量附上;先发再加会让接收方少算一格(p.2)。

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. Figure 2 里 a = (1, 0, 0, 0) 与 s = (4, 4, 9, 7) 是什么关系?

a → s。每一维都 ≤ 且有严格小于,图里也确实有 a → n → … → r → s 这条因果链(p.3)。

8. Figure 2 里 r 收到 d 的 (4, 4, 1, 0),本地上一个是黑点 (1, 1, 7, 4)。r 是多少?

逐分量 max 得 (4, 4, 7, 4),P3 那一维加 1 得 (4, 4, 8, 4)。第 1、2 维走消息值,第 3、4 维走本地值(p.3)。

9. 不计 P3 那个黑点,Figure 1 会变哪些值?

P3 从 q 开始整体减 1:q = 4 … u = 8。连带 P4 的 y = max(3, 4) + 1 = 5,z = 6。P1、P2 不受影响(p.1、p.2)。

10. 不计 P3 那个黑点,Figure 2 为什么只有两行变?

只有 r = (4, 4, 7, 4) 和 s = (4, 4, 8, 7) 变。q 之后到 r 之间没有任何跨进程消息发出,所以变化传不到别的进程(p.3)。

下一步

两张图各重算一遍,不看答案——这是这门课唯一能靠熟练度稳拿分的题型,错也只错在机械步骤上,盯住「本地上一个事件」和「先 max 再 +1」两处,练三遍就不会再错。再把「图里出现无标签事件先在答卷上写一句假设」写进自己的答题模板。然后接着做 T01b 的选择题和广播判定题。

下一讲 →
T01b T01b Tutorial 1(下):四条性质,练习可靠广播判定

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