分散アルゴリズム

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

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

アトミックコミット

アトミックコミットとは、複数の異なる変更を単一の操作として適用する操作です。アトミックコミットが成功すれば、すべての変更が適用されたことになります。アトミックコミットが完了する前にエラーが発生した場合は、コミットは中止され、変更は一切適用されません。

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

コンセンサス

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

より正確には、コンセンサスプロトコルは以下の4つの形式的特性を満たさなければならない。

• 終了：すべての正しいプロセスは、何らかの値を決定します。
• 妥当性：すべてのプロセスが同じ値を提案する場合${\displaystyle v}$そして、すべての正しいプロセスが決定します${\displaystyle v}$。
• 完全性：すべての正しいプロセスは最大で 1 つの値を決定し、もし何らかの値を決定した場合は${\displaystyle v}$、 それから${\displaystyle v}$何らかのプロセスを経て提案されたものに違いない。
• Agreement: if a correct process decides ${\displaystyle v}$, then every correct process decides ${\displaystyle v}$.

Common algorithms for solving consensus are the Paxos algorithm and the Raft algorithm.

Distributed search

Leader election

Leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task is begun, all network nodes are unaware of which node will serve as the "leader," or coordinator, of the task. After a leader election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task leader.

Mutual exclusion

Non-blocking data structures

Reliable Broadcast

Reliable broadcast is a communication primitive in distributed systems. A reliable broadcast is defined by the following properties:

• Validity - if a correct process sends a message, then some correct process will eventually deliver that message.
• Agreement - if a correct process delivers a message, then all correct processes eventually deliver that message.
• Integrity - every correct process delivers the same message at most once and only if that message has been sent by a process.

A reliable broadcast can have sequential, causal or total ordering.

Replication

Resource allocation

Spanning tree generation

Symmetry breaking, e.g. vertex coloring

• Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Introduction to Reliable and Secure Distributed Programming (2. ed.), Springer, Bibcode:2011itra.book.....C, ISBN 978-3-642-15259-7
• C. Rodríguez, M. Villagra and B. Barán, Asynchronous team algorithms for Boolean Satisfiability, Bionetics2007, pp. 66–69, 2007.

• Media related to Distributed algorithms at Wikimedia Commons
• MIT Open Courseware - Distributed Algorithms