5

私は 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).

4

2 に答える 2

2

用語を再定義するだけです (Paxos の反復を 1 回しか調べていないため、1 も捨てましょう):

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

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

3) CreateDecide(n,v) == accept!(x,v)、ID x を持つ提案者からこの値を受け入れるようにノードに要求します。ノードは、n > x の場合に prepare(n) メッセージを確認した場合、メッセージを拒否します。

prepare(n) のクォーラムが達成されると (つまり、過半数がメッセージを承認した場合)、ID n を持つプロポーザーがコマンド accept!(n,v) を送信します。prepare(n+x) (x > 0) が ID n+x の提案者によって送信され、多数決によって確認応答された場合、ack(n,v) メッセージと accept!( n,v) の場合、過半数はタイムスタンプ < n+x, x > 0 で提案された値を受け入れないことを約束しました (AKA ノードは受け入れを拒否します!(n,v))

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

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

于 2010-12-09T03:53:15.623 に答える
0

受け入れられた答えに反論するために、アルゴリズム自体は、ひどく明確に定義された意味で実際に終了する必要はありません。実装定義のアルゴリズムへの参加を個別に終了する各ノードについて説明する方が理にかなっています。参加しているすべてのノードがドロップアウトした時点で、アルゴリズム自体が終了したと言えます。

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

ただし、1つのノードがアルゴリズムが収束したことを (多数派からメッセージを受信することによって) 知ると、ブロードキャストまたはゴシップによってメッセージをAcceptPropose送信するなど、従来の手段を介して選択された値を安全に共有し、他のノードが転送することができます。Decide収束が達成されたことをすべてのノードが認識するまで、それをオンにします。

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

決定時に終了することで有効性が維持されることを納得させるために、耐障害性について少し考える必要があります。どの値が決定されたかを知っているすべてのノードが、それを共有する前に死んだとしても、進行は可能でしょうか? 幸いなことに、答えはイエスです。大多数のノードが生きている限り、それらのいずれかが決定された値を知っていれば、それを他のノードと共有できます。投票数を増やして、別のラウンドを実行します。

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

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

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

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

于 2016-12-13T13:08:07.617 に答える