← COMP5567 全部讲次
T01b · 第 3 周

T01b Tutorial 1(下):四条性质,练习可靠广播判定

选择题考性质名字,简答题考哪条性质被违反,压轴题用性质倒推执行图。

一句话版

这一半只考一件事:给场景,点名性质。先背准四条定义,再判断没交付的进程是正确的还是故障的。

先认识这几个词

读之前最好先懂可靠广播,见 L03a-1。

词 全称 / 读法 一句人话
交付 deliver 进程把收到的消息正式交给上层程序使用
正确进程 / 故障进程 correct / faulty process 从头到尾没崩溃的进程 / 中途崩溃的进程
RB Reliable Broadcast,可靠广播 一个正确进程交付了,所有正确进程都会交付
URB Uniform Reliable Broadcast,一致可靠广播 任何进程(哪怕随后崩溃)交付了,所有正确进程都会交付
TOB Total Order Broadcast,全序广播 在可靠广播之上,还要求所有人交付消息的先后顺序一样
perfect links 完美链路 收发双方都不崩溃时,消息最终必达

题目地图

整份 tutorial 五页题,三种题型,前三讲各考一遍。时钟两题在 T01a,本页是选择题和广播判定题。

题 考什么 主要失分点
选择题 1 TOB 有哪四条标准性质 把 FIFO Order 当成 TOB 的性质
选择题 2 RB 与 URB 的差别 选了 Agreement——两者都有,不构成差别
RB 两问 哪条性质被违反 只答「出错了」,没点名性质
URB 三问 数来源、判 Uniform Agreement 广播者自己那一份算不算来源
重画题 改崩溃集合后重画执行图 漏掉 m2;给崩溃进程补上交付

答题时先点名性质,再引用定义说明是否违反,最后才补一句协议为什么这样设计。

概念卡

1. 四条性质的准确表述(TOB Properties)

人话定义:四条性质合起来,规定一个全序广播「做对了」是什么样子。Validity 管「自己广播的自己得交付」,Agreement 管「一个人交付了别人也得交付」。Integrity 管「不重不造」,Total Order 管「所有人看到的排列一样」。

例子:选择题给了 Validity / Agreement / Total Order / FIFO Order 四个选项。题目问哪个不是 TOB 的标准性质,答 FIFO Order。FIFO(先进先出)要求同一发送方的消息按发送次序交付,属于 FIFO Broadcast。

它和 Total Order 是两个独立维度。全序只保证所有人顺序一致,这个共同顺序不一定符合某个发送方自己的次序。两者都要满足的原语叫 FIFO Total Order Broadcast。

Integrity 这次没进选项,它等于 No Duplication(不重复)加 No Creation(不凭空造),同样是四条之一。

常见误解

以为选项里没出现的性质就不在标准四条里 → Integrity 缺席只是出题时的取舍。

这类题的排除法:Validity 和 Agreement 是所有广播原语的公共底座,Total Order 是 TOB 的定义性性质,三个都排除,剩下那个排序名就是答案。

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

2. 正确进程还是故障进程(Correct vs Faulty)

人话定义:它决定一条「没交付」到底算不算违规。Agreement 只保护正确进程,Uniform Agreement 把前提扩到任何进程。所有判定题的第一问都是「这个进程属于哪一类」。

例子:RB 的 Agreement 前提是「某个正确进程交付了 m」,崩溃进程交付过什么不作数。URB 的 Uniform Agreement 前提是「任一进程交付了 m」,包括交付完立刻崩溃的。Uniform 这个词在分布式文献里的固定含义,就是把约束从正确进程扩展到所有进程。

需要它的理由很实在。一个进程可能在崩溃前已经把交付结果暴露给外部:写了数据库、给用户发了确认。其他人最后都不交付的话,这个外部可见的结果就成了系统里的不一致。

常见误解

把「有进程没交付」直接等同于「性质被违反」→ RB 两问正是一对反例:正确进程 P5 永不交付违反 Agreement,故障进程 P4 不交付不违反。判定的第一步永远是分辨这个进程正确还是故障。

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

逐题拆解

选择题 1:答 FIFO Order,理由见概念卡 1。

选择题 2:问 RB 与 URB 的核心区别,答 Uniform Agreement。两者的 Validity、Integrity 完全相同,Agreement 两者都有,被加强的只有一致性那一条的主语。

