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

L03a-1 可靠广播(一):收到和交付是两回事,可靠性分三级

从时空图的读法讲起,分清 send、receive、deliver,再一级一级看 best-effort、RB、URB 各保证什么、漏洞在哪、差别落在哪一个词上。

一句话版

一个节点想让所有节点都收到同一条消息,这件事叫广播。消息到了手里和消息交给应用是两步,两步之间可以先扣住,协议的全部本事都在这段时间差里。

这一页只回答一个问题:消息最终会不会被大家都交付。答案分三级,一级比一级多要一条保证。协议具体怎么写,留给下一页 L03a-2。

先认识这几个词

读之前最好先懂 happens-before(事件先后),见 L02b-1。

词 全称 / 读法 一句人话
进程 / 节点 process / node 网络里一台各自干活的机器,本讲两个词混用
时空图 space-time diagram 横线代表进程、箭头代表消息的示意图
receive / deliver 接收 / 交付 消息到手叫 receive,协议放行给应用叫 deliver
正确进程 / 故障进程 correct / faulty process 全程不崩溃的叫正确进程,中途崩了的叫故障进程
best-effort 尽力而为广播 能送就送,送不到没人负责补
RB Reliable Broadcast,可靠广播 有正确进程交付,所有正确进程都交付
URB Uniform Reliable Broadcast,一致可靠广播 有任何进程交付,所有正确进程都交付

一个类比:楼下那间传达室

写字楼楼下有间传达室。快递员什么时候把信送到,由外面的世界决定,你插不上手。传达室什么时候把信放进你的信箱,由传达室的规矩决定。

两步之间有段时间差。传达室可以先把一封信扣在架子上,等另一封到了再一起放。协议的全部本事就在这段时间差里。

传达室的规矩可以一级级加严。最松的一档是能送就送,送不到算了。严一点的一档是只要有一个住户拿到了,就保证楼里所有还在的住户都能拿到。再严一档,哪怕拿到信的那个住户当天就搬走了,这条保证也照样成立。

类比在哪里失效:

  • 传达室是一个中心,网络里每个节点自己就是自己的传达室。所以发送方也得先把消息发给自己,走和别人一样的交付流程。
  • 楼里谁搬走了大家看得见,网络里节点崩了别人看不见。「正确进程」和「任何进程」这一字之差,正是 RB 和 URB 的全部区别。
  • 楼里的信基本不会丢。网络里的消息会半路丢,best-effort 那一档对别人收不收得到没有任何承诺。

从零讲起

1. 先补一块:时空图怎么读(补充)

它解决什么问题

这一讲几乎每道题都给一张图,问谁交付了什么、违不违反某条性质。图读不懂,后面的性质再熟也答不出来。时空图就是把「谁在什么时候做了什么、消息从谁飞到谁」画在一张纸上的办法。

直觉

把每个进程想成一条从左往右流的时间河。河上的一个点是这个进程做的一件事,叫事件(event)。两条河之间的斜箭头是一条消息:箭尾是发出去的那一刻,箭头是到达的那一刻。

箭头是斜的,因为消息在网络上要走一段时间。箭头半路打叉,表示这份消息丢了。一条河在某处打叉、后面变成虚线,表示这个进程在那一刻崩溃,之后什么也不做。

一步一步看

目标:学会按横线、圆点、箭头的顺序读一张时空图,看出谁交付了 m。

  1. 先数横线:有几条横线就有几个进程,这张图里是 P、Q、R。

  2. 再看圆点:P 的线上先是 broadcast(m),后面是 deliver(m)。同一条线上越靠右越晚发生。

  3. 再看箭头:从 P 的广播点出发有两条斜箭头,一条落到 Q,一条落到 R。被标出的那条就是消息 m 在路上。

  4. 最后看落点之后:Q、R 收到 m 之后各自 deliver(m)。右侧一栏写着每个进程最后的状态。

    时空图示例:三条横线自上而下是进程 P、Q、R,往右是时间往后。P 先 broadcast(m) 再 deliver(m);两条斜箭头从 P 的广播点分别落到 Q 和 R,标出的那条写着消息 m;Q 和 R 在箭头落点之后各自 deliver(m)

