問題は、すべてのコンピューターがお互いを認識しなければならないことを回避したいということです。ただし、リーダーのみです。
リーダー選挙は、一連の潜在的なリーダー候補の中から 1 人のリーダーを選ぶ問題です。livenessとsafetyという 2 つの必須プロパティがあると考えてください。ここで、生存性は「ほとんどの場合、リーダーがいる」ことを意味し、安全性は「ゼロまたは 1 人のリーダーがいる」ことを意味します。ブロードキャストを使用して、あなたの例でこの安全性をどのように解決するかを考えてみましょう。
すべてのノードが一意の ID を持っていると仮定して、単純な (壊れた) アルゴリズムを選びましょう。各ノードはその ID をブロードキャストしてリッスンします。自身よりも上位の ID を受信すると、参加を停止します。自身よりも低い ID を受信した場合は、再度自身のブロードキャストを送信します。同期ネットワークを想定すると、全員が最後に受け取る ID がリーダーの ID になります。次に、ネットワーク パーティションを導入します。議定書はパーティションのどちらの側でも喜んで継続され、2 人のリーダーが選出されます。
これはこの壊れたプロトコルに当てはまりますが、考えられるすべてのプロトコルにも当てはまります。(少なくとも) 存在するノードの数がわからない場合、通信できないノードと存在しないノードの違いをどのように判断しますか? したがって、最初の安全性の結果があります。存在するノードの数を知る必要があります。そうしないと、リーダーが 1 つだけであることを保証できません。
ここで、安全制約を確率論的な制約に緩和しましょう。「0 人以上のリーダーが存在する可能性がありますが、ほとんどの場合、リーダーは 1 人です」。これにより、問題は扱いやすくなり、広く使用されている解決策はゴシップ (伝染病プロトコル) です。たとえば、この正確な問題の変形について説明しているゴシップ スタイルの障害検出サービスを参照してください。この論文は主に、確率的に正しい障害検出と列挙に関係していますが、それができれば、確率的に正しいリーダー選挙も行うことができます。
私が知る限り、少なくとも参加者を列挙しない限り、一般的なネットワークで安全な非確率的リーダー選挙を行うことはできません。