Loading article…
ランポートの分散相互排除アルゴリズムは、分散システム上の相互排除のための競合ベースのアルゴリズムです。
アルゴリズム
ノードプロパティ
- 各プロセスは、クリティカルセクションに入るための保留中の要求のキューを順番に保持します。キューは、Lamportタイムスタンプから派生した仮想タイムスタンプによって順序付けられます。[1]
アルゴリズム
申請手続き
- リクエストを独自のキューにプッシュする（タイムスタンプ順に並べる）
- すべてのノードにリクエストを送信します。
- 他のすべてのノードからの応答を待機しています。
- 自身の要求がキューの先頭にあり、すべての応答が受信された場合、クリティカル セクションに入ります。
- クリティカル セクションを終了すると、その要求をキューから削除し、すべてのプロセスに解放メッセージを送信します。
その他のプロセス
- リクエストを受信した後、そのリクエストを独自のリクエスト キュー (タイムスタンプ順に並べる) にプッシュし、タイムスタンプで応答します。
- 解放メッセージを受信した後、対応する要求を自身の要求キューから削除します。
メッセージの複雑さ
このアルゴリズムは、リクエストごとに 3( N − 1) 個のメッセージ、つまり ( N − 1) 個のメッセージと 2 つのブロードキャストを作成します。リクエストごとに 3( N − 1) 個のメッセージには次のものが含まれます。
- ( N − 1) リクエストの総数
- ( N − 1) 回答総数
- ( N − 1) リリース総数
欠点
このアルゴリズムにはいくつかの欠点があります。
- いずれかのプロセスが失敗すると進行が停止するため、信頼性が非常に低くなります。
- クリティカルセクションへの入口/出口ごとに3( N −1)メッセージという高いメッセージ複雑性があります。
参照
- Ricart-Agrawala アルゴリズム(Lamport のアルゴリズムの改良)
- ランポートのベーカリーアルゴリズム
- レイモンドのアルゴリズム
- 前川のアルゴリズム
- 鈴木-笠見アルゴリズム
- ナイミ・トレヘルアルゴリズム
参考文献
- ^ Kshemkalyani, A.、Singhal, M. 第 9 章: 分散相互排他アルゴリズム。分散コンピューティング: 原理、アルゴリズム、システム (93 ページ中 10 ページ)。ケンブリッジ大学出版局。