RB 两问

第一问:P1 广播 m,P2、P3、P4 交付了,正确进程 P5 因网络故障始终没收到。答 Agreement 被违反。定义是「若某个正确进程交付了 m,则所有正确进程最终都交付 m」,P5 是正确进程却永不交付。

Validity 成立,广播者 P1 自己交付了。Integrity 也成立:没有重复,没有凭空冒出的消息。答完还要补一句模型前提:RB 建立在 perfect links 之上,题目里的永久丢包超出了这个模型,协议本身没出 bug。

第二问:P4 收到 m 后在交付前崩溃。答 Agreement 依然满足,因为 P4 是故障进程,不在 Agreement 的约束范围内,P1、P2、P3、P5 都会交付。P2、P3 各自转发过一份,P5 至少有两条独立路径拿到 m。画时间线时,P1 给 P2 到 P5 各发一条,发往 P5 的那条落空。P2、P3 收到后各自转发,P4 在收到之后、转发和交付之前打叉。P1、P2、P3、P5 各标一个交付点,P5 的落在收到转发之后。

这就是「收到即转发」存在的理由。只靠广播者单点发送,它发到一半崩溃,就会有人交付、有人永不交付,Agreement 立刻破。

一步一步看

目标:看 P4 交付前崩溃、P5 没收到原发时,四个正确进程能否都交付,Agreement 是否满足。

第二问的时间线,时间从左往右。RB 的规则是第一次收到 m 时先转发给所有人,再交付。

  1. P1 向 P2 到 P5 各发一条 m,发往 P5 的那条落空。

    第 1 步:五条进程横线,P1 向 P2、P3、P4、P5 各发一条 m,青绿标出,发往 P5 的那条是虚线并打叉

  2. P4 收到 m,还没转发、没交付就崩溃。它从此是故障进程,不在 Agreement 的约束范围内。

    第 2 步:P4 收到 m 后在转发和交付之前崩溃,崩溃标记青绿,P4 之后的线变成虚线

  3. P2、P3 收到后各自转发给所有人,P5 从两条独立路径拿到 m。

    第 3 步:P2 和 P3 各自把 m 转发给 P1、P5 和对方,六条转发箭头青绿标出,P5 收到两份转发

  4. P1、P2、P3、P5 各标一个交付点,P5 的落在收到转发之后。四个正确进程都交付,Agreement 满足。

    第 4 步:P1、P2、P3、P5 各有一个交付框,青绿标出,P5 的交付在收到转发之后,崩溃的 P4 没有交付

URB 三问

五个进程,P4、P5 在算法开始前就已崩溃。交付规则改成「收到来自至少 2 个不同进程的副本才交付」。数来源:

  • P1 有三个:自己、P2 转发、P3 转发
  • P2 有两个:P1 原发、P3 转发
  • P3 有两个:P1 原发、P2 转发

三个正确进程全部达到阈值,都能交付。第二问画时间线:P1 发往 P4、P5 的箭头落空,P4、P5 从一开始就打叉。P2、P3 收到后互相转发,也转回 P1。每个正确进程在收到第 2 份副本时标交付。Uniform Agreement 满足:P4、P5 在崩溃前没交付过任何消息。「故障进程交付了而正确进程没交付」这种破坏情形不存在,而正确进程这一侧本来就全交付了。这是对这次固定执行的判断,不是对任意崩溃时序的证明。

一步一步看

目标:看 P4、P5 开始前就崩溃时,三个正确进程能否各凑够 2 个来源,Uniform Agreement 是否满足。

第二问的时间线。交付阈值是 2 个不同来源,P1 自己那份算一个。

  1. P4、P5 开始前已崩溃。P1 广播 m,只有 P2、P3 收到。

    第 1 步:P4、P5 从一开始就是崩溃的虚线,P1 向四个进程广播 m,青绿标出,发往 P4、P5 的两条落空打叉

  2. P2、P3 收到后向所有人转发:P2 转给 P1、P3,P3 转给 P1、P2。

    第 2 步:P2、P3 各自把 m 转发给另外两个正确进程,四条转发箭头青绿标出,发往崩溃进程的转发不画

  3. 数来源:P1 有 3 份,P2、P3 各 2 份,都达到阈值,三者交付。P4、P5 没交付过任何消息,Uniform Agreement 满足。

    第 3 步:P1 来源是自己、P2、P3 共 3 份,P2、P3 各 2 份,三个交付框和来源数青绿标出,P4、P5 没有交付

