2015年5月18日月曜日

Paxos の解説の解説(その 4)

前回 proposer の振る舞いは説明したので、次は acceptor の説明。

"prepare" request と "accept" request のどちらについても、acceptor は自由に無視できる。無視してもアルゴリズムが誤動作することはない。
"prepare" request を無視すると、proposer は(前回説明した)集合 S を作れなくなり、その提案は破棄される。つまり、合意を取るのが遅れることになるが、誤った値が選択されることはない。
"accept" request を何人かの acceptor が無視し、半数未満の acceptor だけが受理したとする。すると、「値 v がいくつかの acceptor によって受理されるが、全体としては選択していない(合意していない)」という状況が生まれる。これは問題だろうか?
当然ながらこの提案は「選択」されない。ではどういう影響があるかというと、この提案が現時点で最大の proposal number を持つので、次の "prepare" request のときに、値 v が proposer に返される。そして、ペアとなる "accept" request で過半数の acceptor が v を受理することになる。もしかしたら、いくつかの acceptor が "accept" request をまた無視するかもしれないが、何ラウンドか繰り返すことで、いつかは過半数を達成するだろう。なので、これは問題なさそうだ。

(これは私の理解であって、解説には書いてないが)結局 Paxos プロトコルは proposer が acceptor を「説得」していく手続きだと思う。proposer の競合やネットワーク障害によって、1 ラウンドの "prepare"/"accept" request では合意に達しないことがある。そのときは、次の "prepare" request が「最も最近発行された(が合意に達しなかった)値を再提案し、より多くの acceptor に受理させる。」そうすれば、いずれ過半数の acceptor が受理し、合意に達するだろう、というのがポイントだ。
もちろんこのプロトコルが停止することは保証されてなくて、それは解説でも触れられている。2 つの proposer が "prepare"/"accept" を順番に発行すると、いつまでも合意に達しない。(「停止性」を保証した改良版 Paxos もあるらしい)

話を元に戻すと、acceptor はリクエストを自由に無視できる。逆に無視しなくてはいけないリクエストがある。proposal number N の "prepare" に応答したらそれ以降は、proposal number が N より小さいリクエストは「無視しなくてはいけない」。それ以外の場合は受理して良い。
直感的には、"prepare" request とは、proposal number N 未満の世界において過半数の acceptor の集合を確認する操作なので、これを応答した後に、N より小さいリクエストによって状態を変えてはいけない、ということになる。

これを acceptor への条件として要請する。
P1a. acceptor は、proposal number N より大きい "prepare" request を受け付けてないとき、そのときのみ、 proposal number N のリクエストを受理する。
これは「P1. acceptor は最初に受け取った提案を必ず受理する」より厳しい条件である。

この条件によって、acceptor が proposal number N の "prepare" request にすでに応答している場合は、N 未満の "prepare" request は無視して良い、という最適化が可能になる。というのは、仮に "prepare" request M (M < N) に応答したとしても、ペアとなる "accept" request は無視しなくてはならないからだ。(なので、"prepare" request に応答する意味がない)


以上で、最初のエントリの最後に書いたプロトコルで、正しく合意が取れることがわかった。

0 件のコメント:

コメントを投稿