Paxosのようなコンセンサス アルゴリズムは、2 人の将軍が「安全に合意するアルゴリズムを設計することは不可能」であることを証明したとき、どのようにして「安全性 (不一致からの自由) を保証する」のでしょうか?
2 台のサーバーで (1) 確実に番号を交換する (つまり、両方のサーバーが確実に番号を受信したことを両方のサーバーが認識する) か、(2) 両方のサーバーが交換が失敗したことを認識し、そうでないことを認識する最も単純なケースを考えると、状態を変更すると、(2 人の将軍のように) メッセージの失敗は常に矛盾を残す方法で発生する可能性があるように思われます (つまり、一方のサーバーは他方が交換を終了したと考えているが、そうではありませんでした)。
では、Paxos (またはその他のもの) はどのようにして「矛盾からの自由」を本当に保証しているのでしょうか? 簡単な言葉での説明はありますか？2 つのサーバーが保証された交換を行う、または失敗時に交換を完全に放棄することを示す最も単純な疑似コードは何ですか?
重要なのは、Paxos による次の仮定です。
Liveness(C;L): 値 C が提案されている場合、最終的に学習者 L は何らかの値を学習します (十分なプロセッサが故障していない場合)。
2 人の将軍の問題の悪いケースは、メッセンジャーが継続的に傍受される場合です。「十分なプロセッサが故障していない場合」の部分は、その可能性を排除します。
つまり、メッセージが継続的にドロップされる場合、Paxos は終了する必要がありません (終了しません)。
Paxos は実際には 2 つの将軍の問題を解決しません。ウィキペディアの記事から引用したように：
一般に、コンセンサス アルゴリズムは、F プロセッサの同時障害にもかかわらず、2F+1 プロセッサを使用して進歩することができます。
2*1 + 1 = 32 つの将軍の問題では、1 つのノードの障害を処理することは、その多くの障害を処理するためにノードが必要になることを意味します。2 将軍問題の不可能性は、N 将軍に一般化されていません。
現実世界で 2 人の将軍の問題を解決する 1 つの方法は、フェンシングです。