重画题:步骤较长,放在下面的完整例题里逐步走。

课件里的坑

  • [课件留白] URB 那道阈值题没说广播者自己持有的那一份算不算来源。两种读法下 P1 都够 2 个,结论不变,但 P2、P3 的数法要在答卷上写明按哪种读法(p.4)。
  • [口径差异] 重画题不止一种合法答案:让 P5 在崩溃前交付 {m1, m2, m3, m4} 同样不违反任何性质,因为它交付的都是正确进程也会交付的消息。代价是要求 P5 崩得更晚、画起来更麻烦,且顺手给 P5 画上 m8 的交付就会出错——给崩溃进程补交付会引入新的 Uniform Agreement 义务,整张图都得改(p.5)。
  • [补充] 选择题 2 的四个选项里,Agreement 是最容易踩的那个。RB 与 URB 的 Validity、Integrity 完全相同,Agreement 两者都有,被加强的只有一致性那一条的主语,所以答 Uniform Agreement(p.1)。

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写三条:TOB 四条性质、Agreement 与 Uniform Agreement 的前件、判定题的第一问。再把下面的「变式题」做一遍。最后回查两处最容易错的地方:重画时漏掉 m2、给崩溃进程补上交付。三步做完再往下看答案。

必背

  1. TOB 四条标准性质:Validity、Agreement、Integrity(No Duplication + No Creation)、Total Order;FIFO Order 属于 FIFO Broadcast,不在其中。
  2. 判定题第一步永远是问「这个没交付的进程是正确进程还是故障进程」:正确进程不交付违反 Agreement,故障进程不交付不违反。
  3. 正确进程永远收不到消息属于 perfect links 假设被打破,RB 协议本身没出错;「收到即转发」是为了广播者中途崩溃时其余正确进程仍能收到。
  4. 本题固定执行中,三个正确进程都收到足够副本;不能把阈值 2 推广成任意故障模型下的 URB 充分条件,安全阈值还取决于故障上限和转发规则。
  5. 重画题解法:先定崩溃集合 → 用 Validity 补出必须被交付的消息 → 用 Uniform Agreement 把正确进程的交付集合拉齐;崩溃进程广播的消息可以无人交付。

完整例题

重画题(p.5)。原图如下:

进程 广播 交付 结局
P1 m1, m2 m1, m3 崩溃
P2 m3 m1, m3, m4 正确
P3 m4 m1, m3, m4 正确
P4 m5, m6, m7 — 广播后立即崩溃
P5 m8 m1, m3, m4 后期崩溃

问题:若 P1 没有崩溃,而 P4 与 P5 崩溃了,重画该图。

题单原图,五条进程时间线:P1 广播 m1、m2,交付 m1、m3 后崩溃;P2 广播 m3,交付 m1、m3、m4;P3 广播 m4,交付 m1、m3、m4;P4 广播 m5、m6、m7 后崩溃;P5 广播 m8,交付 m1、m3、m4,最后崩溃。红箭头是广播,蓝箭头是交付,红叉是崩溃点
图片来源:COMP5567 2026-5567-tutorial-1.docx, p.5

第一步,看原图为什么合法。m2 没有被任何人交付,这是允许的。P1 在 m2 传开之前就崩了,Validity 只约束正确进程的广播;同时没人交付过 m2,Uniform Agreement 的前件不成立。m5 到 m8 同理。

第二步,P1 变正确,Validity 生效。P1 广播的 m1 和 m2 都必须被 P1 自己交付。原图里 m2 无人交付的情形不再允许。

第三步,Uniform Agreement 生效。P1 交付 m2,P2、P3 也必须交付 m2。正确进程的交付集合统一拉齐为 {m1, m2, m3, m4}。

第四步,处理崩溃进程。m5 到 m8 仍可无人交付:广播它们的是故障进程,Validity 不保护;又确实没人交付过,Uniform Agreement 的前件不成立。最简画法是让 P4、P5 在收到任何消息前就崩溃,交付栏留空,并在旁边写明这个假设。

两个最常见的错:漏掉 m2;给 P4 或 P5 补上交付。画了 P5 交付 m8,所有正确进程就也得交付 m8,整张图都要改。

变式题(先自己做)

