L03b-4 交付顺序(四):gossip,以及各档广播的强弱
gossip 用概率换规模;区块链把 gossip 和全序叠起来用;从 best-effort 到 FIFO TOB 的强度链,FIFO TOB 与共识等价,普通全序和因果序互不包含。
一句话版
gossip 让每个节点随机转给几个邻居,换来大网络里也跑得动,代价是少数节点可能永远收不到。把本讲所有广播排成一条强度链,顶端的 FIFO TOB 和共识等价;普通全序和因果序则谁也不包含谁。
读之前最好先懂 L03b-2 的因果序和 L03b-3 的全序。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 概率广播 | probabilistic broadcast | 高概率送到,不打包票 |
| gossip | 传闲话式广播,也叫流行病协议(epidemic protocol) | 随机挑几个邻居转发,层层扩散 |
| 扇出 | fanout | 每个节点每次转给几个邻居 |
| CO-TOB | Causal Order + TOB,因果全序广播 | 既守因果,又要全体排列一样 |
| 共识 | consensus | 一群节点对一个值达成一致 |
| FLP | 三位作者 Fischer、Lynch、Paterson 的首字母 | 异步网络里只要可能有节点崩溃,确定性算法保证不了共识 |
一个类比:小区里传消息
前几页的协议像物业挨家挨户敲门通知,每家都要确认收到。楼少的时候可以,小区一大,物业跑断腿。
gossip 像邻居之间传话。你听到一件事,随手告诉三个人,他们再各告诉三个人。传得飞快,也不用谁来管。可总有一两户恰好没人告诉,一直不知道。
类比在哪里失效:
- 邻居传漏了会补问。gossip 协议本身不补,漏掉的节点就一直不知道。
- 传话会走样。这里转发的是原样消息,内容不变,只是送不送得到靠运气。
从零讲起
1. 为什么要放弃确定性
它解决什么问题
前面几种广播都给确定的保证。它们的实现靠每个节点收到消息后转发给所有人,一条消息就要 O(n²) 次转发。节点上万,网络就扛不住了。
P2P 网络、无线网这类大规模或不可靠的环境里,强交付保证要么太贵,要么根本做不到。
直觉
概率广播换了思路:保证只给到「高概率」。性质清单:
- Probabilistic Validity:正确进程广播消息,所有正确进程以高概率交付它。
- 不保证 Agreement:有可能部分正确进程交付了、另一些没有。
- 不保证任何顺序:全序、FIFO 都没有。
- 高度可扩展,对故障鲁棒。
它比 best-effort 还弱一档。best-effort 的 Validity 是确定的,这里也降成了概率。
一步一步看
目标:看节点数变大时,人人转发和 gossip 的转发次数差距有多悬殊。
拿 URB 那种「人人转发给所有人」和 gossip 比一比转发量。
- URB 式:每个收到的节点转给其余所有节点。n 个节点一共要转约 n² 次。
- gossip:每个节点只转给固定几个随机邻居。总转发次数大约是 n 乘扇出。
- 填进表里对比:
| 节点数 n | URB 式约 n² 次 | gossip 扇出 3 约 3n 次 |
|---|---|---|
| 10 | 100 | 30 |
| 1000 | 1000000 | 3000 |
- n 越大差距越悬殊。gossip 的代价是保证降成了概率。
怎么判断
遇到「该用哪种广播」的题,先问两件事:
- 节点规模多大,能不能承受人人转发给所有人?
- 应用能不能容忍少数节点漏收?
意思是:规模大且能容忍漏收,选概率广播;要求每个人都收到、还要一致,就得付出确定性协议的成本。
常见误解
以为概率广播至少和 best-effort 一样强
更弱。best-effort 的 Validity 是确定的,概率广播的 Validity 只是高概率。
以为「高概率」就等于「一定」
答题时别写成 guaranteed。课件明确写了少数节点可能永远收不到。
试一下
概率广播保证哪几条、放弃哪几条?
保证高概率的 Validity 和可扩展性;放弃确定的 Validity、Agreement、全序和 FIFO。
2. gossip 怎么传
它解决什么问题
概率广播要有一个具体的做法。gossip 就是最常见的那个:转给一个随机子集,靠层层转发覆盖全网。
从哪来(补充)
gossip 的经典早期工作是 Demers、Greene、Hauser、Irish、Larson 等人 1987 年在 PODC 发表的《Epidemic algorithms for replicated database maintenance》,他们用传染病扩散的方式在副本数据库之间传播更新。出处:Gossip protocol(Wikipedia)。
直觉
每个进程把收到的消息转发给其他进程的一个随机子集。时间一长,消息「感染」网络的大部分。别名 epidemic(流行病)就是这么来的:消息传播和传染病扩散用的是同一套数学模型。
扇出是可调的参数。扇出越大,覆盖越快、漏收概率越低,流量也越大。
一步一步看
目标:看 gossip 转几轮后消息覆盖到哪些节点,以及为什么仍可能有节点漏收。
P₁ 用 gossip 广播 M,扇出取 3。
-
第 1 轮:P₁ 随机挑 3 个邻居 P₂、P₃、P₄ 发出 M。
-
第 2 轮:收到的节点再各挑邻居转发。P₂ 转给 P₅,P₃ 转给 P₆,P₄ 碰巧挑中已经收到的 P₂,那一份是重复的,丢弃。
-
P₇ 两轮都没被任何人挑中,这一次就没收到。
-
再传几轮,大概率全网都收到;遇上网络分区或运气不好,像 P₇ 这样的少数节点可能永远收不到。
怎么判断
课件的对照表四项,答题时照着填:
| 性质 | 概率广播 |
|---|---|
| Validity | 高概率 |
| Agreement | 不保证 |
| Total/FIFO Order | 不保证 |
| Scalability | 高 |
意思是:gossip 只承诺「多半能传到」和「人再多也能跑」,其余一概不管。
常见误解
以为扇出 3 是协议规定的
扇出是参数。课件的例子取 3,实际系统按覆盖速度和流量去调。
以为 gossip 保证最终所有人都收到
只是高概率。分区或随机选择不走运时,少数节点可能永远收不到。
试一下
为什么 gossip 也叫 epidemic protocol?
消息在网络里的扩散方式和传染病传播一样,用同一套数学模型描述,可以算出几轮之后覆盖率大概多少。
3. 区块链怎么同时用 gossip 和全序
它解决什么问题
区块链既要在成千上万个节点间散播交易,又要求全网对账本顺序完全一致。前者要规模,后者要一致,单靠一档广播满足不了。
直觉
它分两层。P2P 网络层用 gossip 把交易和区块散出去,要的是可扩展和抗故障,偶尔漏传可以容忍,反正还会重传。共识层用全序那一档把顺序定死,要的是所有人对账本顺序完全一致。
两层解决两个问题,不是二选一。
一步一步看
目标:看一笔交易怎样先靠 gossip 散开,再靠共识层排成全网一致的顺序。
-
用户发起一笔交易,先交给身边几个节点。
-
网络层:这些节点用 gossip 层层转给随机邻居,交易很快散到大部分节点。
-
共识层:出块者把收到的一批交易排好顺序,打包成块。
-
全网按共识认下这个块,每个节点的账本顺序相同。
怎么判断
看到「区块链用的是哪种广播」,要分层回答:
- 散播消息的是哪一层?网络层,用 gossip。
- 定顺序的是哪一层?共识层,用全序。
意思是:只答其中一种都不完整,两层各有分工。
常见误解
以为区块链只用 gossip
gossip 只负责散播,不保证顺序也不保证人人收到。账本顺序靠共识层定。
以为共识层排好顺序就不用 gossip 了
共识层排好的块还要送到所有节点手里,靠的仍是网络层的 gossip。
试一下
网络层偶尔漏传一笔交易,为什么区块链不太在乎?
漏传可以靠重传补上,而且交易最终以共识层认下的块为准,网络层只要「多半传得开」就够了。
4. 强度链:从 best-effort 到共识
它解决什么问题
本讲讲了一串广播,需要一张图说清谁比谁强,以及最强的那一档和共识是什么关系。
从哪来(补充)
全序广播和共识等价,这一结论来自 Chandra 与 Toueg 1996 年的论文《Unreliable failure detectors for reliable distributed systems》;Fischer、Lynch、Paterson 1985 年证明的 FLP 不可能性因此同样适用于全序广播。出处:Atomic broadcast(Wikipedia)。
FIFO TOB 强于因果广播,Kleppmann 的剑桥讲义《Distributed Systems》§4.1 的广播层级图(Slide 85)也这样画,证明留作该节的 Exercise 15。出处:Kleppmann《Distributed Systems》讲义。
这条结论要两个前提。第一,发送方也交付自己广播的消息,全序对这些自交付同样生效,讲义原话是「This includes a node’s deliveries to itself」。第二,全序约束对所有进程生效,包括后来崩溃的进程,讲义的写法是「一个节点上 m1 先于 m2 交付,所有节点上都如此」。课件给全序广播列的 Agreement 和 Total order 只约束正确进程,按这个字面定义,因果链经过一个故障进程时可能断开。全序性质有 uniform(故障进程也受约束)和非 uniform(只约束正确进程)两种写法,区别见 Défago 等人的全序广播综述 §2.3。
直觉
强度链一档比一档多一条要求:Best-effort → Reliable → FIFO Order → Causal Order → FIFO TOB。最后 FIFO TOB 与共识等价。
等价的意思是能互相实现。能做全序广播,就能做共识:拿全序里的第一条消息当决议。能做共识,就能做全序广播:对序列的每个位置逐个跑共识,决定放哪条消息。
为什么 FIFO TOB 强于因果?同一发送方的先后由 FIFO 保住。进程先交付 m 再广播 m′,它本地 m 在 m′ 前,全序又要求所有进程照这个顺序排。这两类关系传递下去,就得到因果顺序。
这段推导默认广播 m′ 的进程之后也交付了 m′,而且全序约束到它。换成课件那种只约束正确进程的字面定义,可以构造反例:故障进程 p 交付了 m,没有任何正确进程交付 m,p 接着广播 m′ 然后崩溃,正确进程交付了 m′,却始终没交付 m。课件列的四条性质都没被违反,因果序被破坏了。
一步一步看
目标:看广播一档档加要求,走到最强的 FIFO TOB 时和共识是什么关系。
-
从最弱的 best-effort 起,逐档往下读,每档多一条要求。
-
走到 FIFO TOB,它比因果序多出「所有进程交付同一个排列」。
-
最后一行:FIFO TOB 与共识等价。
-
由等价得推论:FLP 说异步网络里只要可能有节点崩溃,就没有确定性算法能做共识;那么全序广播也一样做不到。区块链必须引入额外假设,比如同步性、随机性、算力或权益,才能绕过。
怎么判断
问「X 能不能用确定性算法在异步网络里实现」:
- X 是 best-effort、可靠、FIFO 或因果广播:可以,它们都在共识之下。
- X 是 FIFO TOB 或任何全序广播:不行,它和共识等价,FLP 适用。
意思是:链上越过因果序那一步,就跨进了共识的地界。
常见误解
以为强度链里的 FIFO TOB 就是普通 TOB
不是一个对象。链里画的是 FIFO TOB;普通 TOB 只要求全体同序,不一定守因果,不在这条链上。
以为「等价」只是「差不多强」
等价指能互相实现,所以共识的不可能结果原样搬到全序广播上。
试一下
用共识怎么实现全序广播?一句话。
对序列的每个位置逐个跑一次共识,决定这个位置放哪条消息。
5. 普通全序和因果序互不包含
它解决什么问题
强度链里因果序在 FIFO TOB 下面。那普通 TOB 和因果序呢?这是最容易答错的一处。
直觉
普通 TOB 只要求全体排列一样,不管排出来是否违反因果,可能全体一致地把回复排在原话前面。因果序反过来:守因果,但允许并发消息在不同节点顺序不同。
各有一方更严,所以谁也不包含谁。两样都要,就是 CO-TOB。
一步一步看
目标:用 A、B、C 三条消息的排列,看普通全序和因果序为什么谁也不包含谁。
-
先逐项对照两者。
-
再看最小例子:P₁ 广播 A;P₂ 收到 A 后广播 B,所以 A → B;P₃ 独立广播 C。
-
把 A、B、C 的 6 种排列逐个检查,B 排在 A 前的 3 种违反因果。
-
因果序:每个节点各自从守因果的 3 种里挑,可以挑不同的。纯全序:全体挑同一种,6 种里任意一种都行。CO-TOB:全体挑同一种,只能从那 3 种里挑。
怎么判断
判断一组交付记录属于哪一档:
- 有没有节点把有因果先后的两条排反了?有,就不满足因果序。
- 各节点的排列是否完全相同?不同,就不满足全序。
- 两条都满足才是 CO-TOB。
意思是:两个问题分开问,答案组合起来就是档位。
常见误解
以为全序比因果序强
普通 TOB 不守因果,两者不可比。比因果序强的是 FIFO TOB,不是普通 TOB。
以为两者只在并发消息上有分歧
普通 TOB 对有因果关系的消息也未必保持因果顺序,分歧不止在并发消息上。
试一下
P₁、P₂、P₃ 全都按 B A C 交付。满足全序吗?满足因果序吗?
满足全序,全体一样。不满足因果序,B 排在了 A 前面。
把它们串起来
前几页的协议都给确定的保证,代价是每条消息要人人转发给所有人。gossip 换了个方向:随机挑几个邻居转发,保证降成高概率,换来的是节点再多也跑得动。
区块链两样都要。网络层用 gossip 散播交易和区块,共识层用全序定出账本顺序,两层各管一件事。
把所有广播排成一条链,每往上一档多一条要求,顶端的 FIFO TOB 和共识等价。等价带来一个坏消息:FLP 的不可能结果同样落在全序广播头上,区块链只能靠额外假设绕过去。
最后一个容易混的点在链外:普通全序只管一致不管因果,因果序只管因果不管一致,两者互不包含,都要就是 CO-TOB。
课件里的坑
- [概念区分] p.53 强度链里的是 FIFO TOB,p.45 对照表里的是普通 TOB。表里「不保证因果序」说的是普通 TOB,与必背 3 一致;FIFO TOB 在全序也约束故障进程和发送方自交付的前提下强于因果广播。读这两页时别把两者混成一个。
- [课件留白] p.50 只说概率广播用于大规模网络,没点明它比 best-effort 还弱:best-effort 的 Validity 是确定的,这里降成了概率。
- [课件留白] p.51 的扇出 3 只是例子里的取值,课件没说明它是可调参数。扇出越大覆盖越快、流量越大。
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写概率广播的四项性质和 gossip 的转发过程,再把强度链从 best-effort 一路写到共识。然后做课件例题,重点是 A→B 加并发 C 那道比较题。最后回查两个最容易错的地方:以为 gossip 保证人人收到、以为普通全序比因果序强。
必背
- 概率广播 / gossip 放弃确定性换可扩展性:Validity 从「确定」降为「高概率」,扇出若干个随机 peer 层层转发,少数节点可能永远收不到
- 区块链两层分工:网络层用 gossip 散播(要可扩展),共识层用全序定顺序(要一致)
- FIFO TOB 与共识等价,FLP 同样适用;TOB 不保证因果性,与因果序不可比,两者都要就是 CO-TOB
- 普通 TOB 不必保持因果序;FIFO TOB 在全序也约束故障进程和发送方自交付的前提下强于因果广播
- 因果序 / 纯全序 / CO-TOB 在「A→B 加并发 C」这个最小例子上分别允许 3 种(各进程可不同)、6 种(全体必须相同)、3 种(全体必须相同)
课件例题
例 1(课件 p.51):P1 用 gossip 广播 M,四项性质各是什么
题面:P1 把 M 发给 3 个随机邻居,每个收到者再转给 3 个随机邻居,如此几轮。填出 Validity、Agreement、Total/FIFO Order、Scalability 四项。
提示
想想随机选择会漏掉谁,以及有没有谁在排顺序。
解答
| 性质 | 概率广播 |
|---|---|
| Validity | 高概率 |
| Agreement | 不保证 |
| Total/FIFO Order | 不保证 |
| Scalability | 高 |
几轮后大概率全网收到;网络分区或随机选择不走运时,少数节点可能永远收不到。
例 2(课件 p.53、p.45):读强度链和对照表
题面:课件的强度链(下面第一张图),最后 FIFO TOB 与共识标「equivalent」;另一页的表对照 Causal Order URB 和 Total Order Broadcast(下面第二张图)。说明等价的含义,以及表里为什么说 TOB 不一定守因果。
提示
先分清上图和下表说的是不是同一个 TOB。
解答
- 等价指能互相实现:全序里第一条消息可当共识决议;对每个位置逐个跑共识,就排出全序。推论是 FLP 同样适用于全序广播。
- 上图是 FIFO TOB,下表是普通 TOB。普通 TOB 只要求全体同序,可能把回复排在原话前,所以不一定守因果。
- FIFO TOB 多了同一发送方保序,在全序也约束故障进程和发送方自交付的前提下强于因果广播。两处说的对象不同,不矛盾。
例 3(课件 p.46):A → B 加并发 C,因果序和全序各允许哪些顺序
题面:P1 广播 A;P2 收到 A 后广播 B;P3 独立广播 C。因果序 URB 下每个进程可能的交付顺序填三个空;再说明全序广播下的情况。
提示
只有一条因果边 A → B,C 可以插在任何位置。全序看的是全体是否相同。
解答
因果序三个空:C、A、B;A、C、B;A、B、C。全序下所有进程按同一顺序交付,例如全体 A、C、B,或全体 C、A、B。完整推演见下方完整例题。
完整例题
课件 p.46 的场景:P1 广播 A;P2 收到 A 后广播 B,所以 A → B;P3 独立广播 C,与 A、B 都没有因果关系。分别写出因果序、纯全序、CO-TOB 下的情况。
第一步,画出因果关系。只有一条边 A → B,来自规则「交付后再广播」(P2 交付 A 后才广播 B)。C 与 A、B 并发。
第二步,因果序 URB。约束只有一条:A 在 B 前。C 可以插在任何位置,每个进程可能的顺序是:
- C、A、B
- A、C、B
- A、B、C
各进程可以选不同的一种,例如 P1 按 A、B、C,P3 按 C、A、B。B、A、C 之类全部非法,因为 B 跑到了 A 前面。
第三步,纯全序。所有进程必须按同一顺序交付。课件举了两种:全局顺序是 A、C、B,或者 C、A、B。单看全序的定义,3! = 6 种排列都可以选,包括把 B 排在 A 前面的那几种,只要全体一样。
第四步,汇总对比。
| 广播 | 允许几种 | 各进程必须相同吗 |
|---|---|---|
| 因果序 | 3 种 | 不必 |
| 纯全序 | 6 种 | 必须 |
| CO-TOB | 3 种 | 必须 |
再多想一层:表里第一行和第二行谁也不包含谁。因果序排除了 B 在 A 前,全序没排除;全序要求全体一致,因果序不要求。两样都要,就是第三行的 CO-TOB:只能从守因果的 3 种里挑一种,全体照办。这道题和课件开头那个聊天例子是同一个结构,它是能一次区分因果、全序和两者兼得的最小例子。
变式题(先自己做)
变式|自编情境:P1 先后广播 X、Y;P2 收到 X 后广播 Z,与 Y 没有因果关系。
(1) 因果序下每个进程可能的交付顺序有哪些?(2) 某系统让所有进程都按 Z、X、Y 交付,它满足全序吗?满足因果序吗?(3) CO-TOB 下有几种可选的全局顺序?
提示
先画因果边:同一节点先后广播是一条,交付后再广播是另一条。再把 X、Y、Z 的 6 种排列逐个对照。
判分点与答案
(1) 因果边有两条:X → Y(同一节点先后广播),X → Z(交付后再广播)。Y 和 Z 并发。X 必须排第一,剩下两种:X、Y、Z 和 X、Z、Y。
(2) 满足全序:全体一致。不满足因果序:Z 排在 X 前,违反 X → Z。这正是普通 TOB 不保证因果的例子。
(3) 2 种:X、Y、Z 或 X、Z、Y,选定一种全体照办。
判分点:两条因果边各标出来源规则;指出 Y 与 Z 并发;第 (2) 问分开回答全序和因果两个性质。
闪卡自测
1. gossip 放弃了什么、换来了什么?
Validity 降为高概率,Agreement 和顺序都不保证;换来可扩展性和对故障的耐受。少数节点可能永远收不到。
2. 概率广播和 best-effort 谁弱?
概率广播更弱。best-effort 的 Validity 是确定的,概率广播的只是高概率。
3. 扇出调大有什么影响?
覆盖更快、漏收概率更低,流量也更大。
4. 区块链怎么同时用 gossip 和全序广播?
网络层用 gossip 散播,共识层用全序定顺序,分层分工。
5. 写出 p.53 的强度链。
Best-effort → Reliable → FIFO Order → Causal Order → FIFO TOB,FIFO TOB 与共识等价。
6. TOB 和共识是什么关系?有什么推论?
FIFO TOB 与共识等价,所以 FLP 同样适用:异步加可能崩溃时,没有确定性算法能实现全序广播。
7. 普通 TOB 保证因果序吗?两者什么关系?
不保证。两者不可比,因果序允许各节点顺序不同,TOB 允许违反因果;都要就是 CO-TOB。
8. A → B 加并发 C,因果序、纯全序、CO-TOB 各允许几种?
3 种(各进程可不同)、6 种(全体必须相同)、3 种(全体必须相同)。
下一讲
下一讲 L04a 回到具体系统,看比特币怎么在一个谁都能进的开放网络里,用算力抽签决定谁说了算;它的网络层正是本页讲的 gossip。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。