怎么判断

拿到一张时空图,按这个顺序读:横线是谁 → 每条线上有哪些点、先后如何 → 哪些箭头到了、哪些打叉 → 哪条线中途打叉崩溃。

判断「某进程交付过 m 没有」,只看它自己那条线上有没有 deliver(m) 这个点。箭头到了只说明收到了,交付要另画一个点。

常见误解

以为同一条竖线上的点是「同时」发生的

不同进程之间没有共同的钟,图上上下对齐只是画的位置,不代表同一时刻。能确定先后的只有两种情况:同一条线上的左右,和一条箭头的两端(发出一定早于到达)。

试一下

一张图里 R 的线上没有 deliver(m) 的点,但有一条从 P 来的箭头落在 R 上。R 交付了 m 吗?

不能算交付。箭头落下只说明 R 收到(receive)了 m,交付要看 R 的线上有没有 deliver(m) 这个事件。下一个概念讲的就是这两者的差别。

2. send / receive / deliver 与那段时间差

它解决什么问题

如果消息一到就交给应用,协议就没有任何插手的余地:网络送什么顺序,应用就看到什么顺序;网络丢了谁,谁就看不到。把「到手」和「交给应用」拆成两步,协议才能在中间做事。

直觉

课件特意强调四个词各是一件事,每个词都不能混:

  • broadcast:应用对协议说「把这条消息发给所有人」。
  • send:协议真的往某条链路上塞一个包。
  • receive:协议从网络收到一个包,还没给应用看。
  • deliver:协议决定「现在可以让应用看到这条消息了」。

receive 的先后由网络决定,协议管不着。deliver 的先后由协议决定。协议手里唯一的工具是收到之后先扣住不交,扣住消息的地方叫缓冲区(buffer)。

一步一步看

目标:看网络打乱到达顺序后,协议怎样用 buffer 把交付顺序摆回来。

  1. 发送方 p₁ 先 broadcast 出 m₁,再 broadcast 出 m₂。

  2. 网络把顺序弄乱了:p₂ 先 receive 到 m₂,后 receive 到 m₁。

  3. 协议看到 m₂ 先到,但它想按发送的先后交付,于是把 m₂ 扣在 buffer 里。

  4. m₁ 到了,先交付 m₁,再把 m₂ 从 buffer 放出来交付。

    三条泳道的时序图:发送方 p₁ 那条先后发出 m₁、m₂;中间一条是接收方 p₂ 的 receive,网络说了算,m₂ 先到、m₁ 后到;最下一条是 p₂ 的 deliver,协议说了算,先到的 m₂ 被扣在 buffer 里,等 m₁ 交付之后才放出来

怎么判断

看一条性质约束的是谁,只问一句:它说的是 deliver 还是 receive?本讲后面所有性质,Validity、Agreement、No Duplication、No Creation、FIFO、Causal、Total,全部只约束 deliver。

再看发送方:它也要走一遍 deliver。课件对 deliver 的定义里写明,交付的对象包括发送方自己。否则「自己广播的自己一定交付」这句话在它身上没法说。

常见误解

把 receive 和 deliver 当同一件事

混了这两个词,后面的三个排序算法就全看不懂了。那三个算法只做一件事:把已经 receive 的消息暂时不 deliver,等条件满足再放。

以为发送方知道自己发了什么,可以跳过交付

发送方也得和别人一样走一遍 deliver。下一页的协议里,广播的第一步就是把消息发给自己,理由就在这里。

试一下

p₂ 先收到 m₂ 后收到 m₁,最后的交付顺序是 m₁、m₂。这一过程里 m₂ 在哪待过?

在 p₂ 的缓冲区里。它已经被 receive,但协议没有立刻 deliver,等 m₁ 交付之后才放出来。

3. 最弱一档:best-effort

它解决什么问题

