分散アルゴリズム

分散アルゴリズムは、相互接続されたプロセッサから構成されるコンピュータハードウェア上で実行するように設計されたアルゴリズムです。分散アルゴリズムは、通信、科学計算、分散情報処理、リアルタイムプロセス制御など、分散コンピューティングのさまざまなアプリケーション分野で使用されています。分散アルゴリズムによって解決される標準的な問題には、リーダー選出、コンセンサス、分散検索、スパニングツリー生成、相互排除、リソース割り当てなどがあります。^[1]

分散アルゴリズムは並列アルゴリズムのサブタイプであり、通常は同時に実行され、アルゴリズムの個別の部分は独立したプロセッサ上で同時に実行され、アルゴリズムの他の部分が何をしているかについての情報は限られています。分散アルゴリズムの開発と実装における大きな課題の 1 つは、プロセッサ障害や信頼性の低い通信リンクに直面したときに、アルゴリズムの独立した部分の動作をうまく調整することです。特定の問題を解決するために適切な分散アルゴリズムを選択するには、問題の特性と、プロセッサまたはリンク障害の種類と確率、実行できるプロセス間通信の種類、個別のプロセス間のタイミング同期のレベルなど、アルゴリズムが実行されるシステムの特性の両方に依存します。 ^[1]

アトミックコミット

アトミック コミットは、一連の個別の変更を 1 つの操作として適用する操作です。アトミック コミットが成功した場合、すべての変更が適用されたことを意味します。アトミック コミットが完了する前に障害が発生した場合、「コミット」は中止され、変更は適用されません。

アトミック コミット問題を解決するためのアルゴリズムには、2 フェーズ コミット プロトコルと3 フェーズ コミット プロトコルがあります。

コンセンサス

コンセンサス アルゴリズムは、複数のプロセスが共通の決定に同意するという問題を解決しようとします。

より正確には、コンセンサス プロトコルは以下の 4 つの形式的なプロパティを満たす必要があります。

• 終了: すべての正しいプロセスは何らかの値を決定します。
• 有効性: すべてのプロセスが同じ値を提案した場合、すべての正しいプロセスが決定します。${\displaystyle v}$${\displaystyle v}$
• 整合性: すべての正しいプロセスは最大で 1 つの値を決定し、何らかの値を決定する場合は、何らかのプロセスによって提案されている必要があります。${\displaystyle v}$${\displaystyle v}$
• 合意: 正しいプロセスが を決定する場合、すべての正しいプロセスが を決定します。${\displaystyle v}$${\displaystyle v}$

コンセンサスを解決するための一般的なアルゴリズムは、Paxos アルゴリズムとRaft アルゴリズムです。

分散検索

リーダー選挙

リーダー選出とは、複数のコンピュータ (ノード) に分散されたタスクのオーガナイザーとして単一のプロセスを指定するプロセスです。タスクが開始される前は、どのノードがタスクの「リーダー」またはコーディネーターとして機能するかは、すべてのネットワーク ノードにはわかりません。ただし、リーダー選出アルゴリズムが実行されると、ネットワーク全体の各ノードは特定の一意のノードをタスク リーダーとして認識します。

相互排除

非ブロッキングデータ構造

信頼性の高い放送

信頼性の高いブロードキャストは、分散システムにおける通信プリミティブです。信頼性の高いブロードキャストは、次のプロパティによって定義されます。

• 有効性- 正しいプロセスがメッセージを送信すると、最終的には何らかの正しいプロセスがそのメッセージを配信します。
• 合意- 正しいプロセスがメッセージを配信する場合、最終的にはすべての正しいプロセスがそのメッセージを配信します。
• 整合性- すべての正しいプロセスは、そのメッセージがプロセスによって送信された場合にのみ、同じメッセージを最大 1 回配信します。

信頼性の高いブロードキャストには、順次順序、因果順序、または全順序付けが可能です。

レプリケーション

リソースの割り当て

スパニングツリー生成

対称性の破れ、例えば頂点の色付け

• クリスチャン・カチン。ラシッド・ゲラウィ。 Luís Rodrigues (2011)、信頼性が高く安全な分散プログラミング入門(第 2 版)、Springer、Bibcode :2011itra.book....C、ISBN 978-3-642-15259-7
• C. Rodríguez、M. Villagra、B. Barán、「ブール満足度のための非同期チームアルゴリズム」、Bionetics2007、pp. 66–69、2007年。

• ウィキメディア・コモンズの分散アルゴリズムに関連するメディア
• MIT オープン コースウェア - 分散アルゴリズム