ゴシッププロトコル

ウィキペディア

ゴシッププロトコル

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/07/14 06:23 UTC 版)

分散システムにおいて、ゴシッププロトコル（gossip-protocol, ゴシッピング、ゴシップアルゴリズム、エピデミックアルゴリズム、epidemic algorithms, epidemic protocol）とは、システムの参加者間で繰り返し確率的に情報を交換する手法であり、情報の拡散や統計値の計算などに利用される^[1]。

ゴシッププロトコルではランダムに選んだ相手と情報を交換し、自身が持つデータの更新を繰り返す。システムの参加者が不定期的に増減して全体を把握できない状況や、一時的に通信できない場合でも情報を伝搬できる。病気が伝染する様子に似ていることから、エピデミックアルゴリズムとも呼ばれる^[1]。

歴史

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

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

分類

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

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

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

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

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

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

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

出典

1. ^ ^{a b c} Anne-Marie Kermarrec; Maarten van Steen (October 2007). “Gossiping in distributed systems”. ACM SIGOPS Operating Systems Review 41 (5): 2-7. doi:10.1145/1317379.1317381. 
2. ^ Brenda Baker; Robert Shostak (June 1972). “Gossips and telephones”. Discrete Mathematics 2 (3): 191-193. doi:10.1016/0012-365X(72)90001-5. 
3. ^ András Hajnal; Eric Charles Milner; Endre Szemerédi (January 1972). “A cure for the telephone disease”. Canadian Mathematical Bulletin 15: 447-450. doi:10.4153/CMB-1972-081-0. 
4. ^ Frank Harary; Allen J. Schwenk (January 1974). “The communication problem on graphs and digraphs”. Journal of the Franklin Institute 297 (6): 491-495. doi:10.1016/0016-0032(74)90126-4. 
5. ^ Alan Demers; Greene, Dan; Houser, Carl; Irish, Wes; Larson, John; Shenker, Scott; Sturgis, Howard; Swinehart, Dan; Terry, Doug (August 1987). Epidemic algorithms for replicated database maintenance. the Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC '87). Vancouver, British Columbia, Canada: ACM. pp. 1–12. doi:10.1145/41840.41841。
6. ^ ^{a b c d e} Alan Demers; Dan Greene, Carl Houser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry (January 1988). “Epidemic algorithms for replicated database maintenance”. ACM SIGOPS Operating Systems Review 22 (1): 8-32. doi:10.1145/43921.43922.