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

作者: , 共 1264 字

这个问题在 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.

类似文章:
理论计算机 (I) 课上讲的一个问题,很有意思。
Game Theory 即博弈论,目前在经济学中运用得最多 ( 纳什更因为他在这上面的工作拿到了诺贝尔经济学奖 )。但在最近几年,理论计算机界对它的研究也很热。
递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的 overhang 堆积木 - 能伸出桌面多远? 。今天这次课,来自 Aarhus 的 Peter Bro Miltersen 讲了一个很有趣的游戏问题。
在大家玩牌的时候,每一局之前都需要重新洗牌 —— 一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,多数人都不超过 4 次。
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作,不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》,在媒体上又掀起了一轮宣传狂潮,但是有些报道极端弱智,错误百出,所以我趁机纠正一下,并介绍密码学的一个组成部分 ——hash 函数,以及王小云老师在这上面的工作。