この文書はコンピューター工学知識なしでも理解できます。
Byzantine Generals Problem
1982年論文で初めに言及している、コンピューター工学の有名な問題です。
- 色々のGeneralが各自の軍団を指揮しています。
- Generalは他のGeneralに伝令を送って、communicationを取ります。
- Generalは敵を観測して、攻撃や後退の中一つを選びます。
- 誠実なGeneralは伝令の話が正しいならば、動きます。けれど、反逆Generalは伝令の話を従うことも従っていないこともできます。
上記の条件を守ながら、誠実なGeneralは一つの同じ戦略を選び、少数の反逆Generalはこの決定に影響力を持っていないことが問題になります。
論文はGeneralたちの中、誠実なGeneralが2/3を超過(more than)すると、条件を達成する方法があると説明します。 つまり、反逆GeneralがN人あるならば、同じ決定の為、３N＋1人のGeneralが必要になる意味にもなります。
例）
- Generalが３人だと、その中一人が反逆Generalにすると、残り２Generalを混乱させるのができます。
- Generalが４人あれば、その中１人が反逆Generalでも、残り３Generalは同じ決定を選ぶことができます。
２人の誠実なGeneral、１人の反逆General
A、B、C、3人のGeneralが有ります。Aが戦略を決めてBとCに伝令を送ります。 Aの伝令を貰ったBとCは伝えている話をお互い交換します。
最終的にBとCは２通messageを貰っています。
- Aから直接的message.
- Aが反逆Generalならば、AはBとCに違うmessageを送るのができます。
- BやCから間接的message.
- BやCが反逆Generalならば,Aのmessageと違うmessageを相手に送るのができます。
このシナリオではmessageが２つしかない為、どの方が史実なのか判断ができません。
３人の誠実なGeneral、１人の反逆General
今回には、４人 A B C Dを同じ方法で, B C Dは自身以外の残り３人のGeneralから伝令をもらいます。
- Aが反逆Generalならば、選択肢は攻撃や後退しかないので、B C Dの中２人に同じ命令を下達する必要が有ります。
- B C Dは貰った命令を誠実に他のGeneralに伝ます。
- B C Dの中に反逆General１人あるならば、Aは同じ命令を下達して、反逆General以外の２人はAの命令を他のGeneralに伝ます。
自身以外の３人のGeneral中反逆Generalが１人あったとしても,多数決によって、誠実なGeneralは攻撃や後退、同じ戦略で動くのができます。
Blockchain Network
Byzantine Generals Problemを改めて見ると、
- 独立的コンピューター
- 他のコンピュータにアクセスはネットだけ
- コンピュータは特定な目的の為、協力
- その中にはイレギュラーコンピュターが紛れ込んでいる
P2P Networkを使っているBlockchainが成立する為、必然的にByzantine Generals Problemを解決する方法が要求されます。 ネットワークを構成する少数が邪魔になって参加者が影響を受けたら、誰もBlockchain Networkを信頼しないでしょう。
このように、システム構成の一部に問題(反逆者や不安定)を許容するシステムをByzantine Fault Tolerance (BFT)と呼びます。
Reference
- この文書は韓国語文書から翻訳されています。韓国語文書が原文になります。
- Lamport, L.; Shostak, R.; Pease, M. (1982), "Byzantine Generals Problem", ACM Transactions on Programming Languages and Systems.