← COMP5567 全部讲次
L03b-2 · 第 2 周

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′ 当且仅当满足以下之一:

  1. 某个节点先 CO-broadcast m,然后 CO-broadcast m′。这一条就是 FIFO。
  2. 某个节点先 CO-deliver m,然后 CO-broadcast m′。这是「回复」关系。
  3. 存在 m″ 使得 m → m″ 且 m″ → m′。这是传递性。

FIFO 只有规则 1,因果序有 1、2、3,所以因果序蕴含 FIFO 序。多出来的能力全在规则 2:它把 pj 收到的东西和 pj 之后发的东西串起来,跨越了发送方。

一步一步看

目标:看「回复」先于原帖到达时,因果序怎样把它扣到原帖交付之后。

课件的例子是四个节点。

  1. p₁ 广播 m₁₁;p₄ 先广播 m₄₁。

  2. p₄ 交付了 m₁₁,然后广播 m₄₂。按规则 2,m₁₁ → m₄₂。

  3. m₄₂ 先到了 p₃,发往 p₃ 的 m₁₁ 还在路上。

  4. p₃ 已经在 URB 层拿到 m₄₂,FIFO 也放行(p₄ 的上一条 m₄₁ 已交付),但 m₁₁ 还没交付,因果序不许交付 m₄₂,扣下。

  5. m₁₁ 到达并交付后,p₃ 才放出 m₄₂。

    回复先于原帖到达的时空图:四条时间线。p₁ 广播 m₁₁;p₄ 广播 m₄₁、交付 m₁₁、再广播 m₄₂。m₄₂ 先到 p₃,被标出的空心点写着收到 m₄₂、扣下;发往 p₃ 的 m₁₁ 很慢,交付之后,标出的 m₄₂ 才被放出

这一例把三层摊开了:同一条消息可以 URB 层已交付、FIFO 层已放行,却仍被因果层扣下。被扣的消息不丢,只是推迟。

怎么判断

判断 m 和 m′ 有没有因果先后,沿三条规则找链:

  1. 是不是同一个节点先后发的?是,就 m → m′。
  2. m′ 的发送者在发 m′ 之前,是否交付过 m?是,就 m → m′。
  3. 都不是,能不能找到中间消息 m″ 把两段接起来?能,就 m → m′。
  4. 三条都推不出,两个方向也都推不出,就是并发。

常见误解

以为扣下就是丢弃

被扣的消息进缓冲区,前提凑齐后照样交付。正因为不丢,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。

  1. 画因果图:只有一条边 m1 → m2(规则 2)。m3 孤立,与两者都并发。
  2. 没有约束时 3 条消息有 6 种排法。
  3. 因果序只要求 m1 在 m2 前,m3 可以插在三个位置中的任一个。
  4. 剩下 3 种:
m3 插在哪 交付顺序
最前 m3 m1 m2
中间 m1 m3 m2
最后 m1 m2 m3
  1. 用户 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。

  1. p₁ 广播并交付 m₁,p₂ 广播并交付 m₂,两条的 past 都是全 0。

    因果广播向量第 0 步:p₁ 广播并交付 m₁、p₂ 广播并交付 m₂,这四个事件被标出。右栏 delivered 依次是 (1,0,0)、(0,1,0)、(0,0,0)

  2. p₃ 先后交付 m₁、m₂,再广播 m₃,抄下 m₃.past = (1,1,0)。

    因果广播向量第 1 步:m₁ 和 m₂ 两条箭头落到 p₃,p₃ 先后交付后广播 m₃,被标出。右栏 p₃ 的 (1,1,0) 被标出,注明它就是 m₃.past

  3. m₃ 先到 p₁ 和 p₂。p₁ 的 (1,0,0) 第 2 位 0 < 1,缺 p₂ 的那条;p₂ 的 (0,1,0) 第 1 位 0 < 1,缺 p₁ 的那条。两边都扣下。p₃ 自己的 m₃ 不用等,直接交付。

    因果广播向量第 2 步:两条 m₃ 箭头从 p₃ 飞到 p₁ 和 p₂,落点都是空心圆,标着 m₃ 扣下。右栏标出 p₁ 缺第 2 位、p₂ 缺第 1 位,p₃ 为 (1,1,1)

  4. 缺的那条到了:p₁ 交付 m₂、p₂ 交付 m₁,都变成 (1,1,0),条件满足,回扫放出 m₃,三个节点终值都是 (1,1,1)。

    因果广播向量第 3 步:m₂ 箭头落到 p₁、m₁ 箭头落到 p₂,两边先交付缺的那条,再放出 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)。

  1. p₃ 先交付 m₄₁,delivered₃ = (0,0,0,1)。

  2. m₄₂ 到达,第 8 行判断:第 1 位 0 < 1,不满足,走第 17 行进缓冲。

  3. m₁₁ 到达,满足,第 9–10 行交付,delivered₃ = (1,0,0,1)。

  4. 第 12 行回扫:m₄₂ 四位全部满足,放出,delivered₃ = (1,0,0,2)。

    p₃ 的时间线和两次逐分量比对:p₃ 先交付 m₄₁ 得 (0,0,0,1),此时 m₄₂ 到达,比对发现第 1 位 0 小于 m₄₂.past 的 1,条件不满足,m₄₂ 进缓冲;等交付 m₁₁ 后 delivered 变成 (1,0,0,1),再比对四位全部大于等于,条件满足,放出 m₄₂ 得 (1,0,0,2)

