L03b-2 交付顺序(二):因果序,回信不能先于原信
m → m′ 的三条规则,用 delivered 和 past 两个向量判断一条消息能不能交付,以及 CO-URB 的代码骨架和正确性性质。
一句话版
因果序要求:如果一条消息的发送者在发它之前已经看过另一条,那么所有节点都得先交付那一条。判断方法是比两个向量,缺哪一位就等哪个人的消息。
读之前最好先懂上一页 L03b-1 的 FIFO 实现,这一页的代码骨架和它一样。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| m → m′ | m happens causally before m′,因果先于 | 回信不能先于原信 |
| 并发(concurrent) | 互相没有因果先后,记作 m ∥ m′ | 因果序对它们不作约束 |
| CO-URB | Causal Order URB,带因果序的一致可靠广播 | URB 的四条性质再加因果序 |
| delivered_i | 节点 i 的交付计数向量 | 我已交付每个人几条 |
| m.past | 消息带着的向量 | 发送者广播那一刻交付过每个人几条 |
| DC_i(m) | Delivery Condition,交付条件 | 节点 i 判断 m 能否交付的规则 |
一个类比:传达室扣住回信等原信
传达室上一页只管同一个寄信人的先后。现在多一条:王五看过张三的信才写了回信,那么无论谁的信箱,都得先放张三那封,再放王五的回信。
传达室怎么知道王五看过什么?王五寄信时在信封上抄一张清单:「我已经读过张三 1 封、李四 0 封」。传达室拿这张清单和收信人已经放进去的信比,缺了就扣住。
类比在哪里失效:
- 清单只记条数不记是哪封信。能这么做,是因为同一个人的信本来就按序放,条数够了就说明那几封都在。
- 两封互不相干的信谁先谁后,传达室在因果序下完全不管,各个信箱可以放成不同的顺序。
从零讲起
1. 因果先于:三条规则
它解决什么问题
FIFO 只管同一发送方。聊天里最常见的错乱恰恰跨了发送方:原帖是 A 发的,回复是 B 发的,有人先看到回复。因果序要把「看过再回」这种先后也管住。
直觉
M 是一次执行中所有被 CO-broadcast 的消息。m → m′ 当且仅当满足以下之一:
- 某个节点先 CO-broadcast m,然后 CO-broadcast m′。这一条就是 FIFO。
- 某个节点先 CO-deliver m,然后 CO-broadcast m′。这是「回复」关系。
- 存在 m″ 使得 m → m″ 且 m″ → m′。这是传递性。
FIFO 只有规则 1,因果序有 1、2、3,所以因果序蕴含 FIFO 序。多出来的能力全在规则 2:它把 pj 收到的东西和 pj 之后发的东西串起来,跨越了发送方。
一步一步看
目标:看「回复」先于原帖到达时,因果序怎样把它扣到原帖交付之后。
课件的例子是四个节点。
-
p₁ 广播 m₁₁;p₄ 先广播 m₄₁。
-
p₄ 交付了 m₁₁,然后广播 m₄₂。按规则 2,m₁₁ → m₄₂。
-
m₄₂ 先到了 p₃,发往 p₃ 的 m₁₁ 还在路上。
-
p₃ 已经在 URB 层拿到 m₄₂,FIFO 也放行(p₄ 的上一条 m₄₁ 已交付),但 m₁₁ 还没交付,因果序不许交付 m₄₂,扣下。
-
m₁₁ 到达并交付后,p₃ 才放出 m₄₂。
这一例把三层摊开了:同一条消息可以 URB 层已交付、FIFO 层已放行,却仍被因果层扣下。被扣的消息不丢,只是推迟。
怎么判断
判断 m 和 m′ 有没有因果先后,沿三条规则找链:
- 是不是同一个节点先后发的?是,就 m → m′。
- m′ 的发送者在发 m′ 之前,是否交付过 m?是,就 m → m′。
- 都不是,能不能找到中间消息 m″ 把两段接起来?能,就 m → m′。
- 三条都推不出,两个方向也都推不出,就是并发。
常见误解
以为扣下就是丢弃
被扣的消息进缓冲区,前提凑齐后照样交付。正因为不丢,CO-URB 不会破坏 URB 的 Uniformity。
以为 m₄₂ 已经满足 FIFO,就可以交付
FIFO 只检查 p₄ 自己的两条有没有颠倒。m₁₁ 来自 p₁,FIFO 看不到这层依赖,要靠因果层判断。
试一下
上例里 m₄₁ 和 m₄₂ 是什么关系?来自哪条规则?
m₄₁ → m₄₂,来自规则 1:同一节点 p₄ 先后广播。
2. 并发:因果序不管的那一部分
它解决什么问题
课件列完三条规则后留了一个填空:如果没有因果关系呢?答案决定了因果序能管多少、管不了多少。
直觉
没有因果关系的两条消息叫并发。因果序对它们的相对交付顺序不作任何约束,任何节点可以按任意顺序交付,不同节点也可以顺序不同。
这就是因果序弱于全序的根本原因。它只保证每个人看到的顺序「不违背因果」,不保证所有人看到同一个顺序。
一步一步看
目标:数一数因果序还允许几种交付顺序,看清它为什么保证不了所有人看到同一个顺序。
去中心化聊天:A 发 m1;B 收到 m1 后回复 m2;C 没看到 m1、m2 就发了 m3。
- 画因果图:只有一条边 m1 → m2(规则 2)。m3 孤立,与两者都并发。
- 没有约束时 3 条消息有 6 种排法。
- 因果序只要求 m1 在 m2 前,m3 可以插在三个位置中的任一个。
- 剩下 3 种:
| m3 插在哪 | 交付顺序 |
|---|---|
| 最前 | m3 m1 m2 |
| 中间 | m1 m3 m2 |
| 最后 | m1 m2 m3 |
- 用户 A 看第一种、用户 B 看第三种,两者都合法。要所有人一样,得上全序。
怎么判断
列合法顺序时,先画因果图,再把并发的消息当作「可以随便插」,只保证每条因果边的箭头方向在序列里成立。
常见误解
以为因果序保证大家看到的一样
它不保证。并发消息在不同节点可以排成不同顺序,要全体一致得用全序广播。
以为「并发」要求两条消息在同一时刻发出
这里的并发只说没有因果先后,不要求物理时刻相同。m3 可能比 m1 晚发很久,只要 C 没看到 m1,就是并发。
试一下
如果 C 是在看到 m2 之后才发 m3,合法顺序还剩几种?
m1 → m2 → m3,一条链,只剩 1 种:m1 m2 m3。
3. 向量法:delivered 与 past
它解决什么问题
节点怎么自己判断因果前提凑齐没有?它看不到别人脑子里「看过什么」,只能靠消息随身带一份记录。
从哪来(补充)
这套向量就是分布式系统里的向量时钟(vector clock),由 Colin Fidge 和 Friedemann Mattern 在 1988 年各自独立提出,课件没提这个名字。出处:Vector clock(Wikipedia)。
直觉
两个 n 维向量,初值全 0:
- 节点视图
delivered_i[k]:节点 pi 已经 CO-deliver 了多少条由 pk 广播的消息。它是节点状态,会随时间增长。 - 消息视图
m.past[k]:有多少条由 pk 广播的消息因果先于 m。它是消息标签,广播那一刻m.past ← delivered_i抄下来,之后永不改变。
交付条件 DC_i(m):∀k: delivered_i[k] ≥ m.past[k]。含义是 pi 已经交付了足够多的、因果先于 m 的消息。
只记条数就够,是因为规则 1 已经让同一发送方的消息按序交付:pk 的消息交付了 3 条,那就一定是 pk 的前 3 条。
一步一步看
目标:跟着三个节点的 delivered 走一遍,看 m₃ 在每个节点那里要不要等、等的是哪一条。
三个节点,向量按 (p₁, p₂, p₃) 排列。右栏是每个节点此刻的 delivered。
-
p₁ 广播并交付 m₁,p₂ 广播并交付 m₂,两条的 past 都是全 0。
-
p₃ 先后交付 m₁、m₂,再广播 m₃,抄下 m₃.past = (1,1,0)。
-
m₃ 先到 p₁ 和 p₂。p₁ 的 (1,0,0) 第 2 位 0 < 1,缺 p₂ 的那条;p₂ 的 (0,1,0) 第 1 位 0 < 1,缺 p₁ 的那条。两边都扣下。p₃ 自己的 m₃ 不用等,直接交付。
-
缺的那条到了:p₁ 交付 m₂、p₂ 交付 m₁,都变成 (1,1,0),条件满足,回扫放出 m₃,三个节点终值都是 (1,1,1)。
一句话记法:m₃ 在 p₁ 那里等 m₂,在 p₂ 那里等 m₁,在 p₃ 那里不用等。
怎么算
DC_i(m) = 对每一位 k,delivered_i[k] ≥ m.past[k] 都成立。
意思是:m 依赖的每个人的消息,我都至少交付了那么多条。哪一位不够,就是缺那个人的消息。
为什么是 ≥ 不是 =:pi 可能已经交付了一些和 m 并发的消息,它们会让 delivered_i 某些分量超出 m.past。并发消息不该构成阻塞,写成等号会把它们误判成必须等。
常见误解
把 m.past 当成要计算的东西
m.past 不是算出来的,是抄来的:广播那一刻一次赋值。做题时先看发送者在广播那一刻交付过什么。
拿不同下标比较
交付条件永远是同一位比同一位。看到 delivered[a] 和 m.past[b] 里 a 不等于 b,就是笔误。
试一下
p₁ 的 delivered = (2,0,1),收到 m,m.past = (1,0,1)。能交付吗?
能。逐位 2 ≥ 1、0 ≥ 0、1 ≥ 1 都成立。第 1 位超出的那一条是与 m 并发的消息,不阻塞。
4. CO-URB 代码:和 FIFO 同一个骨架
它解决什么问题
把向量法写成可以运行的协议,并说清 CO-broadcast 为什么要等、会不会卡死。
直觉
广播端:
1 当 pi 调用 CO-broadcast(m):
2 done_i ← false
3 m.past[1..n] ← delivered_i[1..n]
4 m.sender ← i
5 URB-broadcast(m)
6 wait until (done_i = true)
接收端:
7 当 pi URB-deliver 了消息 m:
8 if DC_i(m) then
9 CO-deliver(m)
10 j ← m.sender; delivered_i[j] ← delivered_i[j] + 1
11 if j = i then done_i ← true
12 while ∃ m′ ∈ msg_set_i : DC_i(m′) do
13 CO-deliver(m′)
14 j ← m′.sender; delivered_i[j] ← delivered_i[j] + 1
15 msg_set_i ← msg_set_i \ {m′}
16 else
17 msg_set_i ← msg_set_i ∪ {m}
第 3 行是整个算法的心脏:一次赋值就把「发送者发这条消息之前看过什么」封进了消息里。
结构和 FIFO 完全相同:判断、交付、更新状态、回扫缓冲区,否则入缓冲区。差别只在判断条件从比一个数换成比一个向量。分层也不变,因果层坐在 URB 之上,继承四条可靠性性质。
一步一步看
目标:对着代码行号走一遍 p₃,看 m₄₂ 怎样进缓冲,又在哪一行被放出来。
课件四节点题里唯一会卡住的是 p₃,向量按 (p₁, p₂, p₃, p₄) 排列,m₄₂.past = (1,0,0,1)。
-
p₃ 先交付 m₄₁,delivered₃ = (0,0,0,1)。
-
m₄₂ 到达,第 8 行判断:第 1 位 0 < 1,不满足,走第 17 行进缓冲。
-
m₁₁ 到达,满足,第 9–10 行交付,delivered₃ = (1,0,0,1)。
-
第 12 行回扫:m₄₂ 四位全部满足,放出,delivered₃ = (1,0,0,2)。
怎么判断
第 6 行会不会死锁?按两步想:
- 自己广播的 m,m.past 就是广播那一刻自己的 delivered。
- m 被 URB 交付回自己时,delivered 只可能比那时更大,所以 DC 一定成立,第 11 行一定执行,done_i 一定翻成真。
结论:不会死锁。这是一道常见的口头题。
常见误解
以为回扫只要检查一次
放出一条消息会让 delivered 增长,可能让缓冲区里另一条也满足条件,连锁放出好几条,所以是 while 循环。
以为 CO-broadcast 发完就返回
它是阻塞的,要等到自己交付了这条消息才返回。
试一下
如果去掉第 3 行,m.past 一直是全 0,协议会怎样?
每条消息的交付条件都天然满足,什么都不会被扣下,协议退化成普通 URB,因果序失效。
5. 正确性:因果先于推出向量有序
它解决什么问题
要证明这套向量真的抓住了因果关系:只要 m → m′,m′ 的 past 就一定「覆盖」m 的 past,接收方按 past 判断就不会放错。
直觉
要证的性质:若 m → m′,则 ∀k: m.past[k] ≤ m′.past[k],且 ∃k: m.past[k] < m′.past[k]。
两种情况。Case 1,同一节点 pi 先后广播:pi 广播 m 后一定会自己交付 m,第 i 位加 1,再广播 m′ 时抄进去,所以 m′.past[i] = m.past[i] + 1。Case 2,pj 交付了 pi 的 m 再广播 m′:交付时 delivered_j[i] 加了 1,抄进 m′.past,同样多 1。规则 3 的传递性由两种情况串联得到。
一步一步看
目标:用三对消息核对 past,看有因果关系的两对各在哪一位变大,并发那一对又是什么样。
用课件四节点题的三对消息核一遍。
-
m₄₁ → m₄₂:同一节点 p₄ 先后广播,past 第 4 位从 0 到 1。
-
m₁₁ → m₄₂:p₄ 交付 m₁₁ 后广播,第 1 位从 0 到 1。
-
m₁₁ 与 m₄₁:并发,past 都是全 0。
m₄₂.past 的两个非零分量正好各对应一条规则:第 4 位来自规则 1,第 1 位来自规则 2。
怎么判断
性质是单向的:因果先于 ⟹ 向量有序。课件没证反方向,答题时别把「past 有序」当成「有因果」的证据。第三行就是例子:m₁₁ 和 m₄₁ 的 past 相等,可两者是并发的。
常见误解
把性质反过来用
past 可比不代表有因果关系。课件聊天题里 m3.past 和 m1.past 都是全 0,两者却是并发的。
试一下
三节点题里,m1′ 是 p₁ 在交付了 m1、m2、m3 之后广播的。m1′.past 是多少?和 m1.past 比,哪一位严格大?
m1′.past = (1,1,1),m1.past = (0,0,0),三位都严格大。注意不是 (2,1,1):past 是广播之前的快照,m1′ 自己还没交付。
把它们串起来
上一页的 FIFO 只看同一个发送方,回复和原话来自不同的人时它无能为力。因果序把「看过再回」写成规则 2,补上了这一块,同时规则 1 保证它不比 FIFO 弱。
实现上,向量法把「看过什么」变成了数:发送者在消息上抄下自己的交付计数,接收者逐位比较,缺哪一位就等哪个人的消息。代码层面它和 FIFO 是同一个协议换了判断条件,因果层同样坐在 URB 之上。
正确性性质保证这套比较不会放错:因果先于一定推出 past 向量有序。反方向课件没证,不能当结论用。
因果序仍然不管并发消息。两条互不相干的消息,各节点可以排成不同顺序。要让全体看到同一顺序,得看下一页的全序广播。
课件里的坑
- [课件有误] p.37 把 causal 拼成了 casual,一字之差意思完全不同(casual 是随意的),只是拼写,不影响理解。
- [课件有误] p.39 有四处下标印错,部分被示例数值掩盖,照抄却会答错:
delivered₂[3] < m3.past[2]应为delivered₂[1] < m3.past[1];delivered₂ > m1.past应为≥;delivered₃[1] = m1.past[3]应为m1.past[1];delivered₃[2] = m2.past[3]应为m2.past[2]。p1 那一行是对的。 - [课件有误] p.41 的回扫循环写成
while ∃ m'∈ msg_set_i: if DC_i(m') do,while和if混在一个头里语法不成立,应为while ∃ m′ ∈ msg_set_i : DC_i(m′) do。 - [课件留白] p.34 的填空「If no causal relationship?」课件没给答案:并发,因果序不作约束。
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写因果序的三条规则和交付条件 DC_i(m),再把 CO-URB 的广播端和接收端代码各写一遍。然后做课件例题,重点是逐事件推向量。最后回查两个最容易错的地方:把交付条件里的 ≥ 记成 =、把正确性性质反过来用。
必背
- m → m′ 三条规则:同一节点先后广播、交付后再广播、传递性;规则 2 正是 FIFO 做不到的那一条
- 因果序蕴含 FIFO 序,反之不成立:FIFO 管不了跨发送方的因果链
- 交付条件 DC_i(m):∀k: delivered_i[k] ≥ m.past[k],用 ≥ 不用 =;delivered_i 是会增长的节点状态,m.past 是广播那一刻抄下的快照
- 一条消息可以已经 URB-deliver、满足 FIFO,但仍然被因果序禁止 CO-deliver
- 自己广播的消息永远满足 DC,所以 wait until done_i 不会死锁
- 正确性性质 m → m′ ⟹ ∀k: m.past[k] ≤ m′.past[k] 且至少一位严格小于,是单向的:past 可比不代表有因果关系
课件例题
例 1(课件 p.34):两条消息没有因果关系时怎么办
题面:课件在列完三条规则后留了一个填空:「If no causal relationship? ____」。
提示
想想因果序对没有箭头相连的两条消息还能要求什么。
解答
两条消息并发(concurrent),因果序对它们的相对交付顺序不作任何约束,各节点可以排成不同顺序。
例 2(课件 p.35,CO-URB Example 1):p3 为什么不能交付 m42
题面:p1 广播 m11;p4 先广播 m41,再交付 m11,然后广播 m42。p3 已经 URB 交付、也 FIFO 交付了 m42,但还没交付 m11。p3 能 CO-deliver m42 吗?
提示
p4 广播 m42 之前交付过什么?套规则 2。
解答
- p4 交付 m11 后才广播 m42,按规则 2,m11 → m42。
- p3 还没交付 m11,因果前提不齐,不能 CO-deliver m42,只能放进缓冲区。
- 同一条消息可以 URB 层已交付、FIFO 层已放行,却仍被因果层扣下。等 m11 交付后,m42 照样放出,不是丢弃。
例 3(课件 p.36,Exercise 3):三个节点各在哪里缓存、在哪里交付
题面:p1 广播 m1,p2 广播 m2。p3 先后交付 m1、m2,然后广播 m3。m3 到达 p1 时 p1 还没交付 m2,到达 p2 时 p2 还没交付 m1。标出每个节点缓存和交付 m3 的位置。
提示
先写 m3 依赖哪两条消息,再看每个节点缺哪一条。
解答
- m1 → m3、m2 → m3,都来自规则 2:p3 交付了 1 条 p1 的消息和 1 条 p2 的消息后才广播 m3。
- p1:m3 先到,缺 m2,缓存;交付 m2 之后再交付 m3。
- p2:m3 先到,缺 m1,缓存;交付 m1 之后再交付 m3。
- p3:m3 是自己发的,两个前提早已交付,直接交付,不用等。
例 4(课件 p.38–39):同一场景配上向量,填出问号处的 delivered₂
题面:沿用例 3,向量按 (p1, p2, p3) 排列。写出 m3.past,以及 m3 到达 p2 那一刻的 delivered₂,并判断此刻能否交付。
提示
m3.past 抄自 p3 广播那一刻的 delivered₃;问号处是 p2 交付完自己的 m2 之后的状态。
解答
- m1.past = (0,0,0),m2.past = (0,0,0)。p3 广播 m3 前已交付 m1、m2,所以 m3.past = (1,1,0)。
- p2 广播 m2 并交付自己这条后,delivered₂ = (0,1,0),问号处就是它。
- 比对 (0,1,0) 和 (1,1,0):第 1 位 0 < 1,DC₂(m3) 不成立,m3 进缓冲。p2 交付 m1 后变成 (1,1,0),条件满足,交付 m3 得 (1,1,1)。
- p1 对称:交付 m1 得 (1,0,0),m3 到达时第 2 位不够,缓存;交付 m2 得 (1,1,0) 后交付 m3。p3 依次 (1,0,0)、(1,1,0),广播 m3,交付后 (1,1,1)。三个节点终值都是 (1,1,1)。
- p.39 是这三条时间线的逐事件标注版,p2、p3 两行有四处下标印错,答题时按同下标比较写。
例 5(课件 p.40,Exercise 4):写出每个事件的 delivered 向量
题面:三个节点初值都是 (0,0,0)。p1 广播 m1 并交付;p3 交付 m1 后广播 m3;p2 广播 m2 并交付,随后收到 m3 时还没交付 m1;p1 依次交付 m3、m2 后广播 m1′。写出每个事件后的向量。
提示
先把四条消息的 past 定下来,再沿每条时间线从左往右推。m1′.past 是广播之前的快照。
解答
先定 past:m1.past = (0,0,0),m2.past = (0,0,0),m3.past = (1,0,0),m1′.past = (1,1,1)。
- p1:交付 m1 得 (1,0,0);交付 m3 得 (1,0,1),不用缓存;交付 m2 得 (1,1,1);广播 m1′,交付后得 (2,1,1)。
- p2:交付 m2 得 (0,1,0);m3 到达,第 1 位 0 < 1,缓存;交付 m1 得 (1,1,0);放出 m3 得 (1,1,1);交付 m1′ 得 (2,1,1)。
- p3:交付 m1 得 (1,0,0);广播 m3;交付 m2 得 (1,1,0);交付 m3 得 (1,1,1);交付 m1′ 得 (2,1,1)。
三个节点终值都是 (2,1,1):p1 发了 2 条,p2、p3 各 1 条。终值不一致说明中间算错了。
例 6(课件 p.55,Exercise-5):去中心化聊天,画因果图并列出所有交付顺序
题面:A 发 m1;B 收到 m1 后回复 m2;C 没看到 m1 和 m2 就发了 m3。画因果依赖图,列出所有可能的交付顺序。
提示
只有一条因果边;并发的那条可以插在任意位置。
解答
- 因果图只有一条边 m1 → m2(规则 2)。m3 与 m1、m2 都并发。
- 因果序下合法的顺序有 3 种:m3 m1 m2、m1 m3 m2、m1 m2 m3。各节点可以选不同的一种。
- 用向量写:m1.past = (0,0,0),m2.past = (1,0,0),m3.past = (0,0,0)。m3.past 和 m1.past 相同,两者却没有因果关系,正好说明正确性性质只能单向用。
例 7(课件 p.56,Exercise-6):四节点图,写出每个事件的 delivered 和 m.past
题面:p1 广播 m11;p4 先后广播 m41、m42;p3 先收到 m42、后收到 m11。逐步解法见下方完整例题。
提示
关键是 m42.past:p4 广播 m42 之前交付过谁的几条?
解答
m11.past = (0,0,0,0),m41.past = (0,0,0,0),m42.past = (1,0,0,1)。只有 p3 发生缓存,四个节点终值都是 (1,0,0,2)。完整推演见完整例题。
完整例题
拿课件那道四节点的向量题(p.56)走一遍。场景是 p1 广播 m11,p4 先后广播 m41 和 m42,向量按 (p1, p2, p3, p4) 排列,全体初值 (0,0,0,0)。要求写出每个事件的 delivered 和每条消息的 m.past。
第一步,先定三条消息的 past(看发送方在广播那一刻交付过什么):
- m11.past = (0,0,0,0):p1 开局就广播,此前什么都没交付。
- m41.past = (0,0,0,0):p4 的第一条,同理。
- m42.past = (1,0,0,1):p4 在广播它之前已经交付了 m11(p1 的 1 条)和自己的 m41(p4 的 1 条)。
第二步,沿每条时间线从左到右推 delivered。以 p4 为例:起始 (0,0,0,0) → 广播 m41(m41.past ← (0,0,0,0))→ 交付自己的 m41 得 (0,0,0,1) → 交付 m11 得 (1,0,0,1) → 广播 m42(m42.past ← (1,0,0,1))→ 交付自己的 m42 得 (1,0,0,2)。
第三步,找出唯一会卡住的那个节点。是 p3:先交付 m41 得 (0,0,0,1),m42 到达时第 1 位 0 < 1,进缓冲;交付 m11 后变成 (1,0,0,1),四位全部满足,放出 m42 得 (1,0,0,2)。第 4 节的图画的就是这两次比对。
补全 p1、p2:p1 广播 m11 后交付自己这条得 (1,0,0,0),交付 m41 得 (1,0,0,1),交付 m42 得 (1,0,0,2)。p2 先交付 m41 得 (0,0,0,1),再交付 m11 得 (1,0,0,1),最后交付 m42 得 (1,0,0,2)。单纯收到、尚未交付时不递增 delivered。
第四步,自检。四个节点最终全部收敛到 (1,0,0,2):p1 发了 1 条、p2 和 p3 各发 0 条、p4 发了 2 条。这个不变量能发现漏记,但只核对终值不足以证明每步顺序正确。
再多想一层:m42.past 的两个非零分量各对应一条规则,第 4 位的 1 来自规则 1,第 1 位的 1 来自规则 2。
变式题(先自己做)
变式|自编情境:向量按 (p1, p2, p3, p4) 排列,初值全 0。p2 广播 m21。p3 交付 m21 后广播 m31。p1 先收到 m31、后收到 m21。无崩溃,两条最终都送达。
(1) 写出两条消息的 past。(2) 逐事件推 p1 的 delivered,说明 m31 何时能交付。(3) 每个节点的终值是多少?
提示
past 不含正在广播的这条消息。题目说 p1 先收到 m31,不代表先交付它。
判分点与答案
(1) m21.past = (0,0,0,0)(p2 开局就广播);m31.past = (0,1,0,0)(p3 广播前已交付 m21,那是 p2 的第 1 条)。
(2) p1 起始 delivered = (0,0,0,0)。
- m31 到达,比对 (0,1,0,0):第 2 位 0 < 1,不满足,进缓冲。
- m21 到达,比对 (0,0,0,0):满足,交付,delivered = (0,1,0,0)。
- 回扫缓冲区:(0,1,0,0) ≥ (0,1,0,0),放出 m31,delivered = (0,1,1,0)。
(3) 四个节点最终都是 (0,1,1,0):p2 广播 1 条、p3 广播 1 条、p1 和 p4 各 0 条。
判分点:past 不含自己这条;写出缓存和回扫;写出每一步,不只写终值。
闪卡自测
1. 因果序的三条规则是什么?哪一条是 FIFO 做不到的?
同一节点先后广播、交付后再广播、传递性。规则 2 是 FIFO 做不到的那一条,FIFO 只约束同一发送方。
2. 因果序和 FIFO 序谁蕴含谁?
因果序蕴含 FIFO 序。规则 1 正是 FIFO 的要求;反过来不成立。
3. 一条消息已经 FIFO-deliver 了,为什么还可能不能 CO-deliver?
它可能依赖另一个发送方的消息,而那条还没交付。FIFO 看不到跨发送方的依赖,只能由因果层扣下。
4. 写出交付条件 DC_i(m)。为什么是 ≥ 而不是 =?
∀k: delivered_i[k] ≥ m.past[k]。并发消息会让某些分量超出 m.past,那种超出不该构成阻塞。
5. delivered_i 和 m.past 的区别是什么?后者怎么来的?
delivered_i 是节点状态,随交付增长;m.past 是消息标签,广播那一刻 m.past ← delivered_i 一次赋值,此后不变。
6. wait until done_i 会不会死锁?
不会。自己广播时 past 就是当前的 delivered,自己这条回来时一定满足交付条件。
7. 接收端的回扫为什么必须是循环?
放出一条消息会改变 delivered,可能让缓冲区里另一条也满足条件,连锁放出好几条。
8. 两条消息的 past 向量可比,能推出它们有因果关系吗?
不能。课件只证了「因果 ⟹ 向量有序」这一个方向。聊天题里 m1 和 m3 的 past 都是全 0,两者却是并发的。
下一讲
下一页 L03b-3 讲全序广播:所有节点交付的排列必须一样。它和因果序互不包含,两者都要时叫 CO-TOB。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。