詳説 データベース ―ストレージエンジンと分散データシステムの仕組み

10章リーダー選出

同期には、かなりのコストがかかる可能性があります。アルゴリズムの各ステップで参加ノード間の連絡が必要な場合には、通信オーバーヘッドが大幅に増大することがあります。このことは、地理的に分散している大規模なネットワークでは、特に顕著になります。同期のオーバーヘッドを減らし、決定に達するために必要なメッセージのラウンドトリップを削減するため、一部のアルゴリズムは、分散アルゴリズムの実行または調整のステップを制御するリーダー（コーディネータとも呼ばれます）プロセスの存在に依存しています。

一般的には、分散システム内のプロセスは一様なので、どのプロセスでもリーダーの役割を引き受けられます。プロセスでは、リーダーシップが長期間に渡ることが前提にされますが、これは永遠に続く役割ではありません。通常は、プロセスがリーダーであり続けるのは、それがクラッシュするまでです。クラッシュの後で、他のプロセスが新しい選出ラウンドを開始し、選出された場合にはリーダーの役割を引き受けて、先に障害を起こしたリーダーの動作を続行します。

選出アルゴリズムの活性によって、ほとんど途切れることなくリーダーが存在し、選出が最終的には完了することが保証されます。つまり、システムは選出状態を際限なく続けてはなりません。

理想としては、安全性も前提にし、同時に存在できるリーダーは多くても1つであることを保証して、スプリットブレイン（同じ目的のために機能するリーダーが2つ選出されたが、相互の存在を認知していない状況）となる可能性を、完全に排除することが望まれます。ただし現実問題としては、多くのリーダー選出のアルゴリズムが、このルールに違反しています。

リーダープロセスは、たとえば、ブロードキャストにおいてメッセージの全順序を達成するために使用できます。リーダーは、グローバルな状態を収集して保持し、メッセージを受け取り、それらをプロセス間に散布します。また、障害の後や、初期化の間、あるいは重要な状態の変更が行われたときに、システムの再編成を調整するために使用することもできます。 ...