先回答最低的要求:至少别乱来。消息不能重复交付,不能凭空捏造,正确的发送方自己要能交付。best-effort 就是满足这三条、别的一概不管的一档。

直觉

三条性质,每条一句话:

  • 有效性(Validity):正确进程 p 广播 m,则 p 最终把 m 交付给自己。
  • 不重复(No Duplication):每条消息只交付一次。
  • 不捏造(No Creation):交付了一条声称来自 p 的消息,那它确实是 p 之前广播的。

它缺的是一致性(Agreement)。Validity 只管发送方自己,别人收不收得到,它一个字都没说。所以几个节点可以对「有没有 m」看法不一样。

一步一步看

目标:看 best-effort 的三条性质都没违反时,几个进程对「有没有 m」仍可以看法不一。

课件用两张时空图演示这种不一致,两张图失败的对象正好反过来。

  1. 第一种:P 广播 m 并交付给自己,发给 Q 的那份送到,Q 交付了。

  2. 发给 R 的那份半路丢了,R 什么也没收到。协议不补发,三个进程看法不一致。

    best-effort 下接收方失败:P 广播 m 并交付给自己;发给 Q 的箭头送到,Q 交付 m;发给 R 的箭头半路打叉。右侧状态写着 P 交付了 m、Q 交付了 m,R 没有 m 且没人补

  3. 第二种更极端:P 广播完立刻崩溃,自己都没来得及交付。

  4. 发给 Q 的那份丢了,发给 R 的那份送到,R 交付了 m。最后只有 R 有这条消息。

    best-effort 下发送方崩溃:P 广播 m 之后时间线上立刻打叉,自己没交付;发给 Q 的箭头半路打叉;发给 R 的箭头送到,R 交付 m。右侧状态写着 P 崩了自己没交付、Q 没有 m、R 交付了 m

怎么判断

判断一个场景违不违反 best-effort,只查三条:

  • 有没有正确的发送方最后没交付自己的消息?有就违反 Validity。
  • 有没有谁把同一条消息交付了两次?有就违反 No Duplication。
  • 有没有谁交付了一条没人广播过的消息?有就违反 No Creation。

三条都没有,就不违反。别人收没收到不在检查范围里。

常见误解

以为 Validity 保证所有人都收到

它只管正确的发送方自己。第二张图里的发送方崩了,它连自己交付都不受 Validity 约束,别人收没收到更没人负责。

把两张图记反

第一张是 Q 成功、R 失败,发送方自己交付了。第二张是 Q 失败、R 成功,发送方广播完就崩,自己没交付。

试一下

P 正确,广播 m 后自己交付了 m;Q 交付了 m 两次;R 没收到。违反 best-effort 吗?违反哪条?

违反,违反的是 No Duplication:Q 把同一条消息交付了两次。R 没收到不违反任何一条,best-effort 没有 Agreement。

4. 补上一致性:RB

它解决什么问题

best-effort 允许正确的节点之间看法不一。可靠广播(RB)补一条 Agreement,把正确进程之间拉齐:只要有一个正确进程交付了,所有正确进程都得交付。

直觉

RB 有四条性质,前面三条和 best-effort 一样,多出来的是:

Agreement:若 m 被某个正确进程交付,则每个正确进程都最终交付 m。

这句话有两个限定词要抠。前半句(前件)说的是「某个正确进程交付了」,如果只有故障进程交付过,这条性质不触发。后半句(后件)说的是「每个正确进程都交付」,对故障进程没有要求。

所以 RB 只在正确进程内部保证一致。故障进程崩之前知道什么,它不管。

一步一步看

目标:看只有故障进程交付过 m 时,Q、R 一直没有 m 为什么也不违反 RB。

课件用一张反例图说明 RB 的漏洞。

  1. P 广播 m,先把 m 交付给自己。

  2. 发给 Q 和 R 的两份都半路丢了。

  3. P 随后崩溃。

  4. 唯一交付过 m 的是 P,而 P 是故障进程。Agreement 的前件不成立,Q、R 一直没有 m 也不违反 RB。

    RB 的漏洞:P 广播 m、先交付给自己,然后时间线打叉崩溃;发给 Q 和 R 的两份都在半路打叉。标出的是 P 的那次交付;右侧状态写着 P 交付过然后崩了,Q、R 都没有 m

