🎓 レベル：発展 | 重要度：B（重要）
📎 前提：レプリケーション方式（同期／非同期・リーダー／リーダーレス） | 関連：PACELC・結果整合性・障害モデル（クラッシュ・オミッション・ビザンチン）
要点（BLUF）
- ゴシップ（エピデミック）プロトコルは、各ノードがランダムな相手と定期的に情報交換することで、中央サーバなしに状態を全体へ拡散する方式。Dynamo・Cassandra・Consul・Redis Cluster が採用。
- 拡散は感染症のように指数的に広がり、全体収束は約 log N ラウンド——中央集約なしでスケーラブル。反エントロピー（複製の差分を交換して揃える）の実装手段でもある。
- 故障検出はハートビートの延長。固定タイムアウトは誤検知が多いので、phi-accrual（遅延の履歴から疑い度φを連続値で算出）や、検出と拡散を統合したSWIMが使われる。
問題設定 ── 中央なしで「揃える・見つける」
クラスタの「誰が生きているか」「最新の設定は何か」を全ノードで共有したい。中央のレジストリに全員が問い合わせると、そこがボトルネック＆単一障害点（透過性とスケーラビリティ）。中央を置かずに、ノード同士のうわさ話だけで全体を揃え、故障も見つけたい——これがゴシップの動機です。
アルゴリズム ── ゴシップ拡散
flowchart LR
A["ノードA（新情報を持つ）"] -->|"ランダムな相手へ"| B["ノードB"]
B -->|"次のラウンドで拡散"| C["ノードC"]
B -->|"並行に"| D["ノードD"]
C --> E["…指数的に倍々で広がる"]
各ラウンドで、各ノードはランダムに選んだ数ノードに自分の知る情報を送る（push）／もらう（pull）。新情報を持つノードが毎ラウンドおよそ倍増し、感染症の流行のように全体へ広がります。
- 反エントロピー（anti-entropy）：定期的に2ノードが全状態の差分を交換し収束させる（確実だが重い。Merkle木で差分箇所を効率特定）。
- ランナー（rumor-mongering）：新しい更新だけをしばらく広め、十分広まったら止める（軽いが取りこぼしうる）。両者を併用するのが定番。
具体例 ── log N で全体収束（実機）
ラボ 06-05_gossip.py。1ノードが持つ新情報が、各ラウンドでランダムな相手に伝播。収束ラウンド数とノード数の関係：
== ゴシップ拡散の収束ラウンド数 (fanout=1) ==
ノード数 N 収束ラウンド log2(N) 参考
10 6.5 3.3
100 12.8 6.6
1000 18.0 10.0
10000 23.1 13.3
N=1000 の1試行での感染数の推移(ラウンドごと):
[1, 2, 4, 8, 16, 32, 62, 117, 218, 368, 560, 754, 884, 948, 982, 991, 998, 1000]ノード数が10倍になっても収束ラウンドは数ラウンド増えるだけ（10→約6.5、10000→約23）。感染数の推移 1,2,4,8,16,32,… が示す通り、初期は毎ラウンド倍増し、全体収束は O(log N)。中央サーバなしで対数時間に全ノードへ行き渡る——これがゴシップのスケーラビリティです。
故障検出 ── ハートビートから phi-accrual・SWIM へ
「ノードが死んだ」をどう判定するか。障害モデル（クラッシュ・オミッション・ビザンチン） の通り「遅い」と「死んだ」は区別できないので、確率的に疑う設計にします。
| 方式 | 仕組み | 弱点 |
|---|---|---|
| 固定タイムアウト・ハートビート | T秒来なければ死亡 | ネット揺らぎで誤検知多発 |
| phi-accrual | 到着間隔の履歴分布から「今の遅延の疑わしさ」を連続値φで算出。閾値を用途別に調整 | 計算がやや重い |
| SWIM | ランダムな相手をping、無応答なら他ノード経由で間接pingして確認。メンバー変化をゴシップで拡散 | 実装が必要 |
SWIM（Consul/Serf が採用）は故障検出とメンバーシップ拡散を統合し、間接pingで誤検知を減らし、負荷をクラスタ全体に均す優れた設計です。
正しさの観点 ── 確率的な保証
- 収束（安全性に近い性質）：更新が止めば、ゴシップは確率1で全ノードに伝わる（反エントロピー併用なら取りこぼしも修復）。PACELC・結果整合性 の収束機構そのもの。
- 故障検出の完全性 vs 正確性：すべての真の故障をいつか検出（完全性）と、生きたノードを誤検知しない（正確性）は両立しない（FLP的限界、合意問題とFLP不可能性）。phi-accrual は閾値でこのバランスを調整する。
- スケーラビリティ：1ノードあたりの通信は毎ラウンド定数（fanout）なので、N が増えても各ノードの負荷は一定。
なぜ分散だと難しいか（直観）
「全員が同じ事実を知る」を中央なしで、しかも故障の中で達成するのが難所。ゴシップは厳密な即時一貫性を諦め、確率的な最終収束に振ることで、スケールと耐障害を得る。故障検出も「確実な判定」を諦め「疑いの度合い」に変えることで、誤検知と見逃しのバランスを運用で調整可能にしています。諦め方が上手いプロトコル群です。
⚠️ よくある誤解・落とし穴
- 「ゴシップは遅い」→ 1対1の伝播は遅そうに見えるが、倍々で広がるので全体は log N と速い（実機で確認）。
- 「ハートビートのタイムアウトを短くすれば早く検出」→ 短すぎると誤検知が増えフラッピング。phi-accrual で適応的に。
- 「故障検出は正確にできる」→ 非同期では不可能。完全性と正確性のトレードオフが残る。
- 「ゴシップは強一貫を作れる」→ 作れない。結果整合の収束機構。強一貫が要るなら合意（Raft）。
対応ラボ
distributed-systems-study/labs/06-05_gossip.py（N=10〜10000 で収束ラウンドが O(log N)、感染数が倍増することを確認済み）。
関連
- 収束が支える一貫性は PACELC・結果整合性
- 「遅い vs 死んだ」の根本は 障害モデル（クラッシュ・オミッション・ビザンチン）
- リング状態の伝播先は 一貫性ハッシュ