終了を保証する非決定論的なリーダー選出アルゴリズムが (一方向リングで) 存在するかどうか疑問に思っていました。私はそれを考えることができず、非決定論的なものを見つけることもできません. 私が見つけたいくつかは次のとおりです。
プロセス ID が最も大きいノードをリーダー (決定論的) として選択し、終了します。
ノードがリーダーになりたいかどうかをランダムに決定します。リング内にリーダーになりたい別のノードがある場合は、プロセス全体を再起動します。これは終了しませんが、終了する可能性があります。
分散型の非決定論的リーダー選挙アルゴリズムを作成する方法について、誰かがヒントを教えてくれますか? そして多分それを素人の言葉で説明してください。
すべてに感謝します！
保証された終了と保証された正しさ (リーダーは 1 つだけ) の両方を持つ確率論的 (匿名) リーダー選出アルゴリズムは存在しません。私の記憶が正しければ、分散システムに関する N. Lynch の本にその証拠があります。
ただし、アルゴリズムの実行時間が十分に長いため、非終了の確率限界がゼロのアルゴリズムが存在します。さらに、予想される実行時間はかなり短いです (AFIR、k 個のイニシエーターに対して ln(k) のオーダー)。
このようなアルゴリズムの主なアイデアは、2 番目のアプローチに従います。ただし、複数のリーダーがいる場合は単純にプロセスを再開しないでください。最終ラウンドの勝者のみが次のラウンドの候補になることを許可してください。
編集 1-3:
非匿名のリーダー選挙を要求する場合、終了を保証するいくつかの確率的アルゴリズムがあります。たとえば、通常のリング アルゴリズムを使用して、特定の確率でメッセージを遅延させます。ID が小さいほど、遅延の可能性が高くなります。このようにして、勝つ可能性が低いメッセージが早期に消去され、全体的なメッセージが少なくなります。
非匿名メンバーに対して異なる結果が必要な場合は、たとえば 2 フェーズ アルゴリズムを使用できます。
運の要素も分散できます。
終了と非決定論的な結果は、両方のアルゴリズムに付与されます。ただし、最初のメッセージの平均複雑度は低く ( n log n対n² ; 最悪の場合の複雑度は同じ)、公平です (つまり、ID が勝つ確率は均等に分散されますが、2 番目には当てはまりません)。アルゴリズム）。少なくとも最後の欠点は、より洗練されたアルゴリズムによって排除できると確信していますが、ここでの問題は、そのようなアルゴリズムの一般的な存在についてでした。
質問から私が理解していることから、あなたは実際に選挙アルゴリズムを探しているのではなく、1つのクライアントを「リーダー」として公正かつランダムに選択するための分散アルゴリズムに過ぎず、クライアントのサブセットが協力して不正行為を行うことはできません。
これは実際にはかなり簡単です。各クライアントを一組のカードとして扱い、メンタル ポーカーアルゴリズム(一組のカードを公平かつランダムにシャッフルする分散アルゴリズム)を使用してシャッフルします。次に、最初のカードをリーダーとして取ります。