ゴシッププロトコル：噂話のように情報を広める

「各ノードがランダムに選んだ相手へ情報を伝える」。それだけの単純なルールが、驚くほど頑健で高速な情報伝播を生みます。感染症の数理モデルによる裏付けから、Push型・Pull型の違い、HyParViewやPlumtreeといった構造化ゴシップ、Cassandraやlibp2p gossipsubでの実装まで、縁の下の力持ちを詳説します。

疫学モデル：SIモデルとSIRモデル

ゴシップ（うわさ話）プロトコルの原点は、Xerox PARCの複製データベース研究（1987年、Demersらの論文）です。感染症の数理モデルになぞらえ、情報を持つノードを「感染者（Infected）」、持たないノードを「感受性者（Susceptible）」と見立てます。最も単純なSIモデルでは、感染ノードは永久に感染状態を保ち、毎ラウンド誰かに情報を伝え続けます。感染者数は指数的に増え、O(log n)ラウンドでほぼ全ノードに行き渡ります。100万ノードでも約20ラウンドです。ただしSIモデルは、すでに全員が知っている段階でも送信を止めないため、後半のラウンドで大量の無駄なメッセージを生みます。

これを改善するのがSIRモデルです。感染ノードは一定の確率、あるいは一定回数の「空振り」（相手がすでに情報を持っていた）を経験すると「治癒者（Removed）」に遷移し、それ以降は送信をやめます。収束に必要なラウンド数はSIモデルとほぼ変わらずO(log n)のままで、総メッセージ数だけを大きく削減できることが知られています。実運用のゴシップ実装のほとんどは、何らかの形でこのSIR的な「送信の打ち切り」を組み込んでいます。

Push・Pull・Push-Pullの3方式

ゴシップには、情報を「渡しに行く」か「取りに行く」かで3つの基本方式があります。

Karpらによるランダム電話呼び出しモデルの解析（2000年）では、push-pull型はO(log n)ラウンドで全ノードに到達し、さらに「情報がほぼ行き渡ったら送信を打ち切る」終了検出の工夫を組み合わせることで、総メッセージ数をO(n log log n)まで削減できることが示されています。これは素朴なpush型のO(n log n)より大幅に効率的です。

P2Pオーバーレイのメンバーシップ情報（既知ノードリスト）の交換では、pushかpullかの選択がネットワークの分断耐性に効くという実務観察があります。pull型（情報が欲しい側が自分のタイミングで取りに行く）の方が分断しにくい傾向があります。情報の少ないノードが能動的に既知集合を補充できるため、「クラスタ間の橋渡しになっている接続が、情報を運ぶ前に切断されて島が分かれてしまう」事故を避けやすいためです。エントリの生存タイムアウトにも、交換間隔の2倍以上の余裕を持たせるのが安全側の設計です。ただし、この種のトポロジー動態は複数の要因が絡み合って生じるため、単一の設定変更に還元して再現・検証するのは難しく、分散システムのデバッグ全般に共通する難しさが、ここにも表れています。

fanoutと到達確率：パラメータ設計の勘所

各ラウンドで1ノードが情報を伝える相手の数をfanout（扇散度、通常bと表記）と呼びます。fanoutが大きいほど収束は速まりますが、1ノードあたりの送信量はfanoutに比例して増えるため、帯域とCPU負荷はトレードオフです。理論上はランダムな相手選択ゆえに、ごく小さい確率で一部のノードが最後まで情報を受け取れない「取りこぼし」が起こり得ます。

• 安全マージン: 理論上の収束ラウンド数ちょうどで打ち切ると取りこぼし率が無視できないため、実装では理論値に数ラウンドの余裕を足して回すのが定石です。
• ラウンド周期: gossip interval（1ラウンドの間隔）を短くすれば収束は速くなりますが、ネットワーク全体のメッセージレートが増え輻輳を招くため、多くの実装は数百ミリ秒〜数秒の周期を採用します。
• fanoutの典型値: 多くの実運用ゴシップはfanout 3〜6程度に収めており、これ以上大きくしても収束速度の伸びに対して帯域コストの増加が見合わないことが経験的に知られています。

アンチエントロピーとルーマーモンガリング

• アンチエントロピー: 2ノードが状態全体の差分を突き合わせて同期する方式。確実だが重く、定期的な整合性回復に使う。Cassandraの実装では、状態をMerkleツリーでハッシュ化して比較し、差分がある部分木だけを転送することで通信量を抑えている。
• ルーマーモンガリング: 新しい更新（うわさ）だけを一定期間・一定回数だけ広める方式。軽量で高速だが、少数の取りこぼしが起こりうるため、アンチエントロピーと併用される。「相手がすでに知っていた（空振り）」が一定回数続いたら、そのうわさを広めるのをやめるのが典型的な実装。

構造を持たない強さ

ゴシップの最大の魅力は障害への鈍感さです。ツリー型の配信構造は1ノードの故障で下流全体が孤立しますが、ゴシップは経路がランダムに毎回変わるため、ノードの半分が落ちても伝播は続きます。メッセージの重複という無駄を支払う代わりに、維持コストゼロの頑健性を買っています。この割り切りが、チャーンの激しいP2P環境と相性抜群です。

部分ビューとツリー構築：HyParViewとPlumtree

素朴なゴシップは、各ノードが全ノードのアドレス一覧（フルメンバーシップ）を持つ前提で説明されがちですが、これは数万ノード規模になるとメモリと更新コストの両面で破綻します。HyParViewは、この問題を「小さな能動ビュー（実際に通信する少数のピア、典型的に対数オーダーの数）」と「大きな受動ビュー（バックアップ用の候補一覧）」の2層に分けて解決します。能動ビューのピアが落ちると、受動ビューから補充することでオーバーレイの連結性を保ちます。

Plumtree（Plum Tree）は、このHyParView的なランダムオーバーレイの上に、通常運用時は木構造（スパニングツリー）に沿ってeager push（即座に転送）することで、ゴシップより大幅に少ないメッセージ数で配信を完了させます。同時に、木の枝が切れて一部のノードに情報が届かなかった場合に備え、低頻度のlazy push（IHAVE的な要約情報のみ送る）を残しており、これが実質的なゴシップとして働いて木の破損を検知・修復します。「平常時はツリーの効率、障害時はゴシップの頑健性」という良いとこ取りの設計です。

実システムでの活躍

疫学的アルゴリズムの原論文をはじめとする一次文献は参考文献ページを参照してください。伝播速度は分散合意の安全性（フォーク率など）にも直結する重要なパラメータです。

よくある誤解と実務での注意点

• 「必ず全ノードに届く」は誤解: 理論上は確率的なプロセスであり、ごく小さい確率で一部ノードが取りこぼされる。重要なデータはアンチエントロピーなど別の仕組みで補償する必要がある。
• 「fanoutを上げれば安全」も誤解: ネットワーク全体のメッセージ量はおよそfanout×ノード数に比例して増えるため、大規模クラスタでは逆に輻輳やシビル攻撃耐性の低下を招きかねない。
• 低遅延通信の代替ではない: 伝播には「ラウンド数×ラウンド周期」の時間がかかるため、ミリ秒単位のリアルタイム性が必要な用途には不向き。ゲームのような即応性が必要な処理には別の仕組みを組み合わせる。
• 構造化ゴシップも万能ではない: Plumtreeのようなツリーベースのゴシップはメッセージ数を削減できる一方、木構造の管理・修復ロジックの実装コストが上がる。ノード数や更新頻度が小さいうちは、素朴なゴシップの方が実装・運用コストで有利なことも多い。