ランポートの分散相互排除アルゴリズム

ランポートの分散相互排他アルゴリズムは、分散システムにおける相互排他のための競合ベースのアルゴリズムです。

アルゴリズム

節点特性

1. 各プロセスは、クリティカルセクションへの順番に進むための保留中の要求のキューを保持しています。キューは、ランポートタイムスタンプから導出された仮想タイムスタンプによって順序付けられます。^[1]

アルゴリズム

リクエストプロセス

1. リクエストを独自のキューにプッシュする（タイムスタンプ順に並べる）
2. すべてのノードにリクエストを送信します。
3. 他のすべてのノードからの応答を待機しています。
4. 自身の要求がキューの先頭にあり、すべての応答が受信された場合、クリティカル セクションに入ります。
5. クリティカル セクションを終了すると、その要求をキューから削除し、すべてのプロセスに解放メッセージを送信します。

その他のプロセス

1. リクエストを受信した後、リクエストを独自のリクエスト キューにプッシュし (タイムスタンプ順に並べ)、タイムスタンプで応答します。
2. 解放メッセージを受信した後、対応する要求を自身の要求キューから削除します。

メッセージの複雑さ

このアルゴリズムは、リクエストごとに3( N  −1)個のメッセージ、つまり( N  −1)個のメッセージと2つのブロードキャストを作成します。リクエストごとに3( N  −1)個のメッセージには次のものが含まれます。

• ( N  − 1) リクエストの総数
• ( N  − 1) 回答総数
• ( N  − 1) リリースの総数

欠点

このアルゴリズムにはいくつかの欠点があります。

• いずれかのプロセスが失敗すると進行が停止するため、信頼性が非常に低くなります。
• クリティカルセクションへの入口/出口ごとに3( N −1)メッセージという高いメッセージ複雑性があります。

参照

• リカート・アグラワラアルゴリズム（ランポートのアルゴリズムの改良）
• ランポートのベーカリーアルゴリズム
• レイモンドのアルゴリズム
• 前川のアルゴリズム
• 鈴木・笠見アルゴリズム
• Naimi-Trehelアルゴリズム

参考文献

1. Kshemkalyani, A., Singhal, M. 第9章「分散相互排他アルゴリズム」『分散コンピューティング：原理、アルゴリズム、システム』（93ページ中10ページ）ケンブリッジ大学出版局。