怎么判断

第 6 行会不会死锁?按两步想:

  1. 自己广播的 m,m.past 就是广播那一刻自己的 delivered。
  2. 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,看有因果关系的两对各在哪一位变大,并发那一对又是什么样。

用课件四节点题的三对消息核一遍。

  1. m₄₁ → m₄₂:同一节点 p₄ 先后广播,past 第 4 位从 0 到 1。

  2. m₁₁ → m₄₂:p₄ 交付 m₁₁ 后广播,第 1 位从 0 到 1。

  3. m₁₁ 与 m₄₁:并发,past 都是全 0。

    正确性性质的三行表格:m₄₁ 到 m₄₂ 来自同一节点先后广播,past 从 (0,0,0,0) 到 (1,0,0,1),被标出的差别是第 4 位加 1;m₁₁ 到 m₄₂ 来自交付后再广播,第 1 位加 1;m₁₁ 和 m₄₁ 并发,past 相等

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 的广播端和接收端代码各写一遍。然后做课件例题,重点是逐事件推向量。最后回查两个最容易错的地方:把交付条件里的 ≥ 记成 =、把正确性性质反过来用。

必背

  1. m → m′ 三条规则:同一节点先后广播、交付后再广播、传递性;规则 2 正是 FIFO 做不到的那一条
  2. 因果序蕴含 FIFO 序,反之不成立:FIFO 管不了跨发送方的因果链
  3. 交付条件 DC_i(m):∀k: delivered_i[k] ≥ m.past[k],用 ≥ 不用 =;delivered_i 是会增长的节点状态,m.past 是广播那一刻抄下的快照
  4. 一条消息可以已经 URB-deliver、满足 FIFO,但仍然被因果序禁止 CO-deliver
  5. 自己广播的消息永远满足 DC,所以 wait until done_i 不会死锁
  6. 正确性性质 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 吗?

四条时间线 p1 到 p4:p1 广播红色 m11 发往其余节点;p4 先广播蓝色 m41,收到 m11 后再广播黄色 m42;p3 上先用黑点标出 m42 到达(虚线箭头),m11 较晚到达处再标一个黑点,一条点划线从 m42 到达点弧向后方,表示 m42 被推迟交付
图片来源:COMP5567 Lecture_3-Distributed-Broadcast.pdf, p.35
提示

p4 广播 m42 之前交付过什么?套规则 2。

解答
  1. p4 交付 m11 后才广播 m42,按规则 2,m11 → m42。
  2. p3 还没交付 m11,因果前提不齐,不能 CO-deliver m42,只能放进缓冲区。
  3. 同一条消息可以 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 的位置。

三条时间线 p1、p2、p3:p1 广播红色 m1,p2 广播蓝色 m2,两条都先到达 p3;p3 随后广播黄色 m3,m3 到达 p1 时早于蓝色 m2,到达 p2 时早于红色 m1
图片来源:COMP5567 Lecture_3-Distributed-Broadcast.pdf, p.36
提示

