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

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 下,同一发送方先后发的两条消息怎样被节点颠倒交付。

  1. p₃ 先广播 m₃,再广播 m₄。两条都按 URB 协议先发给自己。

  2. p₁ 运气好,按 m₃、m₄ 的顺序交付。

  3. p₂ 先收到 m₄,URB 不扣消息,直接交付 m₄,之后才交付 m₃。

  4. 发送方 p₃ 自己也先收到 m₄ 的那一份,同样先交付 m₄。

    p₃ 先广播 m₃ 后广播 m₄ 的时空图:三条时间线,p₃ 标发送方。p₁ 先交付 m₃ 再交付 m₄;被标出的是 p₂ 和 p₃ 先交付的 m₄,右栏写着 p₂、p₃ 的交付顺序都是 m₄ 在前

  5. 三个节点里有两个把同一发送方的两条消息颠倒了,这在 URB 下完全合法。FIFO 要禁掉的就是这种情形。p₁ 和 p₂ 之间的不一致是另一回事,FIFO 修不了。

怎么判断

拿到一个交付序列,先问它颠倒的是谁和谁的消息:

  1. 同一发送方的两条消息颠倒了:URB 允许,FIFO 不允许。
  2. 不同发送方的消息颠倒了: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 的挑法。

  1. 先画 5 个空位:_ _ _ _ _。
  2. 挑 2 个位置给 p1,例如第 1 和第 3 位。
  3. p1 的消息按内部顺序填进去:m11 _ m12 _ _。
  4. 剩下 3 个位置按顺序填 p3 的消息:m11 m31 m12 m32 m33。
  5. 换一种挑法就得到另一种顺序,挑法一共 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 的边界。

  1. p₁ 依次广播 m₁₁、m₁₂、m₁₃;p₄ 依次广播 m₄₁、m₄₂,然后崩溃。

  2. 在 p₃ 上,p₁ 的三条按 m₁₁、m₁₂、m₁₃ 的顺序交付,FIFO 生效。

  3. 再看跨发送方的一对:p₁ 先交付 m₁₁ 再交付 m₄₂,p₃ 先交付 m₄₂ 再交付 m₁₁。

    FIFO 边界的时空图:四条时间线,p₁ 发 m₁₁ m₁₂ m₁₃,p₄ 发 m₄₁ m₄₂ 后打叉崩溃。被标出的是 p₁ 先交付 m₁₁ 后交付 m₄₂,p₃ 先交付 m₄₂ 后交付 m₁₁,右栏两行顺序相反

  4. 逐个节点检查:p₁ 上 p₁ 的消息有序、p₄ 的消息有序;p₃ 上也一样。FIFO 一条没破。

  5. 可是两个节点对世界的观感已经不同。课件把这页标作 FIFO-URB Problem,就是在提示这条边界。

怎么判断

判断一个交付序列满不满足 FIFO,按发送方拆:

  1. 把交付序列按发送方拆成几条子序列。
  2. 每条子序列是不是按该发送方的发送顺序排?全是,就满足;有一条不是,就违反。
  3. 不同节点之间不用比,各查各的。

常见误解

以为 FIFO 让所有节点看到同一个顺序

这不归它管。各节点可以各选一种交错方式,要全体一致得上全序广播。

以为 FIFO 按「发送时间」给所有消息排队

不同发送方之间没有共用的时间线,FIFO 也不比较它们。它只比同一发送方的序号。

试一下

如果 m₄₂ 是 p₄ 看到 m₁₁ 之后才发的回复,p₃ 先交付 m₄₂ 再交付 m₁₁ 违反 FIFO 吗?该靠什么禁掉?

不违反 FIFO,两条仍来自不同发送方。这是「先看到回复再看到原帖」,要靠因果序禁掉。

4. 崩溃节点交付的是前缀

它解决什么问题

节点中途崩了,它交付到哪算哪。问题是它会不会乱跳,比如交付了第 3 条却没交付第 2 条。

直觉

课件给了两条推论。不崩溃的节点,最终会按每个发送方的广播顺序交付相同的消息序列。崩溃的节点,交付的是每个发送方所广播消息序列的一个前缀。

前缀就是从头开始连续的一段,中间不能缺。FIFO 不允许跳过 m₂ 先交付 m₃,所以崩溃只会让序列在某处整齐截断。

