2015年5月16日土曜日

Paxos の解説の解説(その 2)

前回の続きで、Paxos プロトコルの正しさについて、この解説をもとに解説する。

まず、acceptor が一人しかいない世界を考える。この世界では簡単に合意が取れる(その acceptor が選択した値がただ一つの「合意した」値となる)が、この acceptor が single point of failure となるので良くない。したがって acceptor が複数動いている状況を考える。この状況では、以下の 2 つのルールを守れば、「選択される値は 1 つだけである」という要請を満たせる。(が、以下に書くように、このルールでは結局うまくいかない)

  • acceptor はたかだか 1 つの値しか受理しない
  • 過半数の acceptor が値 x を受理した時に値 x が選択される
この状況において、2 種類以上の値が選択されることはない。

つぎに、proposer が一人しかいない状況で、この proposer が値 x を提案したとする。ネットワーク障害やプロセスダウンなどがない完璧な世界では、x は選択されなくてはならない。そうでないと、いかなる提案も無視されることになり、合意は全く成立しない。したがって、このプロトコルは、
P1. acceptor は最初に受け取った提案を必ず受理する
という条件を満たす必要が有る。
が、しかしこれだけでは十分ではない。2k 個の acceptor が存在する状況で、2 種類の値が同時に提案され、それぞれ k 個の acceptor が受理すると、どちらも過半数に達しないので、どの値も選択されない。

「acceptor は最初に受け取った提案を必ず受理する」という条件と、「過半数の acceptor が値 x を受理した時に値 x が選択される」という条件とを満たした上で、なんらかの値が選択されるために、「acceptor はたかだか 1 つの値しか受理しない」というルールを破棄し、「acceptor は一つ以上の値を受理できる」こととする。
つまり、「acceptor は最初に受け取った提案を必ず受理する」と「acceptor はたかだか 1 つの値しか受理しない」とを同時に要請すると、「最初に受け取った提案を受理し、その後は何もしない」という意味になり、上記の「2k 個の・・・」の例で行き詰まってしまう。

ここまでの議論で、1 つの proposer は複数の提案をする(可能性がある)ことになった。そこで、複数の提案を区別するために、proposal number を導入する。proposal number は自然数とする。また同じ propose による異なる提案は、 異なる proposal number を持つものとする。
つまり、「提案 (proposal)」とは「提案される値 v」と「proposal number n」とのペアとなる。これを [n, v] 書くことにする。「提案」と「提案される値」とを分けて考えることに注意する。acceptor は複数の「提案」を受理することができるが、受理された複数の「提案」は、同じ「提案される値」を含まなくてはならない。したがって、
P2. 提案 [n, v] が選択されたとする。m > n となる提案 [m, u] が選択されたら、u = v でなくてはならない。
という条件が要請される。この条件によって「選択される値は一つである」という要求を満たすことができる。

値が「選択」されるには少なくとも一つの acceptor に「受理」されなくてはならないので、以下の P2a を満たせば P2 を満たすことができる。(P2a は P2 より厳しい条件である。)
P2a. 提案 [n, v] が選択されたとする。m > n となる提案 [m, u] が任意の acceptor に受理されたら、u = v でなくてはならない。

さて、ここで次の状況を考える。
  • 提案 [n, v] がすでに選択されている(= 過半数の acceptor が受理した)
  • acceptor c は(例えばネットワーク障害により)これまでに全く提案を受理しなかった。したがって も受理していない。
  • 新しい proposer が起動し、[m, u] を提案した (m > n and u != v)
この場合、「P1. acceptor は最初に受け取った提案を必ず受理する」というルールにより、c は [m, u] を受理してしまうが、これは P2a に反する。したがって、P2a では不十分だとわかったので、さらに条件を厳しくする。
P2b. 提案 [n, v] が選択されたとする。m > n となる提案 [m, u] が任意の proposer によって提案されたら、u = v でなくてはならない。

P2b を満たすには、proposer は、提案する前に現在選択されている値 v を知らなくてはならない。(そうでないと u != v となる u を提案してしまい、P2b に反する)
どうすればこれが実現できるのか・・・、は次回に続く。

0 件のコメント:

コメントを投稿