リーダー選出

ウィキペディア

リーダー選出

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2010/05/20 17:36 UTC 版)

分散コンピューティングにおいて、リーダー選出は複数のコンピュータ(ノード)に分散されたタスクの取りまとめ役として、一つのプロセスを指定する過程である。タスクが開始する前、全てのネットワークノードは、どのノードが「リーダー」、つまりタスクの取りまとめ役であるかは知らない。しかし、リーダー選出アルゴリズムが実行された後、ネットワーク中の全ノードは特定のノードをタスクリーダーとして認識する。

ネットワークノードは相互に通信を行い、いずれかが「リーダー」状態になるか決定する。そのために、ノード間の対称性を崩すための手法が必要となる。例えば、各ノードが固有のID番号があるのであれば、ノード間にてID番号の比較を行い、最も高いID番号を持っているノードがリーダーであると決定することが出来る。

この問題の定義はLeLannに帰せられることが多く、これをトークンリングネットワークにおいて、トークンが失われた際に新しいトークンを作成する手法として実現した。

リーダー選出アルゴリズムは全送信バイト数と時間という観点で経済的であるよう、設計されている。Gallager、Humblet、Spiraによって提案された一般無向グラフのためのアルゴリズム は分散アルゴリズムのデザイン一般に強いインパクトを与え、分散コンピューティングにおける影響が大きい論文としてダイクストラ賞を受賞した。

無向リング、単一方向リング、完全グラフ、グリッド、有向オイラーグラフなどの他の種類のネットワークグラフについて多くのアルゴリズムが提案された。グラフの種類とリーダー選出アルゴリズムを切り離す一般的な手法が Korach、Kutten、Moranにより提案された。