ダイクストラ・ショルテンアルゴリズム

ダイクストラ・ショルテンアルゴリズム（エドガー・W・ダイクストラとカレル・S・ショルテンにちなんで命名）は、分散システムにおける終了を検出するためのアルゴリズムである。^{[ 1 ] [ 2 ]}このアルゴリズムは、1980年にダイクストラとショルテンによって提案された。^{[ 3 ]}

まず、単純なプロセスグラフであるツリー構造の場合を考えてみましょう。ツリー構造の分散コンピューティングは珍しくありません。このようなプロセスグラフは、計算が厳密に分割統治型である場合に発生する可能性があります。ノードが計算を開始し、問題をほぼ等しい2つ（またはより一般的には2の倍数）の部分に分割し、それらの部分を他のプロセッサに分散します。このプロセスは、問題が単一のプロセッサで解決できるほど十分に小さくなるまで再帰的に続きます。

ダイクストラ・ショルテンアルゴリズムは、以下のように説明できるツリーベースのアルゴリズムです。

• 計算の開始点は、ツリーのルートである。
• 計算メッセージを受信した場合：
  • 受信プロセスが現在計算処理に含まれていない場合、そのプロセスはメッセージの送信元のプロセスに子として加わることでツリーに参加します。（この時点では確認応答メッセージは送信されません。）
  • 受信プロセスが既に計算処理中の場合、そのプロセスは直ちにメッセージの送信者に対して確認応答メッセージを送信します。
• プロセスに子プロセスがなくなり、アイドル状態になると、そのプロセスはツリーの親プロセスに確認メッセージを送信することで、ツリーから自身を切り離します。
• 終了は、開始者が子を持たず、活動を停止した時に発生します。

• ツリー構造の場合、プロセスの終了を検出するのは容易です。リーフプロセスが終了を判定すると、親プロセスにシグナルを送信します。一般的に、プロセスはすべての子プロセスがシグナルを送信するのを待ってから、親プロセスにシグナルを送信します。
• プログラムは、ルートがすべての子ノードからシグナルを受信した時点で終了します。

• 木構造のアルゴリズムは、非巡回有向グラフにも拡張できます。各エッジに、不足量を示す整数属性を追加します。
• 受信エッジにおいて、Deficitは受信したメッセージ数と応答として送信された信号数の差を表します。
• ノードが終了を希望する場合、送信エッジから信号を受信し、それらのエッジの不足分がゼロになるまで待機します。
• そして、各入力エッジにおける不足量がゼロになるように、十分な数の信号を送信する。
• グラフは非巡回グラフであるため、一部のノードは出力エッジを持たず、これらのノードは入力エッジに十分な信号を送信した後、最初に終了します。その後、上位レベルのノードがレベルごとに終了します。

• サイクルが許容される場合、前述のアルゴリズムは機能しません。これは、出力エッジがゼロのノードが存在しない可能性があるためです。したがって、他のノードに相談せずに終了できるノードが存在しない可能性があります。
• ダイクストラ・ショルテン法は、グラフの全域木を暗黙的に作成することでこの問題を解決します。全域木とは、基となるグラフの各ノードを一度ずつ含み、辺集合が元の辺集合の部分集合となる木のことです。
• ツリーは、ソースノード（計算を開始するノード）をルートとして方向付けられます（つまり、チャネルは方向付けられます）。
• スパニングツリーは次のように作成されます。各ノードにFirst_Edgeという変数が追加されます。ノードが初めてメッセージを受信すると、メッセージを受信したエッジでFirst_Edgeを初期化します。First_Edgeはその後変更されません。なお、スパニングツリーは一意ではなく、システム内のメッセージの順序に依存します。
• 各ノードは、以下の3つのステップで終了処理を行います 。
  1. 最初のエッジを除くすべての入力エッジに信号を送信します。（各ノードは、各入力エッジの不足分をゼロにする信号を送信します。）
  2. すべての送信エッジからの信号を待ちます。（各送信エッジで受信される信号の数によって、それぞれの不足量がゼロになるはずです。）
  3. First_Edgeにシグナルを送信します。（ステップ 1 と 2 が完了すると、ノードはスパニングツリー内の親ノードに終了の意思を通知します。）

• 黄のアルゴリズム