ビザンチン将軍問題

Leslie Lamportらが考案した分散システム上の信頼性に関わる問題

ビザンチン帝国の将軍たちがそれぞれ部隊を率いて敵を包囲している

各部隊はそれぞれ離れた場所にいて、伝令を相互に送ることでしか連絡できない

戦局は、将軍たちがいっせいに指令を出して攻撃を仕掛ければ勝てるが、一部の部隊だけで攻撃を仕掛けると負けてしまうという状態

つまり、攻撃か撤退かのどちらかを、全将軍が一致して同意しなければならない

しかし、将軍たちの中には裏切り者、つまり敵に寝返っている将軍がいるかもしれない

裏切り者の将軍は、他の将軍から攻撃の提案を受けると、撤退の提案にすり替えて別の将軍に伝達するかもしれない

そうなると、一部の将軍は攻撃指令と撤退指令の両方を受け取ることも想定され、最悪、一部の部隊だけが攻撃を開始してしまい、負ける可能性も

https://scrapbox.io/files/6929283e7bc8bead8efb69c8.png

図2-A

攻撃（または撤退）を提案した将軍は、他の将軍たちにその提案を送る

その提案を受け取った将軍は別の将軍に転送するが、将軍2が裏切り者の場合は、攻撃を撤退（または撤退を攻撃）に替えて将軍3に送る

このとき将軍3は最初の提案が攻撃だったのか撤退だったのかわからない

なお、図2-B のように、攻撃（または撤退）を提案した将軍が裏切り者である場合も想定される

この場合は他の将軍たちに、攻撃または撤退を替えて送ることもある

ビザンチン将軍問題とは、（裏切り者ではない）誠実な将軍たちが全員一致で攻撃または撤退に同意できる場合、つまり正しい判断に対して、将軍たちの判断を全員一致へと導く方法を考えること

裏切り者の将軍がN 人のとき、誠実な将軍が2N ＋1人以上であれば、誠実な将軍どうしの判断が一致できることがわかっている

将軍4人のうち1人が裏切り者である場合（N ＝1）が図3

耐故障性のある分散システムに対する難問

ビザンチン将軍問題は、耐故障性のある分散システムにおける同意問題として考えられる

ここで言う分散システムは複数のコンピュータが協調することで、1台のコンピュータではできないような処理を実現するもの

同意したい値を通信で他のコンピュータへ送りたくとも、コンピュータは壊れることがあるし、複数のコンピュータがあればそれだけ壊れるコンピュータも増える

さらに、故障しても、そのまま止まれば対処のしようがあるが、動き続け、しかも間違った通信や処理を始めることもあり得る

ビザンチン将軍問題で言えば、故障しても止まらずに、間違った動作を行うコンピュータを裏切りの者の将軍に見立て、他の正常なコンピュータを誠実な将軍に見立てることで、複数の正常コンピュータが同じ値を持つ方法やその条件を扱った

ビザンチン将軍問題とビットコインとの関係

10分単位の取引記録を作るには膨大な計算を必要とするようにし、最も早くブロックチェーンを計算した者にビットコインを渡すことで記録作成のインセンティブを与える

見方を変えると、ビットコインにおけるブロックチェーンのメカニズムは、ビザンチン将軍問題における不誠実な将軍への対応策としてみることができる