课件还补了一句:其他节点仍可以往崩溃节点发消息,但崩溃节点不再交付任何消息。

一步一步看

目标:看崩溃节点的交付记录为什么只能是从头连续的一段,中间不会缺。

  1. 某个正确节点依次广播 m₁、m₂、m₃。

  2. 不崩溃的节点最终按 m₁、m₂、m₃ 交付全部三条。

  3. 一个节点在交付 m₂ 之前崩了,记录停在 [m₁];交付 m₃ 之前崩了,停在 [m₁, m₂];全部交付后才崩,就是完整的三条。

  4. [m₁, m₃] 不可能出现:要交付 m₃,m₂ 必须先交付。

    崩溃节点交付记录的四行表格:某节点依次广播 m₁ m₂ m₃。[m₁]、[m₁, m₂]、[m₁, m₂, m₃] 三行标为是前缀,[m₁, m₃] 一行被标出为不是前缀、跳过了 m₂、违反 FIFO

怎么判断

  1. 把崩溃节点的交付记录按发送方拆开。
  2. 每条子序列是不是那个发送方发送序列的开头连续一段?全是就合法。
  3. 不同发送方的前缀长度可以不一样,互不相干。

这条性质的实际用处:推理崩溃节点处理到哪一步时,只需要知道它最后交付的是哪条,前面的全都交付过。

常见误解

以为「前缀」是对所有消息整体说的

它对每个发送方分别成立。一个崩溃节点对 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,队列为空。

  1. m₁₁ 到达,序号 1 对上,交付,next₂[1] 变 2。

    FIFO 接收端第 1 步的状态表:m₁₁ 到达,序号 1,next₂[1] 从 1 变 2,next₂[3] 为 1,队列为空,被标出的动作格写着对上、交付

  2. m₃₂ 到达,序号 2,可 next₂[3] 还是 1,对不上,放进队列。

    FIFO 接收端第 2 步的状态表:新增一行 m₃₂ 到达,序号 2,next₂[3] 仍为 1,msg_set₂ 变成含 m₃₂,被标出的动作格写着对不上、扣下

  3. m₃₁ 到达,序号 1 对上,交付,next₂[3] 变 2。回扫队列,m₃₂ 的序号正好是 2,放出,next₂[3] 变 3,队列清空。

    FIFO 接收端第 3 步的状态表:新增一行 m₃₁ 到达,序号 1,next₂[3] 从 1 变到 3,msg_set₂ 清空,被标出的动作格写着交付 m₃₁、回扫放出 m₃₂

  4. m₃₃ 到达,序号 3 对上,交付,next₂[3] 变 4。

    FIFO 接收端第 4 步的状态表:新增一行 m₃₃ 到达,序号 3,next₂[3] 从 3 变 4,队列为空,被标出的动作格写着对上、交付

  5. m₁₂ 到达,序号 2 对上,交付,next₂[1] 变 3。p₂ 最终交付 m₁₁、m₃₁、m₃₂、m₃₃、m₁₂。

    FIFO 接收端第 5 步的完整状态表:五行依次是 m₁₁、m₃₂、m₃₁、m₃₃、m₁₂,最后一行动作格被标出,底部写着 p₂ 最终交付顺序 m₁₁ m₃₁ m₃₂ m₃₃ m₁₂

怎么判断

一条消息到了,按三问走:

  1. 它的序号等不等于 next_i[发送方]?等于就交付并加一,不等于就入队,结束。
  2. 交付后,队列里有没有同一发送方、序号等于新 next_i 的消息?有就接着放,一直放到没有为止。
  3. 跑完检查终态:每个 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 让各节点顺序一致、以为崩溃节点可能跳过中间某条。

必背

  1. FIFO 只约束同一发送方的消息,且只对每个节点各自成立;合法交付顺序数 = (a+b+c+…)! / (a! b! c! …)
  2. 崩溃节点在 FIFO 下交付的是每个发送方消息序列的一个前缀,不会跳过中间某条
  3. FIFO 的实现 = 序号 next_i[j] + 等待队列 msg_set_i:序号对上就交付并自增,然后回扫队列;对不上就入队
  4. 排序层坐在 URB 层之上,自动继承四条可靠性性质,只需额外证明新加的顺序性质;换排序策略不用碰可靠性代码
  5. 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 与两者并发。

  1. 不加任何顺序约束:3! = 6 种都可能,包括「恭喜」排在「赢了」前面。
  2. 加 FIFO:三条来自三个发送方,FIFO 不约束,仍是 6 种。
  3. 加因果序:只要求 m1 在 m2 前,剩 3 种:m1 m2 m3、m1 m3 m2、m3 m1 m2。
  4. 全序:还是这 3 种之一,但所有用户必须看到同一种。