怎么判断

判断 RB 的 Agreement 有没有被违反,按三步走:

  1. 圈出所有正确进程。
  2. 看有没有哪个正确进程交付了 m。没有,性质不触发,直接判不违反。
  3. 有的话,再看是不是每个正确进程都交付了 m。缺一个就违反。

常见误解

以为「P 交付了、别人没有」一定违反 RB

要先看 P 是不是正确进程。P 后来崩了,就是故障进程,它的交付不触发 Agreement。

以为这个漏洞无关紧要

交付是有外部后果的。P 在崩之前如果已经按 m 做了事,比如写了数据库、给用户回了执,系统就出现「有人按 m 行动过,但没人知道 m 存在」的状态。课件的说法是把消息带进了坟墓。

试一下

Q 是正确进程,交付了 m;P、R 也正确,但 R 永远没交付 m。违反 RB 吗?

违反。前件成立(正确进程 Q 交付了 m),后件要求每个正确进程都交付,R 是正确进程却没交付。

5. 把故障进程也算上:URB

它解决什么问题

RB 的漏洞来自前件只看正确进程。一致可靠广播(URB)只改一个词,把前件里的「正确进程」换成「任何进程」,交付完就崩的进程也会触发保证。

从哪来(补充)

best-effort、RB、URB 这一套「性质逐条叠加」的写法,常被追溯到 Vassos Hadzilacos 和 Sam Toueg 在 1994 年写的一份技术报告。报告题目是 A modular approach to the specification and implementation of fault-tolerant broadcasts,作者把广播按性质拆成一个个模块,各种广播由不同模块组合而成。

出处:Vassos Hadzilacos 论文列表

直觉

两句话放在一起对比:

  • RB:正确进程交付 ⟹ 所有正确进程交付。
  • URB:任何进程交付 ⟹ 所有正确进程交付。

只有前件变了,后件一个字没动。后件还是只要求正确进程交付,因为没法要求一个已经崩掉的进程再去做什么。Uniform 这个词的意思就是对所有进程一视同仁,不管它后来崩不崩。

一步一步看

目标:看同一个场景换成 URB 后,正确进程 Q、R 为什么必须交付 m。

把 RB 漏洞那个场景换成 URB 再走一遍。

  1. P 广播 m,先交付给自己。按协议,进程总会交付自己广播的消息。

  2. P 随后崩溃。崩之前那次交付已经发生,不能撤销。

  3. 代入 URB:任何进程交付过 m,前件成立。

  4. 所以正确进程 Q、R 都必须最终交付 m。图上多出来的就是这两次交付。

    URB 下的同一场景:P 广播 m、交付给自己、然后崩溃;两条箭头从 P 落到 Q 和 R,Q 和 R 的线上各有一个「必须 deliver(m)」的点被标出。右侧状态写着 P 交付过然后崩了,Q、R 是正确进程

把 RB 和 URB 对这个场景的要求摆成表:

只有 P1 交付了 M 然后崩溃 RB URB
P2 交付 M? 不要求 要求
P3 交付 M? 不要求 要求

怎么判断

判断 URB 的 Uniform Agreement,和 RB 只差第二步:

  1. 圈出所有正确进程。
  2. 看有没有任何进程(正确的、崩了的都算)交付了 m。没有,性质不触发。
  3. 有的话,看是不是每个正确进程都交付了 m。缺一个就违反。

常见误解

以为 URB 要求所有进程都交付

后件没变,崩溃的进程不在要求范围里。

以为广播出去的消息 URB 保证一定有人交付

不保证。URB 只承诺「有一个进程交付了,所有正确进程都交付」。如果谁都没交付,前件不成立,零交付也合法。下一页的四节点例子里就有这样的消息。

试一下

