問題タブ [paxos]

私は 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を実装しています。残念ながら、それは解釈へのいくつかの扉を開いたままにし、主要な実装の問題に関する多くの情報を提供しません。それは不明確で不完全です。

• クラスターが3つの領域に分割され、それぞれに3つのノードが含まれていると仮定します（合計= 9ノード）。リージョン間の通信が切断された場合はどうなりますか？リーダーがクォーラム（5）に到達する方法はありません。

Paxosは無限ループに入りませんか？少なくともクォーラムのノードと通信できない場合は、Paxosを開始するべきではないと思います。

• フェーズ1b：'プロポーザル番号Nが以前のプロポーザルよりも大きい場合、各アクセプターはN未満のプロポーザルを受け入れないことを約束し、このインスタンスで最後に受け入れた値をプロポーザーに送信します'。

「それが受け入れた最後の値」とは何ですか？提案者からの以前の提案番号ですか？この場合、「インスタンス」は正確に何を指しますか？

• フェーズ1aの場合：準備メッセージに同意するための値が含まれていますか、それともこれは承認に延期されていますか？メッセージ？それとも重要ですか？

• フェーズ2a：'アクセプターのいずれかがすでに値を受け入れている場合、リーダーは最大提案番号N 'の値を選択する必要があります。

ここでの価値は何ですか？提案番号ですか？私は信じていませんが、このフレーズは不明確です。

• フェーズ2a：'それ以外の場合、提案者は任意の値を自由に選択できます'。これは何を意味するのでしょうか？何の価値？提案番号は？

• Paxosは、N（提案番号）の値の増加に依存して機能しているようですか？これは正しいです？

• ウィキペディアのエントリでは、Paxosへの参加を開始する前にノードが設定する必要のある初期値については説明していません。これは何？

PS：「Paxos」タグを作成するのに十分な評判がありません（ボランティアはいますか？）

Multi-Paxosアルゴリズムでは、アクセプターの観点からこのメッセージフローを検討します。

受信：準備（N）

返信：Promise（N、null）

受信：受け入れる！（N、V1）

返信：承認済み（N、V1）

受信：承認！（N + 1、V2）

返事： ？

プロトコルによると、この場合、アクセプターの反応はどうあるべきですか？Accepted（N + 1、V2）で応答する必要がありますか、それとも2番目のAccept！を無視する必要がありますか？

このケースは、2番目の提案者がオンラインになり、彼がリーダーである（そして常にそうであった）と信じているときにMulti-Paxosで発生する可能性があると思います。したがって、彼は準備せずにAcceptを送信します。または、彼の準備が単にアクセプターに到達しなかった場合。このケースが発生しない可能性がある場合、その理由を説明できますか？

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

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

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

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

基本的には、次のアルゴリズムを実装し、これらのアルゴリズムを使用して構築されたシステムがさまざまな条件下でどのように動作するかを分析したいと考えています。

• ゴシッププロトコル
• 複数のパクソ
• コンシステント ハッシュ

ここでの私の関心は、これらのアルゴリズムにあります。私は基本的に、これらのアルゴリズムをすばやく記述し、これらのアルゴリズムを深く理解できるプログラミング言語を探しています。

どの言語を選択すればよいですか? Java、Scala、Erlang など。

現在、私は Java と C++ を知っています。

Paxosアルゴリズムは、2F + 1プロセッサを使用する場合、最大Fの障害に耐えることができます。私が理解している限り、このアルゴリズムは固定数のプロセッサでのみ機能します。ノードを動的に追加および削除できる動的環境でこのアルゴリズムを使用することは可能ですか？

誰かが私に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 made simple」という名前の論文を読みましたが、まだいくつかの混乱がありました。

1. 「paxos アルゴリズムのインスタンス」とは何を指していますか? 各インスタンスは、外部クライアントからの入力/コマンドがあることを示していますか? 各インスタンスの paxos アルゴリズムは並行して実行されますか???

2. 提案を発行できる「著名な」提案者が 1 人しかいない場合、paxos アルゴリズムと 2 フェーズ コミット アルゴリズムの違いは何ですか?

3. 実際のプロジェクトで paxos アルゴリズムをどこに適用できますか?

こちらの論文の方がより明確に説明されているようです: http://research.microsoft.com/pubs/64634/web-dsn-submission.pdf

他にアイデアはありますか？