因果序把 6 种压到 3 种,但不保证所有人看到一样的,要一致得上全序。

例 2(课件 p.22):p3 先后 URB 广播 m3、m4,各节点可能怎么交付

题面:p3 先 URB-broadcast m3,再 URB-broadcast m4。画出两种可能的交付情况。

提示

URB 协议里发给自己的那份也走网络队列,队列不保序。

解答
  1. 可能 1:p1、p2、p3 都先交付 m3 再交付 m4。
  2. 可能 2:p1 先 m3 后 m4,p2 先 m4 后 m3,p3 自己也先 m4 后 m3。
  3. 两种都满足 URB。URB 连同一发送方的顺序都不保证,发送方自己也会颠倒,这就是要加 FIFO 的理由。p1 和 p2 之间的不一致 FIFO 修不了,得靠全序。

例 3(课件 p.25):p1 发三条、p4 发两条后崩溃,p3 的交付

题面:p1 依次广播 m11、m12、m13;p4 依次广播 m41、m42 后崩溃。图上标注 p3 在 m12 之后交付 m13。崩溃节点还能交付消息吗?

四条水平时间线 p1 到 p4。p1 先后发出红色 m11、棕色 m12、紫色 m13,每条都向其余节点射出箭头并画一个弯箭头发给自己;p4 先发蓝色 m41,再发黄色 m42,m42 发出后不久 p4 上画着黑色叉号和 crash 字样。p3 线上 m42 和 m11 的到达处各有一个黑点,右下标注「p3: delivers m13 after m12」,紫色弯线从 m13 到达处连到 m12 到达处之后
图片来源:COMP5567 Lecture_3-Distributed-Broadcast.pdf, p.25
提示

FIFO 只看同一发送方;页脚有一句关于崩溃节点的说明。

解答
  1. p3 先 m12 后 m13,符合 FIFO:同一发送方 p1 的先后被保住了。
  2. 别的节点仍可以把消息发给崩溃节点,但崩溃节点不再交付任何消息,它的交付记录停在崩溃那一刻。

例 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 种。逐一列出:

  1. m11 m12 m31 m32 m33
  2. m11 m31 m12 m32 m33
  3. m11 m31 m32 m12 m33
  4. m11 m31 m32 m33 m12
  5. m31 m11 m12 m32 m33
  6. m31 m11 m32 m12 m33
  7. m31 m11 m32 m33 m12
  8. m31 m32 m11 m12 m33
  9. m31 m32 m11 m33 m12
  10. 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] 吗?

提示

想想「前缀」是什么意思。

解答
  1. 不崩溃节点最终按 m1、m2、m3 的顺序交付全部三条。
  2. 崩溃节点可能交付 [m1]、[m1, m2] 或 [m1, m2, m3],都是前缀。
  3. [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。

  1. m11:序号 1 = next_2[1],交付,next_2[1] 变 2。
  2. m31:序号 1 = next_2[3],交付,next_2[3] 变 2。
  3. m12:序号 2 = next_2[1],交付,next_2[1] 变 3。
  4. m32、m33 同理依次交付,next_2[3] 最后是 4。

每一步都对上了,等待队列从头到尾是空的,协议什么额外的事都没做。

第三步,情况 2:乱序到达。假设 URB 交付上来的顺序是 m11、m32、m31、m33、m12。

  1. m11:对上,交付,next_2[1] 变 2。
  2. m32:序号 2,但 next_2[3] 是 1,对不上,放进 msg_set_2。
  3. m31:序号 1 对上,交付,next_2[3] 变 2。回扫队列,m32 的序号正好是 2,放出,next_2[3] 变 3,队列清空。
  4. m33:序号 3 对上,交付,next_2[3] 变 4。
  5. 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 管不着的那类问题:回复和原话来自不同的人,怎么保证回复不先到。实现骨架不变,判断标准从一个序号换成一个向量。

下一讲 →
L03b-2 L03b-2 交付顺序(二):因果序,回信不能先于原信

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