ゴシッププロトコル

Takami Torao #Gossip
  • このエントリーをはてなブックマークに追加

概要

ゴシッププロトコル (gossip protocol, gossipping) または感染プロトコル (epidemic protocol) はネットワーク上での情報マルチキャストの方法。実社会でうわさ話や感染症が伝播する過程と似たモデルである。強い調整者の存在しない分散システムにおいて緩やかな方法で一貫性を保つ結果整合性 (anti-entropy) に基づいている。

アルゴリズム

ゴシッププロトコルは、あるノード \(P\) がネットワーク上の別のノード \(Q\) をランダムに選択し情報の伝達を行う。このとき、一般的には \(P\) と \(Q\) が相互に情報を交換する。仮に \(P \to Q\) への一方向な PUSH のみであれば、ネットワークの大多数のノードが更新済みとなった状況では、確率的に選択されず情報が長期間 unreach な状態のノード (susceptible node) の発生する可能性が高くなる。

すべてのノードが少なくとも一回、ランダムに選ばれた別のノードと情報を交換する期間をラウンドとしたとき、ノード総数 \(N\) のネットワーク全体に新しい情報が伝播するために必要なラウンドのオーダーは式 (\(\ref{o}\)) で表すことができる。対数オーダーであることからゴシップモデルはノード数に対して十分にスケールすることが分かる。\[ \begin{equation} O(\log N) \label{o} \end{equation} \]

以下のフォームは、あるノードの持つ情報がすべてのノードに伝播するまでのラウンド数をシミュレーションする簡単なスクリプトである。例えば 500,000 ノードのネットワークであっても 11 ラウンド程度ですべてのノードに情報が行き渡る事がわかる。

Rumor Spreading

ゴシッププロトコルの変種としてうわさ拡散 (rumor spreading, rumor mongering) または単にゴシッピング (gossipping) と呼ばれる方法がある。これはノード \(P\) が自分の情報を更新してすぐ別のノード \(Q\) への伝播を試みる PUSH 型のアプローチだが、\(Q\) が既にその情報を持っていた場合、ある一定の確率 (またはその状況に遭遇した回数) でそれ以上の他のノードへの伝播を停止する方針を持つ。

相手が既にその情報を持っていた場合にそれ以上の拡散を停止する確率を \(1/k\) としたとき、ネットワーク上で unreach のまま取り残されるノードの比率 \(s\) は 方程式 (\(\ref{s}\)) で表すことができる。

\[ \begin{equation} s = e^{-(k+1)(1-s)} \label{s} \end{equation} \]
s

式より \(k=1\) では \(s=0.203\)、つまり全体の 20% 以上が unreach なノードになりうるが、\(k=4\) では \(s=0.0069\) となり unreach なノードをネットワーク全体の 0.7% 未満まで低下させることができる。

このうわさ拡散はネットワーク上の少数のノードしか情報が更新されていない状況では速やかな情報拡散を行い、多数のノードへ情報が伝播するに伴って拡散を鈍化させネットワークの負荷を低く調整する特徴がある。すべてのノードに情報が行き渡る前に停止する可能性があるため結果整合性をもたないが、定期的な双方向または PULL 型の拡散を併用することで unreach ノードを解消することができる。

アプリケーション実装例

ゴシッププロトコルは可用性を考慮した分散データベースや P2P ネットワークにおいて一般的な設計手法である。一般的に以下の 2 点を目的として利用される。

  1. ネットワーク上に情報を散布する。
  2. ネットワーク全体の集約処理を行う。

データ同期とクエリー

データ同期は最もよく見かける利用例であり、ネットワーク全体のコンフィギュレーションを各参加ノードで同期するようなケースでよく利用されている。また P2P ファイル共有では目的のデータを保持しているノードを探すためのクエリーをネットワーク全体に散布する (flooding) ためにも使用される。

ノード数の見積もり

すべてのノードが信頼できる (つまりビザンチン故障が存在しない) と仮定する。

ネットワークに参加しているノード \(P_i\) が任意の初期値 \(x_i\) を持っており、ランダムに選択したノード \(P_j\) と通信してその平均値 \(\frac{x_i+x_j}{2}\) を双方の新しい値とする。この過程を繰り返すと、すべてのノードが同一の値、つまり全ノードの初期値の平均 \(\frac{\sum_i x_i}{N}\) に収束する。

ここで、あるノード \(P_0\) のみが初期値 \(x_0=1\) を持ち、それ以外のすべてのノードが初期値 \(x_i=0\) として過程を進めたとき、値はネットワークに参加しているすべてのノード数 \(N\) の逆数 \(\frac{1}{N}\) に収束することが分かるだろう。この推定値 \(N\) はノードのグループ分割などに利用することができる。もしノードの参加と離脱が動的に行われるネットワークであれば、ある一定の期間で \(x_i\) を初期状態にリセットすることで時系列での見積もりを行うことができる。

リーダー選出

ノード数の見積もりと同様の方法でリーダー選出を行うことができる。例えば各ノードは \([0,1]\) 区間でランダムに選んだ数値を \(m_i\) として保持する。ノード \(P_i\) と \(P_j\) の交換時に新しい値を \(\max(x_i, x_j)\) とし、\(m_i \lt x_i\) であれば自身がリーダー選挙に負けたことを意味する。

この方法ではどのノードがリーダーとして選出されたかを確定するのは難しいが、自分がリーダーではないことが確定した時点で行うべき動作がある場合や、リーダーではないと確定するまでリーダーとして振る舞って良い場合 (例えば最終的に他のノードにリーダーが確定すればその処理結果が無効化される場合など) のような楽観的な挙動が許される設計で利用することができる。

参考リンク

  1. Andrew S. Tanenbaum, Maarten van Steen 他 (2009) 分散システム第二版, ピアソン