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