2015年5月17日日曜日

Paxos の解説の解説(その 3)

前回のエントリで、このプロトコルは、
P1. acceptor は最初に受け取った提案を必ず受理する
P2b. 提案 [m, v] が選択されたとする。ある proposer が n > m となる提案 [n, u] を発行するならば n = v である。
という 2 つの条件を満たせば良いことがわかった。

P2b を満たすには、proposer は、すでに選択されている値 v を、新しい提案を発行する前に知らなくてはならない。どうすれば v を知ることができるのか? その前に、ある提案があったときに、P2b を満たしているかどうか証明する方法を考える。

まず簡単のために、P2b の仮定を拡張し「提案 m, m+1, m+2, ..., n-1 が全て、値 v を持つ」とする。つまり、
P2b'. 提案 [m, v], [m+1, v], [m+2, v], ..., [n-1, v] が選択されたとする。提案 [n, u] が発行されるならば、u = v である。
また、一般に提案が選択されるには、過半数の acceptor から成る集合 C が存在し、C の要素である acceptor は全てその提案を受理しなくてはならない。これと P2b -> P2b' の拡張とを組み合わせると、P2b' の前提部分は次のように書き換えられる。
提案 [m, v], [m+1, v], [m+2, v], ..., [n-1, v] が選択されたならば、過半数の acceptor からなる集合 C が存在し、C の要素である acceptor は、提案 m, m+1, m+2, ..., n-1 を受理する。また m, m+1, m+2, ..., n-1 は値 v を持つ。
ここから、P2b を満たすには P2c を満たせば良い、と書き換えられる。
P2c. 提案 [n, v] を発行するときには、以下の条件を満たす、過半数の acceptor から成る集合 S が存在する。
  • S のどの要素も proposal number が n 未満の提案を受理していない、または
  • S の各要素が今までに受理した n 未満の提案のうち、proposal number が最大の提案は値 v を持つ。
ここは理解が難しいので、逆向きにも考えてみる。つまり、P2c が満たされたら、P2b がなぜ満たされるのかを考えてみる。

まず、「S の各要素が今までに・・・最大の提案は値 v を持つ」ような S が存在せず、「S のどの要素も proposal number が n 未満の提案を受理していない」ような S しか存在しないとする。ということは、n 未満の提案は、発行されていないか、されたとしても半数未満の acceptor にしか受理されていないことになる。したがって、まだ何も選択されていないことになる。この場合は P2b の前提「提案 [m, v] が選択されたとする」が成立しないので、P2b 全体は成立する。

つぎに「S の各要素が今までに受理した n 未満の提案のうち、proposal number が最大の提案は値 v を持つ」ような S が存在したと仮定する。この「proposal number の最大値」を Mn とする。帰納法の仮定により、提案 Mn が少なくとも 1 つの acceptor に受理されたことから、Mn は選択されたことがわかる。

  • Mn == m の場合、提案 [Mn, v] (つまり [m, v])を過半数の acceptor が受理していたことになるので、P2b が成立する。
  • Mn < m の場合、提案 m は選択されなかったので、上と同様の議論で、P2b は成立する。
  • Mn > m の場合、再帰的に P2c を適用することで、P2b が成立することがわかる。

これで、P2c を満たせば、P2b が満たされることはわかった。(この部分を正しく理解できているか怪しい)

したがって、P2c を満たせるようなプロトコルを考えればよい。これが、最初に説明した "prepare" request と "accept" request の 2 種類のリクエストとなる。
"prepare" request は、acceptor に対して「すでに提案を受理したか」「受理したとしたら受理した値は何か」を確認し、P2c における集合 S を確定するためのリクエストだ。注意が必要なのは、非同期なネットワーク通信を仮定しているので、proposal number n を処理した後に、n より小さい提案が届く場合があるということだ。そのため、"prepare" request は「今後 n 以下の request は受理しないように」と要請する必要がある。

これで、proposer のあるべき振る舞いはわかった。あとは acceptor の挙動と、ちょっとした optimization について論じている。それはまた次に。

0 件のコメント:

コメントを投稿