ビザンチン将軍問題
ビザンチン将軍問題は、東ローマ帝国(ビザンティン帝国、ビザンチン帝国)の将軍たちがそれぞれ軍団を率いて、ひとつの都市を包囲している状況で発生する。将軍たちは、都市攻撃計画について合意したいと考えている。最も単純な形では、将軍たちは、攻撃するか撤退するかだけを合意決定する。一部の将軍たちは攻撃したいと言うだろうし、他は撤退を望むかもしれない。重要な点は、将軍たちはひとつの結論で合意しなければならないということである。つまり、一部の将軍だけで攻撃を仕掛けても敗北することは明らかで、全員一致で攻撃か撤退かを決めなければならないのである。また、将軍たちは、それぞれ離れた場所に各軍団を配置しており、メッセンジャーを相互に送ることで合意を目指す。
問題を複雑にさせているのは、一部の将軍たちが反逆者であって、時折最適でない戦略に票を投じたりして混乱させることである。例えば、9人の将軍が投票するとして、その内の4人が攻撃に投票し、別の4人は撤退に投票した場合、9人目の(反逆者でもある)将軍は、撤退に投票した将軍たちには撤退票を送り、攻撃に投票した将軍たちには攻撃票を送ることができる。