这个问题在 Yao 的理论计算机课上整整讨论了 2 节课。它是一个算法设计问题，也极具趣味性。下面是它的一些介绍和解决方案([1])。
拜占庭帝国就是 5～15 世纪的东罗马帝国，拜占庭即现在土耳其的伊斯坦布尔。我们可以想象，拜占庭军队有许多分支，驻扎在敌人城外，每一分支由各自的将军指挥。将军们只能靠通讯员进行通讯。在观察了敌人以后，忠诚的将军们必须制订一个统一的行动计划——进攻或者撤退。然而，这些将军中有叛徒，他们不希望忠诚的将军们能达成一致，因而影响统一行动计划的制订与传播。问题是：将军们必须有一个协议，使所有忠诚的将军们能够达成一致，而且少数几个叛徒不能使忠诚的将军们做出错误的计划——使有些将军进攻而另一些将军撤退了。
抽象出来，可以表述成：
拜占庭将军问题：设计一个协议，一个司令要送一个命令给他的 n-1 个副官，使得
IC1. 所有忠诚的副官遵守同一个命令。
IC2. 假如司令是忠诚的，则每一个忠诚的副官遵守他送出的该命令。约定：忠诚的将军将遵守协议，而叛徒则可能破坏协议，尽可能的干绕其它人的判断。叛徒是匿名的。而且最后不需要确定谁是叛徒。
注意司令也有可能是叛徒，所以 IC2 与 IC1 是不同的。
递归设计协议 OM(n, m)为
OM(n, 0):
- 司令发送命令给所有副官。
- 副官按照接收到的命令行事。
OM(n, m):
- 司令发送命令给所有副官，设副官 i 收到命令 vi。
- 分为独立的 n-1 轮：对每个副官 i ，将其视为司令，使用协议 A(n-1, m-1)将 vi 发送到所有其它副官。
- 这样每个副官都收到 n-1 条信息，每个副官都按照出现次数更多的命令行事（如果进攻和撤退的命令一样多，则默认取撤退）。
递归证明
引理：当 n>2m+k ， n 个将军中至多 k 个叛徒，协议 A(n, m)满足 IC2 ，即司令是忠诚的，每个忠诚的副官将会执行司令的命令。
进而说明：
当 n>3m 时， n 个将军，且至多 m 个叛徒，协议 A(n, m)可以同时满足 IC1 和 IC2。
更深刻的结论：
当 n<=3m 时， n 个将军中的 m 个叛徒可以让将军们无法达成一致，也就是满足 IC1 和 IC2 的协议不可能存在。
参考：
- The Byzantine Generals Problem, the first paper involved
- 可信计算 VII:拜占庭将军问题
- Byzantine failure - Wikipedia, the free encyclopedia
PS: 标题里 TCS 是Theoretical Computer Science(理论计算机科学)的缩写，这篇文章同属于理论计算机介绍系列文章，算作理论计算机初步系列文章的补充吧。
Q. E. D.
