27

フェーズ 2. (a) プロポーザーは、多数のアクセプターから準備要求 (番号 n) に対する応答を受信した場合、それらのアクセプターのそれぞれに、値 v を持つ番号 n の提案の承認要求を送信します。ここで、v は応答の中で最大番号の提案の値、または応答が提案を報告しなかった場合は任意の値です。

論文で述べたように、

提案者は、いくつかのアクセプターのセットに、提案が受け入れられるようにという要求を送信することにより、提案を発行します。(これは、最初のリクエストに応答したアクセプターのセットと同じである必要はありません。)"

しかし、私の理解では、フェーズ 2.(a) を次のように変更すると:

プロポーザーが多数のアクセプターから準備要求 (番号 n) に対する応答を受信した場合、値 v を持つ番号 n のプロポーザルの多数決アクセプターの任意のセットにアクセプト要求を送信します。応答の中で最大番号の提案、または応答が提案を報告しなかった場合は任意の値です。

アルゴリズムは失敗します。以下に例を示します。全部で 3 つのアクセプター ABC があるとします。X(n:v,m) を使用して、アクセプタ X のステータスを示します。プロポーザル n:v は、X によって受け入れられた最大の番号のプロポーザルです。ここで、n はプロポーザル番号、v はプロポーザルの値、m はX がこれまでに応答した最大の番号付きの準備要求の番号。

  1. P1 が「prepare 1」を AB に送信
  2. 両方の AB は、1 より小さい番号の要求を受け入れないことを約束して P1 に応答します。これで、ステータスは次のようになります: A(-:-,1) B(-:-,1) C(-:-,-)
  3. P1 は応答を受信し、スタックして非常に低速で実行されます
  4. P2 は「prepare 100」を AB に送信します
  5. 両方の AB は、100 より小さい番号の要求を受け入れないことを約束して P2 に応答します。現在のステータスは次のとおりです: A(-:-,100) B(-:-,100) C(-:-,-)
  6. P2 は応答を受信し、値 b を選択して、「accept 100:b」を BC に送信します。
  7. BC が受け入れ要求を受け取り、受け入れます。ステータスは A(-:-,100) B(100:b,100) C(100:b,-) です。提案 100:b が選択されていることに注意してください。
  8. P1 は再開し、値 a を選択し、「accept 1:a」を BC に送信します
  9. B はそれを受け入れませんが、C は何も約束したことがないため、C は受け入れます。ステータス: A(-:-,100) B(100:b,100) C(1:a,-)。選択された提案は放棄され、Paxos は失敗します。

ここで何か見逃しましたか？ありがとう。

4

8 に答える 8

6

すべてのアクセプタに受け入れリクエストをブロードキャストしても問題はありません。元の準備リクエストに応答したものだけに制限する必要はありません。ランポート博士の著書でまれに不適切な言葉遣いを発見しました。

ただし、反例にはバグがあります。まず、表記法は次のように定義されます。

X(n:v,m)承認者 Xのステータスを示す: 提案n:vは、X によって承認された最大の番号の提案です。

しかし、ステップ 7 でノード C は stateC(100:b,-)になり、ステップ 9 で state に変更されますC(1:a,-)。これは有効なトランジションではありません: C によって受け入れられた最大の番号付きの提案であるため、受け入れ1:aた後は状態のままにする必要があります。C(100:b,-)100:b

基本的に、ネットワークは非同期であるため、何も壊さずにすべてのメッセージを遅らせたり並べ替えたりできるため、1:aafterを受け入れることはまったく問題ないことに注意してください。100:b

于 2016-12-13T08:18:28.520 に答える
2

ネクロバンプ。両方のバリアントの弱い部分があっても、矛盾はありません。質問の例のステップ 9 を見てみましょう。

「状態は A(-:-,100) B(100:b,100) C(1:a,-) です。選択された提案は放棄され、Paxos は失敗します」

ただし、この時点では不確定な値しかありません。これは、多数決で受け入れられた値がないためです (b はステップ 6 で多数決で受け入れられたため、最終的には 'b' を選択する必要があります)。

プロトコルを継続するには、新しい投票が必要であり、最終的には新しい投票が受け入れられます。その投票には値「b」が必要です。

証拠: C は、最後に投票 (1, 'a') を受け入れたとしても、受け入れた最高番号の投票が (100, 'b') であるため、準備要求に対して (100, 'b') で応答します。B も (100, 'b') で応答します。したがって、'b' 以外の値で多数決を取得することはもはや不可能です。

ランポートの言葉は、受理者は「もしあれば、受理した n 未満の最大数の提案」で応答するというものです。

受け入れられた回答は、「最も高い番号」と「最後に受け入れられた」を混同しています。ランポートのプロトコルと完全に一致させるためには、C が行った「最新の」受け入れが (1, 'a') であっても、(100, 'b') に応答したことを C が覚えておく必要があります。

(そうは言っても、多くの実装がこれを正しく行わず、この問題に対して脆弱であっても驚かないでしょう。)

于 2016-04-21T03:03:51.080 に答える
2

この論文には確かにあいまいさがあり、アルゴリズムの実装に論文ではなく TLA+ 仕様を使用する必要があるのはそのためです。

値を受け入れるとき、アクセプターはその状態、つまり最後に約束された投票をもう一度更新する必要があります。これはPaxos TLA+ 仕様から明らかです。アクセプターが maxBal を更新するフェーズ 2b を確認し、同じことを行うフェーズ 1b と比較してください。

Leslie Lamport は最近の講演でこの問題を扱い、投票を約束するノードのセットとは異なるアクセプターのセットを許可するために特に行われていると説明しています。

于 2020-04-07T00:22:00.600 に答える