L03 分布式广播：楼下那间可以扣住信件的传达室

一句话版

信送到传达室和信放进你信箱是两件事，能扣住信件的那段时间差，就是所有广播协议干活的地方。

新手入口：先会沿消息箭头找先后，再看本讲。学完应能解释“消息到了为什么还要等”，并用英文区分 receive 与 deliver。先懂四个动作，再背协议缩写。

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

写字楼楼下有间传达室。快递员把信送到传达室，这一步由外面的世界决定，你插不上手；传达室把信放进你的信箱、你才真正看到它，这一步由传达室的规矩决定。两件事之间有一段时间差，传达室可以把一封信先扣在架子上，等另一封先到了再一起放进去——协议的全部本事就在这段时间差里。

传达室的规矩可以一级级加严。最松是能送就送，送不到算了；严一点是只要有一个住户拿到了，就保证楼里所有还在的住户都能拿到；再严是哪怕那人当天就搬走了，这条保证也照样成立。可靠性管够之后才轮到顺序：同一个人寄来的信按寄出先后放；有人先寄了回信而原信还没到，就扣住回信等原信；最严的一档是全楼每个信箱里的排列完全一样。也有不设传达室的做法——见谁跟谁说一嘴，传得飞快，但可能有人始终没听说。

类比在哪里失效：传达室是一个中心，而这里每个节点自己就是自己的传达室，所以发送方必须先把消息发给自己、走和别人一样的交付流程，Validity 这条性质才有得陈述（p.4、p.16）。楼里谁搬走了大家看得见，模型里节点崩了看不见，「正确进程」和「任何进程」这一字之差正是 RB 和 URB 的全部区别（p.12）。还有，楼里的信基本不会丢，而 best-effort 一档的 Validity 只管发送方自己，别人收不收得到没有承诺（p.5）。

概念卡

1. send / receive / deliver 与那段时间差（Broadcast Primitives）

人话定义：broadcast 是应用请求发给所有人，send 是协议往链路塞包，receive 是协议收到包，deliver 是协议决定让应用看到它。

英文注意｜receive / deliver / delivery：前两者是动词，delivery 是名词；搭配 deliver a message to the application。题干的 delivery order 不等于 arrival order。 答题句：A process may receive a message before it is allowed to deliver it.

例子：p.3 写着 Every single word matters: broadcast, send, receive, deliver。后面所有性质——Validity、Agreement、No Duplication、No Creation、FIFO、Causal、Total——全部只约束 deliver。receive 的顺序永远是网络说了算，协议管不着，它唯一能做的就是收到之后先扣住不交，这就是 buffer。p.4 的 Deliver 定义里还有一句「包括交付给它自己」。

那段时间差画出来就是这样：

常见误解

把 receive 和 deliver 当同一件事 → 混了这两个词，Part 2 的三个排序算法就全看不懂了，因为它们做的事只有一件：把已经 receive 的消息暂时不 deliver（p.3）。另一处是以为发送方可以跳过交付流程——它必须和别人一样走一遍 deliver，否则 Validity 在它身上没法陈述（p.4）。

2. 可靠性的三级台阶与 URB 协议（Best-effort / Reliable / Uniform Reliable）

人话定义：三档的差别只在一条性质上，而且只在那条性质的一个词上。

英文注意｜correct / faulty / any：本讲 crash-stop 模型中，correct 指整个执行中不崩溃；faulty 不等于“消息内容答错”。any process 包括之后会崩溃的进程。 答题句：If any process delivers a message, all correct processes eventually deliver it. 这是 uniform agreement；eventually 是“最终”，不承诺固定秒数。

