分散アルゴリズム

ウィキペディア

分散アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/11/20 20:08 UTC 版)

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

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

標準的な問題

アトミックコミット

アトミックコミットとは異なる変更の集合が一つの処理として実行されるような処理のことである。もしアトミックコミットが成功すれば、全ての変更が実行されたことを意味する。もしアトミックコミットが完了するまでに障害があった場合、"コミット"が中止され、どの変更も実行されない。

アトミックコミットプロトコルを実現するアルゴリズムとして、2相コミットプロトコルおよび、3相コミットプロトコルがある。

合意

合意アルゴリズムはいくつかのプロセスが共通の決定に合意する問題を解くものである。

より詳細には、合意プロトコルは以下の4つの特徴を備えなければならない。

• 終了: 全ての正常なプロセスはある値を決定する。
• 有効性: もし全てのプロセスが同じ値 $v$