分散型相互排除とリーダー選出

相互排除とリーダー選出は、古典的な協調問題です。これらは、最大で1つのプロセスのみがクリティカルリソースにアクセスすることを保証し、ピア間で単一の傑出したコーディネーターを選出するものです。

Definition

分散型相互排除は、一度に最大1つのプロセスが共有リソースを保持することを保証しつつ、すべての要求者に対して最終的なアクセスを保証します。リーダー選出は、正確に1つのプロセスをコーディネーターとして決定論的に選択し、すべてのプロセスがその結果に合意します。

Scope

このトピックでは、許可ベースの相互排除アルゴリズム（Lamportのタイムスタンプアルゴリズム、Ricart-Agrawala、Maekawaのクォーラムアプローチ）とトークンベースのアルゴリズム、およびそれらのメッセージ複雑度と公平性の特性について説明します。また、リング（Chang-Roberts）および一般的なネットワーク（いじめっ子アルゴリズム）向けのリーダー選出アルゴリズムについても、識別子と同期に関する仮定を含めて扱います。これらのプリミティブは、協調サービスやレプリケートされたシステム全体で繰り返し現れます。

Core questions

• プロセスはメッセージのみを使用して共有リソースへのアクセスを直列化するにはどうすればよいでしょうか？
• 許可ベースおよびトークンベースのスキーム間におけるメッセージ複雑度と公平性のトレードオフは何でしょうか？
• 一意のリーダーはどのように選出され、リーダーが故障した後に選出はどのように再トリガーされるのでしょうか？

Key theories

許可ベースの相互排除

Ricart-Agrawalaなどのアルゴリズムは、論理タイムスタンプによって要求を順序付けし、要求者がすべての（またはクォーラムの）ピアから許可を得た後に入場を許可することで、クリティカルセクションへの入場あたりのメッセージコストを制限しつつ公平性を実現します。

トークンベースの相互排除

一意のトークンが循環するか、オンデマンドで要求され、その保持者のみがクリティカルセクションに入ることができます。これによりメッセージトラフィックは削減されますが、故障後に失われたトークンを再生成するメカニズムが必要となります。

リーダー選出

リング用のChang-Robertsや一般的なネットワーク用のいじめっ子アルゴリズムなどの選出アルゴリズムは、プロセス識別子を使用して、すべての正しいプロセスが認識する単一の最高優先度のコーディネーターに収束します。

Clinical relevance

リーダー選出は、レプリケートされたシステムがプライマリまたはコーディネーターを選択する必要がある場合に常に呼び出され、分散ロックは相互排除を一般化します。どちらも、クラウドインフラストラクチャ全体で使用される協調システムによってコアサービスとして提供されています。

History

Lamportの1978年の論理クロックに関する論文は、タイムスタンプベースの相互排除アルゴリズムを導入しました。RicartとAgrawalaは1981年にそれを最適化し、Maekawaはその後すぐにクォーラムを導入しました。そしてGarcia-Molinaの1982年のいじめっ子アルゴリズムはリーダー選出を形式化し、この分野にその規範的な協調アルゴリズムを与えました。

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

分散型相互排除は、単一マシン上のロックとどのように異なるのでしょうか？

共有メモリや中央ロックマネージャーに依存することができないため、プロセスはメッセージ交換のみによって純粋に協調する必要があり、単一マシンのロックでは当然のこととされているメッセージ遅延や故障を明示的に処理する必要があります。