ゴシッププロトコル

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

概要

ゴシッププロトコル (gossip protocol, gossipping) または感染プロトコル (epidemic protocol) はネットワーク上で情報をマルチキャストする方法の一つ。うわさ話や感染症が実社会で伝播する過程と似たモデルのプロトコルである。ランダムグラフに基づく非構造化 P2P ネットワークや、強い調整者の存在しない分散ハッシュテーブルといった分散システムにおいて、緩やかな方法で最新の情報を共有する (anti-entropy) 目的でしばしば使用される。

アルゴリズム

ゴシッププロトコルではネットワーク上のあるノード \(P\) が別のノード \(Q\) をランダムに選択して情報の交換を行うことを繰り返す。ここで現実的な実装では以下の 2 つの挙動を併用することが多い。

  • PUSH: 自分が最新の情報を得るとすぐに他のノードへ伝達する。PULL に比べて序盤の伝播速度は速いが終盤では非効率で遅く、さらに全てのノードに情報が伝搬される保証がない。つまり、どのような条件で伝搬を停止したとしても、確率的に選択されず取り残されている unreach なノード (susceptible node) が発生していないことを保証する手段がない。
  • PULL: 定期的に他のノードと接続して情報交換を行う。伝搬速度は遅いがいずれネットワーク全体に情報が伝搬することを確率的に保証することができる。特に、自分以外のほとんどのノードが最新状態であれば最新情報を得られる可能性が高いことから PUSH の unreach ノード問題を補うことができる。全てのノードが最新状態であれば PULL は無駄な通信となる。

あるノードが別のノードと一回情報を交換する期間をラウンドとしたとき、新しい情報がノード総数 \(N\) のネットワーク全体に伝播するために必要なラウンド数はおおむね式 (\(\ref{o}\)) で表すオーダーとなる。\[ \begin{equation} O(\log N) \label{o} \end{equation} \] 式 (\(\ref{o}\)) が対数オーダーを示していることからも分かるように、ゴシックプロトコルは \(N\) の大きな大規模ネットワークにおいても効率的に情報を伝搬することができる。その反面、無駄な通信が多く最終的にネットワーク負荷の高さが問題となることが多い。

以下のフォームは、あるノードの共有した情報がネットワーク上のすべてのノードに伝播するまでのラウンド数を実際に JavaScript でシミュレーションするスクリプトである。例えば 500,000 ノードのネットワークであっても 11 ラウンド程度ですべてのノードに行き渡ることがわかる。

Rumor Spreading

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

通信相手が目的の情報を持っていたときに拡散を停止する確率を \(p=1/k\) としたとき、ネットワーク上で unreach のまま取り残されるノードの比率 \(s\) は式 (\(\ref{s}\)) で表すことができる (wolfram|alpha のグラフ)。

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

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

このうわさ拡散はネットワーク上の少数のノードしか情報が更新されていない状況では速やかな情報拡散を行い、多数のノードが情報を保持するに伴って拡散を鈍化させネットワークの負荷を低く調整する特徴がある。前述の通りすべてのノードに情報が行き渡る前に停止する可能性はあるが、定期的な PULL による拡散を併用することで取り残された unreach ノード問題を解消することができる。

アプリケーション実装例

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

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

データ共有とクエリー

データ共有は最もよく見かける利用例であり、分散システムのクラスタや P2P ネットワーク全体でコンフィギュレーションを同期するようなケースで利用されている。また 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\) を持った状態でこの過程を行うと値は全ノード数の逆数 \(\frac{1}{N}\) に収束する。つまり、これによりネットワークに参加しているすべてのノード数 \(N\) の推定値を得ることができる。

この推定値 \(N\) は利用統計やネットワーク機能の最適化のためのパラメータとして使用することができる。

リーダー選出

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

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

参考リンク

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