先写 m3 依赖哪两条消息,再看每个节点缺哪一条。

解答
  1. m1 → m3、m2 → m3,都来自规则 2:p3 交付了 1 条 p1 的消息和 1 条 p2 的消息后才广播 m3。
  2. p1:m3 先到,缺 m2,缓存;交付 m2 之后再交付 m3。
  3. p2:m3 先到,缺 m1,缓存;交付 m1 之后再交付 m3。
  4. p3:m3 是自己发的,两个前提早已交付,直接交付,不用等。

例 4(课件 p.38–39):同一场景配上向量,填出问号处的 delivered₂

题面:沿用例 3,向量按 (p1, p2, p3) 排列。写出 m3.past,以及 m3 到达 p2 那一刻的 delivered₂,并判断此刻能否交付。

提示

m3.past 抄自 p3 广播那一刻的 delivered₃;问号处是 p2 交付完自己的 m2 之后的状态。

解答
  1. m1.past = (0,0,0),m2.past = (0,0,0)。p3 广播 m3 前已交付 m1、m2,所以 m3.past = (1,1,0)。
  2. p2 广播 m2 并交付自己这条后,delivered₂ = (0,1,0),问号处就是它。
  3. 比对 (0,1,0) 和 (1,1,0):第 1 位 0 < 1,DC₂(m3) 不成立,m3 进缓冲。p2 交付 m1 后变成 (1,1,0),条件满足,交付 m3 得 (1,1,1)。
  4. 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)。
  5. 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′。写出每个事件后的向量。

三条时间线 p1、p2、p3,左侧各写初值向量 0,0,0:p1 广播红色 m1;p2 广播蓝色 m2;p3 收到 m1 后广播黄色 m3;p2 收到 m3 时还没收到 m1,用黄色虚线弧表示推迟交付;p1 依次收到 m3、m2 后再广播第二条红色消息 m1′;p1 上用黑点标出各事件
图片来源:COMP5567 Lecture_3-Distributed-Broadcast.pdf, p.40
提示

先把四条消息的 past 定下来,再沿每条时间线从左往右推。m1′.past 是广播之前的快照。

解答

先定 past:m1.past = (0,0,0),m2.past = (0,0,0),m3.past = (1,0,0),m1′.past = (1,1,1)。

  1. p1:交付 m1 得 (1,0,0);交付 m3 得 (1,0,1),不用缓存;交付 m2 得 (1,1,1);广播 m1′,交付后得 (2,1,1)。
  2. p2:交付 m2 得 (0,1,0);m3 到达,第 1 位 0 < 1,缓存;交付 m1 得 (1,1,0);放出 m3 得 (1,1,1);交付 m1′ 得 (2,1,1)。
  3. 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。画因果依赖图,列出所有可能的交付顺序。

提示

只有一条因果边;并发的那条可以插在任意位置。

解答
  1. 因果图只有一条边 m1 → m2(规则 2)。m3 与 m1、m2 都并发。
  2. 因果序下合法的顺序有 3 种:m3 m1 m2、m1 m3 m2、m1 m2 m3。各节点可以选不同的一种。
  3. 用向量写: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。逐步解法见下方完整例题。

四条时间线 p1 到 p4:p1 广播红色 m11;p4 先广播蓝色 m41,收到 m11 后再广播黄色 m42;p3 上黑点标出 m42 先到达(虚线箭头),之后 m11 到达处再一个黑点,点划线弧表示 m42 被推迟到 m11 之后交付
图片来源:COMP5567 Lecture_3-Distributed-Broadcast.pdf, p.56
提示

关键是 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(看发送方在广播那一刻交付过什么):

  1. m11.past = (0,0,0,0):p1 开局就广播,此前什么都没交付。
  2. m41.past = (0,0,0,0):p4 的第一条,同理。
  3. 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)。

  1. m31 到达,比对 (0,1,0,0):第 2 位 0 < 1,不满足,进缓冲。
  2. m21 到达,比对 (0,0,0,0):满足,交付,delivered = (0,1,0,0)。
  3. 回扫缓冲区:(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。

下一讲 →
L03b-3 L03b-3 交付顺序(三):全序广播,所有人排成同一个序列

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