(自编情境)还是原图那五个进程和八条消息。这次假设只有 P4 崩溃,P1、P2、P3、P5 全部正确。正确进程的交付集合应该是什么?m5 到 m7 呢?

提示

按例题的三步走:先定崩溃集合,再用 Validity 看哪些广播者受保护,最后用 Uniform Agreement 拉齐。

建议得分点与答案(非官方评分细则)

(1) 正确进程是 P1、P2、P3、P5。Validity 要求它们交付自己广播的消息:P1 的 m1、m2,P2 的 m3,P3 的 m4,P5 的 m8。

(2) Uniform Agreement 把这些消息拉齐到每个正确进程,交付集合统一为 {m1, m2, m3, m4, m8}。

(3) m5 到 m7 仍可无人交付。P4 是故障进程,Validity 不保护它的广播;只要没人交付过,Uniform Agreement 的前件就不成立。

判分点:先写崩溃集合;点名 Validity 补出 m8;点名 Uniform Agreement 拉齐;说明 m5 到 m7 为什么可以没人交付。

闪卡自测

1. TOB 的四条标准性质是什么?FIFO Order 为什么不在其中?

Validity、Agreement、Integrity(No Duplication + No Creation)、Total Order(p.1)。FIFO Order 属于 FIFO Broadcast,和 Total Order 是两个独立维度;全序保证所有人顺序一致,但这个共同顺序不一定符合发送方自己的发送次序。两者都要满足的原语叫 FIFO Total Order Broadcast。

2. 一句话说出 Agreement 与 Uniform Agreement 的唯一差别。

前件的主语:Agreement 写「某个正确进程交付了 m」,Uniform Agreement 写「任一进程交付了 m」,包含交付完立刻崩溃的那些。后件都是「所有正确进程最终交付 m」(p.1)。

3. 选择题 2 问 RB 与 URB 的核心区别,为什么不能选 Agreement?

Agreement 两者都有,不构成区别。被加强的只有一致性那一条的主语,所以答 Uniform Agreement(p.1)。

4. 为什么需要 Uniform Agreement?

进程可能在崩溃前已经把交付结果暴露给外部——写了数据库、给用户发了确认。其他人最后都不交付的话,这个外部可见的结果就成了系统里的不一致(p.1、p.4)。

5. 正确进程 P5 因网络故障永不交付,违反了哪条性质?这算协议出 bug 吗?

违反 Agreement——P2、P3、P4 这些正确进程交付了,同为正确进程的 P5 却永不交付。不算协议 bug:RB 建立在 perfect links 之上,永久丢包超出了这个模型(p.3)。

6. RB 里「收到即转发」这一步能防住什么?

防广播者中途崩溃。只靠广播者单点发送,它发到一半崩溃就会出现一部分人交付、一部分人永不交付,Agreement 立刻被破坏;转发让传播不再依赖任何单个进程(p.3)。

7. URB 那题里 P1、P2、P3 各有几个来源?阈值改成 1 会怎样?

P1 有三个(自己、P2 转发、P3 转发),P2 与 P3 各两个,都达到阈值 2(p.4)。在题设 P4、P5 已预先崩溃、其余进程正确的执行里,阈值降到 1 不会凭空制造后续崩溃。若换成动态崩溃模型,必须结合广播与转发规则另证 Uniform Agreement。

8. 「至少 2 个不同来源」这个阈值的设计意图是什么?

等于要求消息在交付前已被至少两个进程见证过。某个进程交付后立刻崩溃,网络里也还留着副本,其余正确进程仍能凑齐阈值(p.4)。

9. 重画题里 m2 为什么在原图可以无人交付、在新图必须被交付?

原图 P1 崩溃,Validity 只保护正确进程的广播,且没人交付过 m2,Uniform Agreement 的前件不成立。新图 P1 变正确,Validity 要求它交付自己广播的 m1 和 m2,再由 Uniform Agreement 把 P2、P3 的交付集合一起拉齐到 {m1, m2, m3, m4}(p.5)。

下一步

性质那一侧背准四条定义,简答题全是点名性质加套定义,定义背不准就写不出得分点。时钟那一侧在 T01a,两张图各重算一遍。按课程进度,下一次课堂时段是 Project 介绍,组队和选题从那时开始。

下一讲 →
L04a L04a 比特币的钱存在哪:交易、UTXO 与 coinbase

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