ゴシッププロトコル

分散システムにおいて、ゴシッププロトコル（gossip protocol、エピデミックアルゴリズム、epidemic algorithmとも呼ばれる）とは、感染症が広がる仕組みをモデルとした、コンピューター間のピア・ツー・ピア通信の手順またはプロセスである。一部の分散システムでは、グループ内のすべてのメンバーにデータを行き渡らせるために、ピア・ツー・ピア方式のゴシップ通信が利用される。また、一部のアドホックネットワークには中央レジストリが存在しないため、共通データを広めるには、各メンバーが近隣のメンバーへ順次伝達していく方法に頼るほかない。

ゴシッププロトコルでは、典型的にはランダムに選んだ相手と非同期に情報を交換することで、データを拡散していく。情報の伝搬には時間がかかるため、ある時点で参加者が保持しているデータは互いに異なる場合があり、ゴシップによる情報伝搬では一般に強い整合性は保証されない。一方、最低限の通信路が復旧し、競合する更新を一貫した方法で解決できれば、各参加者の状態が最終的に同一となる結果整合性を実現できる。仕組みが比較的単純で、情報伝搬のための中心的な管理主体を必要とせず、メンバーが不定期に増減する場合や一時的な通信障害が発生する場合にも、情報を伝搬し続けられるよう設計できる。

歴史

1970年代初頭、グラフ理論の分野において「ゴシップ問題 (gossip problem)」あるいは「電話病 (telephone disease)」と呼ばれる問題が議論された。この問題は、n人がそれぞれ持つ異なる情報を電話を使って交換する場合、全員がすべての情報を得るには何回の通話が必要かという問題である。

その後、1987年にゼロックスのパロアルト研究所において、大規模ネットワークにおけるデータベースの複製方法としてゴシッププロトコルが提案された。

分類 ゴシッププロトコルは以下の2種類の変種がある。

アンチエントロピー (anti-entropy) ルーモアモンガリング (rumor mongering) - "rumor monger"はおしゃべりな人、噂屋の意。

アンチエントロピーでは各参加者が繰り返しランダムに選んだ相手と通信し、互いが持つ情報を比較して新しい情報を交換する。一方、ルーモアモンガリングでは新しい情報を得た参加者がランダムに選んだ相手にその情報を伝える処理を繰り返す。そして、相手がその情報をすでに知っていたという状況が繰り返されると、情報の伝達を停止する。このとき、一定回数を越えた際に止める方法と、確率的に停止する方法がある。

ルーモアモンガリングでは一部の参加者に情報が伝わらないことがあるが、効率は良い。一方、アンチエントロピーでは時間が経てば確実にすべての参加者に情報が行き渡るものの、その時点で互いが知っている情報を比較する処理のコストが高い。ブロードキャストやルーモアモンガリングでおおまかに情報を拡散した後、補助的に低い頻度でアンチエントロピーを使う方法も提案されている。

データベース複製以外の応用

データベースの複製以外の応用としては、各参加者が持つ値の平均値など、統計値の計算がある。

各参加者はまず自分が持つ値を暫定的な平均値とする。そして各参加者と暫定値を交換し、自分の暫定値と相手の暫定値の平均を新しい暫定値とする。これを繰り返すと、各参加者が持つ値は平均値に近付いていく。同様の方法で、最大値や最小値なども計算できる。

出典