Gossip プロトコル

ランダムなピアを選択し、最新情報を互いに交換する——gossip は「雑談」のような方式で、O(log N) ラウンド以内に情報をクラスター全体に伝播させる。リーダーも合意形成も単一障害点もない。その代償として、収束するまでクラスター状態が一時的に不整合になる。メンバーシップの伝播から整合性修復まで、gossip は分散型分散システムの情報ハイウェイである。

3種類のGossip

Gossip の核心は「各ノードが周期的にランダムなピアを選択して情報を交換する」ことにある。情報の流れに応じて3種類に分類される。

Push (Rumor Mongering)

ノードが更新を持つ → ランダムなピアに積極的にプッシュ → ピアがさらにプッシュ。

「ホット」な更新（直近で発生し、急速な伝播が必要な場合）に適している。更新が十分にプッシュされなかった場合（rumor が循環を停止した場合）、フォールバック（anti-entropy）が必要になる。

Pull

ノードがランダムなピアから最新情報を積極的にプルする。新規参加ノードや長時間同期が取れていないノードに適している——プルを1回実行するだけで追いつける。

Push-Pull

双方が要約を交換し → 各自が相手側で自分より新しい更新をプルする。最も効率的——双方が恩恵を受け、ネットワーク利用率が最大になる。

エピデミック・ブロードキャスト

エピデミックは確率的信頼性を保証する：O(log N) ラウンド後、すべてのノードがメッセージを受信する確率はほぼ 1 である。

収束分析

毎ラウンド: 各ノードがランダムな1つのピアを選択して push-pull を実行
Round 1: 1 ノード → 2 ノードが情報を取得
Round 2: 2 → 4
Round 3: 4 → 8
...
Round log₂(N): すべてのノードが情報を取得

これは完全な伝播を仮定している（無限の帯域幅、パケットロスなし）
実際には: ラウンドごとに fanout = O(log N) → 確率的なカバレッジ

信頼性ブロードキャストとの比較

信頼性ブロードキャスト（Raft の AppendEntries など）: O(N) メッセージ、確定的な信頼性、リーダーが必要
エピデミック・gossip: ノードあたり O(log N) メッセージ、確率的な信頼性、リーダー不要、ノード障害/ネットワーク分断を許容

Anti-Entropy + Merkle ツリー

Gossip はメッセージを失う可能性がある（確率的であるため）。Anti-entropy は完全な比較によって欠落を補填する。

Merkle ツリー: 各リーフノード = データブロックのハッシュ、各内部ノード = 子ノードのハッシュ。2つのノードがルートハッシュを比較 → 同一であればデータは整合している → 異なれば子ノードを再帰的に比較 → 具体的な不整合ブロックを特定 → これらのブロックのみを送信。

利点: 全データを転送しなくても不整合な部分を特定できる。BitTorrent、Cassandra、Dynamo はすべて anti-entropy に Merkle ツリーを使用している。

SWIM の Gossip レイヤー

SWIM の ping/ping-req レイヤーは障害検出を担当する。検出結果（suspected/confirmed dead）は gossip を介して伝播される。これは push gossip の1つの実装例である：suspected/dead といった稀なイベントのみが伝播される。

参考文献

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

キーワード: gossip, push-pull, エピデミック・ブロードキャスト, anti-entropy, Merkle ツリー, SWIM, 確率的信頼性