問題タブ [consensus]

私は Paxos を調べていますが、この不自然な例でアルゴリズムがどのように動作するかについて混乱しています。下の図がシナリオを説明していることを願っています。

いくつかのポイント:

• 各エージェントは、提案者/受容者/学習者として機能します
• メッセージの形式を準備する(instance, proposal_num)
• メッセージにフォームがあることを提案する(instance, proposal_num, proposal_val)
• Server1 と Server2 の両方が同時に提案プロセスを開始することを決定します
• 最初に、メッセージ M1、M2、および M3 が同時に発生します。

ここでは、プロトコルが「正しい」、つまり 1 つの値のみS2が選択されているにもかかわらず、サーバー 1 とサーバー 2 は、提案番号が異なるためにそれが選択されたと信じているようです。

Paxos アルゴリズムは、Decide(...)メッセージが学習者に送信されたときにのみ終了しますか? 私はPaxos Made Simpleを誤解しているに違いありませんが、提案者がPropose(...)メッセージの定足数を達成した瞬間に選択が行われたと思いました。

Decide(...)メッセージがエージェントに送信された後にのみ選択が行われる場合、サーバー 2Decide(1, 5, S2)は後でPrepare(1, 7).

Paxos の実際の使用例のリストを教えてください。それは、より大きな問題の一部としてコンセンサスを必要とする実際の問題です。

以下は Paxos の使用例ですか?

ポーカー サーバーで互いにポーカーをプレイしている 2 つのクライアントがあるとします。ポーカー サーバーが複製されます。私が Paxos について理解しているのは、現在のポーカーのハンドを表すメモリ内データ構造の一貫性を維持するために使用できるということです。つまり、すべてのレプリカが正確に同じハンドのメモリ内状態を持っていることを確認してください。

しかし、なぜ Paxos が必要なのでしょうか? 新しいカードを配る必要があるとします。すべてが正しければ、同じコードを実行する各レプリカは同じカードを生成します。クライアントがすべての複製されたサーバーから最新の状態を要求して、最も多く表示されるカードを選択できないのはなぜですか。そのため、1 つのサーバーにエラーが発生した場合でも、クライアントは過半数を選択するだけで正しい状態を取得できます。

誰かが私にPaxosアルゴリズムが分散データベースでどのように使用されているかの実際の例を教えてもらえますか？アルゴリズムを説明するPaxosに関する多くの論文を読みましたが、実際の例で実際に説明しているものはありません。

簡単な例として、口座が複数のセッション（つまり、出納係での預金、借方操作など）によって変更されている銀行アプリケーションがあります。Paxosは、どの操作が最初に行われるかを決定するために使用されますか？また、Paxosプロトコルの複数のインスタンスとはどういう意味ですか？これはいつどのように使用されますか？基本的に、私は抽象的な用語ではなく具体的​​な例を通してこれらすべてを理解しようとしています。

ここに paxos アルゴリズムの疑似コードを貼り付けました。

Paxosコンセンサスアルゴリズムの「ビュー」とは何ですか?

誰かが私を正しい方向に向けることができるかどうか疑問に思っていました.

アルゴリズムは、各ノードには、ノードが追跡する必要がある一連の情報を含む「状態」があることを示しています。

ノード #1 とノード #2 の 2 つのノードがあるとします。最も単純なケースでは、ノード #2 がノード #1 に参加し、両方とも paxos をプレイします。2 が 1 に参加した後、ノード #1 とノード #2 の状態は正確にどうなりますか? 「views」データ構造はいつ変更され、何が含まれますか? 誰かが paxos をプレイする 2 つのノードのこの単純なケースを説明できれば、複数ノードのケースを理解できると思います。

私の現在の理解（正しくないと確信しています）は次のとおりです。

1. ノード #2 はメッセージを送信してノード #1 に参加します。
2. ノード #1 はノード #2 から参加を求めるメッセージを受信します。
3. ノード #1 が主導権を握り、フェーズ 1 に入り、my_num = max(0,0) + 1 = 1 を計算します。
4. ノード #1 は、views[0] (空) のすべてのノードを送信します。 prepare(1,1)
5. ノード #1 が最初の連絡先ノード (ノード #2) を送信します prepare(1,1)
6. ノード #1 がノード #1 (自身) を送信する prepare(1,1)
7. ノード #2 は prepare(1,1) を受け取ります。num_h=1 を設定し、リーダー PROMISE(0,{empty list}) に戻ります。
8. ノード #1 は prepare(1,1) を受け取り、その num_h=1 を設定し、自身を PROMISE(0,{empty list}) に戻します。

フェーズ 2 に進みます

これは私がかなり混乱しているところです。

ノード #1 はリーダーであり、2 つの PROMISE(0,{empty list}) メッセージを受け取ります。アルゴリズムによると、リーダーがビュー [0] でプロミスの過半数を取得した場合、「v」の値を設定し、ACCEPT メッセージをすべてのレスポンダーに送信できます。

私が混乱しているのは、現在リーダーのビュー[0]が空であるため、空のリストの大部分をどのように計算できるでしょうか?

また、リーダーが Promise の過半数を受け取り、セット v = ping 可能なノードのセット (自己を含む) に進むと仮定しましょう。ping可能なノードとは正確には何ですか? ノード #1 とノード #2 だけですか?

すべての/あらゆる助けに感謝し、助けてくれた人に間違いなくポイントを与えます.

コンセンサス アルゴリズムを実装しました (Paxos に基づく)。ランダムなテストケースをいくつか追加しましたが、問題ないようです。しかし、モデル チェックを介してテストを行いたいですか? 適切な記事が見つかりませんでした。Paxos でのモデル チェックの方法を共有してください

ありがとう

Paxosのようなコンセンサス アルゴリズムは、2 人の将軍が「安全に合意するアルゴリズムを設計することは不可能」であることを証明したとき、どのようにして「安全性 (不一致からの自由) を保証する」のでしょうか?

2 台のサーバーで (1) 確実に番号を交換する (つまり、両方のサーバーが確実に番号を受信したことを両方のサーバーが認識する) か、(2) 両方のサーバーが交換が失敗したことを認識し、そうでないことを認識する最も単純なケースを考えると、状態を変更すると、(2 人の将軍のように) メッセージの失敗は常に矛盾を残す方法で発生する可能性があるように思われます (つまり、一方のサーバーは他方が交換を終了したと考えているが、そうではありませんでした)。

では、Paxos (またはその他のもの) はどのようにして「矛盾からの自由」を本当に保証しているのでしょうか? 簡単な言葉での説明はありますか？2 つのサーバーが保証された交換を行う、または失敗時に交換を完全に放棄することを示す最も単純な疑似コードは何ですか?

既知の論文Impossibility of Distributed Consensus with one Faulty Process (JACM85)で、FLP (Fisher、Lynch、および Paterson) は、完全に非同期のコンセンサス プロトコルでは、1 つの未発表のプロセスの停止さえ許容できないという驚くべき結果を証明しました。

補題 3 では、D が 0 価と 1 価の配置の両方を含むことを示した後、次のように述べています。

1 つのステップで一方が他方の結果である場合、2 つの構成ネイバーを呼び出します。簡単な帰納法により、Dᵢ = e(Cᵢ) が i 価、i = 0, 1 となる近傍 C₀, C₁ ∈ C が存在します。

彼らがそのようなC₀とC₁の存在を主張する場合を除いて、私は証明全体に従うことができます. ヒントを教えてください。