例子：best-effort = Validity + No Duplication + No Creation，缺 Agreement，所以节点之间可以有不一致的世界观，且 Validity 只管发送方自己（p.5）。Reliable = best-effort + Agreement，即「正确进程交付 ⟹ 所有正确进程交付」，漏洞是故障进程可以交付完就崩、把消息带进坟墓（p.9、p.11）。Uniform Reliable 把前件的「正确进程」换成「任何进程」，后件不变（p.12、p.14）。协议本身只有一句话：先发给自己，收到后先转发再交付，用 MJ 集合去重（p.16、p.19）。

常见误解

以为广播出去就一定会被交付 → URB 只承诺「有一个进程交付了，所有正确进程都交付」，不承诺广播的消息一定被交付，p.17 里 m3 和 m5 就是零交付的例子（p.17、p.18）。另一处是把「先转发后交付」这两步的顺序当细节 → 对调之后协议直接退化成 RB，这是 URB 区别于 RB 的实现关键（p.16）。还要记住 URB 完全不管顺序，同一发送方的两条消息在任何节点（包括发送方自己）都可能颠倒（p.19、p.22）。

3. 顺序的三档：FIFO、因果、全序（Delivery Order）

人话定义：FIFO 管同一个发送方的相对次序，因果序管「回信不能先于原信」，全序管「所有人看到的排列必须一样」。

英文注意｜causal / casual / concurrent：causal 是因果的，casual 是随意的；concurrent 在这里指没有因果先后，不要求物理时刻相同。 答题句：Causal order does not constrain the relative delivery order of concurrent messages.

英文注意｜total order / same sender：total order 比较各进程的排列；FIFO 的限定是同一发送方，不是所有发送方共用一条发送时间线。 答题句：Total order alone does not guarantee causal order.

例子：FIFO 只约束同一发送方的消息，而且只对每个节点各自成立，不同节点可以看到不同的全局顺序（p.24、p.26）；合法交付顺序数就是各发送方消息序列的交错数 (a+b+c+…)! / (a! b! c! …)，课件那道题是 5!/(2!3!) = 10 种（p.27）。因果序的 m → m′ 有三条规则：同一节点先后广播、交付后再广播、传递性（p.34）。全序只要求所有人一致，不要求哪个顺序才对（p.44、p.45）。

三档之间的强弱关系：

常见误解

以为因果序保证大家看到的一样 → 它不保证。用户 A 看 m1 m2 m3、用户 B 看 m3 m1 m2，两者都合法且互不矛盾，要所有人一致得上全序（p.53）。规则 2「交付后再广播」是 FIFO 做不到的那一条，因果序的全部额外力量都在这里（p.34）。还有一条容易漏：因果序对并发消息不作任何约束（p.34、p.53）。

4. 向量法：delivered 与 past（Vector-based CO-URB）

人话定义：每个节点维护一个 delivered_i 记「我已交付了每个人的几条」，每条消息随身带一个 m.past 记「发它的人在广播那一刻交付过每个人的几条」。

英文注意｜for every / at least / implies：∀ 是每个分量，≥ 是至少；A implies B 只表示 A ⟹ B，不能擅自反推。 答题句：Deliver the message only if every component of the local delivered vector is at least the corresponding component of the message’s past vector.

例子：交付条件 DC_i(m) 是 ∀k: delivered_i[k] ≥ m.past[k]，逐分量比较，全部满足才交付，否则进缓冲区（p.37）。m.past 不是算出来的，是抄来的——广播那一刻 m.past ← delivered_i 一次赋值，此后永不改变（p.41 第 3 行、p.38）。正确性性质：m → m′ ⟹ ∀k: m.past[k] ≤ m′.past[k] 且至少一位严格小于（p.42、p.43）。

常见误解

把交付条件里的 ≥ 记成 = → 用 ≥ 是因为并发消息会让某些分量超出，那不该构成阻塞（p.37）。第二处是把正确性性质反过来用：课件只证了「因果 ⟹ 向量有序」，反向没证，past 向量可比并不代表有因果关系（p.43、p.55）。第三处是担心自己广播的消息会卡住——它永远满足 DC，所以 p.41 第 6 行的 wait until done_i 不会死锁（p.41、p.42）。

