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

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 网络、无线网这类大规模或不可靠的环境里,强交付保证要么太贵,要么根本做不到。

直觉

概率广播换了思路:保证只给到「高概率」。性质清单:

  1. Probabilistic Validity:正确进程广播消息,所有正确进程以高概率交付它。
  2. 不保证 Agreement:有可能部分正确进程交付了、另一些没有。
  3. 不保证任何顺序:全序、FIFO 都没有。
  4. 高度可扩展,对故障鲁棒。

它比 best-effort 还弱一档。best-effort 的 Validity 是确定的,这里也降成了概率。

一步一步看

目标:看节点数变大时,人人转发和 gossip 的转发次数差距有多悬殊。

拿 URB 那种「人人转发给所有人」和 gossip 比一比转发量。

  1. URB 式:每个收到的节点转给其余所有节点。n 个节点一共要转约 n² 次。
  2. gossip:每个节点只转给固定几个随机邻居。总转发次数大约是 n 乘扇出。
  3. 填进表里对比:
节点数 n URB 式约 n² 次 gossip 扇出 3 约 3n 次
10 100 30
1000 1000000 3000
  1. n 越大差距越悬殊。gossip 的代价是保证降成了概率。

怎么判断

遇到「该用哪种广播」的题,先问两件事:

  1. 节点规模多大,能不能承受人人转发给所有人?
  2. 应用能不能容忍少数节点漏收?

意思是:规模大且能容忍漏收,选概率广播;要求每个人都收到、还要一致,就得付出确定性协议的成本。

常见误解

以为概率广播至少和 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. 第 1 轮:P₁ 随机挑 3 个邻居 P₂、P₃、P₄ 发出 M。

    gossip 第 1 轮:七条时间线 P₁ 到 P₇,P₁ 广播 M,三条箭头指向 P₂、P₃、P₄,三个新收到的节点被标出,右栏写已知

  2. 第 2 轮:收到的节点再各挑邻居转发。P₂ 转给 P₅,P₃ 转给 P₆,P₄ 碰巧挑中已经收到的 P₂,那一份是重复的,丢弃。

  3. P₇ 两轮都没被任何人挑中,这一次就没收到。

    gossip 第 2 轮:P₂ 转给 P₅、P₃ 转给 P₆,被标出;P₄ 转给 P₂ 的那份是重复,空心点标着重复丢弃;P₇ 上一个空心点写着一直没被选中,右栏写没收到

  4. 再传几轮,大概率全网都收到;遇上网络分区或运气不好,像 P₇ 这样的少数节点可能永远收不到。

怎么判断

课件的对照表四项,答题时照着填:

性质 概率广播
Validity 高概率
Agreement 不保证
Total/FIFO Order 不保证
Scalability 高

意思是:gossip 只承诺「多半能传到」和「人再多也能跑」,其余一概不管。

常见误解

以为扇出 3 是协议规定的

扇出是参数。课件的例子取 3,实际系统按覆盖速度和流量去调。

以为 gossip 保证最终所有人都收到

只是高概率。分区或随机选择不走运时,少数节点可能永远收不到。

试一下

为什么 gossip 也叫 epidemic protocol?

消息在网络里的扩散方式和传染病传播一样,用同一套数学模型描述,可以算出几轮之后覆盖率大概多少。

3. 区块链怎么同时用 gossip 和全序

它解决什么问题

区块链既要在成千上万个节点间散播交易,又要求全网对账本顺序完全一致。前者要规模,后者要一致,单靠一档广播满足不了。

直觉

它分两层。P2P 网络层用 gossip 把交易和区块散出去,要的是可扩展和抗故障,偶尔漏传可以容忍,反正还会重传。共识层用全序那一档把顺序定死,要的是所有人对账本顺序完全一致。

两层解决两个问题,不是二选一。

一步一步看

目标:看一笔交易怎样先靠 gossip 散开,再靠共识层排成全网一致的顺序。

  1. 用户发起一笔交易,先交给身边几个节点。

  2. 网络层:这些节点用 gossip 层层转给随机邻居,交易很快散到大部分节点。

  3. 共识层:出块者把收到的一批交易排好顺序,打包成块。

  4. 全网按共识认下这个块,每个节点的账本顺序相同。

    区块链两层分工表格:网络层用 gossip,要传得开、扛得住故障,代价是偶尔漏传;共识层用全序广播,要全网账本顺序一致,代价是贵、和共识等价。共识层用的全序广播一格被标出

怎么判断

看到「区块链用的是哪种广播」,要分层回答:

  1. 散播消息的是哪一层?网络层,用 gossip。
  2. 定顺序的是哪一层?共识层,用全序。

意思是:只答其中一种都不完整,两层各有分工。

常见误解

以为区块链只用 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 时和共识是什么关系。

  1. 从最弱的 best-effort 起,逐档往下读,每档多一条要求。

  2. 走到 FIFO TOB,它比因果序多出「所有进程交付同一个排列」。

  3. 最后一行:FIFO TOB 与共识等价。

    广播强度链表格:Best-effort、Reliable、FIFO Order、Causal Order、FIFO TOB 从弱到强排列,每行写比上一行多了什么;最后一行共识与 FIFO TOB 等价,被标出

  4. 由等价得推论:FLP 说异步网络里只要可能有节点崩溃,就没有确定性算法能做共识;那么全序广播也一样做不到。区块链必须引入额外假设,比如同步性、随机性、算力或权益,才能绕过。

