L03b-1 交付顺序(一):FIFO,同一个人寄的信按先后放
URB 为什么不管顺序,FIFO 只约束什么、合法顺序怎么数,崩溃节点交付的前缀,以及序号加等待队列的实现。
一句话版
URB 只保证消息送到,不管先后。FIFO 加了一条最朴素的规矩:同一个发送方发的消息,每个节点都按发出的先后交付;做法是给消息贴序号,序号对不上的先扣下。
读之前最好先懂 L03a-1 的三档可靠性和 L03a-2 的 URB 协议。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| FIFO | First In First Out,先进先出 | 同一人发的消息按发出先后交付 |
| FIFO-URB | 带 FIFO 序的一致可靠广播 | URB 的四条性质再加一条 FIFO |
| 交错(interleaving) | 把几条队列穿插成一条 | 各发送方内部顺序不变,彼此之间随便插 |
| 前缀(prefix) | 序列开头连续的一段 | [m1]、[m1, m2] 是 [m1, m2, m3] 的前缀 |
| next_i[j] | 节点 i 期待来自 j 的下一个序号 | 对上了才交付 |
| msg_set_i | 节点 i 的等待队列 | 序号对不上的消息先放这里 |
一个类比:传达室按编号放同一个人的信
还是楼下那间传达室。上半讲它只管信送没送齐,现在多了一条规矩:同一个寄信人的信,按他寄出的先后放进信箱。
张三在每封信角上写了编号。第 2 封先到了,传达室就扣住它,等第 1 封到了再一起放。李四和张三之间谁先谁后,传达室不管。
类比在哪里失效:
- 楼里只有一间传达室,网络里每个节点各自扣信。FIFO 只对每个节点各自成立,两个节点可以把张三和李四的信穿插成不同的顺序。
- 传达室还能看邮戳,网络里没有全局时钟,只能靠发送方自己写在消息上的序号。
从零讲起
1. 消息都送到了,为什么还要管顺序
它解决什么问题
URB 只承诺交付与否,不承诺先后。聊天、转账这类应用一旦顺序错乱,读的人会看到前后矛盾的世界:回复跑到了原话前面,取款排到了存款前面。
直觉
课件用一个聊天室开场。用户 1 说英格兰赢了,用户 2 看到后回了句恭喜,用户 3 独立地说爱尔兰输了。三条消息来自三个人,各节点收到的顺序全看网络。
更直接的问题出在同一个发送方身上。一个节点先广播 m3 再广播 m4,URB 下任何节点都可能先交付 m4,连发送方自己也不例外,因为发给自己的那份也只是塞进了不保序的队列。
这一讲要往 URB 上加的顺序有三档:URB(不管顺序)→ FIFO-URB → CO-URB(带因果序的 URB)。课件的结论是因果序蕴含 FIFO 序,本页只讲 FIFO 这一档。
一步一步看
目标:看 URB 下,同一发送方先后发的两条消息怎样被节点颠倒交付。
-
p₃ 先广播 m₃,再广播 m₄。两条都按 URB 协议先发给自己。
-
p₁ 运气好,按 m₃、m₄ 的顺序交付。
-
p₂ 先收到 m₄,URB 不扣消息,直接交付 m₄,之后才交付 m₃。
-
发送方 p₃ 自己也先收到 m₄ 的那一份,同样先交付 m₄。
-
三个节点里有两个把同一发送方的两条消息颠倒了,这在 URB 下完全合法。FIFO 要禁掉的就是这种情形。p₁ 和 p₂ 之间的不一致是另一回事,FIFO 修不了。
怎么判断
拿到一个交付序列,先问它颠倒的是谁和谁的消息:
- 同一发送方的两条消息颠倒了:URB 允许,FIFO 不允许。
- 不同发送方的消息颠倒了:URB 和 FIFO 都允许,要管得上因果序或全序。
常见误解
以为发送方自己总会按顺序交付自己的消息
发给自己也走 URB,URB 不管顺序,发送方自己也可能先交付后发的那条。
以为 FIFO 能修好聊天室例子
那三条消息来自三个不同的人,FIFO 只约束同一发送方,对这个例子毫无帮助。要让「恭喜」排在「赢了」之后,得用下一页的因果序。
试一下
聊天室三条消息 m1(赢了)、m2(恭喜,回复 m1)、m3(独立的另一条)。不加任何顺序约束时,一个用户可能看到几种顺序?
三条消息任意排列,3! = 6 种,包括「恭喜」排在「赢了」前面。
2. 先补一块:几条队列穿插有多少种排法(补充)
它解决什么问题
FIFO 题最常见的问法是「一个节点有多少种合法交付顺序」。答这类题要会数「保持各自内部顺序、互相穿插」的排法,这是排列组合里的多重组合数。
直觉
两个发送方,p1 发 2 条,p3 发 3 条,一共 5 个交付位置。FIFO 只规定 p1 的两条内部先后、p3 的三条内部先后。
所以只要决定 5 个位置里哪 2 个给 p1,剩下的给 p3,每种挑法对应唯一的一种交付顺序。数挑法就是数顺序。
一步一步看
目标:看为什么数合法交付顺序,就是数 5 个位置里挑 2 个给 p1 的挑法。
- 先画 5 个空位:_ _ _ _ _。
- 挑 2 个位置给 p1,例如第 1 和第 3 位。
- p1 的消息按内部顺序填进去:m11 _ m12 _ _。
- 剩下 3 个位置按顺序填 p3 的消息:m11 m31 m12 m32 m33。
- 换一种挑法就得到另一种顺序,挑法一共 C(5,2) 种。
| 挑给 p1 的位置 | 得到的顺序 |
|---|---|
| 1、2 | m11 m12 m31 m32 m33 |
| 1、3 | m11 m31 m12 m32 m33 |
| 2、5 | m31 m11 m32 m33 m12 |
| 4、5 | m31 m32 m33 m11 m12 |
怎么算
两个发送方各发 a、b 条:合法顺序数 = C(a+b, a) = (a+b)! / (a! b!)。
意思是:先把 a+b 条消息当成全不一样的去排,有 (a+b)! 种;再把每个发送方内部被打乱的排法除掉,因为内部顺序是定死的。
推广到多个发送方:合法顺序数 = (a+b+c+…)! / (a! b! c! …)。课件那道题 5!/(2!·3!) = 10。
常见误解
以为答案是 5! = 120
5! 把同一发送方内部的先后也算成可变的,FIFO 恰恰把它们定死了。要除掉 2! 和 3!。
试一下
三个发送方各发 1 条,FIFO 下一个节点有多少种合法顺序?这说明了什么?
3!/(1!·1!·1!) = 6,和完全不加约束一样多。每个发送方只发一条时,FIFO 没有任何约束力,聊天室那个例子就是这种情况。
3. FIFO 管什么、不管什么
它解决什么问题
FIFO 解决「同一个人先说后说的话被倒着读」。性质是:如果一个节点先 FIFO-broadcast m、后 FIFO-broadcast m′,那么没有任何节点会在交付 m 之前交付 m′。
直觉
FIFO-URB 把 URB 的四条性质原样保留,只换了名字(URB-Validity、URB-Integrity、URB-Reliability、URB-Uniformity),再加这一条 FIFO message delivery。课件的一句话版是 same message order from the same process for each node。
这句话里有两个限定词,答题时都要写出来。from the same process 说的是只管同一个发送方,不同发送方的消息之间没有约束。for each node 说的是每个节点各自满足,不同节点之间不要求看到同一个顺序。
一步一步看
目标:看每个节点都守住 FIFO 时,不同节点对跨发送方的消息仍可能顺序不同。
课件拿四个节点演示 FIFO 的边界。
-
p₁ 依次广播 m₁₁、m₁₂、m₁₃;p₄ 依次广播 m₄₁、m₄₂,然后崩溃。
-
在 p₃ 上,p₁ 的三条按 m₁₁、m₁₂、m₁₃ 的顺序交付,FIFO 生效。
-
再看跨发送方的一对:p₁ 先交付 m₁₁ 再交付 m₄₂,p₃ 先交付 m₄₂ 再交付 m₁₁。
-
逐个节点检查:p₁ 上 p₁ 的消息有序、p₄ 的消息有序;p₃ 上也一样。FIFO 一条没破。
-
可是两个节点对世界的观感已经不同。课件把这页标作 FIFO-URB Problem,就是在提示这条边界。
怎么判断
判断一个交付序列满不满足 FIFO,按发送方拆:
- 把交付序列按发送方拆成几条子序列。
- 每条子序列是不是按该发送方的发送顺序排?全是,就满足;有一条不是,就违反。
- 不同节点之间不用比,各查各的。
常见误解
以为 FIFO 让所有节点看到同一个顺序
这不归它管。各节点可以各选一种交错方式,要全体一致得上全序广播。
以为 FIFO 按「发送时间」给所有消息排队
不同发送方之间没有共用的时间线,FIFO 也不比较它们。它只比同一发送方的序号。
试一下
如果 m₄₂ 是 p₄ 看到 m₁₁ 之后才发的回复,p₃ 先交付 m₄₂ 再交付 m₁₁ 违反 FIFO 吗?该靠什么禁掉?
不违反 FIFO,两条仍来自不同发送方。这是「先看到回复再看到原帖」,要靠因果序禁掉。
4. 崩溃节点交付的是前缀
它解决什么问题
节点中途崩了,它交付到哪算哪。问题是它会不会乱跳,比如交付了第 3 条却没交付第 2 条。
直觉
课件给了两条推论。不崩溃的节点,最终会按每个发送方的广播顺序交付相同的消息序列。崩溃的节点,交付的是每个发送方所广播消息序列的一个前缀。
前缀就是从头开始连续的一段,中间不能缺。FIFO 不允许跳过 m₂ 先交付 m₃,所以崩溃只会让序列在某处整齐截断。
课件还补了一句:其他节点仍可以往崩溃节点发消息,但崩溃节点不再交付任何消息。
一步一步看
目标:看崩溃节点的交付记录为什么只能是从头连续的一段,中间不会缺。
-
某个正确节点依次广播 m₁、m₂、m₃。
-
不崩溃的节点最终按 m₁、m₂、m₃ 交付全部三条。
-
一个节点在交付 m₂ 之前崩了,记录停在 [m₁];交付 m₃ 之前崩了,停在 [m₁, m₂];全部交付后才崩,就是完整的三条。
-
[m₁, m₃] 不可能出现:要交付 m₃,m₂ 必须先交付。
怎么判断
- 把崩溃节点的交付记录按发送方拆开。
- 每条子序列是不是那个发送方发送序列的开头连续一段?全是就合法。
- 不同发送方的前缀长度可以不一样,互不相干。
这条性质的实际用处:推理崩溃节点处理到哪一步时,只需要知道它最后交付的是哪条,前面的全都交付过。
常见误解
以为「前缀」是对所有消息整体说的
它对每个发送方分别成立。一个崩溃节点对 p₁ 的消息可能停在 [m₁₁, m₁₂],对 p₃ 的消息停在 [m₃₁],两者互不相干。
试一下
崩溃节点的交付记录是 m₃₁、m₁₁、m₃₂,其中 p₁ 发了 m₁₁、m₁₂,p₃ 发了 m₃₁、m₃₂、m₃₃。合法吗?
合法。p₁ 的子序列 [m₁₁] 是前缀,p₃ 的子序列 [m₃₁, m₃₂] 也是前缀。
5. 实现:序号加等待队列
它解决什么问题
节点怎么知道一条消息该不该现在交付?发送方给每条消息贴上自己的序号;接收方为每个发送方记一个期待的下一个序号,对上就交付,对不上就先放进等待队列。
直觉
每个节点 pi 维护三个变量:
| 变量 | 含义 | 初值 |
|---|---|---|
seq_nb_i |
pi 自己的发送序号,附在消息上 | 1 |
next_i[j] |
pi 期待来自 pj 的下一条消息的序号 | 全部为 1 |
msg_set_i |
等待队列 | 空 |
广播端只有四行:标上发送方、贴上序号、序号加一、调用 URB-broadcast。
当 pi 调用 FIFO-broadcast(m):
m.sender ← i
m.seq_nb ← seq_nb_i; seq_nb_i ← seq_nb_i + 1
URB-broadcast(m)
课件的接收端只有文字没有代码。按文字补全是这样,输入是 URB-deliver 上来的消息,不是网络原始包:
当 pi URB-deliver 了来自 pj 的消息 m:
if m.seq_nb = next_i[j] then
FIFO-deliver(m); next_i[j] ← next_i[j] + 1
while msg_set_i 里有来自 pj、序号 = next_i[j] 的 m′ do
FIFO-deliver(m′); next_i[j] ← next_i[j] + 1
从 msg_set_i 删去 m′
else
把 m 放进 msg_set_i
结构是一个四层栈:应用层、FIFO 层、URB 层、网络层。FIFO 层坐在 URB 之上,去重和可靠性都在下一层解决了,它只管排序。所以 FIFO-URB 原样继承 URB 的四条性质,只需额外证明 FIFO 那一条。
一步一步看
目标:跟着 p₂ 的计数器和等待队列,看乱序到达的五条消息怎样排回各发送方的顺序。
p₁ 发 m₁₁(序号 1)、m₁₂(序号 2);p₃ 发 m₃₁、m₃₂、m₃₃(序号 1、2、3)。在 p₂ 上,URB 交付上来的顺序是 m₁₁、m₃₂、m₃₁、m₃₃、m₁₂。初值 next₂[1] = next₂[3] = 1,队列为空。
-
m₁₁ 到达,序号 1 对上,交付,next₂[1] 变 2。
-
m₃₂ 到达,序号 2,可 next₂[3] 还是 1,对不上,放进队列。
-
m₃₁ 到达,序号 1 对上,交付,next₂[3] 变 2。回扫队列,m₃₂ 的序号正好是 2,放出,next₂[3] 变 3,队列清空。
-
m₃₃ 到达,序号 3 对上,交付,next₂[3] 变 4。
-
m₁₂ 到达,序号 2 对上,交付,next₂[1] 变 3。p₂ 最终交付 m₁₁、m₃₁、m₃₂、m₃₃、m₁₂。
怎么判断
一条消息到了,按三问走:
- 它的序号等不等于 next_i[发送方]?等于就交付并加一,不等于就入队,结束。
- 交付后,队列里有没有同一发送方、序号等于新 next_i 的消息?有就接着放,一直放到没有为止。
- 跑完检查终态:每个 next_i[j] 应该等于该发送方的条数加 1,队列为空。
常见误解
以为交付一条就结束
交付后要自增 next_i[j] 并回扫队列,可能一次连放好几条。漏了这两步,排在后面的消息永远出不来。课件的文字只写了「相等就交付」,答题时要写全。
以为比较要写成 ≥
URB 已经去重,同一序号不会来两次。来的要么正好是期待的那条,要么更靠后,不会更靠前,所以用「等于」。
试一下
在 p₂ 上,URB 交付上来的顺序改成 m₃₃、m₃₂、m₃₁。每一步之后队列里有什么?
m₃₃ 到达,next₂[3] = 1,入队,队列 {m₃₃}。m₃₂ 到达,仍对不上,队列 {m₃₂, m₃₃}。m₃₁ 到达,对上交付,next₂[3] 变 2,回扫放出 m₃₂,变 3,再放出 m₃₃,变 4,队列清空。一次连放两条。
把它们串起来
可靠性和顺序是两件事。URB 已经把「送不送得到」管住了,对先后一字不提,所以排序被做成一层薄封装,坐在 URB 上面。
这层封装只做一件事:收到之后先判断能不能交付,不能就扣下。FIFO 的判断标准是一个数,比对消息上的序号和自己期待的序号。
因为可靠性全靠下层,FIFO-URB 原样继承 URB 的四条性质,证明时只需要补新加的那一条。不崩溃的节点最终交付每个发送方的全部消息且保序,崩溃节点只交付前缀。
FIFO 的局限也要记清:它只看同一发送方。聊天室里「恭喜」比「赢了」先到,两条来自不同的人,FIFO 管不着。下一页的因果序就是为这件事加的,它的实现骨架和 FIFO 一样,只是把「比一个数」换成「比一个向量」。
课件里的坑
- [课件有误] p.25 写的是「crash nodes cannot delivery any messages」,动词位置写成了名词,下一页 p.26 同一句已改成 deliver。
- [课件留白] p.32 的 FIFO-URB 伪代码只有广播那一半,接收端的判断、入队、交付后自增并回扫这一整段代码缺失,只在 p.31 以文字存在。上面第 5 节补全了。
- [课件留白] p.28 和 p.29 是课堂现场画的空白模板,只有时间线和消息标签,没有箭头和交付事件。下面的完整例题把它们跑了一遍。
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写 FIFO 的两个限定词和交错数公式,再写出接收端的完整伪代码,包括交付后自增和回扫队列两步。然后把课件例题和变式题做一遍。最后回查两个最容易错的地方:以为 FIFO 让各节点顺序一致、以为崩溃节点可能跳过中间某条。
必背
- FIFO 只约束同一发送方的消息,且只对每个节点各自成立;合法交付顺序数 = (a+b+c+…)! / (a! b! c! …)
- 崩溃节点在 FIFO 下交付的是每个发送方消息序列的一个前缀,不会跳过中间某条
- FIFO 的实现 = 序号 next_i[j] + 等待队列 msg_set_i:序号对上就交付并自增,然后回扫队列;对不上就入队
- 排序层坐在 URB 层之上,自动继承四条可靠性性质,只需额外证明新加的顺序性质;换排序策略不用碰可靠性代码
- next_i[j] 用「等于」比较:URB 已保证不重复,到来的消息要么正是期待的那条,要么更靠后、要等
课件例题
例 1(课件 p.21):聊天室三条消息,用户可能看到哪些顺序
题面:用户 1 发「England has won the cricket match」,用户 2 回「Congratulations」,用户 3 发「Ireland has lost the cricket match」。考虑网络的不确定性,用户实际可能观察到哪些交付顺序?
提示
先判断三条消息之间谁和谁有因果关系,再分别套无序、FIFO、因果序、全序四种约束。
解答
记三条为 m1、m2、m3,m1 → m2(回复),m3 与两者并发。
- 不加任何顺序约束:3! = 6 种都可能,包括「恭喜」排在「赢了」前面。
- 加 FIFO:三条来自三个发送方,FIFO 不约束,仍是 6 种。
- 加因果序:只要求 m1 在 m2 前,剩 3 种:m1 m2 m3、m1 m3 m2、m3 m1 m2。
- 全序:还是这 3 种之一,但所有用户必须看到同一种。
因果序把 6 种压到 3 种,但不保证所有人看到一样的,要一致得上全序。
例 2(课件 p.22):p3 先后 URB 广播 m3、m4,各节点可能怎么交付
题面:p3 先 URB-broadcast m3,再 URB-broadcast m4。画出两种可能的交付情况。
提示
URB 协议里发给自己的那份也走网络队列,队列不保序。
解答
- 可能 1:p1、p2、p3 都先交付 m3 再交付 m4。
- 可能 2:p1 先 m3 后 m4,p2 先 m4 后 m3,p3 自己也先 m4 后 m3。
- 两种都满足 URB。URB 连同一发送方的顺序都不保证,发送方自己也会颠倒,这就是要加 FIFO 的理由。p1 和 p2 之间的不一致 FIFO 修不了,得靠全序。
例 3(课件 p.25):p1 发三条、p4 发两条后崩溃,p3 的交付
题面:p1 依次广播 m11、m12、m13;p4 依次广播 m41、m42 后崩溃。图上标注 p3 在 m12 之后交付 m13。崩溃节点还能交付消息吗?
提示
FIFO 只看同一发送方;页脚有一句关于崩溃节点的说明。
解答
- p3 先 m12 后 m13,符合 FIFO:同一发送方 p1 的先后被保住了。
- 别的节点仍可以把消息发给崩溃节点,但崩溃节点不再交付任何消息,它的交付记录停在崩溃那一刻。
例 4(课件 p.26):p1 先交付 m11 再交付 m42,p3 先交付 m42 再交付 m11,违反 FIFO 吗
题面:沿用例 3 的图,p1 的交付顺序是 m11 然后 m42,p3 是 m42 然后 m11。
提示
先看两条消息是不是同一个发送方,再想 FIFO 要不要求两个节点一致。
解答
不违反。m11 来自 p1,m42 来自 p4,发送方不同,FIFO 不比较它们;FIFO 也只对每个节点各自成立,不要求 p1 和 p3 一致。课件把它标成 FIFO-URB Problem,是在提示 FIFO 的边界:要管跨发送方的因果得上因果序,要让各节点一致得上全序。
例 5(课件 p.27,Exercise 2):p1 发 2 条、p3 发 3 条,FIFO 下有多少种交付顺序
题面:p1 依次广播 m11、m12,p3 依次广播 m31、m32、m33。为每个进程列出所有可能的 FIFO 交付顺序。
提示
5 个位置里挑 2 个给 p1,剩下的给 p3。
解答
公式:5!/(2!3!) = 10 种。逐一列出:
- m11 m12 m31 m32 m33
- m11 m31 m12 m32 m33
- m11 m31 m32 m12 m33
- m11 m31 m32 m33 m12
- m31 m11 m12 m32 m33
- m31 m11 m32 m12 m33
- m31 m11 m32 m33 m12
- m31 m32 m11 m12 m33
- m31 m32 m11 m33 m12
- m31 m32 m33 m11 m12
这 10 种是每个进程各自的可选项,不同进程可以选不同的一种。
例 6(课件 p.28–29):消息按序到达与乱序到达两种情况
题面:两张空白图,p1 依次广播 m11、m12,p3 依次广播 m31、m32、m33,分别标 case1 messages in sequence 和 case2 messages not in order。逐步跑法见下方完整例题。
提示
case1 里协议什么都不用做;case2 才用得上等待队列。
解答
case1 每条到达时序号都正好对上,队列始终为空。case2 某条消息先于它前一条到达,被扣进 msg_set,等前一条交付后由回扫放出。两种情况最终交付的都是例 5 那 10 种之一。
例 7(课件 p.30):正确节点依次广播 m1、m2、m3,崩溃节点可能交付什么
题面:写出不崩溃节点和崩溃节点各自可能的交付序列。崩溃节点可能交付 [m1, m3] 吗?
提示
想想「前缀」是什么意思。
解答
- 不崩溃节点最终按 m1、m2、m3 的顺序交付全部三条。
- 崩溃节点可能交付 [m1]、[m1, m2] 或 [m1, m2, m3],都是前缀。
- [m1, m3] 不可能:跳过 m2 先交付 m3 违反 FIFO。
完整例题
课件 p.28 和 p.29 是两张同样的空白图:p1 依次广播 m11、m12,p3 依次广播 m31、m32、m33,分别标「按序到达」和「乱序到达」。拿 p2 当观察点,把接收端协议跑一遍。
第一步,写初值。p2 的 next_2[1] = 1,next_2[3] = 1,msg_set_2 为空。消息上的序号:m11 是 1、m12 是 2;m31 是 1、m32 是 2、m33 是 3。
第二步,情况 1:按序到达。假设 URB 交付上来的顺序是 m11、m31、m12、m32、m33。
- m11:序号 1 = next_2[1],交付,next_2[1] 变 2。
- m31:序号 1 = next_2[3],交付,next_2[3] 变 2。
- m12:序号 2 = next_2[1],交付,next_2[1] 变 3。
- m32、m33 同理依次交付,next_2[3] 最后是 4。
每一步都对上了,等待队列从头到尾是空的,协议什么额外的事都没做。
第三步,情况 2:乱序到达。假设 URB 交付上来的顺序是 m11、m32、m31、m33、m12。
- m11:对上,交付,next_2[1] 变 2。
- m32:序号 2,但 next_2[3] 是 1,对不上,放进 msg_set_2。
- m31:序号 1 对上,交付,next_2[3] 变 2。回扫队列,m32 的序号正好是 2,放出,next_2[3] 变 3,队列清空。
- m33:序号 3 对上,交付,next_2[3] 变 4。
- m12:序号 2 对上,交付,next_2[1] 变 3。
p2 最终的交付顺序是 m11、m31、m32、m33、m12,是例 5 那 10 种之一。
第四步,自检。终态 next_2[1] = 3、next_2[3] = 4,各等于该发送方的条数加 1,队列为空。如果终态队列非空,说明漏了回扫那一步。
再多想一层:m32 被扣下时,它其实已经被 URB 交付上来了,只是 FIFO 层不放。这就是分层的意思:URB 层说「到了」,FIFO 层再决定「什么时候给应用」。
变式题(先自己做)
变式|改编自课件 p.27:p2 依次广播 m21、m22,p4 依次广播 m41、m42、m43。
(1) 一个不崩溃的节点在 FIFO 下有多少种合法交付顺序?(2) 某节点交付 m41、m21、m43、m22、m42,合法吗?(3) 另一节点中途崩溃,交付记录是 m21、m41、m42,合法吗?若是 m41、m43 呢?
提示
先套交错数公式。判断合法性时把交付序列按发送方拆成两条子序列,各看是不是按发送顺序;崩溃节点再看每条子序列是不是前缀。
判分点与答案
(1) 5!/(2!3!) = 10 种,和课件那道题条数相同,只是换了发送方。
(2) 不合法。拆出 p4 的子序列是 m41、m43、m42,m43 在 m42 之前,违反 FIFO。p2 的子序列 m21、m22 没问题,但一处违反就整体不合法。
(3) m21、m41、m42 合法:p2 的子序列 [m21] 是前缀,p4 的子序列 [m41, m42] 也是前缀。m41、m43 不合法:跳过了 m42。
判分点:写出公式与结果;按发送方拆子序列;崩溃节点用「每个发送方各自的前缀」判断。
闪卡自测
1. URB 保证同一发送方的消息按序交付吗?
不保证。一个节点先广播 m3 再广播 m4,任何节点都可能先交付 m4,连发送方自己也一样。
2. FIFO 性质的两个限定词是什么?
同一发送方、每个节点各自。FIFO 不比较不同发送方的消息,也不要求不同节点看到同一顺序。
3. 聊天室三条消息来自三个人,FIFO 下合法顺序有几种?
6 种。FIFO 只约束同一发送方,三条来自三个人,等于没有约束。要求回复在原话之后得用因果序,剩 3 种。
4. 两个发送方分别发 2 条和 3 条,FIFO 下一个节点有多少种合法交付顺序?
5!/(2!3!) = 10 种,公式是 (a+b+…)!/(a! b! …)。各节点可以选不同的一种。
5. 崩溃节点可能交付 [m1, m3] 吗?
不可能。崩溃节点交付的是每个发送方序列的前缀,跳过 m2 违反 FIFO。
6. FIFO-URB 每个节点维护哪三个变量?初值是多少?
seq_nb_i 自己的发送序号,初值 1;next_i[j] 期待来自 pj 的下一个序号,初值全为 1;msg_set_i 等待队列,初值为空。
7. 序号对上之后,除了交付还要做哪两件事?
把 next_i[j] 加一;回扫 msg_set_i,把来自 pj、序号正好等于新 next_i[j] 的消息接着放出,可能连放好几条。
8. FIFO 层的输入是 receive 还是 URB-deliver?这意味着什么?
URB-deliver。FIFO 层坐在 URB 之上,去重和可靠性已由下层保证,它自动继承 URB 的四条性质,只需证明新加的 FIFO 一条。
下一讲
下一页 L03b-2 处理 FIFO 管不着的那类问题:回复和原话来自不同的人,怎么保证回复不先到。实现骨架不变,判断标准从一个序号换成一个向量。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。