algorithm - 分散システム: リーダー選挙

Question

私は現在、ある種のLeader Electionを実装する必要がある分散システムに取り組んでいます。問題は、すべてのコンピューターがお互いを認識しなければならないことを回避したいということです。ただし、リーダーのみです。たとえば、ブロードキャストを使用して目的を達成するための高速な方法はありますか?

それとも、優れたリーダー選挙を行うために、少なくとも 1 つを知っていればよいのでしょうか?

すべてのコンピューターが同じサブネット上にあると想定されます。

ご協力いただきありがとうございます。

Answer 1

問題は、すべてのコンピューターがお互いを認識しなければならないことを回避したいということです。ただし、リーダーのみです。

リーダー選挙は、一連の潜在的なリーダー候補の中から 1 人のリーダーを選ぶ問題です。livenessとsafetyという 2 つの必須プロパティがあると考えてください。ここで、生存性は「ほとんどの場合、リーダーがいる」ことを意味し、安全性は「ゼロまたは 1 人のリーダーがいる」ことを意味します。ブロードキャストを使用して、あなたの例でこの安全性をどのように解決するかを考えてみましょう。

すべてのノードが一意の ID を持っていると仮定して、単純な (壊れた) アルゴリズムを選びましょう。各ノードはその ID をブロードキャストしてリッスンします。自身よりも上位の ID を受信すると、参加を停止します。自身よりも低い ID を受信した場合は、再度自身のブロードキャストを送信します。同期ネットワークを想定すると、全員が最後に受け取る ID がリーダーの ID になります。次に、ネットワーク パーティションを導入します。議定書はパーティションのどちらの側でも喜んで継続され、2 人のリーダーが選出されます。

これはこの壊れたプロトコルに当てはまりますが、考えられるすべてのプロトコルにも当てはまります。(少なくとも) 存在するノードの数がわからない場合、通信できないノードと存在しないノードの違いをどのように判断しますか? したがって、最初の安全性の結果があります。存在するノードの数を知る必要があります。そうしないと、リーダーが 1 つだけであることを保証できません。

ここで、安全制約を確率論的な制約に緩和しましょう。「0 人以上のリーダーが存在する可能性がありますが、ほとんどの場合、リーダーは 1 人です」。これにより、問題は扱いやすくなり、広く使用されている解決策はゴシップ (伝染病プロトコル) です。たとえば、この正確な問題の変形について説明しているゴシップ スタイルの障害検出サービスを参照してください。この論文は主に、確率的に正しい障害検出と列挙に関係していますが、それができれば、確率的に正しいリーダー選挙も行うことができます。

私が知る限り、少なくとも参加者を列挙しない限り、一般的なネットワークで安全な非確率的リーダー選挙を行うことはできません。

Answer 2

前回見た興味深い「分散型メカニズム」ソリューションの 1 つとして、Apache Zookeeperプロジェクトをお勧めします。これはオープン ソース ソリューションであるため、少なくともそこからいくつかのアイデアを得ることができるはずです。また、集中的に開発されているため、ソリューションの一部として再利用できる可能性があります。

ZooKeeper は、構成情報の維持、命名、分散同期の提供、およびグループ サービスの提供を行うための集中型サービスです。これらの種類のサービスはすべて、分散アプリケーションによって何らかの形で使用されます。それらが実装されるたびに、避けられないバグや競合状態を修正するために多くの作業が行われます。これらの種類のサービスを実装することは難しいため、アプリケーションは通常、最初はそれらを軽視し、変更が存在すると脆弱になり、管理が困難になります。正しく実行されたとしても、これらのサービスの実装が異なると、アプリケーションの展開時に管理が複雑になります。