Lecture 6: Gossip Protocols — 流言协议（Epidemic Protocol）
Lecture 6: Gossip Protocols — 流言协议（Epidemic Protocol）
讲义对应：CS 425 FA2026 “Gossiping”（讲义文件
L4.FA26.pdf，34 页；课堂标注版L4.FA26-annotated.pdf；FA2025 同主题版本L5.FA25.pdf，32 页）。本笔记在全课程中编号为第 6 讲。 教材对应：Coulouris, Distributed Systems: Concepts and Design 5th Ed. Ch. 4（进程间通信与多播）、Ch. 15（副本维护与流行病式传播）；补充：Demers et al., Epidemic Algorithms for Replicated Database Maintenance, PODC 1987；Karp, Schindelhauer, Shenker, Vöcking, Randomized Rumor Spreading, FOCS 2000。 阅读材料：讲义引用的流行病学经典 [Bailey 75]；可靠多播 ACK/NAK 开销的结论 [Birman99]。
6.1 概述
本讲要解决的问题是多播（Multicast）：如何把一条消息可靠、快速地送达一组进程。中心化发送者存在带宽瓶颈，树状多播（SRM/RMTP）虽然能保证 100% 送达，却要付出 $O(N)$ 的 ACK/NAK 控制开销，并且对树结构的破坏极其敏感。本讲引入第三条道路——流行病式多播（Epidemic Multicast），也就是现在通称的 Gossip 协议：每个节点周期性地随机挑选少量对端交换信息，像传染病一样把消息扩散到全网。
它的思想转折点在于放弃确定性保证：gossip 不承诺”100% 送达”，只承诺”以高概率在 $O(\log N)$ 轮内送达几乎所有人”。用这一点点确定性换来的，是没有中心、没有固定结构、只需部分成员视图、任意比例节点故障都能继续工作的可扩展性与容错性。这一”概率换规模”的思路是整门课最重要的设计范式之一，也是后面故障检测（Lecture 7 的 SWIM）与键值存储（Lecture 9/10 的 Cassandra、Dynamo 的成员管理与反熵修复）的直接基础。
6.2 核心概念与分布式机制图解
6.2.1 多播问题（Multicast Problem）
- 定义与目的：多播 = 把一条消息发送给一个进程组中的所有成员。对它的两个硬性需求是：
- 可靠性（Reliability / Atomicity）：理想情况下 100% 的组成员都收到；至少也要保证”要么都收到、要么都可被修复”。
- 速度（Speed）：消息要尽快到达，吞吐不能被组成员数拖死。
- 直观解释（”它是什么？”）：就像一个办公室要给 300 名员工发同一份通知。方案 A 是秘书挨个打电话（中心化，秘书累死）；方案 B 是建立一个”谁通知谁”的树（树状多播，结构一断就有人收不到）；方案 C 是只告诉身边几个人，让每个人再各自告诉几个还没听说的人——这就是 gossip，”办公室八卦”式的传播。
- 机制图解：三种方案的拓扑与代价对比。
+------------------------+ +------------------------+ +------------------------+
| (a) 中心化 unicast | | (b) 树状多播 SRM/RMTP | | (c) 流行病 gossip |
| S ──▶ P1 | | S | | P0 ──▶ 2 个随机节点 |
| S ──▶ P2 | | / \ | | 每个收到的人再各自 |
| S ──▶ P3 | | P1 P2 | | 随机告诉 2 个节点 |
| S ──▶ P4 | | / \ / \ | | （没有固定结构） |
| | | P3 P4 P5 P6 | | |
+------------------------+ +------------------------+ +------------------------+
发送者带宽 O(N) 先生成树，再沿树分发 每节点每轮 O(1) 条消息
发送者 = 单点故障 用 ACK/NAK 修复丢包 每轮有大量备选路径
延迟 = 串行发送时间 控制开销 O(N) [Birman99] 延迟 O(log N) 轮（高概率）
最坏：发送者崩溃→全网失联 最坏：内部节点崩溃→子树失联 最坏：漏极少数节点（需反熵）
- 关键假设与系统模型：多播组规模 $N$（从几十到百万级）；成员关系可以完整已知（中心化、树状），也可以是部分成员视图（partial view）（gossip 必需且充分）；进程可能崩溃、消息可能丢失；不要求同步时钟，只要求”轮”（gossip period）这个本地节奏。
6.2.2 树状可靠多播与它的天花板（SRM / RMTP）
- 定义与目的：先在组成员之间建立一棵生成树（spanning tree），用树来分发多播消息；再用确认机制修补丢失的消息。
- 两种修补机制：
- SRM（Scalable Reliable Multicast）：用 NAK（否定确认，”我没收到”）。NAK 的好处是丢包少时几乎没有反馈流量；坏处是丢包一多，NAK 会同时涌向发送者，形成 NAK 风暴（NAK storm）。SRM 的对策是给每个 NAK 加随机延迟并用指数退避错开重传请求。（讲义在此处留了一个课堂梗：”为什么 SRM 被称作一个 talented 协议？”关键就在 NAK + 随机延迟/退避这两个设计要点上。）
- RMTP（Reliable Multicast Transport Protocol）：用 ACK（肯定确认），但 ACK 只发给指定接收者（designated receivers），再由它们负责重传缺失的多播消息，从而把确认流量收敛到局部。
- 天花板：这些协议仍然产生 $O(N)$ 的 ACK/NAK 开销（[Birman99]）。更致命的是结构脆弱性：树中任何一个内部节点崩溃，它下面整棵子树都收不到消息，必须先重建树才能继续。
这就是讲义提出”第三种方案”的动机：能不能不要结构、不要确认、不要全组成员列表？
6.2.3 流行病学模型：S、I、R 三态（Epidemic Model）
- 定义与目的：借自流行病学（ Epidemiology）的抽象 [Bailey 75]。把每个进程看作人群中的个体，把”消息”看作传染病，则每个个体在任何时刻处于三种状态之一：
| 状态 | 名称 | 在 gossip 中的含义 |
|---|---|---|
| $S$ | Susceptible（易感） | 还没有收到这条消息 |
| $I$ | Infective（感染） | 已收到消息，并且正在把消息传播出去（”hot”） |
| $R$ | Removed（移除 / 免疫） | 已收到消息，但已停止传播（”cold”） |
- 机制图解（状态转换图）：
感染接触：β = b/n（单位时间“感染-易感”节点对的接触率）
┌──────────────────────────────────────────────────────────┐
│ ▼
+-------------+ S─I 接触，传染 +-------------+ γ 恢复 +-------------+
| S | ────────────────▶ | I | ─────────▶ | R |
| 易感 | | 感染中 | | 移除/免疫 |
| （不知道） | | （知道且传播）| | （知道但不传） |
+-------------+ +-------------+ +-------------+
│ ▲
└──┘ 自环：一轮里 I 会接触 b 个随机节点
· anti-entropy（反熵） : γ = 0，节点一旦知道就永远传播 ⇒ 只会收敛到“全员知道”
· rumor mongering（流言）: γ > 0，节点在若干次“白费口舌”后变冷 ⇒ 可能提前熄火
- 关键假设与系统模型：$n+1$ 个个体均匀混合（mixing homogeneously）——任意两个个体接触的机会均等，等价于”成员视图是全网均匀随机采样”，也就是逻辑上的完全图。初始时刻 $x_0=n$（$n$ 个易感）、$y_0=1$（1 个感染），且恒有 $x+y=n+1$。感染-易感接触会让后者变成感染，并且（在 SIR 的经典设定里）一旦感染就永久感染；这正是讲义里 $y$ 只增不减的原因。
6.2.4 数学分析（一）：从 SIR 微分方程到 $O(\log n)$ 轮
这是本讲最核心的理论部分。记 $x$ 为易感人数、$y$ 为感染人数，接触率 $\beta$ 的含义是：单位时间内一个感染节点与任意一个特定节点发生接触的概率。若每个感染节点每轮接触 $b$ 个随机节点，则对某一对节点而言 $\beta = b/n$（这一点很关键，下面的所有结论都建立在它之上）。
第一步：写出微分方程。 新增感染的数量正比于”感染-易感”配对数 $xy$：
\[\frac{dx}{dt} = -\beta x y, \qquad x+y = n+1,\qquad x(0)=n,\ y(0)=1.\]第二步：说明 $y$ 满足逻辑斯谛（logistic）增长。 代入 $x = (n+1)-y$：
\[\frac{dy}{dt} = \beta\,(n+1-y)\,y = \beta y\big((n+1)-y\big).\]这就是标准的逻辑斯谛方程：当 $y \ll n+1$ 时 $\frac{dy}{dt}\approx \beta(n+1)y$，是指数增长（这正是 gossip 前几轮”爆炸式扩散”的数学形式）；当 $y$ 逼近 $n+1$ 时增长率趋于 0，曲线变成 S 形并饱和——因为”找不到还没被感染的人了”。
第三步：解方程（讲义留了 “can you derive it?”）。 分离变量：
\[\frac{dx}{x(x-(n+1))} = \beta\,dt \;\Longrightarrow\; \frac{1}{n+1}\Big[\ln\big((n+1)-x\big)-\ln x\Big] = \beta t + C .\]用初值 $x(0)=n$ 定出 $\frac{(n+1)-x(0)}{x(0)} = \frac{1}{n}$，于是
\[\boxed{\;x(t)=\frac{n(n+1)}{n+e^{\beta(n+1)t}},\qquad y(t)=\frac{n+1}{1+n\,e^{-\beta(n+1)t}}\;}\]两个解互补：$x+y=n+1$ 恒成立（可自行代入验证）。
第四步：代入 $\beta=b/n$，算出 $t=c\log n$ 时的覆盖情况。 取 $t = c\log n$，则 $\beta(n+1)t \approx bc\log n$，故 $e^{\beta(n+1)t}\approx n^{bc}$：
\[y(c\log n) = \frac{n+1}{1+n\,e^{-bc\log n}} = \frac{n+1}{1+n^{1-bc}} \;\approx\; n\quad(\text{当 } bc>1),\] \[x(c\log n)=\frac{n(n+1)}{n+n^{bc}}\approx \frac{n}{1+n^{bc-1}}\;\approx\; n^{\,2-bc}.\]第二式就是讲义的可靠性结论：在 $c\log n$ 轮内，除约 $n^{2-cb}$ 个节点之外的所有节点都收到了消息。取 $c,b$ 为与 $n$ 无关的小常数，例如令 $cb\ge 3$，则未覆盖的期望节点数为 $n^{2-cb}\le 1/n$，由马尔可夫不等式 $\Pr[\text{存在未覆盖节点}] \le \mathbb{E}[\text{未覆盖数}] \le 1/n$。同时每个节点发送的消息不超过 $cb\log n$ 条，全网总消息数为 $O(n\log n)$——注意这个数字不是白来的，它的主导项恰恰是最后那几个节点（见 6.2.7）。
第五步：为什么 $\log N$ 算”低延迟”。 $\log N$ 在理论上不是常数，但它增长得极慢：$\log_2 1000\approx 10$，$\log_2 10^6\approx 20$，$\log_2 10^9\approx 30$，全部 IPv4 地址（$2^{32}$）也只要 32，IPv6 是 128。若 gossip 周期是 1 秒，1000 个节点约 10 秒收敛、100 万个节点约 20 秒收敛——节点数增大 1000 倍，延迟只增加 10 秒，这就是 gossip 可扩展性的来源。
轮次演化的直观图（每个知情节点每轮把消息交给 1 个随机节点，知情人数每轮翻倍）：
轮 0 |# | i = 1
轮 1 |## | i = 2
轮 2 |#### | i = 4
轮 3 |######## | i = 8
轮 4 |################ | i = 16
+--------------------------------------------------+
每个知情节点每轮把消息交给 1 个随机节点 ⇒ 知情人数每轮翻倍
4| *
3| *
2| *
1| *
0|*
+-----+----+----+----+----+----+----+--→ 轮数
0 1 2 3 4 5 6 7
⇒ 第 t 轮 i_t = 2^t：对数坐标下是直线 ⇒ 覆盖 n 个节点需 t = log2(n) 轮
下界（讲义”为什么 $O(\log N)$ 已经是最快的”）：任何多播协议要让 $N/2$ 个节点收到消息，都必须在”知情集合”上长出一棵扇出为常数的生成树；常数扇出的树覆盖 $N$ 个节点，树高必然是 $\Omega(\log N)$。因此 $O(\log N)$ 轮是所有 gossip 形式不可突破的下界（讲义原话 “that’s the fastest you can spread a message” 说的正是这个下界，而不是说所有协议都能做到）。
6.2.5 反熵模型（Anti-Entropy）
- 定义与目的：最”笨”也最可靠的流行病协议。每个节点周期性（每隔 $\Delta$ 秒）随机挑一个节点，与它交换数据以消除差异。”反熵”这个名字来自热力学：熵代表混乱（副本之间的不一致），反熵就是主动消除不一致。
- 三种变体（差异极大，必须区分清楚）：
Push : A ───(我的全部数据/更新)───▶ B 我推给你，你只收不发
Pull : A ◀──(你的全部数据/更新)──── B 我向你要，你不主动给
Push-Pull : A ◀────────交换────────▶ B 双方互相补齐（最常用）
差异检测：先比校验和/根哈希，只传“对方缺的那部分”
- 为什么 anti-entropy 一定能最终收敛：在没有新更新的前提下，考虑任意一条更新 $u$，令 $\mathrm{holders}(u)$ 为持有 $u$ 的节点集合。反熵的合并规则是”版本新者胜、缺失者补齐”，因此：
- 单调性（安全）：节点只会获得更新的数据，永远不会因为反熵而丢失一条已知的更新，所以 $\mathrm{holders}(u)$ 随时间是单调不减的。若某一轮双方状态相同，则什么也不变（差异只减不增）。
- 推进性（活性）：只要 $h=\vert \mathrm{holders}(u)\vert <n$，本轮”没有任何新节点获知 $u$”的概率为 $\prod_{i\in \mathrm{holders}}(h/n) = (h/n)^h \le 1/n < 1$。也就是说每一轮都有严格正的概率取得进展。
- 综合 1 与 2：$h$ 是一个取值于有限集合 $\{1,\dots,n\}$ 的单调过程，且在每个非吸收态都有正概率前进，故它以概率 1 在有限时间内到达 $h=n$——这就是最终一致性（eventual consistency）。
- 收敛速度：在 $h\le n/2$ 的阶段，每个持有者与一个随机节点交换，$h$ 期望每轮翻倍，所以 $O(\log n)$ 轮即可完成（本文 6.4.2 的实验中 $n=500$ 用 6 轮；尾部因为所有 $n$ 个节点每轮都在发起交换，$n-h$ 个未知者每轮平均被接触约 1 次，也只需 $O(1)$ 轮级别）。
- 致命缺点：无差别开销。 即使一条新更新都没有，所有节点仍然每 $\Delta$ 秒交换一次，全网恒定产生 $O(n)$ 条消息/轮；如果每次还传全量数据，开销更是与数据量成正比。两个经典优化：
- 只传差异：先交换校验和（checksum）/根哈希，相同就立即结束（一次往返、$O(1)$ 代价）。
- Merkle 树（哈希树）：把键空间分段，逐层哈希成一棵树，两边自顶向下比对，只有哈希不同的子树才继续下探，最终只传输真正有差异的那些键值对。找出一处差异只要 $O(\log n)$ 次哈希交换，而不是全量传输。
root = H(h01‖h23‖h45‖h67)
/ \
H(0..3) H(4..7)
/ \ / \
H(0..1) H(2..3) H(4..5) H(6..7)
/ \ / \ / \ / \
h0 h1 h2 h3 h4 h5 h6 h7
[k0] [k1] [k2] [k3] [k4] [k5] [k6] [k7]
副本 A 与副本 B 只比根哈希 → 不同 → 只在哈希不同的子树里继续 → 只传 [k3] 这一项
（Cassandra / Dynamo 的“反熵修复（repair）”正是这一机制，详见 Lecture 9）
- 关键假设：成员视图可得（随机选对端即可，无需全量）；合并语义是幂等、可交换、单调的（通常靠”版本号大者胜”实现）；对消息丢失免疫（丢一次下一轮继续）。
6.2.6 流言传播模型（Rumor Mongering）
- 定义与目的：反熵的问题是”没事也打电话”。流言传播（又叫 rumor mongering / 谣言传播）反过来：只在有新消息时才通信。节点一旦收到新更新就变成”hot”（infective），周期性把这条更新推给随机节点；如果对方已经有这条更新（白费口舌），就以概率 $1/k$ 停止传播，变”cold”（removed）。
- 直观解释：办公室里你听到一个八卦，会兴奋地到处讲；讲了几次发现对方早就知道了，你也就没兴趣再讲了——八卦热度的衰减正是 $1/k$ 停止规则。这也解释了为什么谣言能瞬间传遍办公室（指数扩散），却总是”传不到最后那几个人”（热度先于覆盖耗尽）。
- 机制图解：
收到新更新 每轮随机推给 1 个节点
┌──────────────┐ ┌───────────────────────┐
│ S (不知道) │──收到更新──▶ │ I / hot (继续传播) │
└──────────────┘ └───────────┬───────────┘
│ 推给 Pj
┌──────────────────┴──────────────────┐
▼ ▼
Pj 没有这条更新 Pj 已经有这条更新
⇒ 有效传播，Pj 也变 hot ⇒ 以概率 1/k 变 cold (R)
以概率 1-1/k 再撑一轮
量化它的缺陷（”未被覆盖节点数的期望”）：这是讲义没有展开、但必须会算的部分。设 $k$ 为停止参数，$q$ 为最终没有收到更新的节点比例，$n$ 为节点数。
均值场推导：整个过程中”总推送次数” = 成功推送 + 白费推送。成功推送恰好等于被通知的人数 $\approx n(1-q)$（每条成功推送让一个新人知道）；白费推送方面，每个知情节点平均要浪费 $k$ 次才变冷，所以白费推送 $\approx k\,n(1-q)$。于是总推送 $P\approx (1+k)n(1-q)$。一个特定节点始终没被推到的概率为 $(1-1/n)^{P}\approx e^{-(1+k)(1-q)}$，即
\[q \;=\; e^{-(1+k)(1-q)} .\]解这个方程：$k=1\Rightarrow q\approx0.203$；$k=2\Rightarrow q\approx0.060$；$k=3\Rightarrow q\approx0.020$；$k=5\Rightarrow q\approx0.003$。也就是说，只要 $k$ 有限，就有常数比例（或至少 $\Theta(n)$ 量级）的节点永远收不到消息。作为特例，如果每个知情节点只推一次就停（最朴素的”一次性八卦”），则方程退化为 $q=e^{-(1-q)}$，解为 $q\approx 0.5671$——超过一半的节点收不到，这就是”谣言会死”的经典结论。
本文 6.4.2 的模拟实验对这四个预测做了实测（40 次实验平均，$n=500$）：$k=1$ 实测 0.209、$k=2$ 实测 0.060、$k=3$ 实测 0.020、$k=5$ 实测 0.003，与公式吻合。
优点与缺点并存：优点是开销极小（没有新消息时流量为 0，传播期每条消息只携带一条更新）；缺点是不保证全覆盖，必须靠别的机制兜底。
6.2.7 两种模型结合：真实系统的标准做法
把”快”和”全”分开实现，是工业系统的通行做法：
新更新产生
│
▼
┌─────────────────────────────┐ （毫秒~秒级）
│ Rumor Mongering：快速扩散 │ ──▶ 几轮内覆盖 90%+ 节点，开销 O(n)
└─────────────────────────────┘
│ 漏掉的那几个（q·n 个）节点
▼
┌─────────────────────────────┐ （秒~分钟级 / 定期 repair）
│ Anti-Entropy：兜底修复 │ ──▶ 保证最终一致，代价是持续 O(n)/轮
└─────────────────────────────┘
- Cassandra 的做法就是典型：成员状态与负载信息用 gossip（流言） 每秒一轮快速扩散；而副本之间的数据差异由反熵修复（
nodetool repair）+ Merkle 树兜底（细节见 Lecture 9）。 - Bimodal Multicast [ACM TOCS ‘99] 是同一思路的经典实现：多播消息用轻量的树状/懒惰方式先发一遍，再用 gossip 做”修复”，从而呈现双峰延迟分布——绝大多数消息很快到达，剩下的极少数最终也会到达。
6.2.8 Push / Pull / Push-Pull：头部与尾部的不对称性
反熵与流言传播都有三种发起方式，讲义只给了一句”hybrid variant: push-pull”，但为什么 push-pull 最优值得完整推导。
Push : 知情者主动 ──▶ 随机节点 “我有，我给你”
Pull : 未知者主动 ──▶ 随机节点 “我没有，你有没有？”
Push-Pull : 一次接触，双向交换 “我们俩把各自有的都给对方”
关键洞察：push 与 pull 的浪费发生在过程的两端。
| 阶段 | Push（知情者发起） | Pull（未知者发起） |
|---|---|---|
| 头部（知情者少、$\;i\ll n$） | 每次接触命中易感节点的概率 $\approx 1$，几乎不浪费，且 $i$ 每轮翻倍 | 每次拉取命中知情节点的概率 $\approx i/n\approx 0$，几乎全是空转 |
| 尾部（未知者少、$x\ll n$） | 每次接触命中未知节点的概率 $\approx x/n\approx 0$，几乎全是浪费 | 每次拉取命中知情节点的概率 $\approx 1$，几乎不浪费 |
把这个直觉写成递推式（$x=n-i$ 为未知人数，每节点每轮接触 1 个随机节点）：
\[\text{Push:}\quad x_{t+1}=x_t\Big(1-\tfrac1n\Big)^{\,n-x_t}\approx e^{-1}x_t \qquad\Longrightarrow\qquad \text{尾部是几何收缩，需 } \ln n \text{ 轮}\] \[\text{Pull:}\quad x_{t+1}=x_t\cdot\frac{x_t}{n}=\frac{x_t^{2}}{n} \qquad\Longrightarrow\qquad \text{尾部是双重指数（超指数）收缩，需 } O(\log\log n) \text{ 轮}\]一眼看出差别：push 的尾部每轮只把未知人数乘以 $e^{-1}\approx 0.368$（单指数），而 pull 的尾部把 $x$ 变成 $x^2/n$——未知人数 500 → 250 → 62 → 4 → 0，几步就清干净。pull 的指数在”指数位置”上，所以叫双重指数/超指数收缩：把 $p=x/n$ 写成比例，$p_{t+1}=p_t^{k+1}$（每轮 $k$ 次拉取时），于是 $\log(1/p)$ 每轮乘以 $(k+1)$，从 $p=1/2$ 降到 $p=1/n$ 只需 $O(\log\log n)$ 轮。这正是讲义所说的 “This is super-exponential… Second half of pull gossip finishes in time $O(\log\log(N))$”。
三者合并成一张表（完整推导见 6.3.4，文献结论来自 Karp et al., FOCS 2000）：
| 协议 | 谁发起 | 头部（到 $n/2$） | 尾部（最后一半） | 总轮数 | 总消息数 |
|---|---|---|---|---|---|
| Push | 知情节点 | 每轮 $\times 2$，$\log_2 n$ 轮 | 几何收缩，$\ln n$ 轮，每轮仍发 $\Theta(n)$ 条 | $\log_2 n+\ln n$ | $\Theta(n\log n)$（尾部主导） |
| Pull | 未知节点 | 每轮 $\times 2$（但每次查询成功率仅 $i/n$，头部几乎全浪费） | 双重指数收缩，$O(\log\log n)$ 轮 | $\Theta(\log n)$ | $\Theta(n\log n)$（头部主导） |
| Push-Pull | 双方交换 | 每轮 $\times 3$（既可能被推到，也可能拉到），$\log_3 n$ 轮 | 双重指数收缩，$O(\log\log n)$ 轮 | $\log_3 n+O(\log\log n)$ | $\Theta(n\log\log n)$（最优） |
为什么 push-pull 能同时拿下两端：头部靠 push 的效率（$i$ 每轮 $\times 3$ 而不是 $\times 2$，因为一个未知节点既可能被知情者推到、也可能自己拉到），尾部靠 pull 的双重指数收缩。Karp 等人的阶段分析给出的账本是：启动/指数增长阶段虽然轮数 $O(\log n)$，但每轮传输量与知情人数成正比，等比求和只有 $O(n)$ 条；收缩阶段每轮 $O(n)$ 条但只需要 $O(\log\log n)$ 轮，合计 $O(n\log\log n)$。他们还证明了两条下界：任何地址盲（address-oblivious）算法至少要发 $\Omega(n\log\log n)$ 条消息；而任何在 $O(\log n)$ 轮内完成的随机呼叫算法至少要发 $\Omega(n\log n)$ 条消息——时间最优与通信最优无法用随机电话同时达成，push-pull 的 $\Theta(n\log\log n)$ 已经是最优解。
ASCII 曲线对比（横轴轮数，纵轴已知消息的节点比例；取自本文 6.4.1 的模拟器输出，$n=1000$）：
100%| b b l l p p p p
94%| l p
88%| b p
81%|
75%| l p
69%|
62%|
56%| b
50%| l p
44%|
38%|
31%| p
25%| b l
19%| p
12%| l
6%| b l l
0%|b b b l p
+------------------------------------------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17
图例: p = push, l = pull, b = push-pull
· push（p）：前 10 轮就冲到 50%，但 90%→100% 花了 5 轮，最后几个节点怎么都追不上
· pull（l）：头部每轮空转近 n 条查询，靠尾部双重指数收缩反超
· push-pull（b）：9 轮全部完成，头部因子 3、尾部超指数，两头的浪费都被消掉
6.2.9 容错性与概率保证
讲义反复强调 gossip 的三个属性：lightweight（轻量）、fast（快）、highly fault-tolerant（高度容错）。容错性可以精确地算出来：
- 丢包：设每条消息以概率 $1-p$ 丢失。那么在感染率 $\beta=b/n$ 中把 $b$ 换成 $pb$（等价于 $p$ 折的有效接触率），头部从 $\log_2 n$ 变成 $\log_{1+p}n$、尾部从 $\ln n$ 变成 $\frac1p\ln n$（Karp 等人的精确结果：$\log_{1+p}n+\frac1p\ln n$）。所以 50% 丢包 ⇒ $b\to b/2$ ⇒ 要拿到同样的可靠性，轮数大约翻倍（讲义口径）。
- 节点故障：50% 的节点崩溃 ⇒ $n\to n/2$ 且 $b\to b/2$（能干活的人减半）⇒ 结论同上。
- 流行病会不会”夭折”？ 可能，但概率很小。早期感染人数少时，传播过程近似一个分支过程：每个感染节点平均产生 $b$ 个新感染，后代分布可近似为均值 $b$ 的 Poisson 分布。分支过程的灭绝概率 $q$ 是方程 $q=e^{-b(1-q)}$ 的最小不动点：$b=2$ 时 $q\approx 0.203$，$b=3$ 时 $q\approx 0.06$，$b=1$ 时 $q=1$（临界，必然熄灭）。所以只要 $b>1$，一旦有几个节点染上，以高概率整场疫情不会熄灭——这正是讲义所说 “Possible, but improbable… 所以前面的分析实际上是 ‘with high probability’ 的行为”。
- 概率保证的写法：把”以概率 $1-1/n$ 在 $O(\log n)$ 轮内完成”拆成两部分：① 用 6.2.4 的马尔可夫界保证覆盖率（未覆盖期望 $n^{2-cb}\le 1/n$）；② 用分支过程/切诺夫界保证过程不早夭（失败概率随初始感染数与轮数指数衰减）。两者取并集界即可。
6.2.10 拓扑感知与 Gossip 的变体
- 朴素的纯随机选择会打爆核心路由器。真实的网络拓扑是分层的：两个子网各 $N/2$ 个节点，中间由一台核心路由器相连。
+--------------------------------+
| 核心路由器 (core router) |
+---------------+----------------+
|
+-----------------------------------+
| |
+-------------------+ +-------------------+
| 子网 A | | 子网 B |
| N/2 个节点 | | N/2 个节点 |
+-------------------+ +-------------------+
每个节点每轮随机选一个全网节点，目标落在另一个子网的概率是 $1/2$，于是每轮有 $\Theta(N)$ 条消息穿过核心链路——路由器负载 $O(N)$，而它是个瓶颈资源。
- 修正（讲义给出的方案）：子网 $i$ 内有 $n_i$ 个节点时，以概率 $1-1/n_i$ 在子网内部选 gossip 目标，以概率 $1/n_i$ 选到子网外。此时每个子网每轮的跨网消息期望为 $n_i\cdot\frac{1}{n_i}=\Theta(1)$，核心路由器负载降到 $O(1)$；而扩散时间仍是 $O(\log N)$——因为子网内在 $O(\log n_i)$ 轮内就能传遍，且跨网的那 $\Theta(1)$ 条消息会不断地把最新消息带出去，两个子网各自内部再扩散。
- 其他变体：
- 分层 gossip（hierarchical）：同机房/同子网内用高频 gossip，跨机房用低频 gossip（Consul 的 LAN pool + WAN pool、跨数据中心元数据同步都用这个结构）。
- 空间 gossip（spatial gossip）：按地理/机架/时延聚类选对端，让”近的邻居多聊、远的邻居少聊”，同时兼顾延迟与带宽成本。
- 反馈机制（feedback）：流言传播中的 $1/k$ 停止规则就是一种反馈——用对方的回应（”我早就知道了”）来决定自己是否继续传播；没有反馈的 gossip 会永远以固定频率发消息。
- 确定性拓扑 vs 随机选择：在网格、环、超立方（hypercube）等规则拓扑上也可以做确定性的 gossip（例如超立方上每个节点每轮与某一维的对端交换）。确定性邻居在无故障时更快更省，但一旦邻居崩溃，传播路径被切断，可能永久性地丢失信息；随机选择则让每一轮都有大量备选路径，代价是消息冗余。用冗余换容错，这是贯穿本讲的主线。
6.2.11 真实系统中的 Gossip
讲义列出了一串实现，按”它用 gossip 做什么”分类更有价值：
| 系统 | Gossip 的用途 | 要点 |
|---|---|---|
| Clearinghouse / Bayou [PODC ‘87] | 邮件与数据库事务的传播 | 反熵 + 流言传播的最早系统化应用（Demers 等人的工作） |
| refDBMS [Usenix ‘94] | 参考文献数据库副本同步 | 反熵修复 |
| Bimodal Multicast [ACM TOCS ‘99] | 可靠多播 | 树状/懒惰传播 + gossip 修复 ⇒ 双峰延迟分布 |
| Usenet NNTP [‘79] | 新闻组文章在服务器之间转发 | store-and-forward 式的懒惰 gossip，见下面的时序图 |
| 传感器网络 [Li Li et al., Infocom ‘02；PBBF, ICDCS ‘05] | 数据汇聚、时间同步 | 低功耗、只依赖部分邻居 |
| AWS EC2 / S3 [’00s] | （业界传闻）大规模集群状态管理 | 讲义原文标注为 “rumored” |
| Cassandra | 成员管理与节点状态传播 | 每秒一轮 gossip，seeds 引导，$\Phi$ 累积故障检测器；数据差异用 Merkle 树反熵修复 |
| Dynamo | 成员管理 + 反熵 | 副本同步用 Merkle 树（详见 Lecture 9/10） |
| Consul（Serf/SWIM） | 成员管理与故障检测 | ping + 间接探测（ping-req）、suspicion 机制，详见 Lecture 7 |
| Redis Cluster | 集群总线（cluster bus）上的状态交换 | 每个节点 PING/PONG 中夹带随机的其他节点信息；PFAIL → 投票 → FAIL |
| Bitcoin / Ethereum | 区块与交易的扩散 | 比特币是 inv/getdata 的泛洪式中继；以太坊使用 libp2p gossipsub 的 mesh 式 gossip + peer scoring |
NNTP 的服务器间协议很值得看，因为它把”pull 发现 + push 传输”组合得非常干净：
上游服务器 (upstream) 下游服务器 (downstream)
| |
| CHECK <Message-ID1> <Message-ID2> ... | ← “我这边有这些文章，你有吗？”
|----------------------------------------------------->| （本质是 pull 式差异探测）
| 238 {Give me!} | ← “这几篇我没有，给我”
|<------------------------------------------------------|
| TAKETHIS <Message> |
|----------------------------------------------------->| （push 式传输）
| 239 OK |
|<------------------------------------------------------|
| |
服务器保留文章一段时间 → 懒惰地（lazily）转发 → 到期删除。
Message-ID 就是更新的唯一标识，等价于 gossip 中的 update id / version。
设计要点：没有”全网广播”，没有全局目录。每台服务器只知道自己的邻居；文章以”尽力而为”的方式逐跳扩散，因此不保证每台服务器都能收到每篇文章——这正是 gossip 的语义：最终一致，而非确定性全覆盖。
6.2.12 用 Gossip 做聚合：为什么”对邻居取平均”是错的
Gossip 不只能广播，还能做聚合计算（SUM / AVG / MAX / COUNT）。但这里有一个著名的陷阱。
直觉方案（错的）：让每个节点每轮取自己和邻居的平均值，$x_i \leftarrow \frac{x_i+\sum_{j\in N(i)}x_j}{1+\vert N(i)\vert }$。看起来”平均的平均还是平均”，实际上它收敛到的不是算术平均。原因：这个迭代矩阵是行随机的，其平稳分布正比于节点度数，因此收敛值是
\[\bar{x}_\infty=\frac{\sum_i (d_i+1)x_i}{\sum_i (d_i+1)}\quad(\text{度加权平均})\;\ne\;\frac{\sum_i x_i}{n}\quad(\text{真平均}).\]只有在正则图（所有节点度数相同）或完全图上两者才一致。本文 6.4.3 的实验里，一个度分布从 1 到 8 不等的图上，邻居平均收敛到 49.1404，而真平均是 51.2928，度加权平均恰好是 49.1404——完全吻合。
- 更糟的方案：拉到邻居的值就直接拷贝（$x_i\leftarrow x_j$，voter 模型）。这连”平均”都不是：系统会收敛到某一个初始值（每个节点都持有同一个 $x_k$）。它的期望确实等于真平均（对称性保证 $P(\text{收敛到 }x_k)=1/n$），但单次运行的误差是 $O(\sigma)$，永远不会随轮数收敛到 0。
正确做法：Push-Sum（比值和 / 带权重）。每个节点维护一对值 $(s_i,w_i)$，初始 $(x_i,1)$；每轮把两者都减半，一半留给自己、一半寄给随机节点，收到的一半则相加。因为质量 $\sum s_i$ 与权重 $\sum w_i$ 都守恒，所以比值
\[\frac{\sum_i s_i}{\sum_i w_i}=\frac{\sum_i x_i}{n}=\text{真平均}\]是一个不变量；而随机混合会让每个节点手上的 $s_i/w_i$ 在 $O(\log n)$ 轮内逼近这个不变量。细节与正确性证明见算法 6.3.3，可运行实现在 6.4.3。这类”带质量权重的平均”（AGEM 等 gossip 聚合框架也是同一思想）才是分布式聚合的正确形态。
6.3 算法伪代码与正确性分析
算法 6.3.1：反熵（Anti-Entropy，push-pull 变体）
假设与系统模型
- 进程数 $n$；异步系统，只有本地定时器，无全局时钟。
- 故障模型：crash-recovery（节点可能崩溃后重启并保留持久化状态）；不处理 Byzantine 故障。
- 通道：消息可能丢失、乱序、重复；不要求 FIFO。
- 成员视图：每个节点持有一个部分成员视图（partial view） $M_i$，只要它采样近似均匀即可，不要求全网一致。
- 数据模型：每个节点持有键值映射 $D_i:\text{key}\to(\text{value},\text{version})$；合并算子是幂等、可交换、单调的（版本号大者胜，同版本值相同）。
伪代码
Algorithm AntiEntropy-PushPull(Δ) 在每个节点 Pi 上独立运行
状态:
D_i : 本地数据集 {key → (value, version)}
M_i : 部分成员视图（若干节点的地址，可随时增删）
c_i : 本地缓存的 Merkle 树根（D_i 变化时重算）
upon timer tick (每 Δ 秒触发一次, 抖动 jitter 随机化):
Pj ← 从 M_i 中均匀随机选一个节点
send ⟨DIGEST, root(D_i), c_i⟩ to Pj
upon receive ⟨DIGEST, r_j, c_j⟩ from Pj:
if c_i == c_j : # 哈希相同 ⇒ 两边完全一致
return # 代价 O(1)，不传任何数据
else: # 自顶向下定位差异子树
for each subtree t where hash_i(t) ≠ hash_j(t):
在 t 覆盖的键范围里，取出 D_i 有而版本更高的条目
send ⟨DIFF, {(k, v, ver) ...}⟩ to Pj
upon receive ⟨DIFF, S⟩ from Pj: # S 是对方比本节点新的条目集合
for each (k, v, ver) in S:
if k ∉ D_i or ver > D_i[key].version:
D_i[k] ← (v, ver)
重算受影响的 Merkle 路径
send ⟨DIFF, {D_i 中比对方新的条目}⟩ to Pj # 双向补齐：pull 的一半
算法逻辑解说
- 定时器到点，节点随机挑一个伙伴，发出摘要（根哈希）。注意”随机”是反熵的关键：不需要任何拓扑知识。
- 对方比较根哈希。相同 ⇒ 一次往返结束（这是没有更新时的最小开销）；不同 ⇒ 借助 Merkle 树自顶向下定位，只发送真正有差异的条目。
- 接收方按”版本大者胜”合并，然后把自己比对方新的条目回送（push-pull 的第二半），一次会话双向补齐。
- 数值小例子：$n=4$，节点 A 持有
{k1:v1, k2:v2}，B 持有{k1:v1, k2:v9}。A 随机选中 B 并发送根哈希 ⇒ 不等；下探到叶 $h_2$ 不等（$v2\ne v9$）⇒ B 把(k2,v9)发给 A。下一轮若 B 又随机选中 C 且 D，则 $v9$ 继续扩散。每次会话只传一条差异，而两个版本的收敛在 $O(\log n)$ 轮内完成。
正确性论证
- 安全性（一致性与单调性）：合并规则只做”取更新的版本”，因此对任意一条更新 $u$，持有者集合 $\mathrm{holders}(u)$ 单调不减；且同一 key 的取值只会向版本号更大的方向变化，不会在两个值之间来回震荡（版本号是全序）。所以不会出现”A 覆盖了 B 的新值”这类数据丢失。
- 活性（最终一致性）：设 $h=\vert \mathrm{holders}(u)\vert <n$。一轮内 $u$ 没有传播到任何新节点的概率是 $\prod_{i\in \mathrm{holders}(u)}\Pr[P_i\text{ 选中了 holders 内的节点}] = (h/n)^h \le (1-1/n) < 1$（当 $h\le n-1$ 时 $h/n\le (n-1)/n$）。即每一轮都有 $>0$ 的概率取得进展；又因为 $h$ 取值于有限集合且单调不减，该过程必以概率 1 在有限时间内到达 $h=n$。这正是”在没有新更新的前提下，以概率 1 在有限时间内所有节点状态一致”。
- 速度：$h\le n/2$ 时每个持有者都独立地找随机伙伴，$h$ 的期望每轮翻倍 ⇒ $O(\log n)$ 轮达成一致（实验：$n=500$ 用 6 轮）。
复杂度
- 消息复杂度：每节点每 $\Delta$ 秒 1 条（摘要），全网 $O(n)$ 条/轮；有差异时额外的数据量正比于差异大小（Merkle 树把它压到”最小必要”）。
- 时间：一致所需轮数 $O(\log n)$；实际延迟 = 轮数 × $\Delta$。
- 空间：每节点 $O(\vert D_i\vert )$ 存放数据 + $O(\vert D_i\vert )$ 存放 Merkle 树哈希 + $O(\vert M_i\vert )$ 存放成员视图。
- 代价特征：无更新时仍持续 $O(n)$/轮 ⇒ 反熵必须配”抖动 + 差异检测”才能实用。
算法 6.3.2：流言传播（Rumor Mongering）
假设与系统模型
- 进程数与成员视图同 6.3.1；异步、crash-stop/crash-recovery。
- 通道可能丢消息（这正是它需要的容错类型）。
- 每条更新 $u$ 在每个节点上有一个独立的三态状态；停止参数 $k\ge 1$。
伪代码
Algorithm RumorMongering(Δ, k) 在每个节点 Pi 上独立运行
状态（对每条更新 u）:
state[u] ∈ {S(不知道), I=hot(传播中), R=cold(已停)}
ctr[u] : 冗余接触计数器（可选，用于“k 次白费口舌”变体）
buf_i : 待传播的更新集合（可只保留最近/高优先级的若干条）
# ---- 新更新进入系统 ----
upon 应用层产生更新 u (或) upon receive ⟨RUMOR, u⟩ from Pj:
if u ∉ buf_i: # 第一次见到这条更新
buf_i ← buf_i ∪ {u}
state[u] ← I ; ctr[u] ← 0 # 变“hot”
else: # 冗余接触：对方比我先知道
with probability 1/k:
state[u] ← R # 变“cold”，不再传播
# 以概率 1-1/k 继续留在 hot（下轮再试一次）
# ---- 定期传播 ----
upon timer tick (每 Δ 秒):
for each u in buf_i with state[u] == I:
Pj ← 从 M_i 中均匀随机选一个节点（可排除自己）
send ⟨RUMOR, u⟩ to Pj
if 一次传播轮次预算用尽: drop u from buf_i # 防止无限增长
算法逻辑解说
- 节点第一次拿到一条更新时”兴奋”起来（hot），并把它放进待传播缓冲。
- 每个 gossip 周期，所有 hot 的更新各推给一个随机节点。
- 如果对方已经知道（冗余接触），按概率 $1/k$ 变冷；$k$ 越小越”薄情”（传播得少、开销小、漏得多），$k$ 越大越”执着”（覆盖更全、开销更大）。
- 数值小例子：$n=6$，$k=1$（一次冗余就停）。节点 A 有更新，推给 B（B 变 hot）；下一轮 A、B 各推一个：A→C（有效）、B→A（冗余，A 变冷）。再下一轮 B→D（有效）、C→E（有效）、D→F（有效）……若某轮所有 hot 节点的推送全部落在知情节点上，则全员变冷，传播彻底停止，此时可能仍有 1~2 个节点不知道——这就是”谣言之死”。
正确性论证
- 安全性：任何收到消息的节点都保留了完整更新（不丢数据）；不会出现部分更新（一条 RUMOR 就是一条完整更新）。
- 活性（有条件的）：只要还存在 hot 节点，传播就在继续；一旦所有节点变冷，传播必然停止（进程终止性成立）。
- 覆盖性（关键：它不保证全覆盖）：如 6.2.6 所推，未被覆盖的节点比例满足均值场方程 $q=e^{-(1+k)(1-q)}$，$k$ 有限时 $q>0$ 是常数级，即期望有 $\Theta(n)$ 个节点永远收不到。因此 rumor mongering 只能与反熵（算法 6.3.1）配合使用：前者负责”快”，后者负责”全”。
复杂度
- 消息复杂度：只在有新更新时产生流量；一次更新的总推送数 $P\approx(1+k)n(1-q)=O(kn)$，平均每节点 $O(k)$ 条。
- 时间：头部 $O(\log n)$ 轮覆盖绝大多数节点；尾部会提前停滞（不是”慢”，而是”停”）。
- 空间：每节点 $O(\vert \text{buf}\vert )$，必须限制缓冲大小（否则更新无限堆积）。
算法 6.3.3：Push-Sum 聚合（计算全网平均值）
假设与系统模型
- $n$ 个节点，每个节点 $P_i$ 有一个私有初始值 $x_i$，目标：所有节点算出 $\mu=\frac1n\sum_i x_i$。
- 同步轮（round-based）；异步实现需要额外的收敛判据，此处用同步轮简化。
- 通道可靠（丢包只会减慢收敛，不会破坏不变式——因为丢失的消息等价于”这一轮没发”，而守恒性由”减半后保留一半”保证）。
- 成员视图：每轮从 $M_i$ 中均匀随机选一个非自己的节点。
伪代码
Algorithm PushSum()
初始:
s_i ← x_i # “质量”：初始值的份额
w_i ← 1 # “权重”：自己这份质量的所有权
upon round t at node Pi: # 每轮对每个节点执行一次
s_i ← s_i / 2 # 把质量对半切
w_i ← w_i / 2 # 权重同步对半切
Pj ← 从 M_i 中均匀随机选 j ≠ i
send ⟨PUSHSUM, s_i, w_i⟩ to Pj # 寄出“另一半”
upon receive ⟨PUSHSUM, s_j, w_j⟩ from Pj:
s_i ← s_i + s_j # 收到的份额直接累加
w_i ← w_i + w_j
# 任何时刻，节点 Pi 对 μ 的估计为：
est_i ← s_i / w_i
算法逻辑解说
- 想象每个节点手里有一块”质量” $x_i$ 和一张”所有权凭证” $w_i=1$。传播时把质量和凭证一起对半切，一半留在本地、一半寄走；收到的人把份额累加进自己的账户。
- 关键在于：质量和凭证永远同步流动。一个只拥有别人 1/8 质量份额的节点，同时也拥有 1/8 的凭证份额，所以比值 $s_i/w_i$ 始终是”这些质量所对应的平均值”。
- 数值小例子：$n=2$，$x_1=10$、$x_2=20$，$\mu=15$。第 1 轮：节点 1 变成 $(5,0.5)$ 并把 $(5,0.5)$ 寄给节点 2；节点 2 变成 $(10,0.5)$ 并把 $(10,0.5)$ 寄给节点 1。结果 $s_1=5+10=15,\ w_1=0.5+0.5=1\Rightarrow \text{est}_1=15$；$s_2=10+5=15,\ w_2=1\Rightarrow\text{est}_2=15$。一轮就精确收敛（$n=2$ 的退化情形）。
正确性论证
- 不变式 1（质量守恒）：$\sum_i s_i = \sum_i x_i$ 恒成立。归纳：每轮每节点把 $s_i$ 切成 $s_i/2+s_i/2$，一半留给自己、一半寄给别人，全网总量不变：$\sum_i s_i^{(t+1)}=\sum_i s_i^{(t)}/2+\sum_i s_i^{(t)}/2=\sum_i s_i^{(t)}$。
- 不变式 2（权重守恒）：$\sum_i w_i = n$ 恒成立，证明同上（初值每个 $w_i=1$）。
- 由两个不变式立即得到：$\frac{\sum_i s_i}{\sum_i w_i}=\frac{\sum_i x_i}{n}=\mu$ 是系统的一个不变量。也就是说真值从未被破坏，剩下的问题只是”每个节点能不能把它算出来”。
- 收敛性：
- 取期望并利用”每个节点的另一半均匀落到某个节点”：$\mathbb{E}[s_i^{(t+1)}]=s_i^{(t)}/2+\sum_{j\ne i}\frac{s_j^{(t)}}{2(n-1)}$，其唯一不动点是 $s_i^*=S/n$（$S=\sum_j x_j$），偏差以因子 $\rho=\frac12\big(1-\frac{1}{n-1}\big)$ 每轮收缩 ⇒ $O(\log n)$ 轮后 $\mathbb{E}[s_i]\approx S/n$；对 $w_i$ 同理有 $\mathbb{E}[w_i]\to 1$。
- 更强地，$s_i/w_i$ 始终是初始值的加权平均：$s_i/w_i=\sum_j \frac{p_{ji}}{w_i}x_j$，其中 $p_{ji}$ 是节点 $j$ 的质量落到 $i$ 的比例。随着轮数增加，$p_{ji}$ 在节点间充分混合、逐渐趋近 $1/n$，权重也就越来越均匀，于是所有估计一起逼近 $\mu$。
- 严格的高概率界由 Kempe、Dobra、Gehrke（PODC 2003）给出：$O(\log n)$ 轮内所有节点的 $s_i/w_i$ 都在 $\mu\pm\varepsilon$ 内（$\varepsilon$ 由初始值范围与轮数决定）。本文 6.4.3 的实验中，$n=64$ 时 60 轮后最大误差为 $3.0\times10^{-8}$，$\sum s_i$ 与 $\sum w_i$ 在整个过程中精确守恒。
复杂度
- 消息复杂度：每节点每轮 1 条消息 ⇒ 全网 $O(n)$ 条/轮，$O(n\log n)$ 条总计（到 $\varepsilon$ 精度需 $O(\log n+\log\frac1\varepsilon)$ 轮）。
- 空间：每节点 $O(1)$ 个浮点/定点数（$(s_i,w_i)$），与 $n$ 无关。
- 精度注意：$(s_i,w_i)$ 是浮点数会累积舍入误差，实践中用定点数或周期性重新归一化。
算法 6.3.4：传播时间与消息数的期望分析（分析性伪代码）
这一节把 6.2.8 的直觉写成可执行的递推式，用来回答”给定 $n$ 和模式，需要多少轮、多少消息”。
假设与系统模型
- 同步轮；$n$ 个节点，成员视图均匀随机（逻辑完全图）；每轮每个”行动者”接触 1 个随机节点；无消息丢失（丢包时把有效接触率乘以 $p$ 即可，见 6.2.9）。
- 记号：$i_t$ 为第 $t$ 轮开始时的已知人数，$x_t=n-i_t$ 为未知人数，$p_t=x_t/n$。
伪代码（递推式求解器）
Analysis GossipRounds(n, mode):
i ← 1 ; x ← n-1 ; rounds ← 0 ; msgs ← 0
while x > 0 and rounds < CAP:
rounds ← rounds + 1
if mode == PUSH:
# 头部：每个知情者推给 1 个随机节点，某个未知者被命中的概率 ≈ i/n
new ← x * (1 - (1 - 1/n)^i) # 期望新增感染
cost ← i # 本轮消息数 = 知情人数
# 尾部（x << n）: (1-1/n)^i ≈ e^{-i/n} ≈ e^{-1} ⇒ x ← 0.368x（几何收缩）
if mode == PULL:
new ← x * (1 - (1 - i/n)^k) # 每个未知者拉 k 次（默认 k=1），命中知情者概率 i/n
cost ← x # 本轮消息数 = 未知人数（头部最贵）
# 尾部（x << n）: 未知者拉到未知者的概率 x/n ⇒ x ← x²/n（双重指数收缩）
if mode == PUSH_PULL:
new ← x * (1 - (1 - i/n)^k * (1 - 1/n)^i) # 推、拉两条通道叠加：
# 只有“既没拉到知情者、也没有被知情者推到”的未知者才会继续未知
cost ← i + x # 双方都发起 ⇒ 每轮 n 条
# 头部增长因子 3（推命中 + 拉命中），尾部仍为 x ← x²/n
i ← i + new ; x ← n - i ; msgs ← msgs + cost
return rounds, msgs
# 解析结论（Karp et al., FOCS 2000，均为高概率界）：
# PUSH : 轮数 = log2(n) + ln(n) ± o(log n) ; 消息 = Θ(n log n) （尾部主导）
# PULL : 轮数 = Θ(log n)（头部慢热 + 尾部 O(log log n) 超指数收缩）
# 消息 = Θ(n log n) （头部主导）
# PUSH-PULL : 轮数 = log3(n) + O(log log n) ; 消息 = Θ(n log log n) （最优）
# 丢包概率 1-p:PUSH 轮数 = log_{1+p}(n) + (1/p)·ln(n) ± o(log n)
# 下界 : 地址盲算法需 Ω(n log log n) 条消息；O(log n) 轮内完成需 Ω(n log n) 条消息
算法逻辑解说：三种模式的差别只体现在两行上——“本轮新增感染”的期望与“本轮谁发消息”。push 的发送者是知情者（头部便宜、尾部昂贵），pull 的发送者是未知者（头部昂贵、尾部便宜），push-pull 两者叠加（头部增长因子 $\times3$、尾部沿用 pull 的超指数收缩）。
正确性论证：这三条递推式是对随机过程的一阶矩（期望）近似，其合法性来自”每个接触独立且均匀随机”，因此新增感染数服从二项分布，期望即上式；把期望值当作确定值使用，误差由切诺夫界控制，得到的就是”高概率（with high probability）”结论。它们不是精确等式：真实的 $i_t$ 是随机变量，且在 $i_t$ 很小时（前几轮）方差相对较大——这正是”流行病可能早夭”的根源（见 6.2.9 的分支过程分析）。
复杂度：递推式本身 $O(\text{轮数})=O(\log n)$ 次迭代，每种模式 $O(1)$ 时间。
6.4 代码示例与分布式实现
6.4.1 Gossip 传播模拟器（push / pull / push-pull 三模式对比）
"""Gossip 传播模拟器：push / pull / push-pull 三种模式，SIR 状态，纯离散轮次模拟。
每个节点处于三种状态之一：
S = susceptible（易感，尚未收到消息）
I = infective （感染，已收到消息并主动参与传播）
R = removed （移除，已收到消息但已停止传播，仅当 stop_after 有限时出现）
一轮（round）= 一次同步的全局时间片：所有节点同时动作，轮末统一生效。
"""
import random
S, I, R = 0, 1, 2
def simulate(n, mode, seed=42, stop_after=None, cap=400):
"""返回 (每轮感染比例, 总轮数, 总联系次数, 有效联系次数, 达50%轮数, 尾部轮数)。
消息计数口径：一次“联系”(contact) = 一条消息。
push : 每个 I 节点每轮向 1 个随机节点推送 -> 每轮 i 条
pull : 每个 S 节点每轮向 1 个随机节点拉取 -> 每轮 s 条
push-pull : I 节点推送 + S 节点拉取 -> 每轮 i+s = n 条
"""
rng = random.Random(seed)
state = [S] * n
state[0] = I # 节点 0 是唯一的初始携带者
age = [0] * n # 已保持 I 状态的轮数
history, messages, useful = [], 0, 0
final_round = 0
half_round = None
for rnd in range(1, cap + 1):
infective = [i for i in range(n) if state[i] == I]
susceptible = [i for i in range(n) if state[i] == S]
newly = []
if mode == "push":
for _ in infective:
v = rng.randrange(n)
messages += 1
if state[v] == S: # 命中易感节点 -> 有效
newly.append(v); useful += 1
elif mode == "pull":
for u in susceptible:
v = rng.randrange(n)
messages += 1
if state[v] != S: # 拉到了知情节点 -> 有效
newly.append(u); useful += 1
else: # push-pull
for _ in infective:
v = rng.randrange(n); messages += 1
if state[v] == S:
newly.append(v); useful += 1
for u in susceptible:
v = rng.randrange(n); messages += 1
if state[v] != S:
newly.append(u); useful += 1
for v in newly: # 轮内按“轮初状态”判定，轮末统一生效
if state[v] == S:
state[v] = I; age[v] = 0
if stop_after is not None: # 有限感染期 -> 出现 R 状态
for i in range(n):
if state[i] == I:
age[i] += 1
if age[i] >= stop_after:
state[i] = R
known = sum(1 for s in state if s != S)
history.append(known / n)
if half_round is None and known >= n / 2:
half_round = rnd
if known == n or not [s for s in state if s == I]:
final_round = rnd
break
thr90 = next((t + 1 for t, v in enumerate(history) if v >= 0.9), None)
tail = None if (thr90 is None or final_round is None) else final_round - thr90 + 1
return history, final_round, messages, useful, half_round, tail
def plot_curves(series, width=66, height=17):
"""series: [(label, char, [ratio...])] -> ASCII 折线图（纵轴比例，横轴轮数）"""
max_t = max(len(r) for _, _, r in series)
grid = [[" "] * width for _ in range(height)]
for _, ch, ratios in series:
for t, v in enumerate(ratios):
x = int(round(t * (width - 1) / max(1, max_t - 1)))
y = height - 1 - int(round(min(max(v, 0.0), 1.0) * (height - 1)))
grid[y][x] = ch
out = []
for row in range(height):
pct = int(round((height - 1 - row) * 100 / (height - 1)))
out.append("%4d%%|" % pct + "".join(grid[row]))
out.append(" +" + "-" * width)
axis = [" "] * width
step = max(1, max_t // 10)
for k in range(0, max_t + 1, step):
x = min(int(round(k * (width - 1) / max(1, max_t - 1))), width - len(str(k)))
for j, c in enumerate(str(k)):
if x + j < width:
axis[x + j] = c
out.append(" " + "".join(axis) + " <- 轮数")
return "\n".join(out)
if __name__ == "__main__":
random.seed(2026)
for n in (100, 1000, 10000):
print("=" * 78)
print("n = %d 节点，初始只有节点 0 知道消息（无停止规则，感染节点持续传播）" % n)
print("=" * 78)
rows, curves = [], []
for mode, ch in (("push", "p"), ("pull", "l"), ("push-pull", "b")):
h, rnds, msg, use, half, tail = simulate(n, mode)
rows.append((mode, rnds, half, tail, msg, use))
curves.append((mode, ch, h))
print(plot_curves(curves))
print(" 图例: p = push, l = pull, b = push-pull")
print()
print(" 模式 轮数 达50%轮数 尾部轮数(90%->100%) 联系次数 有效联系 每节点消息")
for mode, rnds, half, tail, msg, use in rows:
print(" %-10s %5d %9d %12d %13d %10d %11.1f" %
(mode, rnds, half, tail, msg, use, msg / n))
print()
print(" 结论: push 头部最快但尾部拖沓；pull 头部每轮空转 ~n 条查询；")
print(" push-pull 用最少轮数完成，且每轮每节点最多发 1 条消息。")
print()
print("=" * 78)
print("扩展性验证：完成轮数是否随 log2(n) 增长")
print("=" * 78)
print(" 模式 n 轮数 log2(n) 联系次数 每节点消息")
for mode in ("push", "pull", "push-pull"):
for n in (100, 1000, 10000):
h, rnds, msg, use, half, tail = simulate(n, mode, seed=7)
lg = n.bit_length() - 1
print(" %-10s %6d %7d %8.1f %10d %10.1f" % (mode, n, rnds, lg, msg, msg / n))
r100 = simulate(100, "push-pull", seed=7)[1]
r10k = simulate(10000, "push-pull", seed=7)[1]
assert r10k - r100 <= 12, (r100, r10k)
print()
print(" 断言通过：节点数扩大 100 倍，push-pull 完成轮数仅增加 %d 轮（%d -> %d）。"
% (r10k - r100, r100, r10k))
print(" 注：轮数无法低于“常数扇出生成树的高度”，O(log n) 是所有 gossip 形式的下界。")
实际输出（节选，n = 1000）：
100%| b b l l p p p p
94%| l p
88%| b p
81%|
75%| l p
69%|
62%|
56%| b
50%| l p
44%|
38%|
31%| p
25%| b l
19%| p
12%| l
6%| b l l
0%|b b b l p
+------------------------------------------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 <- 轮数
模式 轮数 达50%轮数 尾部轮数(90%->100%) 联系次数 有效联系 每节点消息
push 17 10 5 6870 1243 6.9
pull 13 10 3 9359 999 9.4
push-pull 9 6 2 9000 1318 9.0
模式 n 轮数 log2(n) 联系次数 每节点消息
push 100 16 6.0 930 9.3
push 1000 17 9.0 6872 6.9
push 10000 21 13.0 76236 7.6
pull 100 11 6.0 831 8.3
pull 1000 12 9.0 8756 8.8
pull 10000 19 13.0 150534 15.1
push-pull 100 7 6.0 700 7.0
push-pull 1000 9 9.0 9000 9.0
push-pull 10000 12 13.0 120000 12.0
【代码做什么？】
simulate()建立一个 $n$ 节点的同步轮次世界，节点 0 是唯一初始知情者。- 每轮先按模式收集”谁向谁发了消息”：push 由 $I$ 节点发起、pull 由 $S$ 节点发起、push-pull 两者都发起；每条联系计 1 条消息（
messages），若这次联系把消息带给了新节点则计入useful。 - 轮内所有判定都用轮初状态（
state[v] == S），轮末统一生效——这就是”同步轮”语义，避免了同一轮内先后顺序带来的偏差。 - 记录每轮结束时”已知消息的节点比例”，最后用
plot_curves()把三条曲线画在一张 ASCII 图上。 - 输出对比表（轮数、达 50% 轮数、尾部轮数、联系次数、有效联系、每节点消息），并对 $n=100/1000/10000$ 重复，验证轮数随 $\log n$ 增长。
【分布式机制透视】
- 同步轮 vs 真实异步：真实 gossip 没有全局轮，每个节点有自己的定时器；用”轮”抽象是因为只要各节点周期近似相同，轮次分析就能刻画延迟。代码里”轮末统一生效”对应现实中”这一轮发的消息都在下一轮被处理”。
- 随机选对端：
rng.randrange(n)模拟”从均匀随机成员视图中挑一个伙伴”。真实系统只用部分视图（M_i里只有几十个地址），只要采样近似均匀，分析结论依然成立。 - 消息与冗余：
messages计量所有发出的联系，useful计量真正带来新信息的联系，二者之差就是 gossip 的冗余成本。push 的冗余集中在尾部（6870 − 1243），pull 的冗余集中在头部（9359 − 999），这与 6.2.8 的分析完全一致。 - S 状态即”未收到”：
state[v] == S就是”这条消息对这个节点而言仍是易感态”。若把stop_after设为有限值，$I$ 会在若干轮后变成 $R$，此时传播链断裂，模拟器会提前结束——这正是 rumor mongering 的场景（见 6.4.2）。
【与理论的对应】
- 对应算法 6.3.4 的递推式：
newly的期望正是 $x_t(1-(1-i_t/n)^{b})$（push）与 $x_t\cdot i_t/n$（pull）。 - 对应 6.2.4 的解 $y(t)=n/(1+ne^{-bt})$：曲线前段的指数上升就是 logistic 的指数段。
- 输出的 “轮数 ≈ $\log_2 n$ 级别”验证了 6.2.4 第四步与 6.2.8 的轮数公式；尾部轮数的差异（push 5 轮、push-pull 2 轮）验证了”push 尾部几何收缩 / pull-pull 尾部双重指数收缩”。
- 一个重要而诚实的说明：本模拟器按”每次联系计 1 条消息”的朴素口径计数，于是 push-pull 被记成 $n\times$轮数。理论上的 $\Theta(n\log\log n)$ 最优性来自更精细的口径——只统计携带该消息的传输，因为 push-pull 在增长阶段的每轮传输量正比于知情人数而非 $n$，等比求和只有 $O(n)$。成本口径会改变”谁最优”的结论，这一点本身值得记住。
6.4.2 反熵与流言传播的收敛性对比
"""反熵（Anti-Entropy）与流言传播（Rumor Mongering）的收敛性对比实验。
场景：n 个副本节点维护同一份数据。前 15 轮系统处于“稳定期”（没有任何新更新），
第 16 轮在节点 0 注入一条新更新，观察两种维护协议的传播过程与通信开销。
Anti-Entropy : 每轮每个节点随机挑一个伙伴，交换摘要/全量状态（无论有无更新）
Rumor Mongering: 收到新更新的节点变 “hot”，每轮向随机节点推送；若对方已
经有该更新（冗余接触），则以概率 1/k 变为 “cold” 并停止传播
"""
import random
import math
N = 500
STEADY_ROUNDS = 15
RUN_ROUNDS = 60
def anti_entropy_round(holders, n, rng):
"""一轮反熵（push-pull）：每个节点与一个随机伙伴交换状态。返回 (消息数, 新增知情数)。"""
msgs, new = 0, 0
for i in range(n):
j = rng.randrange(n)
msgs += 1 # 一次反熵会话 = 一条（携带摘要的）消息，无更新也发
if j in holders and i not in holders:
holders.add(i); new += 1
elif i in holders and j not in holders:
holders.add(j); new += 1
return msgs, new
def rumor_round(hot, holders, n, rng, k):
"""一轮流言传播。返回 (消息数, 新增知情数, 下一轮的 hot 集合)。"""
msgs, new = 0, 0
nxt = set()
for u in hot:
v = rng.randrange(n)
msgs += 1
if v in holders: # 冗余接触：以概率 1/k 停止（变 cold）
if rng.random() >= 1.0 / k:
nxt.add(u)
else: # 有效接触：对方变 hot
holders.add(v); new += 1
nxt.add(u); nxt.add(v)
return msgs, new, nxt
def plot_curves(series, width=64, height=13):
max_t = max(len(r) for _, _, r in series)
grid = [[" "] * width for _ in range(height)]
for _, ch, ratios in series:
for t, v in enumerate(ratios):
x = int(round(t * (width - 1) / max(1, max_t - 1)))
y = height - 1 - int(round(min(max(v, 0.0), 1.0) * (height - 1)))
grid[y][x] = ch
out = []
for row in range(height):
out.append("%4d%%|" % int(round((height - 1 - row) * 100 / (height - 1))) + "".join(grid[row]))
out.append(" +" + "-" * width)
axis = [" "] * width
for kk in range(0, max_t + 1, max(1, max_t // 8)):
x = min(int(round(kk * (width - 1) / max(1, max_t - 1))), width - len(str(kk)))
for j, c in enumerate(str(kk)):
axis[x + j] = c
out.append(" " + "".join(axis) + " <- 注入更新后的轮数")
return "\n".join(out)
def solve_q(k):
"""求解 q = exp(-(1+k)(1-q))：流言传播结束后仍未收到更新的节点比例（均值场预测）。"""
q = 0.5
for _ in range(200):
q = math.exp(-(1 + k) * (1 - q))
return q
if __name__ == "__main__":
rng = random.Random(2026)
# ---------- 阶段 1：稳定期，没有任何新更新 ----------
print("=" * 74)
print("阶段 1：稳定期（无任何新更新），观察两种协议是否还在产生流量")
print("=" * 74)
print(" 轮次 Anti-Entropy 消息数 Rumor Mongering 消息数")
holders = set() # 反熵世界里“所有节点状态一致”= 更新集合相同，此处无更新
for rnd in range(1, STEADY_ROUNDS + 1):
ae_msgs, _ = anti_entropy_round(holders, N, rng)
rm_msgs, _, _ = rumor_round(set(), holders, N, rng, k=2)
if rnd <= 5 or rnd % 5 == 0:
print(" %4d %18d %22d" % (rnd, ae_msgs, rm_msgs))
print(" => 反熵每轮固定产生 n 条消息（无更新时全是无用开销）；流言传播为 0（无 hot 节点）。")
# ---------- 阶段 2：注入一条新更新 ----------
print()
print("=" * 74)
print("阶段 2：第 16 轮在节点 0 注入一条新更新，比较传播速度与最终覆盖率")
print("=" * 74)
ae_holders, rm_holders = {0}, {0}
hot = {0}
ae_curve, rm_curve = [], []
ae_msgs_total = rm_msgs_total = 0
ae_msgs_until_done = 0
ae_done = None
for step in range(1, RUN_ROUNDS + 1):
m1, _ = anti_entropy_round(ae_holders, N, rng)
m2, _, hot = rumor_round(hot, rm_holders, N, rng, k=2)
ae_msgs_total += m1; rm_msgs_total += m2
if ae_done is None:
ae_msgs_until_done += m1
ae_curve.append(len(ae_holders) / N); rm_curve.append(len(rm_holders) / N)
if ae_done is None and len(ae_holders) == N:
ae_done = step
print(plot_curves([("anti-entropy", "a", ae_curve), ("rumor-mongering", "r", rm_curve)]))
print(" 图例: a = Anti-Entropy（兜底、保证全覆盖）, r = Rumor Mongering（k=2，快速但不保证全覆盖）")
print()
print(" Anti-Entropy : 全部 %d 个节点达成一致用了 %d 轮（达一致前共 %d 条消息），"
% (N, ae_done, ae_msgs_until_done))
print(" 此后 %d 轮仍在“例行公事”，累计花费 %d 条消息 —— 这就是反熵的稳定期开销。"
% (RUN_ROUNDS - ae_done, ae_msgs_total - ae_msgs_until_done))
print(" Rumor Mongering: %d 轮后覆盖 %.1f%%（%d/%d），花费 %d 条消息，此后彻底静默"
% (RUN_ROUNDS, 100 * len(rm_holders) / N, len(rm_holders), N, rm_msgs_total))
print(" => 流言传播快（前几轮就覆盖绝大多数节点）却漏掉少量节点；反熵慢但最终必然全覆盖。")
# ---------- 阶段 3：验证“未被覆盖节点数”的理论预测 ----------
print()
print("=" * 74)
print("阶段 3：流言传播的覆盖率缺陷有多大？（%d 次实验平均，n=%d）" % (40, N))
print("=" * 74)
print(" k 实测未覆盖比例 理论 q=e^{-(1+k)(1-q)} 实测未覆盖节点数")
for k in (1, 2, 3, 5):
uncovered = 0
for t in range(40):
r = random.Random(1000 + 37 * t + k)
hs, ht = {0}, {0}
for _ in range(120):
if not ht:
break
_, _, ht = rumor_round(ht, hs, N, r, k)
uncovered += N - len(hs)
frac = uncovered / 40 / N
print(" %3d %16.3f %22.3f %18.1f" % (k, frac, solve_q(k), uncovered / 40))
print(" => 未覆盖比例近似满足 q = e^{-(1+k)(1-q)}：停止规则越宽松(k 越大)漏得越少，")
print(" 但只要 k 有限，就存在常数比例的节点永远收不到 —— 这正是必须叠加反熵兜底的原因。")
实际输出（节选）：
轮次 Anti-Entropy 消息数 Rumor Mongering 消息数
1 500 0
5 500 0
15 500 0
=> 反熵每轮固定产生 n 条消息（无更新时全是无用开销）；流言传播为 0（无 hot 节点）。
100%| aaaa aaaaaaaaaaaaaaa aaaaaaaaaaaaaa aaaaaaaaaaaaaaa aaaaaaaa
92%| rrrrrrrrrrr rrrrrrrrrrrrrr rrrrrrrrrrrrrrr rrrrrrrr
83%| r
75%| r
67%| a r
50%| r
33%| r
25%| r
17%| a
8%| a rr
0%|rrrr
+----------------------------------------------------------------
0 7 14 21 28 35 42 49 56 <- 注入更新后的轮数
Anti-Entropy : 全部 500 个节点达成一致用了 6 轮（达一致前共 3000 条消息），
此后 54 轮仍在“例行公事”，累计花费 27000 条消息 —— 这就是反熵的稳定期开销。
Rumor Mongering: 60 轮后覆盖 92.6%（463/500），花费 1417 条消息，此后彻底静默
k 实测未覆盖比例 理论 q=e^{-(1+k)(1-q)} 实测未覆盖节点数
1 0.209 0.203 104.7
2 0.060 0.060 30.0
3 0.020 0.020 9.9
5 0.003 0.003 1.3
【代码做什么？】
anti_entropy_round()：模拟”每轮每个节点随机挑一个伙伴交换状态”。无论有没有更新都发消息——这就是反熵稳定期开销的来源。rumor_round()：模拟”hot 节点推送 + 冗余接触以概率 $1/k$ 变冷”。返回下一轮仍然 hot 的集合（新被感染的节点也进入 hot）。- 阶段 1（无更新）对比两者的空转流量；阶段 2 注入一条更新，画出两条覆盖率曲线；阶段 3 用 40 次独立实验统计”最终未覆盖节点数”，并与解析解 $q=e^{-(1+k)(1-q)}$ 对照。
solve_q()用不动点迭代解那个超越方程。
【分布式机制透视】
- 两个协议的时间尺度不同：反熵是”周期性、无条件”的（代码里每轮都跑），流言传播是”事件驱动、有生命周期”的（
hot集合为空就自然静默）。真实系统里两者必须共存：Cassandra 用秒级 gossip 传播成员状态（流言式），用低频 repair 修数据（反熵式）。 holders集合就是”副本状态差异”的抽象：一条更新在多少个节点上存在，就代表副本有多不一致。反熵的合并是单调的（集合只增不减），流言传播则可能”传一半就停”。- 消息计量的诚实性：反熵的 1 条消息是”一次摘要交换”，真实数据量大时还要额外传输差异；流言传播的 1 条消息就是整条更新。所以”反熵 27000 条 vs 流言 1417 条”这个对比在条数上成立，在字节数上差距会缩小——但”稳定期是否空转”这一本质差别与字节数无关。
【与理论的对应】
- 6 轮达成一致 ↔ 算法 6.3.1 的活性证明与”$h$ 每轮翻倍”分析（$n=500$，$\log_2 500\approx9$，实测更快）。
- 覆盖率 92.6% ↔ 6.2.6 的 $q=e^{-(1+k)(1-q)}$；阶段 3 的四个 $k$ 值上，实测与理论几乎逐位吻合（0.209/0.203、0.060/0.060、0.020/0.020、0.003/0.003）。
- “反熵最终 100%、流言传播停在 92.6%” ↔ 6.2.7 的两层结构：流言负责快，反熵负责全。
6.4.3 Push-Sum 平均值计算
"""Push-Sum 聚合 gossip：用“比值和”(s_i, w_i) 让全网节点收敛到真实平均值。
核心不变式： Σ_i s_i = Σ_i x_i （质量守恒） Σ_i w_i = n （权重守恒）
因此 (Σ_i s_i) / (Σ_i w_i) = 真实平均 μ
每个节点只用本地估计值 s_i / w_i，在 O(log n) 轮内收敛到 μ。
程序最后对照三种"直觉上很自然但错误"的做法：
1) 直接拷贝随机邻居的值 -> 收敛到某个随机初始值，不是均值
2) 无权重地对邻居取平均 -> 收敛到“度加权平均”，不是算术平均
"""
import random
def push_sum(n, values, rounds=30, seed=1):
"""每个节点每轮把自己的 (s,w) 减半，把另一半发给一个随机节点。"""
rng = random.Random(seed)
s = [float(v) for v in values]
w = [1.0] * n
trace = []
for t in range(rounds):
new_s = [x / 2.0 for x in s] # 先算出保留的一半
new_w = [x / 2.0 for x in w]
for i in range(n):
j = rng.randrange(n - 1) # 随机选一个“别人”，避免自环
if j >= i:
j += 1
new_s[j] += s[i] / 2.0 # 另一半寄出去
new_w[j] += w[i] / 2.0
s, w = new_s, new_w
est = [s[i] / w[i] for i in range(n)]
mu = sum(values) / n
err = max(abs(e - mu) for e in est)
trace.append((t + 1, err, sum(s), sum(w), min(w)))
return s, w, trace
def copy_gossip(n, values, rounds, seed):
"""错误做法 1：拉到随机邻居的值就直接覆盖自己（纯拷贝，不是求平均）。"""
rng = random.Random(seed)
x = list(map(float, values))
for _ in range(rounds):
nxt = list(x)
for i in range(n):
nxt[i] = x[rng.randrange(n)]
x = nxt
return x
def neighbor_average(n, adj, values, rounds):
"""错误做法 2：每轮把自己和所有邻居的值取算术平均（无权重）。"""
x = list(map(float, values))
for _ in range(rounds):
nxt = list(x)
for i in range(n):
nxt[i] = (x[i] + sum(x[j] for j in adj[i])) / (1 + len(adj[i]))
x = nxt
return x
if __name__ == "__main__":
N = 64
random.seed(2026)
values = [random.uniform(0, 100) for _ in range(N)]
true_avg = sum(values) / N
print("=" * 74)
print("Push-Sum 求全网平均：n=%d，真实平均值 μ = %.6f" % (N, true_avg))
print("=" * 74)
print(" 轮次 最大绝对误差 Σs_i（应恒为 Σx_i） Σw_i（应恒为 n） min(w_i)")
s, w, trace = push_sum(N, values, rounds=60, seed=1)
for t, err, ss, ww, mw in trace:
if t <= 3 or t % 10 == 0:
print(" %4d %18.8f %20.4f %15.4f %10.6f" % (t, err, ss, ww, mw))
est = [s[i] / w[i] for i in range(N)]
worst = max(abs(e - true_avg) for e in est)
print()
print(" 60 轮后：所有 %d 个节点的估计值最大误差 = %.3e" % (N, worst))
assert abs(sum(s) - sum(values)) < 1e-6, "质量守恒被破坏"
assert abs(sum(w) - N) < 1e-6, "权重守恒被破坏"
assert worst < 1e-6, "未收敛到真实平均值"
print(" 断言通过：Σs_i 与 Σw_i 严格守恒，且每个节点的 s_i/w_i 都收敛到 μ。")
print()
print("=" * 74)
print("对照实验：两种“看起来对”的错误做法")
print("=" * 74)
c = copy_gossip(N, values, rounds=400, seed=3)
print(" 1) 纯拷贝邻居值（voter 模型）：400 轮后全网的值为 %.4f，真实平均 %.4f，"
% (c[0], true_avg))
print(" 误差 %.4f —— 这是某个随机节点的初始值，收敛到它是必然的，收敛到均值是偶然的。" % abs(c[0] - true_avg))
adj = [[] for _ in range(N)] # 构造一个度分布高度不均的图
rng = random.Random(11)
for i in range(N):
for _ in range(rng.choice([1, 1, 2, 8])): # 度数从 1 到 8 不等
j = rng.randrange(N)
if j != i and j not in adj[i]:
adj[i].append(j); adj[j].append(i)
na = neighbor_average(N, adj, values, rounds=500)
deg_w = sum((len(adj[i]) + 1) * values[i] for i in range(N)) / sum(len(adj[i]) + 1 for i in range(N))
print(" 2) 无权重邻居平均（500 轮后）：全网值 %.4f，真实平均 %.4f，误差 %.4f"
% (na[0], true_avg, abs(na[0] - true_avg)))
print(" 它收敛到的其实是“度加权平均” %.4f —— 因为随机游走的平稳分布正比于度数。" % deg_w)
print()
print(" 结论：要让 gossip 正确计算聚合值，必须让“消息质量”和“自身权重”一起流动，")
print(" 用比值 s_i/w_i 作估计（push-sum），而不是对值本身做平均或拷贝。")
实际输出（节选）：
Push-Sum 求全网平均：n=64，真实平均值 μ = 51.292758
轮次 最大绝对误差 Σs_i（应恒为 Σx_i） Σw_i（应恒为 n） min(w_i)
1 40.21910342 3282.7365 64.0000 0.500000
3 40.21910342 3282.7365 64.0000 0.125000
10 4.10353336 3282.7365 64.0000 0.026367
20 0.11856749 3282.7365 64.0000 0.141853
30 0.00411205 3282.7365 64.0000 0.048061
40 0.00013537 3282.7365 64.0000 0.023970
50 0.00000067 3282.7365 64.0000 0.036604
60 0.00000003 3282.7365 64.0000 0.164853
60 轮后：所有 64 个节点的估计值最大误差 = 3.021e-08
断言通过：Σs_i 与 Σw_i 严格守恒，且每个节点的 s_i/w_i 都收敛到 μ。
1) 纯拷贝邻居值（voter 模型）：400 轮后全网的值为 39.8773，真实平均 51.2928，
误差 11.4154 —— 这是某个随机节点的初始值，收敛到它是必然的，收敛到均值是偶然的。
2) 无权重邻居平均（500 轮后）：全网值 49.1404，真实平均 51.2928，误差 2.1523
它收敛到的其实是“度加权平均” 49.1404 —— 因为随机游走的平稳分布正比于度数。
【代码做什么？】
push_sum()让每个节点维护 $(s_i,w_i)$，每轮各自减半并把另一半发给一个随机节点（j != i），收到的份额累加。- 每轮记录三个量：最大估计误差、$\sum s_i$、$\sum w_i$——后两个用于验证不变式。
- 60 轮后断言误差小于 $10^{-6}$，并断言两个守恒量精确不变。
copy_gossip()与neighbor_average()分别实现两种”直觉上很对”的错误做法，用来做对照。
【分布式机制透视】
- “质量”和”权重”必须绑在一起传输，这是 push-sum 与朴素平均的本质区别。它对应真实系统里的”带权聚合”：例如要计算全网平均负载，每个节点必须把自己的负载除以节点数——但谁都不知道精确的 $n$，于是用 $w_i$ 这个”自我称重”的分母在传播中自动形成。”权重的流动”其实就是把”$n$ 是多少”这个全局信息给分布式地算出来了。
- 随机选对端 + 同步轮：与 6.4.1 相同的抽象。异步实现要额外解决”怎么知道已经收敛”的问题（可用多轮估计值的方差作为停止判据）。
- 初始阶段的误差不下降（前 3 轮误差恒为 40.2）：因为 $w_i$ 的分布还没有混合，估计值取自极少数样本。这是 push-sum 的”头部慢”，与 pull gossip 的头部慢同源，都来自”信息还没扩散开”。
【与理论的对应】
- $\sum s_i$ 与 $\sum w_i$ 两列在整个过程中数值不变，验证了算法 6.3.3 的不变式 1 与不变式 2；因此 $\frac{\sum s_i}{\sum w_i}=51.292758$ 这个不变量始终等于真平均。
- 误差从 40 → 4 → 0.12 → 0.0041 → 0.000135 → 6.7e-7，大致每 10 轮下降两个数量级 ⇒ 几何收敛，对应”$O(\log n+\log\frac1\varepsilon)$ 轮”的复杂度结论。
- 对照组精确复现了 6.2.12 的度加权公式：邻接平均收敛到 49.1404，与该图上的度加权平均完全相等（不是巧合，而是行随机迭代矩阵平稳分布的直接后果）。
6.5 性能与可扩展性分析
（1）消息复杂度与延迟
| 协议 | 每轮消息数 | 总消息数 | 轮数（延迟） | 覆盖保证 |
|---|---|---|---|---|
| Push（无停止规则） | $i_t$（知情人数） | $\Theta(n\log n)$ | $\log_2 n+\ln n$ | 高概率全覆盖（尾部昂贵） |
| Pull | $x_t$（未知人数） | $\Theta(n\log n)$ | $\Theta(\log n)$ | 高概率全覆盖（头部昂贵） |
| Push-Pull | $i_t+x_t=n$（朴素口径） | $\Theta(n\log\log n)$（只计携带消息的传输，最优） | $\log_3 n+O(\log\log n)$ | 高概率全覆盖 |
| Anti-Entropy | $n$（周期性，无条件） | $O(n)$/轮，长期 $O(n\cdot T/\Delta)$ | $O(\log n)$ | 最终一致（概率 1） |
| Rumor Mongering | 仅 hot 节点数 | $O(kn)$ | 头部 $O(\log n)$，尾部停滞 | 不保证：漏 $\Theta(n)$ |
（2）关键结论与工程换算
- 每节点每轮 $O(1)$ 条消息 ⇒ 全网每轮 $O(n)$ 条，总 $O(n\log n)$ 量级。这是 gossip”轻量”的精确含义：每个节点的负载与集群规模无关，这正是它相对树状多播（ACK 汇聚到根、$O(N)$ 控制开销）的根本优势。
- 延迟 = 轮数 × gossip 周期 $\Delta$：$\Delta=1$ 秒时，$n=1000$ 约 10 秒、$n=10^6$ 约 20 秒、$n=10^9$ 约 30 秒。规模涨 1000 倍，收敛时间只涨 10 秒。
- 空间复杂度：每节点 $O(1)$ 状态（+ 数据本身），只需要部分成员视图（几十个地址），不需要全量成员表，也不需要树结构。
- 容错：50% 丢包或 50% 节点崩溃 ⇒ 有效接触率减半 ⇒ 达到同样可靠性的轮数约翻倍（不是不可用，而是变慢）。任意比例的节点故障都不会”切断”传播，因为没有固定结构可被切断——这正是随机选择对确定性的胜利。
（3）与确定性多播的系统级对比
| 维度 | 树状可靠多播（SRM / RMTP） | Gossip / 流行病多播 |
|---|---|---|
| 覆盖语义 | 确定性 100%（靠 ACK/NAK 修复） | 高概率全覆盖；纯 rumor mongering 只保证”大多数人” |
| 控制开销 | $O(N)$ ACK/NAK [Birman99]；NAK 风暴风险 | 每节点 $O(1)$/轮，无确认风暴，但有消息冗余 |
| 结构依赖 | 生成树 + 完整组成员；树断需重建 | 无结构，只需部分成员视图 |
| 故障容忍 | 内部节点崩溃 ⇒ 整棵子树失败 | 任意节点崩溃只损失”那一份”流量，信息仍从其他路径到达 |
| 延迟 | 树高 $O(\log N)$，可确定性规划 | $O(\log N)$ 轮 × 周期，高概率而非确定 |
| 带宽瓶颈 | 根/父节点、ACK 汇聚点 | 无集中热点（拓扑感知后核心链路负载 $O(1)$） |
| 最适合 | 小规模、强一致、可静态规划的组播 | 大规模、动态成员、容忍最终一致 |
（4）缺点清单（必须诚实面对）
- 不保证 100% 覆盖：纯 push/pull/rumor mongering 都只给概率保证；要全覆盖必须叠加反熵（或”push + 反熵”两层结构）。
- 消息冗余：push 尾部、pull 头部都有大量无效通信；拓扑感知、Merkle 摘要、$1/k$ 停止规则都是在削这部分浪费。
- 终止判据困难：Karp 等人明确指出，朴素的 push-pull 必须精确地在恰当的时刻停止（论文中取 $\lceil \log n+\log\log n\rceil$ 轮这样的全局估计）——停得太早会留下常数比例的节点没收到，停得太晚通信量会从 $O(n\log\log n)$ 退化到 $O(n\log n)$。他们为此设计了分布式的 median-counter 终止算法，并证明它能容忍 $f$ 个对抗性节点故障（只漏 $O(f)$ 个节点）。
- 延迟不是确定性的：不能像树状多播那样给出”最多 $T$ 毫秒”的硬承诺，只能给”高概率在 $k$ 轮内”。
- 对成员视图质量敏感：如果成员视图不是近似均匀采样（例如新节点都只知道 seeds），传播会退化为”星形”，头部的指数增长消失。
6.6 关键要点
- Gossip 用”以高概率正确”换取了确定性协议拿不到的可扩展性与容错性：$O(\log N)$ 轮、每节点每轮 $O(1)$ 条消息、无中心、无结构、任意节点故障都不致命——这是”概率换规模”范式的样板。
- push 与 pull 的浪费发生在过程的两端：push 头部高效、尾部 $\Theta(n\log n)$ 条消息白费；pull 头部每轮空转、尾部以双重指数 $x\leftarrow x^2/n$ 在 $O(\log\log n)$ 轮内清干净。push-pull 把两者拼起来，达到最优的 $\Theta(n\log\log n)$。
- 反熵保证”全”但持续付出代价，流言传播保证”快”但会留漏网之鱼：$q=e^{-(1+k)(1-q)}$ 量化了”谣言之死”——有限 $k$ 下总有常数比例的节点永远收不到。真实系统的标准做法是流言扩散 + 反熵兜底（Cassandra、Dynamo、Bimodal Multicast 皆然）。
- 随机选择本身就是容错机制：确定性邻居在故障时会切断传播路径，随机选择让每一轮都有大量备选路径；代价是消息冗余。所有拓扑优化（子网内概率 $1-1/n_i$、分层、spatial）都必须保住这条性质，否则会重新引入单点。
- 做聚合时，值必须和权重一起流动：对邻居值取无权重平均会收敛到度加权平均，直接拷贝邻居值会收敛到某个随机的初始值——只有 push-sum 这类”比值和”算法才能在 $O(\log n)$ 轮内算出真正的全局平均。
- $\log N$ 的威力在于它长得太慢：$\log_2$ 从 1000 到 10 亿只从 10 涨到 30，所以 gossip 的延迟几乎不随规模变化——这是”可扩展性”这个词最有力的实例。
6.7 常见陷阱与注意事项
- 把”$O(\log N)$ 轮”当成”$O(\log N)$ 条消息”。轮数与消息数是两个独立维度：push 的轮数只有 $\log_2 n+\ln n$，但消息数是 $\Theta(n\log n)$，因为尾部每一轮都在让近 $n$ 个节点白跑一趟。正确做法：分别报告延迟与通信开销，并明确口径（是”每次联系”还是”携带新消息的传输”）。
- 忽略 gossip 的终止问题。停止太早，剩下常数比例的节点永远收不到；停止太晚，通信量从 $O(n\log\log n)$ 退化到 $O(n\log n)$。正确做法：用携带”消息年龄”的计数器（如 Karp 等人的 median-counter）或叠加反熵兜底，而不是固定”跑 10 轮就算了”。
- 以为 rumor mongering 能覆盖所有人。它是会”熄火”的：$k$ 有限时未覆盖率 $q$ 满足 $q=e^{-(1+k)(1-q)}$，$k=1$ 时高达 20%。正确做法：把 rumor mongering 当作”快速路径”，另设 anti-entropy 作”慢速但完整”的兜底。
- 在稳定期仍然每轮传全量数据。反熵的 $O(n)$/轮流量在无更新时 100% 是浪费，而且随数据量线性增长。正确做法：先比 Merkle 树根哈希，相同就立即结束；只传差异子树。
- 选对端时”就近”选得太彻底。若所有节点都只和同机架内的邻居 gossip，跨机架的新消息就永远传不出去（传播被分区隔离）；反之若完全随机，核心链路负载又是 $O(N)$。正确做法：以 $1-1/n_i$ 的概率选子网内、$1/n_i$ 选子网外——既保住扩散性，又把跨网负载压到 $O(1)$。
- 把消息丢失等同于”这一轮浪费了”。gossip 对丢包极其鲁棒（有效接触率打折、轮数按比例增加即可），但前提是每一轮都重新随机选对端；如果实现里把”对端”缓存成固定列表且不刷新，一次网络抖动就可能让两个分区长期失联。
- 用 gossip 做平均时直接对值取平均或拷贝。前者收敛到度加权平均（非正则图上与真值偏差可达 4% 以上，实验中 49.14 vs 51.29），后者收敛到某个随机初始值（误差 $O(\sigma)$）。正确做法：push-sum 的 $(s_i,w_i)$ 比值和，且注意浮点误差与 $w_i$ 过小导致的数值不稳。
- 忽略了消息体积与”更新种类”的差异。gossip 一条消息可能是 100 字节的成员状态，也可能是 100 MB 的数据块；同样”1 条消息/轮”意味着完全不同的带宽。正确做法：gossip 只承载元数据/小更新（成员表、版本向量、摘要），大批量数据走单独通道——这正是 Cassandra 让 gossip 只管成员、让 repair 走 Merkle 差异的原因。
6.8 思考题（带答案）
问题 1（计算题）：某集群有 $n=10^6$ 个节点，采用 push gossip，每个感染节点每轮向 $b=3$ 个随机节点推送，gossip 周期 $\Delta=1$ 秒，不设停止规则。请估算（a）覆盖一半节点所需轮数；（b）到达 $t=c\log n$ 时仍未覆盖的节点数（取 $c$ 使 $cb=6$，使用讲义口径 $x\approx n^{2-cb}$）；（c）每个节点发送的消息数上限。若网络有 50% 丢包，上述结论如何变化？
答：（a）头部每轮近似 $\times(1+b)$ 增长（$i_{t+1}\approx i_t(1+b)$，因为每个感染者的 $b$ 次接触几乎都命中易感节点），因此达到 $n/2$ 需要 $\log_{1+b}(n/2)=\log_4(5\times10^5)\approx 9.5$ 轮，约 10 秒。（b）$x\approx n^{2-cb}=n^{2-6}=n^{-4}=10^{-24}<1$，即高概率没有任何节点漏掉；等价地，$y(t)\approx n/(1+n^{1-bc})=n/(1+n^{-5})\approx n$，全部覆盖。（c）每个节点发送 $cb\log n=6\log_2 10^6\approx 120$ 条消息（讲义口径 $cb\log n$）。（d）50% 丢包 ⇒ 有效接触率 $b\to b/2=1.5$ ⇒ 头部从 $\log_4 n$ 变成 $\log_{2.5}n$、尾部从 $\ln n$ 变成 $2\ln n$：要获得与无丢包相同的可靠性，轮数大约翻倍（精确式为 $\log_{1+p}n+\frac1p\ln n$，$p=0.5$）。
问题 2（”直观但错误”）：有同学提出：既然 gossip 每个节点每轮只发 1 条消息，那么”每轮全网消息数 = $n$”，于是 push 和 push-pull 的总消息数都应该是 $n\times$ 轮数，二者一样多。这个推理错在哪里？
答：错在把”每轮每节点都发消息”当成了所有协议的共同前提。（1）push 只有知情节点发消息，头部只有 $i_t\ll n$ 个节点在发，所以头部每轮远小于 $n$ 条；代价出现在尾部：$i_t\approx n$ 时每轮 $\approx n$ 条，而尾部要持续 $\ln n$ 轮 ⇒ 尾部一项就是 $\Theta(n\log n)$。（2）push-pull 的关键在于”一次接触同时服务推与拉两个方向”：在增长阶段每轮传输量正比于知情人数（而不是 $n$），等比求和只有 $O(n)$；只有收缩阶段的 $O(\log\log n)$ 轮才按 $n$ 计费，总计 $\Theta(n\log\log n)$。（3）因此”朴素按每次联系计一条”的口径会系统性高估 push-pull（本文 6.4.1 的模拟器就属于这种口径，$n=1000$ 时 push-pull 记到 9000 条，而 push 只记到 6870 条——但 push-pull 只用 9 轮完成，push 要 17 轮）。成本口径必须与协议的”有用工作量”一致，否则结论会被口径推翻。
问题 3（”直观但错误”）：要计算全网所有节点的平均 CPU 负载，有同学设计了一个 gossip：每个节点每轮随机挑一个邻居，把自己的负载值改成”我和邻居的平均值”。他声称”平均值的平均值还是平均值，所以最终大家都会收敛到真实平均”。请指出错误，并说明正确的做法。
答：错。这个迭代是 $x_i\leftarrow\frac{x_i+\sum_{j\in N(i)}x_j}{1+d_i}$，其迭代矩阵是行随机的，收敛值为 $\frac{\sum_i(1+d_i)x_i}{\sum_i(1+d_i)}$——度加权平均，只有在所有节点度数相同（或完全图）时才等于算术平均。原因：这类平均过程等价于图上的随机游走，其平稳分布正比于度数，度数大的节点的话语权被放大了。本文 6.4.3 的实验精确复现了这一点：一个度数在 1~8 之间变化的图上，收敛值 49.1404 与度加权平均 49.1404 完全一致，而真平均是 51.2928。此外还有一个更严重的错误版本：直接把邻居的值拷贝过来（$x_i\leftarrow x_j$），那不是求平均而是”多数决/选民模型（voter model）”，系统会收敛到某一个初始值 $x_k$，单次运行的误差是 $O(\sigma)$ 且不随轮数下降。正确做法是用 push-sum：每轮把 $(s_i,w_i)$ 同时减半并把一半寄给随机节点，收到则累加，估计值取 $s_i/w_i$。因为 $\sum s_i$ 与 $\sum w_i$ 分别是守恒量，$\frac{\sum s_i}{\sum w_i}$ 恒等于真平均；随机混合再让每个节点在 $O(\log n)$ 轮内收敛到这个比值。
问题 4（系统设计）：Cassandra 集群要求在 1000 个节点规模下，新写入的数据能在秒级被所有副本感知，同时保证任何时刻都不会有数据永久不一致。请说明应该怎样组合本讲的机制，并解释为什么不能只选一种。
答：应当采用两层结构。（1）快层（rumor mongering / gossip）：节点状态、成员关系、schema 版本这类小元数据用每秒一轮的 gossip 快速扩散，头部 $O(\log n)$ 轮（1000 节点约 10 秒内覆盖绝大多数节点），开销只有每节点每轮 1 条消息。（2）全层（anti-entropy + Merkle 树）：数据副本的差异用周期性的反熵修复兜底。因为第一层的 rumor mongering 有 $q=e^{-(1+k)(1-q)}$ 的固有缺陷（$k=1$ 时漏 20%），它永远无法单独保证”所有副本都拿到”；而反熵虽然慢（$O(\log n)$ 轮、每轮 $O(n)$ 条消息），却具备”单调合并 + 概率 1 最终一致”的保证。（3）用 Merkle 树把反熵的成本压下来：两边先比根哈希，相同就一次往返结束，只在哈希不同的子树里传差异，避免”每轮传全量数据”。（4）此外还要在反熵里加抖动（jitter），防止所有节点同一时刻选中同一批对端造成流量尖峰。这正是 Cassandra/Dynamo 的实际架构：gossip 负责成员与状态，repair 负责数据反熵。