Reading: Impossibility of Distributed Consensu with One Faulty Process

主要な結論は、”No consensus protocol is totally correct in spite of one fault.” という有名なものです。

まず、用語を整理しておくと、

という感じです。

この論文のおおまかな論理構成は、

  1. 故障したプロセスが 1 つ以上存在しても totally correct な consensus protocol を仮定する。
  2. initial configuration は bivalent である。
  3. bivalent な configuration から event を経て到達可能な configuration 群には bivalent な configuration が含まれる。
  4. bivalent な初期状態から、あるプロセスが届いたメッセージを処理し event を得て、その event の適用の結果さらに bivalent な configuration に至り、以下無限に同じことが繰り返されうる。
  5. よって、初期状態から永遠に合意に至らないパスがあるので 1 の仮定に矛盾がある。

という風になっています。注意深く読めば分かると思います。

Comments

comments powered by Disqus