分散アルゴリズム

分散アルゴリズム（ぶんさんアルゴリズム、英語: Distributed algorithm）とは、相互接続されたプロセッサにより構成されるハードウェア上で実行するために設計されたアルゴリズムである。分散アルゴリズムは分散コンピューティングの多くの応用分野において使われ、その例として、通信、科学計算、分散情報処理、リアルタイムプロセス管理などがある。分散アルゴリズムによって解決された標準的な問題として、リーダー選出、合意、分散検索、全域木生成、ミューテックス、リソース割り当てなどがある^[1]^[2]。

典型的な分散アルゴリズムは、並列に実行され、アルゴリズムの各部が独立したプロセッサ上で同時に実行され、アルゴリズムの他の部分については限定的な情報しか持たない。分散アルゴリズムを開発し、実装する上での大きな課題となるのが、プロセッサ障害が発生し、通信接続が不確実であるような環境において、アルゴリズムの独立した部分の動作を統制することである。与えられた問題に対し、適切な分散アルゴリズムを選択することは、問題の特徴と、アルゴリズムが実行されるシステムの特徴の両方に依存する。ここでシステムの特徴とは、プロセッサの性能や、通信接続の障害、可能なプロセス間通信の種類、プロセス間の同期を行う際の精度などを指す^[1]。

標準的な問題

アトミックコミット: アトミックコミットとは異なる変更の集合が一つの処理として実行されるような処理のことである。もしアトミックコミットが成功すれば、全ての変更が実行されたことを意味する。もしアトミックコミットが完了するまでに障害があった場合、"コミット"が中止され、どの変更も実行されない。; アトミックコミットプロトコルを実現するアルゴリズムとして、2相コミットプロトコルおよび、3相コミットプロトコルがある。

合意: 合意アルゴリズムはいくつかのプロセスが共通の決定に合意する問題を解くものである。; より詳細には、合意プロトコルは以下の4つの特徴を備えなければならない。

終了: 全ての正常なプロセスはある値を決定する。
有効性: もし全てのプロセスが同じ値 $v$ を提案する場合、全ての正常なプロセスは $v$ を決定する。
整合性: 全ての正常なプロセスは最大1つの値を決定し、もし値 $v$ を決定した場合は、 $v$ が他のプロセスによって提案されている。
合意: もし正常なプロセスが $v$ を決定した場合、すべての正常なプロセスは $v$ を決定する。

Paxosアルゴリズムは、合意を実現するための典型的なアルゴリズムである。

分散情報検索

リーダー選出

ミューテックス

信頼性のあるブロードキャスト

信頼性のあるブロードキャストとは、分散システムにおける通信の基本要素である。以下の特徴によって定義されるものである:

有効性 - 正常なプロセスがメッセージを送信するならば、ある正常なプロセスがいずれそのメッセージを伝送する

合意 - 正常なプロセスがメッセージを伝送するならば、全ての正常なプロセスがいずれそのメッセージを伝送する

整合性 - 全ての正常なプロセスが同じメッセージを最大1回伝送し、それはあるプロセスによりそのメッセージが送信された場合だけである

レプリケーション
リソース割り当て
全域木生成

脚注

^ ^a ^b Lynch, Nancy (1997). Distributed Algorithms (1st ed.). San Francisco, CA: Morgan Kaufmann Publishers. ISBN 978-1558603486
^ 増澤利光、山下雅史：「適応的分散アルゴリズム」、共立出版、ISBN 978-4-320-12251-2 (2010年6月30日)

外部リンク

MIT's Open Course - Distributed Algorithms

[lynch1997-1] Lynch, Nancy (1997). Distributed Algorithms (1st ed.). San Francisco, CA: Morgan Kaufmann Publishers. ISBN 978-1558603486

[2] 増澤利光、山下雅史：「適応的分散アルゴリズム」、共立出版、ISBN 978-4-320-12251-2 (2010年6月30日)

[1]

[2]