把它们串起来

这一讲分两半，接缝在 p.20：可靠性解决「消息会不会被交付」，顺序解决「按什么次序交付」。两半共用同一个结构——排序层坐在 URB 层之上，自动继承四条可靠性性质，只需额外证明新加的那条顺序性质，换排序策略不用碰可靠性代码（p.33）。两个排序协议的骨架也完全一样：条件满足就交付、更新状态、回扫缓冲区，否则入缓冲区；差别只在条件是标量比较还是向量比较（p.32、p.41）。

时钟的分工在这里收口。FIFO TOB 有两种实现：sequencer 由单个 leader 定序（有单点问题），或用 Lamport 时钟加确定性打破平局（p.46、p.47）。选 Lamport 而不是向量，正是因为标量时钟能排出唯一全序但丢掉了并发信息，向量时钟能判因果却排不出唯一全序——全序用标量、因果用向量，各取所需（p.47）。

最后两条结论要一起记。一是强度关系并非一条直线：FIFO TOB 与共识等价，所以 FLP 不可能性同样适用，异步加可能崩溃的环境下没有确定性算法能实现全序广播（p.52）；而 TOB 并不保证因果性，它和因果序在这一维上不可比，两者都要就得上 CO-TOB。二是概率广播这条旁支——gossip 把 Validity 从「确定」降为「高概率」，扇出若干随机 peer 层层转发，少数节点可能永远收不到，换来可扩展性（p.49、p.50）。区块链分层用：网络层 gossip 散播，共识层全序定顺序（p.51、p.44）。

课件里的坑

• [课件有误] p.25 写的是「crash nodes cannot delivery any messages」，动词位置写成了名词，下一页 p.26 同一句已改成 deliver（p.25）。
• [课件留白] p.32 的 FIFO-URB 伪代码只有广播那一半，接收端的判断、入缓冲、交付后自增并回扫这一整段代码缺失，只在 p.31 以自然语言存在（p.32）。
• [课件有误] p.37 把 causal 拼成了 casual，一字之差意思完全不同，不过只是拼写，不影响理解（p.37）。
• [课件有误] p.39 有四处下标印错，部分索引问题被示例数值掩盖，照抄却会答错：delivered₂[3] < m3.past[2] 应为 delivered₂[1] < m3.past[1]；delivered₂ > m1.past 应为 ≥；delivered₃[1] = m1.past[3] 应为 m1.past[1]；delivered₃[2] = m2.past[3] 应为 m2.past[2]。p1 那一行是对的（p.39）。
• [课件有误] p.41 第 13 行写成 while ∃ m'∈ msg_set_i: if DC_i(m') do，while 和 if 混在一个头里语法不成立，应为 while ∃ m′ ∈ msg_set_i : DC_i(m′) do（p.41）。
• [概念区分] p.52 上图是 FIFO TOB，下表是普通 TOB。普通 TOB 不必保持因果序；FIFO TOB 在本课标准模型下强于因果广播，因此两处不矛盾。补充来源：Kleppmann 讲义 §4.1。

课后 10 分钟：考点复习

这 10 分钟怎么用：合上页面，先默写三条——send / receive / deliver 三个动作、三级可靠性台阶、交付条件 DC_i(m)；再把下面的「变式题」做一遍；最后回查两个最容易错的地方——把 receive 和 deliver 当同一件事、把交付条件里的 ≥ 记成 =。三步做完再往下看答案。

必背

