このシナリオでのPaxosエージェントの適切な動作は何ですか？

Question

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

いくつかのポイント：

\ n
• 各エージェントは、提案者/承認者/学習者として機能します
\ n
• メッセージの準備にはフォーム(instance, proposal_num)があります
\ n
• メッセージのフォームが(instance, proposal_num, proposal_val)であることを提案します
\ n
• Server1とServer2の両方が、提案プロセスを同時に開始することを決定します
\ n
• 冒頭のメッセージM1、M2、M3は同時に発生します
\ n

ここでは、プロトコルは「正しい」、つまり1つの値S2のみが選択されていますが、Server1とServer2は、提案番号が異なるために選択されたと考えているようです。

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

Decide(...)メッセージがエージェントに送信された後にのみ選択が行われた場合、Server2は、後のDecide(1, 5, S2)を見たため、回復したときにPrepare(1, 7)の送信を終了する必要がありますか？

Answer 1

用語を再定義するだけです（Paxosの反復を1回だけ調べているので、1も捨てましょう）：

1）Propose（n）== proposal（n）、現在のアイデンティティnを持つ提案者からのメッセージ

2）AcceptPrepare（n、v）== ack（n、v）、提案者nに送信されるメッセージ。このノードがまだ値を受け入れていない場合、vは空白です。現在、vは受け入れた値と同じです。

3）CreateDecide（n、v）== accept！（x、v）、アイデンティティxを持つ提案者からこの値を受け入れるようにノードに要求します。ノードは、n> xであるprepare（n）メッセージを確認した場合、メッセージを拒否します。

prepare（n）のクォーラムが達成されると（つまり、過半数がメッセージを確認した場合）、IDがnの提案者はコマンドaccept！（n、v）を送信します。prepare（n + x）、x> 0が、アイデンティティn + xの提案者によって送信され、ack（n、v）メッセージとaccept！（n、v）の場合、過半数はタイムスタンプ 0で提案された値を受け入れないことを約束しました（別名、ノードは受け入れを拒否します！（n、v））

選択は、過半数が無視することを約束していないaccept！（n、v）メッセージを受信するとすぐに行われます。

したがって、server2がオンラインに戻り、accept！（5、S2）を送信すると、5 <7であるため、無視されます。

Answer 2

受け入れられた答えに対位法を与えるために、アルゴリズム自体は、ひどく明確に定義された意味で実際に終了する必要はありません。実装で定義されているアルゴリズムへの参加を個別に終了する各ノードについて話す方が理にかなっています。次に、参加しているすべてのノードがドロップアウトしたときにアルゴリズム自体が終了したと言うことができます。これが知りたい場合に役立ちます。

アクセプターの大多数が同じ投票に対してAcceptProposeメッセージを送信するとすぐに、アルゴリズムは効果的に収束しました（これが発生すると、最終的にどの値を決定できるかについてのオプションがないという意味で）が、これは状況ではありません。これは実際に観察できます。たとえば、このAcceptProposeメッセージのセットが送信される直前にネットワークがメッセージのドロップを開始した場合、接続が復元されるまで、ノードはアルゴリズムが収束したことを知ることができません。

ただし、アルゴリズムが収束したことを1つのノードが認識すると（多数派からAcceptProposeメッセージを受信したことにより）、ブロードキャストやゴシップでDecideメッセージを送信したり、他のノードでAcceptProposeメッセージを送信したりするなど、従来の方法で選択した値を共有しても安全です。すべてのノードが収束が達成されたことを認識するまで転送します。

各ノードは、アルゴリズムが収束した値を知ったら、アルゴリズムへの参加を終了できますが、実装の制約によっては、より長く参加し続けることをお勧めします。

決定時に終了することで活気が保たれることを自分自身に納得させるには、フォールトトレランスについて少し考える必要があります。決定された値を知っているすべてのノードが、共有する前に死ぬことになった場合でも、進歩は可能でしょうか。答えは、幸いなことに、はいです。ノードの大部分が生きている限り、ノードのいずれかが決定された値を知っている場合は、他のノードと共有できます。そうでない場合は、選択する必要がある参加ノードの大部分があります。より高い投票数と別のラウンドを実行します。

---

受け入れられた答えで注意すべきことの1つは、次のフレーズです。

\ n

選択は、過半数が無視することを約束していないaccept！（n、v）メッセージを受信するとすぐに行われます。

\ n

まず、プロトコルにはProposeメッセージを無視することを約束することについては何もありません。約束は、AcceptProposeメッセージが無視/拒否されるべきであることに関係します。AcceptProposeメッセージの大部分は、投票数に関係なく、選択した値を学習するために常に使用できます。

第二に、過半数がAcceptProposeのメッセージを送信するとすぐに、効果的に選択が行われます。これを直接観察することはできないため、選択が行われたことを知る前に、少なくとも1つのノードが過半数からAcceptProposeメッセージを受信するまで待つ必要があります。それが起こったら、実装の制約により適しているかどうかに応じて、より多くのDecidedメッセージまたは1114メッセージのブロードキャスト/ゴシップを介して選択した値を共有できます。