P 广播 m 后、交付前就崩了;Q 收到并交付了 m,随后也崩了;R 正确,还没收到 m。URB 下 R 必须交付 m 吗?

必须。Q 交付过 m,前件「任何进程交付」成立,R 是正确进程,必须最终交付。换成 RB 就不必须,因为交付过 m 的 Q 是故障进程。

把它们串起来

这一讲分两半:可靠性解决「消息会不会被交付」,顺序解决「按什么次序交付」。本页和下一页是前一半。

读题先读图。时空图上,进程是横线,消息是斜箭头,交付是线上的一个点。箭头到了只算收到,交付要另看。

起点是把 receive 和 deliver 分开。所有性质只约束 deliver,协议的本事全在「收到了先不交」。

在这个前提下,可靠性一级比一级多要一点。best-effort 只保证不重复、不捏造、正确的发送方自己交付。RB 加上 Agreement,把正确进程之间拉齐。URB 只改前件里的一个词,把交付完就崩的故障进程也算进来。

怎么用一个很短的协议实现 URB,留给 L03a-2。

课件里的坑

  • [课件留白] 开头点名了四种消息顺序,包括 absolute order(按真实物理时间排序),但后面只展开了 FIFO / causal / total 三种。异步系统没有全局时钟,absolute order 实现不了,所以课件只提名字。
  • [概念区分] best-effort 的两张图(p.7、p.8)失败对象是反过来的:p.7 是 Q 成功、R 失败;p.8 是 Q 失败、R 成功,且发送方 P 广播完就崩、自己都没交付。
  • [概念区分] p.15 的第二步「P1 交付 M」来自 Validity:进程总是交付自己广播的消息。考题问「P1 明明崩了为什么算交付过」,答案就是这一步在崩之前已经合法发生。

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写三条:send / receive / deliver 三个动作、三级可靠性各有哪几条性质、RB 和 URB 差在哪个词。再把下面的「变式题」做一遍。最后回查两个最容易错的地方:把 receive 和 deliver 当同一件事、以为 URB 要求所有进程都交付。

必背

  1. send / receive / deliver 是三件事,所有性质只约束 deliver;receive 由网络说了算,协议唯一的手段是收到后先扣住不交。
  2. 三级可靠性:best-effort = Validity + No Duplication + No Creation;Reliable 再加 Agreement;Uniform 把 Agreement 前件的「正确进程」换成「任何进程」。
  3. best-effort 缺 Agreement,节点之间可以出现不一致的世界观;Validity 只管发送方自己。
  4. RB 的漏洞:故障进程可以交付完就崩,把消息带进坟墓。
  5. URB 的 Agreement 后件不变,仍只要求正确进程交付;RB 和 URB 的全部差别在前件。

课件例题

例 1(课件 p.7):best-effort 下,P、Q 交付了而 R 没有

题面:三个进程 P、Q、R。P 执行 Broadcast(m) 并交付 m;发给 Q 的那份送到,Q 交付 m;发给 R 的那份标着 Delivery failed。图右侧写着 Inconsistent:P delivered、Q delivered、R failed。问:这违反 best-effort 吗?

时空图:P、Q、R 三条横线是三个进程。P 上 Broadcast(m) 后紧接着 Deliver(p,m);从 P 引出一条线到 Q,Q 上标 Deliver(p,m);另一条线指向 R,在半路标 Delivery failed,没到达 R。右侧方框标题红字 Inconsistent,框内写 P delivered、Q delivered、R failed
图片来源:COMP5567 Lecture_3-Distributed-Broadcast.pdf, p.7
提示

把 best-effort 的三条性质逐条代进去,看哪一条管得到 R。

解答

不违反。best-effort 只有 Validity、No Duplication、No Creation 三条:P 自己交付了 m,Validity 成立;没人重复交付、没人交付捏造的消息。它没有 Agreement,所以 R 没收到不算违规,结果就是三个节点对「有没有 m」看法不一致。

例 2(课件 p.8):发送方广播完就崩了

题面:P 执行 Broadcast(m) 后立刻崩溃,自己没有交付 m。发给 Q 的那份 Delivery failed,发给 R 的那份送到,R 交付了 m。问:发送方失败时会发生什么?

