ビザンチン将軍問題
すると、この9人目の将軍から撤退票を受けた将軍たちは(撤退が過半数であると判断して)撤退するだろうし、残りの将軍たちは(攻撃が過半数であると判断して)攻撃を開始するだろう(しかし攻撃はうまくいかないだろう)。更に問題を複雑にするのは、将軍たちは物理的に離れた場所にいるため、使者に投票の信書を運ばせねばならないが、票を届けるのに失敗する場合もあるし、偽の票に改竄される可能性もあることである。
誠実な将軍たち(反逆者でない将軍たち)が全員一致で攻撃(あるいは撤退)に同意している場合、ビザンチン・フォールトトレラント性は達成可能である。ある将軍が正しい判断をする場合、他の誠実な将軍たちは必ずその判断に合意する。さもなくば、合意された戦略を選択することは、見当違いの方法ということになる。
この問題を合意問題として定式化したのは、マーシャル・ピーズ、ロバート・ショスタク、レスリー・ランポートの1980年の論文である。
例えば、2008年に、Amazon S3 が1ビットのハードウェアの障害がシステム全体に伝播したことで数時間ダウンしたことがある。
ビザンチン・フォールトトレラント性 (BFT) のあるアルゴリズムでは、そのアルゴリズムの実行経路を表す論理的抽象概念としてのプロセスがビザンチン故障に対処する。故障していないプロセスは、正当である。
ビザンチン故障を前提とした実世界の環境モデルでは、ハードウェアの故障やネットワーク輻輳・切断やソフトウェアのバグや悪意ある攻撃によって、コンピュータやネットワークが予期しない動作をする。ビザンチン・フォールトトレラント性アルゴリズムは、そのような故障や障害に対処し、仕様で解決するよう指定された問題を解決できなければならない。そのようなアルゴリズムは、一般に「ビザンチン故障の状態にあるプロセスを何個まで許容し対処できるか」によって特徴付けられる。これを回復力(resilience) t で表す。
ビザンチン将軍問題も含めた古典的な合意問題の多くは、システムのプロセス数を n としたとき、n > 3t を満たさない場合の解が存在しない。言い換えれば、全プロセスの3分の1未満が障害という状況でないと、正しい動作を保証できない。