問題タブ [paxos]

誰でも、「完全非同期契約プロトコル」のステップ 3 (以下を参照) を明確にしてください。

プロセス P: 初期値 xp。

• ステップ 0 : 設定しr := 1ます。
• ステップ 1(1, r, xp) :すべてのプロセスにメッセージを送信します。
• ステップ 2N - t :タイプのメッセージが受信されるまで待ちます(1, r, x)。複数のN/2メッセージが同じ値を持つ場合v、そのメッセージ(2, r, v, D)をすべてのプロセスに送信します。それ以外の場合は、メッセージ(2, r, ?)をすべてのプロセスに送信します。
• ステップ 3N - t :タイプのメッセージが(2, r)到着する まで待ちます。
  • (a) D メッセージが 1 つある場合は(2, r, v, D)、 を設定しxp := vます。
  • t(b) D メッセージより多い場合は、決定しvます。
  • (c) Else セットxp = 1または0確率 1/2 のそれぞれ。
• ステップ 4 : 設定r := r + 1してステップ 1 に進みます。

私はこのプロトコルを次のように理解しています。

最初のステップで、各ノードは他のすべてのノードにその状態を通知します。

2 番目のステップで、各ノードは、値を決定するのに十分な情報を「見た」かどうかを判断します。つまり、過半数を待ちます。多数派が同じ値を持っている場合、「多数派が考えているのを見た」のように、この情報をブロードキャストし始めますv。それ以外の場合は、決心しなかったというメッセージを送信します。

最後に、3 番目のステップで、複数のt「決定的な」メッセージがあるかどうかを確認します (tノードのメッセージが配信されない場合に備えて、少なくとも 1 つの「決定的な」メッセージがあります)。しかし、 D メッセージを1 つxp := vだけ受信した場合にのみ設定する理由がわかりません。2 つの D メッセージを受信すると 3c に分類されます。この場合、v にランダムな値を割り当てます。なぜですか?

3 番目のステップを次のように説明できないのはなぜですか。

• (a) D メッセージがゼロの場合、1/2 の確率で設定xp = 1または0それぞれ。
• t(b) D メッセージより多い場合は、決定しvます。
• (c) Else セットxp := v.