时空图:P、Q、R 三条横线。P 上 Broadcast(m) 之后不远处打叉,表示 P 崩溃,P 自己没有交付;发往 Q 的细线在半路打叉,标 Delivery failed;发往 R 的箭头到达 R,R 上标 Deliver(P, m);右下有 Time 箭头
图片来源:COMP5567 Lecture_3-Distributed-Broadcast.pdf, p.8
提示

先判断 P 是正确进程还是故障进程,再看 Validity 管不管得到它。

解答

出现不一致:R 交付了 m,P 和 Q 没有。这仍然不违反 best-effort。P 是故障进程,Validity 只约束正确进程广播的消息,所以 P 自己没交付也不算违规;Q 没收到同样没有性质去管。和例 1 对照,两张图失败的对象正好反过来。

例 3(课件 p.11):RB 下发送方交付完再崩

题面:P 执行 Broadcast(m),先交付给自己,之后崩溃。发给 Q 和 R 的两份都是 Delivery failed。图右侧:P delivered、Q failed、R failed。问:p 交付了 m 然后崩溃,会怎样?

时空图:P、Q、R 三条横线。P 上 Broadcast(m) 后紧接着 Deliver(p,m),之后在 P 线上打叉表示崩溃;从 P 发往 Q 和 R 的两条线都停在半路,各标 Delivery failed。右侧方框写 P delivered、Q failed、R failed
图片来源:COMP5567 Lecture_3-Distributed-Broadcast.pdf, p.11
提示

RB 的 Agreement 前件写的是「正确进程交付」。交付过 m 的是谁?它正确吗?

解答

发送方和接收方的状态不一致:P 交付过,Q、R 都没有。RB 的 Agreement 前件是「正确进程交付」,唯一交付过的 P 是故障进程,前件不成立,所以 RB 不被违反。这就是 RB 的漏洞:故障进程交付完就崩,把消息带进了坟墓。

例 4(课件 p.13):URB 下同一个场景该是什么样

题面:P 执行 Broadcast(m),交付给自己,之后崩溃。这次 Q 和 R 都画了 Deliver(p,m)。图下注明:p 既可以是正确进程,也可以是故障进程。问:为什么这张图里 Q、R 必须交付?

时空图:P、Q、R 三条横线。P 上 Broadcast(m) 后紧接着 Deliver(p,m),之后在 P 线上打叉表示崩溃;从 P 引出的两条线分别到达 Q 和 R,Q、R 上都标 Deliver(p,m),说明两个接收方都交付了 m
图片来源:COMP5567 Lecture_3-Distributed-Broadcast.pdf, p.13
提示

和例 3 比,前件里换了哪个词?

解答

URB 的前件是「任何进程交付」。P 崩之前交付过 m,前件成立,所以所有正确进程 Q、R 都必须最终交付 m。和例 3 对照,图上只多了两个交付点,差别就是前件里「正确」换成「任何」这一个词。

例 5(课件 p.14–15):只有 P1 交付后崩溃,RB 和 URB 各要求什么

题面和逐步解法见下方「完整例题」。

提示

先分清谁正确、谁交付过,再分别代入两条 Agreement。

解答

RB 下 P2、P3 都不要求交付;URB 下 P2、P3 都必须最终交付。推导见完整例题。

完整例题

这题就是课件的 Concrete Example,课件还配了一张对照表。

题面:P1 广播 M;P1 交付 M 后崩溃,此时 P2、P3 都还没收到 M;P2、P3 是正确进程,仍在运行。问:在 RB 和 URB 下,P2、P3 是否必须交付 M?

  1. 先确认谁是正确进程:P1 崩了,是故障进程;P2、P3 是正确进程。
  2. 再确认谁交付过:只有 P1。按协议,进程总会交付自己广播的消息,所以 P1 崩之前交付了 M。
  3. 代入 RB 的 Agreement:「正确进程交付 ⟹ 所有正确进程交付」。交付过 M 的只有故障进程 P1,前件不成立,RB 不要求 P2、P3 交付。它们可能永远收不到 M,这是允许的。
  4. 代入 URB 的 Uniform Agreement:「任何进程交付 ⟹ 所有正确进程交付」。P1 交付过,前件成立,P2、P3 必须最终交付 M。
  5. 对照表:P2 交付 M?RB 不要求,URB 要求。P3 交付 M?RB 不要求,URB 要求。

