Hirschberg–Sinclair algorithm とは

Hirschberg-Sinclairアルゴリズムは、同期リングネットワークにおけるリーダー選挙問題のために設計された分散アルゴリズムです。その発明者、Dan HirschbergとJ. B. Sinclairにちなんで命名されました。
このアルゴリズムでは、プロセスごとに一意のID(UID)を使用する必要があります。アルゴリズムはフェーズで動作し、UIDを双方向に送信します。メッセージは2Phase Numberホップの距離を離れ、メッセージは元のプロセスに戻ります。メッセージが「出て」いる間、各受信プロセスは着信UIDをそれ自身のものと比較します。 UIDが自身のUIDより大きい場合、メッセージはオンになります。それ以外の場合は、UIDが自身のUIDよりも小さい場合、その情報は渡されません。フェーズの終わりに、プロセスは、受信メッセージの両方を受信した場合に、次のラウンドでメッセージを送信するかどうかを判断できます。フェーズは、プロセスがその近隣の両方の両方からメッセージを受信するまで続きます。現時点では、プロセスはリング内で最大のUIDであることを認識し、それをリーダーと宣言します。