ビザンチン将軍問題

ビザンチン将軍問題（ビザンチンしょうぐんもんだい、英語: Byzantine Generals Problem）とは、相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題である[1]。フォールトトレラントシステムでの多数決の妥当性や分散コンピューティングの処理の妥当性に関わる問題と言え、二人の将軍問題を一般化したものと言える。

ビザンチン将軍問題に帰結される故障や障害をビザンチン故障（Byzantine Failure、あるいはビザンチン障害）と呼ぶ。また、ビザンチン将軍問題が発生しても全体として正しく動作するシステムをビザンチン・フォールトトレラント性（Byzantine Fault Tolerance）があるという。

問題

ビザンチン将軍問題は、東ローマ帝国（ビザンティン帝国、ビザンチン帝国）の将軍たちがそれぞれ軍団を率いて、ひとつの都市を包囲している状況で発生する。将軍たちは、都市攻撃計画について合意したいと考えている。最も単純な形では、将軍たちは、攻撃するか撤退するかだけを合意決定する。一部の将軍たちは攻撃したいと言うだろうし、他は撤退を望むかもしれない。重要な点は、将軍たちはひとつの結論で合意しなければならないということである。つまり、一部の将軍だけで攻撃を仕掛けても敗北することは明らかで、全員一致で攻撃か撤退かを決めなければならないのである。また、将軍たちは、それぞれ離れた場所に各軍団を配置しており、メッセンジャーを相互に送ることで合意を目指す。

問題を複雑にさせているのは、一部の将軍たちが反逆者であって、時折最適でない戦略に票を投じたりして混乱させることである。例えば、9人の将軍が投票するとして、その内の4人が攻撃に投票し、別の4人は撤退に投票した場合、9人目の（反逆者でもある）将軍は、撤退に投票した将軍たちには撤退票を送り、攻撃に投票した将軍たちには攻撃票を送ることができる。すると、この9人目の将軍から撤退票を受けた将軍たちは(撤退が過半数であると判断して)撤退するだろうし、残りの将軍たちは(攻撃が過半数であると判断して)攻撃を開始するだろう（しかし攻撃はうまくいかないだろう）。更に問題を複雑にするのは、将軍たちは物理的に離れた場所にいるため、使者に投票の信書を運ばせねばならないが、票を届けるのに失敗する場合もあるし、偽の票に改竄される可能性もあることである。

誠実な将軍たち（反逆者でない将軍たち）が全員一致で攻撃（あるいは撤退）に同意している場合、ビザンチン・フォールトトレラント性は達成可能である。ある将軍が正しい判断をする場合、他の誠実な将軍たちは必ずその判断に合意する。さもなくば、合意された戦略を選択することは、見当違いの方法ということになる。

この問題を合意問題として定式化したのは、マーシャル・ピーズ、ロバート・ショスタク、レスリー・ランポートの1980年の論文である[2]。

ビザンチン故障

ビザンチン故障とは、分散コンピューティングにおいて、アルゴリズムを実行中に発生する故障・障害である。不作為障害 (omission failures) と作為障害 (commission failures) が含まれる。不作為障害とは、クラッシュ、要求を受信しそこなうこと、応答を返しそこなうことなどを指す。一方、作為障害とは、要求を不正に処理すること、局所状態が壊れること、要求に対して不正または一貫しない応答を返すことなどを指す。ビザンチン故障が発生すると、ビザンチン・フォールトトレラント性を備えていないシステムは、予期しない動作をすることがある。

例えば、あるサブルーチンの出力が別のサブルーチンの入力になっているとき、第一のサブルーチンで生じた小さな丸め誤差が、第二のサブルーチンで大きな誤差を生じることがある。さらに、その結果を第三のサブルーチンに入力すると、その誤差はさらに大きくなることがあり、無意味な値を生成することもある。別の例として、ソースコードのコンパイルがある。コンパイラは、小さな構文上の誤りから、多くの誤りが生じることがある。こうなると、コンパイラの構文解析器は、ソースプログラムの字句情報や構文情報を見失ってしまう。そのような障害や故障が主要なインターネットサービスを停止させたこともある。例えば、2008年に、Amazon S3 が1ビットのハードウェアの障害がシステム全体に伝播したことで数時間ダウンしたことがある[3]。

ビザンチン・フォールトトレラント性 (BFT) のあるアルゴリズムでは、そのアルゴリズムの実行経路を表す論理的抽象概念としてのプロセスがビザンチン故障に対処する。故障していないプロセスは、正当である。

ビザンチン故障を前提とした実世界の環境モデルでは、ハードウェアの故障やネットワーク輻輳・切断やソフトウェアのバグや悪意ある攻撃によって、コンピュータやネットワークが予期しない動作をする。ビザンチン・フォールトトレラント性アルゴリズムは、そのような故障や障害に対処し、仕様で解決するよう指定された問題を解決できなければならない。そのようなアルゴリズムは、一般に「ビザンチン故障の状態にあるプロセスを何個まで許容し対処できるか」によって特徴付けられる。これを回復力（resilience） t で表す。

ビザンチン将軍問題も含めた古典的な合意問題の多くは、システムのプロセス数を n としたとき、n > 3t を満たさない場合の解が存在しない。言い換えれば、全プロセスの3分の1未満が障害という状況でないと、正しい動作を保証できない。

初期の解決策

