Paxosリーダーの選挙が終了しない可能性があります

Question

私はPaxos製の簡単な用紙を勉強しています.Paxosは、2人の提案者がより高い提案番号で互いに競争している場合に進歩を保証しないという事実に苦労しています。進歩を保証するために、彼をリーダーにする著名な提案者を選出しなければならない。

しかし、人々はPaxosを使用して優秀な提案者を選ぶことを提案しているので、ここで問題が発生します。

このシナリオは実装固有のものであることを理解しています。例えば、選択するプロセスに与えられた識別されたセットが注文された場合、P1セット< P2が設定されます。

しかし、私は実際の実装でこの処理方法を理解したいと思いますか？

Answer 1

普段のアプローチでは、おそらくリーダーの決闘の可能性は低いと思われる無作為タイムアウトを使用することです。紙の中で「タイムアウト」を検索すると、これが言及されます。

安定したリーダーが出現して進展するのに平均でX秒かかる場合（最小のメッセージラウンドトリップ数で見積もることができます）、各ノードには、 Xの倍数。リーダーになるたびに新しい乱数を使用することで、リーダーの大戦の確率は低くなります。

ランダムタイムアウトの上限としてXの大きな倍数を設定した場合、リーダーの延長戦の確率は低くなります。しかし、リーダーが出現するまでの平均時間も長くなっています。それはトレードオフです。

非常に高速なフェイルオーバーが必要な実装では、タイムアウトの小さいランダムな間隔を使用することがありますが、リーダーの決闘が迅速に解決する仕組みを実装しようとします。任意のメカニズムを発明することができます。

1つのノードがリーダーになるという利点があることを保証する簡単なメカニズムは、次のとおりです。各ノードには、投票用紙の注文に使用される固有の番号があります。リーダーの決闘の間、各ノードは指数バックオフを使用することができます。指数バックアップは、独自の固有番号でスケーリングされます。例えば、リーダーになることができなかったそれぞれのノード番号がNであれば、そのタイムアウトウィンドウの上限に1 + 1/Nを掛けることができる。これは、任意の決闘中に、最も高いNを有するノードが、他のノードがより速くバックオフするので、リーダーになることを試みることにおいてより積極的であることを意味する。