怎么判断

问「X 能不能用确定性算法在异步网络里实现」:

  1. X 是 best-effort、可靠、FIFO 或因果广播:可以,它们都在共识之下。
  2. X 是 FIFO TOB 或任何全序广播:不行,它和共识等价,FLP 适用。

意思是:链上越过因果序那一步,就跨进了共识的地界。

常见误解

以为强度链里的 FIFO TOB 就是普通 TOB

不是一个对象。链里画的是 FIFO TOB;普通 TOB 只要求全体同序,不一定守因果,不在这条链上。

以为「等价」只是「差不多强」

等价指能互相实现,所以共识的不可能结果原样搬到全序广播上。

试一下

用共识怎么实现全序广播?一句话。

对序列的每个位置逐个跑一次共识,决定这个位置放哪条消息。

5. 普通全序和因果序互不包含

它解决什么问题

强度链里因果序在 FIFO TOB 下面。那普通 TOB 和因果序呢?这是最容易答错的一处。

直觉

普通 TOB 只要求全体排列一样,不管排出来是否违反因果,可能全体一致地把回复排在原话前面。因果序反过来:守因果,但允许并发消息在不同节点顺序不同。

各有一方更严,所以谁也不包含谁。两样都要,就是 CO-TOB。

一步一步看

目标:用 A、B、C 三条消息的排列,看普通全序和因果序为什么谁也不包含谁。

  1. 先逐项对照两者。

    因果序 URB 和普通全序广播的对照表:守因果一行,因果序守、普通 TOB 不一定,这一格被标出;并发消息一行,因果序允许不同顺序、TOB 必须同一顺序;全局顺序一行,因果序不要求、TOB 要求;Uniformity 一行,因果序 URB 有,TOB 通常有

  2. 再看最小例子:P₁ 广播 A;P₂ 收到 A 后广播 B,所以 A → B;P₃ 独立广播 C。

  3. 把 A、B、C 的 6 种排列逐个检查,B 排在 A 前的 3 种违反因果。

    A、B、C 六种排列在三档下的表格:A B C、A C B、C A B 守因果;B A C、B C A、C B A 违反 A 到 B 的因果,B A C 那一格被标出;纯全序 6 种都能选,CO-TOB 只能从前 3 种里选

  4. 因果序:每个节点各自从守因果的 3 种里挑,可以挑不同的。纯全序:全体挑同一种,6 种里任意一种都行。CO-TOB:全体挑同一种,只能从那 3 种里挑。

怎么判断

判断一组交付记录属于哪一档:

  1. 有没有节点把有因果先后的两条排反了?有,就不满足因果序。
  2. 各节点的排列是否完全相同?不同,就不满足全序。
  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 保证人人收到、以为普通全序比因果序强。

必背

  1. 概率广播 / gossip 放弃确定性换可扩展性:Validity 从「确定」降为「高概率」,扇出若干个随机 peer 层层转发,少数节点可能永远收不到
  2. 区块链两层分工:网络层用 gossip 散播(要可扩展),共识层用全序定顺序(要一致)
  3. FIFO TOB 与共识等价,FLP 同样适用;TOB 不保证因果性,与因果序不可比,两者都要就是 CO-TOB
  4. 普通 TOB 不必保持因果序;FIFO TOB 在全序也约束故障进程和发送方自交付的前提下强于因果广播
  5. 因果序 / 纯全序 / 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 不一定守因果。

课件强度链:Best effort broadcast、Reliable broadcast、FIFO Order、Causal order、FIFO TOB 五个方框从左到右用标着 stronger 的箭头相连,Reliable broadcast 另有一条线直通 FIFO TOB;FIFO TOB 上方用虚线连到 consensus,虚线旁标 equivalent
图片来源:COMP5567 Lecture_3-Distributed-Broadcast.pdf, p.53
课件对照表,三列为 Property、Causal Order URB、Total Order Broadcast:Causality 一行分别是 Respected 和 Not necessarily respected;Concurrent msgs 一行是可按任意顺序交付和必须按同一顺序交付;Global order 一行是 Not required 和 Required;Uniformity 一行是 Yes (URB) 和 Yes (usually)
图片来源:COMP5567 Lecture_3-Distributed-Broadcast.pdf, p.45
提示

先分清上图和下表说的是不是同一个 TOB。

解答
  1. 等价指能互相实现:全序里第一条消息可当共识决议;对每个位置逐个跑共识,就排出全序。推论是 FLP 同样适用于全序广播。
  2. 上图是 FIFO TOB,下表是普通 TOB。普通 TOB 只要求全体同序,可能把回复排在原话前,所以不一定守因果。
  3. 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 可以插在任何位置,每个进程可能的顺序是:

  1. C、A、B
  2. A、C、B
  3. 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。

下一讲 →
T01a T01a Tutorial 1(上):两张时钟图,一步不漏地手算

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