1. send / receive / deliver 是三件事，所有性质只约束 deliver；receive 由网络说了算，协议唯一的手段是收到后先扣住不交。
2. 三级可靠性：best-effort = Validity + No Duplication + No Creation；Reliable 再加 Agreement；Uniform 把 Agreement 前件的「正确进程」换成「任何进程」。
3. URB 协议一句话：先发给自己，收到后先转发再交付，用 MJ 集合去重；把转发和交付两步对调就退化成 RB。
4. 广播了不等于会被交付：URB 只承诺「有一个进程交付了，所有正确进程都交付」。
5. FIFO 只约束同一发送方的消息，且只对每个节点各自成立；合法交付顺序数 = (a+b+c+…)! / (a! b! c! …)。
6. m → m′ 三条规则：同一节点先后广播、交付后再广播、传递性；规则 2 正是 FIFO 做不到的那一条。
7. 交付条件 DC_i(m)：∀k: delivered_i[k] ≥ m.past[k]，用 ≥ 不用 =；delivered_i 是会增长的节点状态，m.past 是广播那一刻抄下的快照。
8. FIFO TOB 与共识等价，FLP 同样适用；TOB 不保证因果性，与因果序不可比，两者都要就是 CO-TOB。

完整例题

拿课件那道四节点的向量题（p.56）走一遍。场景是 p1 广播 m11，p4 先后广播 m41 和 m42，向量按 (p1, p2, p3, p4) 排列，全体初值 (0,0,0,0)。要求写出每个事件的 delivered 和每条消息的 m.past。

第一步，先定三条消息的 past（看发送方在广播那一刻交付过什么）：

1. m11.past = (0,0,0,0)——p1 开局就广播，此前什么都没交付。
2. m41.past = (0,0,0,0)——p4 的第一条，同理。
3. m42.past = (1,0,0,1)——p4 在广播它之前已经交付了 m11（p1 的 1 条）和自己的 m41（p4 的 1 条）。

第二步，沿每条时间线从左到右推 delivered。以 p4 为例：起始 (0,0,0,0) → 广播 m41（此刻把 m41.past ← (0,0,0,0)）→ 交付自己的 m41 得 (0,0,0,1) → 交付 m11 得 (1,0,0,1) → 广播 m42（m42.past ← (1,0,0,1)）→ 交付自己的 m42 得 (1,0,0,2)。

第三步，找出唯一会卡住的那个节点。是 p3，卡住和放行两个时刻的逐分量比对如下；p1 和 p2 的到达次序不触发缓存，直接顺次交付。

补全 p1、p2：p1 广播 m11 时 past=(0,0,0,0)，随后交付自己这条得 (1,0,0,0)，交付 m41 得 (1,0,0,1)，交付 m42 得 (1,0,0,2)。p2 先交付 m41 得 (0,0,0,1)，再交付 m11 得 (1,0,0,1)，最后交付 m42 得 (1,0,0,2)。广播时复制 past，单纯接收尚未交付时不递增 delivered。

第四步，自检。四个节点最终全部收敛到 (1,0,0,2)：p1 发了 1 条、p2 和 p3 各发 0 条、p4 发了 2 条。这个不变量能发现漏记，但只核对终值不足以证明每步顺序正确。

再多想一层：这里的因果链其实有两条，m41 → m42 来自规则 1（同一节点先后广播），m11 → m42 来自规则 2（p4 交付 m11 后才广播 m42）。m42.past 的两个非零分量正好各对应一条——第 4 位的 1 是规则 1 的产物，第 1 位的 1 是规则 2 的产物。

变式题（先自己做）

English question（自编练习）：Use vector order (p1, p2, p3, p4), initially all zero. Process p2 broadcasts m21. After delivering m21, p3 broadcasts m31. Process p1 receives m31 before m21. Assume no crashes and eventual delivery of both messages.

Write both past vectors. Trace p1’s delivered vector and explain when m31 can be delivered. What is the final vector at every process?

提示

读题：trace 要逐事件推演，explain 要给理由；before 在这里修饰 receive。题目说 p1 先收到 m31，不代表先交付它。past 不含正在广播的这条消息。

建议得分点与答案（非官方评分细则）