ビザンチン・フォールトトレラント性の目的は、ビザンチン故障に対して防御できることである。最初の解決策は 1982年、ランポートらの論文で示された[1]。彼らはビザンチン将軍問題を「司令官と副官」問題に帰結することができると指摘することから始めた。「司令官と副官」問題とは、誠実な副官は司令官が誠実である場合にその命令を忠実に守らなければならないというものである。おおまかに言えば、将軍達の投票では、その票を司令官の命令と考えることができる。

  • メッセージに嘘があったとしても、反逆的な将軍が全将軍の人数の3分の1未満であれば「ビザンチン・フォールトトレラント性」は達成される。一人の司令官と二人の副官を想定したとき、司令官が反逆者ならば「司令官と副官」問題を解決できないことを証明することで、3分の1以上の反逆者がいる場合の解決策がないことを証明したのである。A、B、C の三人がいて、A が反逆者だったとする。A が B には攻撃すると言い、C には撤退すると言い、B と C が相互にやりとりして A からどう指示されたかを教えあった場合、B も C も誰が反逆者であるかを判断できない（例えば、B か C が反逆者だった場合でも指示が食い違う）。将軍の人数を n、反逆者の人数を t としたとき、解決策が存在するのは n が (3 × t + 1) 以上の場合のみである[4]。
  • 2番目の解決策は、偽造不可能なサイン(現代のコンピュータシステムでは、これは公開鍵暗号で達成されるだろう)を必要とするが、任意の数の反逆的な将軍がいても「ビザンチン・フォールトトレラント性」を維持可能である。
  • また、すべての将軍が直接互いと通信できるわけではないいくつかの状況におけるバリエーションも提示されている。

実用的なビザンチン・フォールトトレラント性

ビザンチン・フォールトトレラント性のあるレプリケーションプロトコルは、かつてはコストがかかりすぎて実用的でないとされていた[要出典]。1999年、ミゲル・カストロとバーバラ・リスコフは、"Practical Byzantine Fault Tolerance" (PBFT) アルゴリズム（実用的ビザンチン・フォールトトレラント・アルゴリズム）を提唱した[5]。これは、ミリ秒以下のレイテンシを加えただけで毎秒数千の要求を処理できる高性能なビザンチン状態機械のレプリケーションを提供する。

PBFTの登場でBFTレプリケーションの研究が活発化し、Q/U[6]、HQ[7]、Zyzzyva[8]、ABsTRACTs[9]といった低コストで性能を向上させるプロトコルや、Aardvark[10]のように堅牢性を向上させるプロトコルが登場した。

UpRight[11] は、そういった研究成果を取り入れて開発されたオープンソースのサービス構築用ライブラリである。"up" は故障や障害が発生しても動き続けること、"right" は正しい動作を続けることを意味する。

BFT の応用例としてビットコインがある。Peer to Peer の電子マネーシステムであり、一連のHashcash風のproof-of-workを並列的に生成する。この一連の proof-of-work はビザンチン将軍問題を解く鍵である[12][13]。

脚注

  1. ^ a b Lamport, L.; Shostak, R.; Pease, M. (July 1982). “The Byzantine Generals Problem”. ACM Transactions on Programming Languages and Systems 4 (3): 382–401. doi:10.1145/357172.357176. http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf. 
  2. ^ Pease, M.; Shostak, R.; Lamport, L. (April 1980). “Reaching Agreement in the Presence of Faults”. Journal of the ACM 27 (2): 228–234. doi:10.1145/322186.322188. 
  3. ^ Amazon S3 Availability Event: July 20, 2008
  4. ^ P. Feldman and S. Micali. An optimal probabilistic protocol for synchronous Byzantine agreement. SIAM J. Computing, 26(4):873{933, 1997.
  5. ^ M. Castro and B. Liskov, Practical Byzantine Fault Tolerance and Proactive Recovery, ACM Transactions on Computer Systems, v. 20 n. 4, pp. 398-461, 2002.
  6. ^ M. Abd-El-Malek, G. Ganger, G. Goodson, M. Reiter, J. Wylie, Fault-scalable Byzantine Fault-Tolerant Services, Association for Computing Machinery Symposium on Operating Systems Principles, 2005.
  7. ^ J. Cowling, Danial Myers, Barbara Liskov, Rodrigo Rodrigues, Liuba Shrira, HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, 2006.
  8. ^ R. Kotla, L. Alvisi, M. Dahlin, A. Clement, E. Wong, Zyzzyva: Speculative Byzantine Fault Tolerance, ACM Transactions on Computer Systems, v. 27 n. 4, December 2009
  9. ^ R, Guerraoui, N. Knežević, M. Vukolić, V. Quéma, The Next 700 BFT Protocols, Proceedings of the 5th European conference on Computer systems (EuroSys), 2010.
  10. ^ A. Clement, E. Wong, L. Alvisi, M. Dahlin, M. Marchetti, Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults, USENIX Symposium on Networked Systems Design and Implementation, April 22–24, 2009.
  11. ^ UpRight. Google Code repository for the UpRight replication library.
  12. ^ “What Is Bitcoin?”. 2011年7月3日閲覧。
  13. ^ 野口悠紀雄“『「ビットコイン」を正しく理解する』（ダイヤモンドオンライン、2014年2月20日）【第1回】第4章 社会はいかにして構築しうるか？:「ビザンチン将軍問題」に解を与えた”. 2014年2月20日閲覧。

参考文献

関連項目

外部リンク