Gossip 协议

随机选对端、互相交换最新信息——gossip 用"闲聊"的方式在 O(log N) 轮内把信息传播到整个集群。没有 leader、没有共识、没有单点,代价是收敛前集群状态暂时不一致。从成员传播到反熵修复,gossip 是去中心化分布式系统的信息高速公路。

三类 Gossip

Gossip 的核心是"每个节点周期性随机选一个 peer 交换信息"。根据信息流向分为三种：

Push (Rumor Mongering)

节点有更新 → 主动推给随机 peer → peer 继续推。

适合"hot"更新（最近发生、需要快速传播）。如果更新没有被推够足够多次（rumor stops circulating），需要 fallback（anti-entropy）。

Pull

节点主动从随机 peer 拉最新信息。适合新加入或长时间未同步的节点——只需一次 pull 就能追上。

Push-Pull

双方交换摘要 → 各自拉对方有新于自己的更新。最有效——双方都受益，网络利用率最高。

Epidemic Broadcast

Epidemic 保证了概率性可靠：O(log N) 轮后所有节点收到消息，概率 ≈ 1。

收敛分析

每轮: 每个节点随机选 1 个 peer 做 push-pull
Round 1: 1 node → 2 nodes know
Round 2: 2 → 4
Round 3: 4 → 8
...
Round log₂(N): 所有 node 都知道

这假设完美传播（无限带宽, 无丢包）
实际中: fanout = O(log N) per round → 概率性覆盖

对比可靠广播

• Reliable broadcast (如 Raft AppendEntries): O(N) 消息, 确定性可靠, 需要 leader
• Epidemic gossip: O(log N) 消息 per node, 概率性可靠, 无 leader, 容忍节点故障/网络分区

Anti-Entropy + Merkle Trees

Gossip 可能丢消息（概率性）。Anti-entropy 用全量比较填补遗漏。

Merkle tree: 每个 leaf node = hash(data block), 每个 internal node = hash(children)。两节点比较 root hash → 相同则数据一致 → 不同则递归比较 children → 定位到具体不一致的 block → 只传输这些 block。

优势：不需要传输全部数据就能找到不一致的部分。BitTorrent, Cassandra, Dynamo 都用 Merkle tree 做 anti-entropy。

SWIM 的 Gossip 层

SWIM 的 ping/ping-req 层负责故障检测。检测结果（suspected/confirmed dead）通过 gossip 传播。这是 push gossip 的一条实例：只有 suspected/dead 这类罕见事件被传播。

参考

• 论文⁠: "Epidemic Algorithms for Replicated Database Maintenance" (Demers et al, 1987)
• 论文⁠: "SWIM" (Das et al, 2002 — section 4: Dissemination)

Keywords: gossip, push-pull, epidemic broadcast, anti-entropy, Merkle tree, SWIM, probabilistic reliable