Suggested answer: The past vectors are (0,0,0,0) and (0,1,0,0). Process p1 buffers m31 until it delivers m21. Its vector changes from (0,0,0,0) to (0,1,0,0), then to (0,1,1,0), the final vector at every process.

自检点：past 不含自己这条；解释缓存与重新检查；写出每一步，不只写终值。

(1) m21.past = (0,0,0,0)（p2 开局就广播）；m31.past = (0,1,0,0)（p3 广播前已交付 m21，那是 p2 的第 1 条）。

(2) p1 起始 delivered = (0,0,0,0)。

1. m31 到达，比对 m31.past = (0,1,0,0)：第 2 位 0 < 1，条件不满足 ⟹ 进缓冲。
2. m21 到达，比对 m21.past = (0,0,0,0)：四位全部满足 ⟹ 交付，delivered = (0,1,0,0)。
3. 重查缓冲区：(0,1,0,0) ≥ (0,1,0,0) ⟹ 放出 m31，delivered = (0,1,1,0)。

(3) 四个节点最终都收敛到 (0,1,1,0)：p2 广播 1 条、p3 广播 1 条、p1 和 p4 各 0 条，对得上。这里的因果链只有一条 m21 → m31，来自规则 2（p3 交付 m21 后才广播），所以 m31.past 只有第 2 位非零。

闪卡自测

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

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

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

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

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

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

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

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

5. 写出 URB 协议的三件事。把哪两步对调会出问题？

先把消息发给自己；收到之后先转发给所有人、再交付；用 MJ 集合去重（p.16、p.19）。把「转发」和「交付」对调，协议就退化成 RB。

6. 三个发送方分别广播了 2、3 条消息，FIFO 下合法的交付顺序有多少种？

按交错数公式 (a+b+…)!/(a! b! …) 算。课件那道题是两个发送方各 2 条和 3 条，5!/(2!3!) = 10 种（p.27）。

7. 因果序的三条规则是什么？哪一条是 FIFO 做不到的？

同一节点先后广播、交付后再广播、传递性（p.34）。规则 2 是 FIFO 做不到的那一条——FIFO 只约束同一发送方，管不了「B 交付了 A 的消息之后才发的那条」。

8. 写出交付条件 DC_i(m)。为什么是 ≥ 而不是 =？

∀k: delivered_i[k] ≥ m.past[k]（p.37）。用 ≥ 是因为并发消息会让 delivered_i 的某些分量超出 m.past，那种超出不该构成阻塞。

9. delivered_i 和 m.past 的区别是什么？后者怎么来的？

delivered_i 是节点状态、会随交付增长；m.past 是消息标签，广播那一刻 m.past ← delivered_i 一次赋值，此后永不改变（p.37、p.41 第 3 行）。

10. FIFO TOB 的两种实现各是什么？为什么全序用标量时钟而因果用向量时钟？

sequencer 由单个 leader 定序（存在单点），或用 Lamport 时钟加确定性打破平局（p.46、p.47）。标量时钟能排出唯一全序但丢掉并发信息，向量时钟能判因果却排不出唯一全序，所以各用各的（p.47）。

11. TOB 和共识是什么关系？TOB 保证因果性吗？

FIFO TOB 与共识等价，所以 FLP 同样适用——异步加可能崩溃的环境下没有确定性算法能实现全序广播（p.52）。TOB 不保证因果性，与因果序不可比，两者都要就是 CO-TOB。

12. gossip 放弃了什么、换来了什么？区块链怎么同时用它和全序广播？

把 Validity 从「确定」降为「高概率」，扇出若干个随机 peer 层层转发，少数节点可能永远收不到，换来的是可扩展性（p.49、p.50）。区块链分层用：网络层 gossip 散播，共识层全序定顺序（p.51、p.44）。

下一讲

下一讲回到具体系统，看比特币怎么在一个谁都能进的开放网络里，用算力抽签替代前面这些点名式的协议来决定谁说了算。