L03a-2 可靠广播(二):先转发再交付,一个十行的 URB 协议
把 URB 协议逐帧跑一遍:为什么先发给自己、为什么先转发后交付、MJ 集合管什么,以及课件四节点图里哪些消息没人交付。
一句话版
URB 只靠一句话实现:先把消息发给自己,收到一条新消息时先转发给所有人、再交付,见过的就不再处理。这一页把这句话一帧一帧跑出来,讲清它为什么够用,以及它不管的那件事。
URB 的定义(任何进程交付 ⟹ 所有正确进程交付)见上一页 L03a-1。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| URB-broadcast | URB 广播 | 应用请求群发;协议只把消息发给自己 |
| URB-deliver | URB 交付 | 协议把消息放行给应用 |
| MJ | message judger,已见消息集合 | 记下「这条见过」,用来去重 |
| 转发 | forward / relay | 收到一条新消息,原样发给其他节点 |
| 非故障节点 | non-faulty node | 课件图里全程没崩的节点,等于正确进程 |
| 伪代码 | pseudocode | 不能直接运行、只写清步骤的算法草稿 |
一个类比:传达室的转抄规矩
还是楼下那间传达室,只是现在每个住户家里都有一间。规矩是:任何一封新信到了你家传达室,先抄一份寄给其他所有住户,再放进你自己的信箱。每封信都登记编号,登记过的就不再处理。
这样一来,只要有人拿到了信,信在他拿到之前就已经寄出去了,他当天搬走也带不走这封信。登记簿保证同一封信不会被反复寄来寄去。
类比在哪里失效:
- 现实里寄出去的信一般按顺序到,网络里两封信谁先到不确定,连寄给自己的两封也一样。
- 住户寄信给自己显得多余,协议里这一步不能省:发送方要和别人走同一条交付路径。
- 抄信要花时间和纸,类比体现不出转发带来的消息条数代价。
从零讲起
1. URB 协议逐行跑一遍
它解决什么问题
上一页的 URB 只是一条要求:任何进程交付了 m,所有正确进程都得交付。要求写出来容易,难的是怎么做到,因为节点随时可能崩。这个协议给出一种做法,全文十来行。
直觉
伪代码如下,pi.MJ 是节点 pi 见过的消息集合。
1 初始化:pi.MJ ← Ø
2 当 pi 调用 URB-broadcast(m):
3 把 m 发给 pi 自己
4 当 pi 收到 m(来自 pj 或自己):
5 if m ∉ pi.MJ then
6 pi.MJ ← pi.MJ ∪ {m}
7 for each k ∈ {1,…,n} \ {i, j} do
8 把 m 发给 pk
9 end for
10 URB-deliver(m)
11 end if
读法是把它分成两个事件。第 2–3 行管「我要广播」:只把消息塞给自己。第 4–11 行管「我收到一条消息」:没见过就记下、转发、交付,见过就什么也不做。
发送方自己的那一份也走第 4 行这条路。所以全网只有一套接收逻辑,发送方和接收方没有区别。
一步一步看
目标:看 p₁ 交付完就崩溃时,m 能否仍被 p₂、p₃ 两个正确进程各交付一次。
三个节点 p₁、p₂、p₃,p₁ 广播 m。每一帧里青绿色是这一步新发生的事,右栏是三个节点此刻的 MJ。
-
p₁ 调用 URB-broadcast(m),按第 3 行只把 m 发给自己。三个 MJ 都是空的。
-
m 回到 p₁。第 5 行判断没见过,第 6 行记进 MJ₁,第 7–8 行转发给 p₂ 和 p₃,最后第 10 行交付。
-
p₁ 交付完立刻崩溃。可是 m 已经在去 p₂、p₃ 的路上了,崩溃收不回它。
-
p₂ 第一次收到 m,记进 MJ₂。第 7 行排除自己和来源 p₁,于是只转发给 p₃,然后交付。
-
p₃ 第一次收到 m(来自 p₁ 那份),记进 MJ₃,转发给 p₂,然后交付。
-
p₂、p₃ 又各自收到对方转来的 m。这次 m 已经在 MJ 里,第 5 行不通过,直接丢掉。
最后 p₂、p₃ 两个正确进程都交付了 m,每个只交付一次。发送方 p₁ 交付完就崩,也没能把 m 带走。
怎么判断
给一个节点收到消息的场景,按伪代码的顺序问三句:
- 这条消息在不在它的 MJ 里?在,就什么也不做,结束。
- 不在:记进 MJ,然后发给谁?除了自己和发来的那个节点,其余所有人。
- 发完之后才交付。
判断协议跑完后谁交付了 m:只要有一个节点走到了第 10 行,它之前一定走过第 8 行,m 已经发往其余所有节点。
常见误解
以为 URB-broadcast 会直接群发
第 3 行只发给自己。群发发生在消息绕回自己、走到第 8 行的时候。这样发送方和接收方走同一条代码路径,Validity 自然成立。
以为第 7 行排除 i 和 j 是正确性所必需
那只是省掉发回给自己和来源的两份,它们本来就有这条消息。去掉这个排除,协议照样正确,只是多发几条。
试一下
四个节点 p₁…p₄,p₂ 第一次收到来自 p₄ 的 m。按第 7 行,p₂ 要把 m 发给谁?
发给 p₁ 和 p₃。i = 2(自己)和 j = 4(来源)被排除,剩下 {1, 3}。
2. 为什么一定要先转发、后交付
它解决什么问题
URB 和 RB 的区别在于:交付完就崩的进程也不能把消息带走。协议里只有一处在管这件事,就是第 8 行排在第 10 行之前。
直觉
节点交付 m 的那一刻,m 已经离开它、飞向所有其他节点了。崩溃可以随时发生,但它发生在交付之后,消息早就送出去了。
反过来想:如果先交付再转发,交付和转发之间有一段空隙。节点恰好在空隙里崩溃,它交付过 m,m 却从来没有离开过它。
一步一步看
目标:看对调成先交付后转发、p₁ 又恰好在两步之间崩溃时,URB 为什么被违反。
把协议改成「先交付后转发」,再跑一次 p₁ 广播 m。
-
p₁ 调用 URB-broadcast(m),m 发给自己。
-
m 回到 p₁,没见过,记进 MJ。
-
改过的协议先交付 m。
-
p₁ 还没来得及执行转发那两行,就崩溃了。p₂、p₃ 从来没见过 m。
-
对照定义:交付过 m 的 p₁ 是故障进程,RB 的前件不成立,RB 没被违反;URB 的前件「任何进程交付」成立,正确的 p₂、p₃ 却没交付,URB 被违反。
怎么判断
看一个广播协议能不能做到 Uniform,找它的交付语句,问:执行到交付时,消息是不是已经发给了所有其他节点?
- 是:交付者崩溃也带不走消息,可以做到 URB。
- 否:交付和发送之间有空隙,只能做到 RB。
页面顶上那句 first send out to itself/others, then URB-deliver,就是这个判断的答案句。
常见误解
把「先转发后交付」当成可以随便调换的实现细节
两步对调,节点可能在交付之后、转发之前崩溃,消息就被带进坟墓,协议直接退化成 RB。这一处先后就是 RB 和 URB 在实现上的全部差别。
试一下
某协议规定:收到新消息后,先转发给一半节点,交付,再转发给另一半。能做到 URB 吗?
不能。交付和第二次转发之间仍有空隙。节点在这里崩溃,后一半节点可能永远收不到;前一半节点如果也都崩了,交付过的消息就没有正确进程知道。
3. MJ 集合:去重,也让转发停下来
它解决什么问题
每个节点都会把新消息转发给其他所有人。没有记录的话,同一条消息会被转来转去,还会被交付好几次。
直觉
MJ 是每个节点各自记下的「见过的消息」集合。只有第一次见到的消息才往下走(记录、转发、交付),见过的一律丢掉。
一个集合管两件事。第一是 No Duplication:每条消息只走一次第 10 行。第二是让转发停下来:每个节点对同一条消息只转发一次,转发总数有上限,全网最终安静下来。
一步一步看
目标:看 MJ 怎样让每个节点只交付一次 m,并让转发停下来。
还是上面三节点的例子,把每个节点收到 m 的每一次列成表。
- p₁ 收到自己发的 m:首次见到,转发、交付。
- p₂ 收到 p₁ 转来的 m:首次见到,转发给 p₃、交付。
- p₃ 收到 p₁ 转来的 m:首次见到,转发给 p₂、交付。
- p₂、p₃ 收到对方转来的 m:已在 MJ 里,丢掉。
| 收到的那一份 | m 在 MJ 里吗 | 做了什么 |
|---|---|---|
| p₁ 收到自己的 m | 不在 | 记录、转发给 p₂ p₃、交付 |
| p₂ 收到 p₁ 的 m | 不在 | 记录、转发给 p₃、交付 |
| p₃ 收到 p₁ 的 m | 不在 | 记录、转发给 p₂、交付 |
| p₂ 收到 p₃ 的 m | 在 | 丢掉 |
| p₃ 收到 p₂ 的 m | 在 | 丢掉 |
如果没有 MJ,第 4 步那两份也会被转发和交付,p₂、p₃ 各交付两次,并且转发永远停不下来。
怎么判断
想知道某个节点会不会处理一条消息,只看它的 MJ:在里面就不处理,不在里面就完整走一遍并把它加进去。
想知道少了 MJ 会违反什么:No Duplication(重复交付),外加协议跑不完(无限转发)。
常见误解
以为 MJ 只是性能优化
去掉它会直接违反 No Duplication,而且转发永不终止,协议都跑不完。
试一下
n 个节点、没有崩溃时,按这个协议一条消息在网络上一共被发送多少次?(发给自己那一次也算)
发起者发给自己 1 次,再转发给其余 n − 1 个节点。其余每个节点第一次收到时,转发给除自己和来源之外的 n − 2 个节点。总数 = 1 + (n − 1) + (n − 1)(n − 2) = 1 + (n − 1)²。n = 3 时是 5 次,和上面那张表的行数一致。
4. URB 不管的那件事:顺序,以及「广播 ≠ 交付」
它解决什么问题
URB 管「谁最终能收到」,完全不管「按什么次序收到」。还有一点容易误会:广播出去的消息,URB 并不保证一定有人交付。课件的四节点图把这两件事一起摆出来。
直觉
底层网络只保证最终送达,不保证顺序,发给自己的两条消息也一样。p₃ 先广播 m₃、再广播 m₄,两条都只是塞进自己的收件队列。网络完全可以先把 m₄ 送回来。
如果 p₃ 在 m₃ 绕回来之前崩了,m₃ 就从来没走到第 8 行,也就从没离开过 p₃。没有任何节点交付过它,URB 的前件不成立,这也合法。
一步一步看
目标:在课件四节点图里看两件事:各节点交付顺序可以不同,广播了的消息也可能没人交付。
-
先读图:p₁、p₂ 全程正确,p₃、p₄ 末尾崩溃。
-
逐条线列事件:p₁ 广播 m₁,之后依次交付 m₂、m₄、m₁。p₂ 广播 m₂,之后依次交付 m₄、m₂、m₁。
-
p₃ 先广播 m₃、再广播 m₄,m₄ 先绕回来,交付 m₄ 并转发出去,然后崩溃。
-
p₄ 广播 m₅,只交付了 m₁ 就崩溃,m₅ 自己那份还没绕回来。
-
结果:m₃ 和 m₅ 广播了,但没有任何节点交付。
怎么判断
查 Uniform Agreement 有没有被违反,对每条消息做两步:
- 有没有任何节点交付过它?没有,跳过,不违反。
- 有的话,它的交付者里是否包含全部正确节点?包含就成立,缺一个就违反。
查顺序问题:URB 下任何交付顺序都合法,包括发送方自己颠倒自己的两条消息。
常见误解
以为发送方自己总能按发送顺序看到自己的消息
队列不保序,p₃ 先交付 m₄ 也合法。同一发送方的两条消息,在任何节点(包括发送方自己)都可能颠倒,顺序要另加一层来管。
以为 p₁ 先广播 m₁、最后才交付 m₁ 是画错了
不矛盾。广播只是把 m₁ 发给自己,消息在自己的队列里排到很后面才回来,广播和交付的时刻可以隔很远。
试一下
在上图里,m₄ 被谁交付过?它满足 Uniform Agreement 吗?
p₁、p₂、p₃ 都交付过 m₄。正确节点是 p₁、p₂,都在交付者里,满足。
把它们串起来
上一页把 URB 定义成「任何进程交付 ⟹ 所有正确进程交付」。这一页给出实现,关键就是一句「先转发,后交付」:节点交付 m 的那一刻,m 已经在去往别人的路上。
协议的另外两处设计各管一件事。广播只发给自己,让发送方和别人走同一条交付路径。MJ 负责去重,也让转发停下来。
URB 留下的空白是顺序。课件的四节点图正好把这件事暴露出来:p₃ 自己的两条消息颠倒了,而且有消息广播了却零交付。下半讲在 URB 之上加一层排序,可靠性性质直接继承,只需额外证明新加的顺序性质。
课件里的坑
- [课件留白] p.18 Exercise 1「p4 不崩溃会怎样」在课件上是空白页,答案见下面的课件例题。
- [课件留白] p.19 的推演里打了三个问号(m4 能否先于 m3 被收到、p3 收到 m3 没有、p3 会不会交付 m3),课件没给答案。依次是:能、没有、不会。
- [易错] p.17 里 m3 零交付的原因在 p3 自己,和 p4 崩不崩无关;Exercise 1 把 p4 改成不崩溃,m3 仍然零交付。
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写三条:URB 协议那一句话、MJ 的两个作用、URB 管不管顺序。再把下面的「变式题」做一遍。最后回查两个最容易错的地方:以为广播了就一定被交付、以为先交付后转发也一样。
必背
- URB 协议一句话:先发给自己,收到后先转发再交付,用 MJ(message judger,已见消息集合)去重;把转发和交付两步对调就退化成 RB。
- 广播了不等于会被交付:URB 只承诺「有一个进程交付了,所有正确进程都交付」。
- MJ 集合有两个作用:判断消息是不是第一次收到,既保证 No Duplication,又让互相转发能停下来。
- URB 完全不管顺序:同一发送方的两条消息,在任何节点(包括发送方自己)都可能颠倒。
- 课件四节点图里 m3 和 m5 零交付:发送方在自己那份消息绕回来之前就崩了,消息从没离开过它。
课件例题
例 1(课件 p.17):四节点 URB 图里,哪些消息没人交付
题面和逐步解法见下方「完整例题」。
提示
对每个崩溃节点,看它广播的消息有没有在它崩溃前绕回它自己。
解答
m3 和 m5 零交付,不违反 URB。推导见完整例题。
例 2(课件 p.18,Exercise 1):如果 p4 没有崩溃,重画上一题的图
题面:沿用例 1 的四节点图,只把 p4 改成不崩溃。问:哪些节点的交付会变?m3 和 m5 还是零交付吗?
提示
p4 不崩,它自己那份 m5 迟早会绕回来。再想 m3 卡住的原因跟 p4 有没有关系。
解答
- p4 最终收到自己的 m5,首次见到,先转发给 p1、p2、p3,再交付。p1、p2 收到转发的 m5,也转发并交付。所以 m5 从零交付变成 p1、p2、p4 都交付。p3 已经崩了,收不收得到不影响结论。
- p4 还会交付 m2 和 m4。这两条本来就被转发到全网,只是原图里 p4 崩得太早。p4 的交付序列是 m1、m5、m2、m4,相对顺序不确定,URB 不管顺序。
- m3 仍然没有任何节点交付。m3 卡死的原因是 p3 在自己收到 m3 之前就崩了,m3 从没离开过 p3。改 p4 的命运救不了 m3。
例 3(课件 p.19):把 m3、m4 那一段逐步推演,回答三个问号
题面:p3 广播 m3(发给自己),再广播 m4(发给自己)。p3 收到自己的 m4 并交付,把 m4 发给 p1、p2、p4,随后崩溃。p1、p2 先后收到 m4,各自转发后交付。课件在三处打了问号:m4 能比 m3 先被收到吗?p3 崩溃前收到 m3 了吗?p3 会交付 m3 吗?结论写着:最终 p1 和 p2 都有 m4。
提示
网络保证顺序吗?交付语句写在伪代码的哪个分支里?
解答
- 能。底层网络只保证最终送达,不保证顺序,发给自己的两条消息也一样。
- 没有。p3 在 m3 绕回来之前就崩了。
- 不会。交付只发生在第 5 行的接收分支里,没收到就没有交付。
- 页面顶上那句「first send out to itself/others, then URB-deliver」就是协议的一句话总结:先发出去,再交付。
完整例题
拿课件那道四节点 URB 图(p.17)走一遍。p1、p2 是非故障节点,p3、p4 最后都崩了。各节点从左到右的事件如下:
| 节点 | 事件序列 |
|---|---|
| p1(非故障) | 广播 m1 → 交付 m2 → 交付 m4 → 交付 m1 |
| p2(非故障) | 广播 m2 → 交付 m4 → 交付 m2 → 交付 m1 |
| p3 | 广播 m3 → 广播 m4 → 交付 m4 → 崩溃 |
| p4 | 广播 m5 → 交付 m1 → 崩溃 |
问:哪些消息没有任何节点交付?这违反 Uniform Agreement 吗?
第一步,看 p1 自己的 m1。p1 第一件事就广播 m1,交付 m1 却是最后一件事。这不矛盾:广播只是把 m1 发给自己,消息在自己的队列里排到很后面才回来。广播的时刻和交付的时刻可以隔很远。
第二步,找零交付的消息。p3 先广播 m3 再广播 m4,网络把 m4 先送了回来。p3 交付 m4 并把它转发出去,然后就崩了,m3 那份永远没回来。所以 m3 没有任何节点交付。m5 同理:p4 广播 m5 后只交付了 m1 就崩了,m5 也是零交付。
第三步,逐条核对 Uniform Agreement。被交付过的消息有三条:m1(p1、p2、p4)、m2(p1、p2)、m4(p1、p2、p3)。每一条的交付者都包含全部非故障节点 {p1, p2},成立。m3、m5 没人交付,前件不成立,也不违反。
结论:m3 和 m5 零交付,不违反 URB。一条消息被广播了,不等于会被交付。
变式题(先自己做)
自编情境:把 URB 协议改成「收到首次见到的消息,先交付,再转发」。改完的协议还满足 URB 吗?举一个出事的场景。
提示
想一个节点交付之后、转发之前就崩了的情形,再对照 RB 和 URB 的 Agreement 前件。
判分点与答案
判分点:指出退化成 RB;给出「交付后、转发前崩溃」的场景;用前件里的「正确进程 / 任何进程」解释。
只满足 RB,不满足 URB。场景:P1 交付了 M,还没来得及转发就崩了。M 从未离开 P1,P2、P3 永远收不到。
P1 是故障进程,RB 的前件「正确进程交付」不成立,RB 不被违反。URB 的前件是「任何进程交付」,P1 交付过,P2、P3 就必须交付,这里没做到,URB 被违反。
闪卡自测
1. 写出 URB 协议的三件事。把哪两步对调会出问题?
先把消息发给自己;收到之后先转发给所有人、再交付;用 MJ(message judger,已见消息集合)去重(p.16、p.19)。把「转发」和「交付」对调,协议就退化成 RB。
2. URB-broadcast 为什么只把消息发给自己?
让发送方和接收方走同一条代码路径,Validity 自动成立,不用另写「发送方交付自己」的逻辑(p.16 第 3 行)。
3. 第 7 行为什么排除 i 和 j?去掉会出错吗?
排除 i 是不用发给自己,排除 j 是不用回发给来源,它们已经有这条消息了。这是优化,去掉不影响正确性(p.16)。
4. MJ 集合起什么作用?少了它会怎样?
判断每条消息是不是第一次收到(p.19)。少了它,节点互相转发同一条消息会无限循环,同一条消息还会被交付多次,违反 No Duplication。
5. p.17 的图里,为什么 m3 没有任何节点交付?
p3 先广播 m3 再广播 m4,m4 先绕回来,p3 交付并转发 m4 后就崩了。m3 只发给过 p3 自己,从没离开过 p3(p.17、p.19)。
6. p.17 里 p1 第一件事广播 m1,最后才交付 m1,矛盾吗?
不矛盾。广播只是把 m1 发给自己,消息在自己的队列里排到很后面才回来,广播和交付的时刻可以隔很远(p.17)。
7. p4 不崩溃时,m3 会被交付吗?
不会。m3 卡死的原因在 p3:它在自己收到 m3 之前就崩了,m3 从没离开过 p3,和 p4 无关(p.18)。
8. 发送方 p3 先广播 m3 后广播 m4,它自己先交付 m4,合法吗?
合法。按 URB 协议第 3 行,两条消息都只是塞进自己的网络队列,队列不保序。URB 完全不管顺序,顺序要另加一层来管(p.19)。
下一讲
下半讲 L03b-1 在 URB 之上加交付顺序:先看顺序到底有几种可能,再讲 FIFO 怎么用序号和缓冲区把同一发送方的消息排好。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。