黄のアルゴリズム

黄のアルゴリズムは、分散システムにおける終了を検出するためのアルゴリズムである。このアルゴリズムは、1989年にShing-Tsaan HuangによってInformation Processing Letters誌に提案された。^[1]

終了検出の基礎は、分散システム プロセスの状態の概念にあります。分散システム内のプロセスは、常にアクティブ状態またはアイドル状態のいずれかになります。アクティブ プロセスはいつでもアイドル状態になる可能性がありますが、アイドル プロセスは計算メッセージを受信したときにのみ再びアクティブになります。

終了は、分散システム内のすべてのプロセスがアイドル状態になり、転送中の計算メッセージがなくなったときに発生します。

Huang のアルゴリズムは次のように説明できます。

• 最初はすべてのプロセスがアイドル状態です。
• 分散タスクは、プロセスが別のプロセスに計算メッセージを送信することによって開始されます。メッセージを送信するこの最初のプロセスは、「制御エージェント」です。
  • 制御エージェントの初期重量は（通常 1）です。${\displaystyle w}$
• 計算全体を通して次のルールが適用されます。
  • メッセージを送信するプロセスは、現在の重みを自分自身とメッセージの間で分割します。
  • メッセージを受信するプロセスは、メッセージの重みを自身に追加します。
  • プロセスはアイドル状態になると、その重み全体を含むメッセージを制御エージェントに送り返し、アイドル状態になります。
  • 終了は、制御エージェントの重みが で、アイドル状態にあるときに発生します。${\displaystyle w}$

Huang のアルゴリズムの弱点は、メッセージが転送中に失われた場合や、プロセスがアクティブ状態の間に失敗した場合に終了を検出できないことです。

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