---
title: Gossip プロトコル
url: https://doc.liz6.com/ja/distributed-systems/05-members-and-discovery/02-gossip-protocol
locale: ja
area: distributed-systems
tags:
- distributed-systems
- members-and-discovery
date: 2026-06-30
modified: 2026-07-16
description: ランダムなピアを選択し、最新情報を互いに交換する——gossip は「雑談」のような方式で、O(log N) ラウンド以内に情報をクラスター全体に伝播させる。リーダーも合意形成も単一障害点もない。その代償として、収束するまでクラスター状態が一時的に不整合になる。メンバーシップの伝播から整合性修復まで、gossip は分散型分散システムの情報ハイウェイである。
---

# 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, 確率的信頼性*