TCS: 拜占庭将军问题 (The Byzantine Generals Problem)

作者:, 发表于

理论计算机笔记

查看该系列所有文章

这个问题在Yao的理论计算机课上整整讨论了2节课。它是一个算法设计问题,也极具趣味性。下面是它的一些介绍和解决方案([1])。

拜占庭帝国就是5~15世纪的东罗马帝国,拜占庭即现在土耳其的伊斯坦布尔。我们可以想象,拜占庭军队有许多分支,驻扎在敌人城外,每一分支由各自的将军指挥。将军们只能靠通讯员进行通讯。在观察了敌人以后,忠诚的将军们必须制订一个统一的行动计划——进攻或者撤退。然而,这些将军中有叛徒,他们不希望忠诚的将军们能达成一致,因而影响统一行动计划的制订与传播。问题是:将军们必须有一个协议,使所有忠诚的将军们能够达成一致,而且少数几个叛徒不能使忠诚的将军们做出错误的计划——使有些将军进攻而另一些将军撤退了。

抽象出来,可以表述成:

拜占庭将军问题:设计一个协议,一个司令要送一个命令给他的n-1个副官,使得
IC1. 所有忠诚的副官遵守同一个命令。
IC2. 假如司令是忠诚的,则每一个忠诚的副官遵守他送出的该命令。

约定:忠诚的将军将遵守协议,而叛徒则可能破坏协议,尽可能的干绕其它人的判断。叛徒是匿名的。而且最后不需要确定谁是叛徒。

注意司令也有可能是叛徒,所以IC2与IC1是不同的。

递归设计协议OM(n, m)为

OM(n, 0):

  1. 司令发送命令给所有副官。
  2. 副官按照接收到的命令行事。

OM(n, m):

  1. 司令发送命令给所有副官,设副官i收到命令vi。
  2. 分为独立的n-1轮:对每个副官i,将其视为司令,使用协议A(n-1, m-1)将vi发送到所有其它副官。
  3. 这样每个副官都收到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的协议不可能存在。

参考:

  1. The Byzantine Generals Problem, the first paper involved
  2. 可信计算VII:拜占庭将军问题
  3. Byzantine failure - Wikipedia, the free encyclopedia

PS: 标题里TCS是Theoretical Computer Science(理论计算机科学)的缩写,这篇文章同属于理论计算机介绍系列文章,算作理论计算机初步系列文章的补充吧。

Q.E.D.


上一篇:理论计算机初步:从hash函数到王小云的MD5破解2006年9月18日
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在hash函数破解上做出重大贡献的王小云教授的工作,不过前两天王小云获得求是

下一篇:"完美"的洗牌次数 - 7次2006年12月15日
在大家玩牌的时候,每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。