变式题(先自己做)

自编情境:P1 广播 M 后、交付前就崩溃;P2 收到并交付了 M,随后也崩溃;P3 是正确进程,还没收到 M。在 best-effort、RB、URB 三级下,P3 是否必须交付 M?

提示

先列出谁是正确进程、谁交付过 M。再把三级的性质逐条代进去,注意 Validity 管的是谁、Agreement 前件写的是「正确」还是「任何」。

判分点与答案

判分点:① 指出 P1、P2 都是故障进程,只有 P3 正确;② best-effort 和 RB 都不要求,理由要落在 Validity 只管正确的发送方、RB 前件要求正确进程交付;③ URB 要求,理由是 P2 交付过且前件是任何进程。

  1. best-effort:不要求。Validity 只约束正确进程广播的消息,P1 是故障进程;也没有 Agreement。
  2. RB:不要求。交付过 M 的只有 P2,P2 是故障进程,前件不成立。
  3. URB:要求。P2 交付过 M,前件「任何进程交付」成立,正确进程 P3 必须最终交付 M。

闪卡自测

1. broadcast、send、receive、deliver 各是谁做的?哪些性质约束哪一个?

broadcast 是应用层向协议提的请求,send 是协议往链路塞包,receive 是协议收到包,deliver 是协议决定让应用看到(p.3)。所有性质只约束 deliver,receive 的顺序永远由网络决定。

2. 为什么发送方也要把消息交付给自己?

p.4 的 Deliver 定义明写包括交付给它自己。它必须走和别人一样的 deliver 流程,否则 Validity 这条性质在它身上没法陈述,这也是 URB 协议「先发给自己」的理由(p.4、p.16)。

3. best-effort 有哪三条性质?缺的那条带来什么后果?

Validity、No Duplication、No Creation(p.5)。缺 Agreement,所以节点之间可以出现不一致的世界观;而且 Validity 只管发送方自己,别人收不收得到没有承诺。

4. best-effort 的两张图,失败的对象有什么不同?

第一张是 Q 成功、R 失败;第二张是 Q 失败、R 成功,而且发送方 P 广播完就崩、自己都没交付(p.7、p.8)。

5. RB 和 URB 的差别到底在哪一个词上?RB 的漏洞是什么?

Agreement 的前件:RB 写「正确进程交付 ⟹ 所有正确进程交付」,URB 换成「任何进程交付 ⟹ 所有正确进程交付」,后件不变(p.12、p.14)。RB 的漏洞是故障进程可以交付完就崩,把消息带进坟墓(p.11)。

6. P1 广播 M、交付 M 后崩溃,P2、P3 正确且还没交付。RB 和 URB 下 P2、P3 必须交付 M 吗?

RB 下不必须:唯一交付过 M 的 P1 是故障进程,前件不成立。URB 下必须:P1 崩之前确实交付过 M,任何进程交付就触发(p.14、p.15)。

7. URB 要求崩溃的进程也交付吗?

不要求。后件仍是「所有正确进程交付」,崩溃的进程不在要求范围里(p.12)。

8. 广播出去的消息,URB 保证一定有人交付吗?

不保证。URB 只承诺「有一个进程交付了,所有正确进程都交付」;如果谁都没交付,前件不成立,零交付也合法(p.17)。

下一讲

L03a-2 接着讲 URB 协议本身:先发给自己、先转发再交付、用 MJ 去重,以及课件那道四节点时空图里哪些消息没人交付。

下一讲 →
L03a-2 L03a-2 可靠广播(二):先转发再交付,一个十行的 URB 协议

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