← COMP5567 全部讲次
L07a · 第 7 周

L07a 两将军与拜占庭将军:信道会丢,人会撒谎

先看两将军问题为什么在会丢消息的信道上永远确认不了,再把故障升级成会撒谎的拜占庭故障,最后写清整讲的验收标准 Agreement 与 Validity。

一句话版

两位忠诚的将军隔着会丢信的山谷,发多少条确认都定不下来,这是两将军问题。把信道修好、换成有人会撒谎,就是拜占庭将军问题。这一页讲清这两个问题各难在哪,以及「有叛徒时怎样才算成功」的两个条件。

读之前最好先懂崩溃故障和原子提交,见 L06a。本讲后面几页的下界和算法,全都拿这一页的两个条件来验收。

先认识这几个词

词 全称 / 读法 一句人话
信道 channel 消息走的那条路,可能丢信
崩溃故障 crash fault 节点停了,只会沉默
拜占庭故障 Byzantine fault 出故障的节点可以撒谎,对不同的人说不同的话
指挥官 / 副官 Commander / Lieutenant 一个人下令,其余人执行
叛徒 traitor 出拜占庭故障的那个人,可能是指挥官也可能是副官
Agreement 一致性 所有忠诚副官执行同一条命令
Validity 有效性 指挥官忠诚时,忠诚副官执行他的命令
BFT Byzantine Fault Tolerance,拜占庭容错 有人撒谎时,诚实节点仍能达成一致

一个类比:微信群里传达老板的指令

老板给三个下属私聊发指令:「明天上线」或「明天不上线」。下属之间会在群里互相转述「老板跟我说的是……」。

先设想一种情况:大家都老实,可是网络很差,消息时有时无。你发「收到」,不知道老板看到没有。老板回「好」,他也不知道你看到没有。来回确认多少次,最后发消息的那个人总是心里没底。这是两将军问题。

再设想另一种情况:网络很好,消息一定到,也看得出是谁发的。可是群里有人会撒谎,甚至老板自己就可能两头说不同的话。这是拜占庭将军问题。

两种情况的麻烦来自不同的地方。前一种是路不可靠,后一种是人不可靠。

类比在哪里失效:

  • 本讲假设消息一定送达,群聊里却常有人不回消息。
  • 本讲假设能察觉谁没说话,群聊里你分不清他是没看到还是故意不说。
  • 群里的人可以私下商量,本讲的忠诚副官只能按规定的规则转发和表决。

从零讲起

1. 两将军问题

它解决什么问题

两个人要同时做一件事,单独做就失败。他们只能靠一条会丢消息的路来商量。这个问题问的是:存在一种发消息的办法,能让两人都确定「对方知道我们约好了」吗?答案是没有。

这一条结论把后面的拜占庭问题和信道问题分开。本讲之后的算法,都先假设信道可靠,再去对付撒谎的人。

从哪来(补充)

这个问题最早由 E. A. Akkoyunlu、K. Ekanadham、R. V. Huber 在 1975 年发表。1978 年,Jim Gray 给它起名「两将军悖论」,课件标的就是这一次。

出处:Wikipedia: Two Generals’ Problem

直觉

两支军队驻在山谷两侧,敌军占着谷底。将军 A 和将军 B 都忠诚,谁也不骗谁。他们约好要一起进攻,只派一支军队冲上去会被消灭。

能用的只有信使。信使穿过谷底时可能被抓,信就丢了。

问题出在一个很朴素的事实上:发信的人看不到信有没有送到。每条信都有这个毛病,包括「我收到了」这种确认信。

一步一步看

目标:看每多发一条确认信,「对方收到没有」这份不确定为什么总落在发最后一条信的人身上。

下面三帧按时间往右走。上面一条线是将军 A,下面一条是将军 B,斜线是一条信。青绿色是这一步新发的那条信。

  1. A 派信使送去「黎明进攻」,信送到了。可是 A 自己看不到送达,所以 A 不确定 B 收到没有。

    两将军确认链第 1 步:上方时间线是将军 A,下方是将军 B,A 发出黎明进攻斜线到达 B;底部写着 A 不确定 B 收到没有

  2. B 收到了,回一条「好」,也送到了。这回轮到 B 看不到送达:B 不确定 A 收到确认没有。B 怕 A 没收到、A 不出兵,所以 B 也不敢一个人冲。

    两将军确认链第 2 步:A 的黎明进攻已到达 B,B 回的好斜线到达 A 并标成青绿;底部写着 B 不确定 A 收到确认没有

  3. A 收到「好」,再发一条「很高兴你同意」,这条在半路丢了。现在 A 又陷入同样的处境:B 收到没有?

    两将军确认链第 3 步:前两条信都已送达,A 发出的很高兴你同意在半路断开并打叉;底部写着不确定落回了发最后一条信的人

  4. 再发一条也一样。每多一条确认,只是把「对方收到没有」从一方推给另一方。

把三步摆成一张表,就是课件那张消息表:

步 消息 送到了吗 谁不确定
1 黎明进攻 是 A 不确定 B 是否收到
2 好,黎明进攻 是 B 不确定 A 是否收到确认
3 很高兴你同意 否 A 不确定 B 是否收到确认

怎么判断

想判断「有没有一个办法能保证两人一致」,可以用倒推。

先假设有一个办法,发 k 条信就一定能让两人一致。看最后那第 k 条:它可能会丢。收信的人如果因为它丢了就改主意,这个办法就不保证一致了。所以收信人的决定不能依赖第 k 条,前 k−1 条就够用。

同样的理由再用一次,k−1 条里的最后一条也可以去掉。一路倒推到 0 条信,两个人一句话没说就能保证一致,这显然做不到。所以开头的假设不成立。

判断方法压成一句:只要信道可能丢掉最后一条信,就不存在确定能成功的确认办法。实际系统只能接受「大概率」或「超时就当成功」这类较弱的确认。

常见误解

以为多发几轮确认就能解决

每一轮确认本身也会丢。发一万条,第一万条的发送方照样不知道它到没到。轮数加多只是让失败变得少见,确定性的一致始终达不到。

以为两将军问题里有人在撒谎

两位将军都忠诚,问题全出在信道上。有人撒谎是下面拜占庭将军问题的设定,两个问题难在不同的地方。

试一下

A 和 B 约好:「收到对方的第 2 条确认才出兵」。第 4 条信丢了,谁心里没底?

第 4 条是 B 发给 A 的(第 1、3 条由 A 发,第 2、4 条由 B 发)。B 看不到它送没送到,所以 B 心里没底。换什么规则都一样,最后一条信的发送方总是不确定。

2. 拜占庭故障:会撒谎的节点

它解决什么问题

上一讲的两阶段提交、三阶段提交假设节点只会崩溃:出了事就停下,不再发消息。真实系统里还有更糟的情况,比如程序有 bug、硬件出错,或者节点被人控制了。这种节点会继续发消息,内容却是错的,甚至给不同的人发不同的内容。

拜占庭故障就是把故障模型放到最坏:出故障的节点想怎么做都行。能扛住这种故障的系统,才敢放在互不信任的人之间用,区块链就是这种场合。

从哪来(补充)

这个问题最早出自 SRI 为 NASA 做的 SIFT 项目。1978 年 Robert Shostak 构思并形式化了它,当时叫「interactive consistency」。Pease、Shostak、Lamport 在 1980 年发表了《Reaching Agreement in the Presence of Faults》,这篇论文后来获得 2005 年的 Dijkstra 奖。

1982 年的论文《The Byzantine Generals Problem》用了现在这个名字。Lamport 自己回忆,最早叫它「阿尔巴尼亚将军问题」,后来觉得拜占庭将军更合适才改了名。

出处:Wikipedia: Byzantine fault、Lamport 论文列表

直觉

把同一个坏节点 X 放进两种故障模型里比一比。

崩溃的 X 像断了电的对讲机,你听不到它,但它说过的话都是真的。拜占庭的 X 像一个两面派,对 P 说「进攻」,回头对 Q 说「撤退」。转述别人的话时,它也可以改内容。

两面派比沉默可怕得多。沉默的人能被发现,两面派说的每句话单看都像正常消息。

一步一步看

目标:同样只坏一个节点,对比崩溃和拜占庭两种故障,看难度差在哪里。

  1. 左边是崩溃故障:X 停了,什么都不发。P、Q 只是收不到 X 的消息,它们收到的东西里没有假话。

  2. 右边是拜占庭故障:X 还在发消息,可是对 P 说进攻、对 Q 说撤退。P、Q 各自看到的消息都像真的。

  3. 从图上数,两边坏掉的节点一样多,都是一个。难度的差别全在坏节点能做什么。

    崩溃故障和拜占庭故障对比:左框里 X 被打叉、什么都不发,P、Q 收不到消息;右框里 X 画成虚线圈,青绿箭头对 P 说进攻、对 Q 说撤退

怎么判断

拿到一个故障描述,问一句:坏节点会不会发出「内容不对」的消息?

  • 只会停下、不发了,是崩溃故障。
  • 会发错的内容、给不同人发不同的内容、转述时改内容,是拜占庭故障。
  • 故意不发也算在拜占庭故障里。拜占庭节点的行为包括了崩溃节点能做的一切。

本讲的判断口径和课件一致:拜占庭节点可以任意行为。

常见误解

以为过半数诚实就能对付拜占庭故障

崩溃故障下,过半数常常就够了。拜占庭故障下,坏节点能两头说话,只用口头消息时要超过三分之二的节点诚实,下一页会推出这个门槛。

以为拜占庭节点一定会撒谎

它可以撒谎,也可以老老实实,还可以时而真时而假。协议要在它采取最坏做法时也成立,所以分析时总按最坏的情况算。

试一下

一个节点硬盘坏了,之后每次都回复「余额 0」,而真实余额不是 0。这是哪种故障?

拜占庭故障。它没有停下,还在发消息,只是内容是错的。崩溃故障的节点只会不回复。

3. Agreement 与 Validity:有叛徒时怎样算成功

它解决什么问题

一群将军要商量出一个共同行动,其中可能有叛徒。在动手设计算法之前,得先写清「什么结果算成功」。课件把它写成两个条件,本讲后面每个下界、每个算法,都拿这两条来检验。

直觉

课件先把问题简化:一位指挥官下令,其余的人是副官,负责执行。谁都可能是叛徒,指挥官自己也不例外。

「所有人对一个值达成一致」可以拆成「每个人轮流当一次指挥官,把自己的值可靠地发出去」。所以解决「一个人下令、多人执行」的版本就够了。

成功要满足两件事。第一,忠诚的副官彼此不能分道扬镳。第二,指挥官忠诚的话,忠诚副官得照他的命令办。

一步一步看

目标:用一位指挥官和三位副官,弄清 Agreement 和 Validity 各管什么,以及指挥官是叛徒时只剩哪一条。

  1. 画出一位指挥官 C 和三位副官 L1、L2、L3。C 给每位副官发一条命令。

    拜占庭将军问题的指挥官副官模型:上方圆圈是指挥官 C,三条命令箭头分别指向下方的副官 L1、L2、L3;底部写着问题只问忠诚副官最后执行什么命令

  2. 问题只关心忠诚副官最后执行什么。叛徒执行什么不重要,它本来就不守规矩。

  3. 第一条要求:所有忠诚副官执行同一条命令。这一条叫 Agreement。

  4. 第二条要求:如果 C 忠诚,每个忠诚副官执行 C 发的那条命令。这一条叫 Validity。

  5. 再看 C 是叛徒的情形。C 可能给不同人发不同的命令,这时没有「C 的命令」可以服从,所以 Validity 不作要求,只看 Agreement。

指挥官 要满足的条件
忠诚 Validity;满足了它,Agreement 自动成立
叛徒 只要 Agreement

怎么判断

给你一个结局,按下面的顺序判:

  1. 先划掉所有叛徒,只看忠诚副官的决定。
  2. 忠诚副官的决定全都一样吗?一样,Agreement 满足。
  3. 指挥官忠诚吗?忠诚,再看忠诚副官是否都执行了他的命令,是就满足 Validity。
  4. 指挥官是叛徒,第 3 步跳过。

两条为什么缺一不可?只有 Agreement 的话,大家可以约好「永远撤退」,彼此一致却完全不理指挥官。只有 Validity 的话,指挥官是叛徒时,副官们可以各干各的。

课件用 10 位将军的例子说明好结局和坏结局。好计划是至少 6 位忠诚将军进攻,或者全体忠诚将军撤退。坏计划是不超过 5 位忠诚将军进攻、其余撤退,进攻的人去送死。

常见误解

以为指挥官是叛徒时协议就失败了

指挥官是叛徒时,只要忠诚副官彼此一致就算成功。后面会看到一个例子:叛徒指挥官发了不同命令,三个忠诚副官照样一致选择进攻。

以为 Validity 要求叛徒副官也服从命令

两个条件都只约束忠诚副官。叛徒副官做什么都不算进判断里。

试一下

指挥官忠诚,下令进攻。两位忠诚副官都撤退了,一位叛徒副官进攻。两个条件各满足吗?

先划掉叛徒。两位忠诚副官都撤退,彼此一致,Agreement 满足。指挥官忠诚却下令进攻,忠诚副官没照办,Validity 不满足,所以这次失败。

把它们串起来

两将军问题先排除一个干扰项。路会丢信时,连两个都忠诚的人都确认不了彼此。所以本讲后面统一假设:消息一定送达,收信人知道是谁发的,谁没发也能察觉。

信道修好以后,剩下的难点在人。拜占庭节点可以撒谎、两头说话、转述时改内容,比只会沉默的崩溃节点难对付得多。

要对付它,先定好验收标准。Agreement 管忠诚副官之间一致,Validity 管忠诚指挥官的命令被执行。指挥官是叛徒时只看 Agreement。

下一页问一个最直接的问题:至少要多少人,才可能同时满足这两条?

课件里的坑

  • [读图提醒] 两将军问题课件标为「Gray 等人 1978 年提出」。按 Wikipedia,问题 1975 年就由 Akkoyunlu 等人发表,1978 年是 Jim Gray 命名的那一次。答题照课件写即可(p.3)。
  • [读图提醒] p.10 末行「When the loyal generals are the majority」只说过半;口头消息下要超过 2/3,以 p.11 为准(p.10–11)。
  • [对照记忆] 两将军是人可靠、信道不可靠;拜占庭将军是信道可靠、人不可靠。考试问两者区别就答这一组对照(p.3、p.14)。
  • [定义细节] p.9 方框里的 Agreement 和 Validity 是必背定义。p.8 最后一条「每个忠诚副官服从收到的命令」只是直觉描述,答题写 p.9 的版本(p.8–9)。

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先画出两将军的三步消息表,写出每步谁不确定;再默写 Agreement 和 Validity,说清指挥官是叛徒时哪条不用管;最后做变式题。

必背

  1. 两将军问题:两人都忠诚、信道会丢消息,无论发多少条确认,最后一条的发送方总不确定
  2. 两将军是人可靠、信道不可靠;拜占庭将军是信道可靠(消息必达、知道发送者),人可能是叛徒
  3. 崩溃故障只会沉默,拜占庭故障可以任意行为:对不同的人说不同的话、转述时撒谎、故意不发
  4. 拜占庭将军问题两个条件:Agreement(忠诚副官服从同一命令)、Validity(指挥官忠诚时服从他的命令)
  5. 指挥官是叛徒时 Validity 不作要求,只看 Agreement;指挥官忠诚时 Agreement 可由 Validity 推出

课件例题

例 1(课件 p.5–6):两将军的确认链

A 发「黎明进攻」,B 收到;B 回「好」,A 收到;A 再发「很高兴你同意」,这条丢了。每一步谁不确定?

提示

每一步只问一件事:刚发出这条信的人,能看到它送到了吗?

解答

第 1 步后 A 不确定 B 收到没有;第 2 步后 B 不确定 A 收到确认没有;第 3 步丢失后 A 又不确定。无论发多少条,最后一条的发送方总不确定。

例 2(课件 p.9):10 位将军的好计划和坏计划

10 位将军里有叛徒。什么样的结局算好计划,什么样算坏计划?叛徒到几个就可能出现坏计划?

提示

好坏看忠诚将军的行动:进攻的人够不够多,或者是不是一起撤退。

解答

好计划:至少 6 位忠诚将军进攻,能赢;或者全体忠诚将军撤退。坏计划:不超过 5 位忠诚将军进攻、其余撤退,进攻的人送死。课件括号里写「4 个及以上叛徒」时可能出现坏计划,和下一页的下界对得上:10 位将军最多容忍 3 个叛徒。

完整例题

题目:用 Agreement 和 Validity 判断下面三个结局是否成功。指挥官 C,副官 L1、L2、L3。

  • 结局一:C 忠诚、下令进攻;L3 是叛徒。L1、L2 进攻,L3 撤退。
  • 结局二:C 是叛徒,给 L1 发进攻、给 L2 和 L3 发撤退;三位副官都忠诚,最后都撤退。
  • 结局三:C 是叛徒;三位副官都忠诚,L1 进攻,L2、L3 撤退。

解:

  1. 结局一:划掉 L3。L1、L2 都进攻,Agreement 满足。C 忠诚且下令进攻,L1、L2 照办,Validity 满足。成功。
  2. 结局二:C 是叛徒,Validity 不作要求。三位忠诚副官都撤退,Agreement 满足。成功。虽然有人收到的是进攻,但大家一致就够了。
  3. 结局三:C 是叛徒,只看 Agreement。L1 进攻、L2 和 L3 撤退,三人不一致,Agreement 不满足。失败。

要点:判断前先划掉叛徒,再看指挥官是否忠诚。叛徒指挥官的情形只判 Agreement。

答题格式:每个结局写两行,一行写 Agreement 是否满足,一行写 Validity 是否适用、是否满足。

变式题(先自己做)

(1) 两将军问题里,A 和 B 约定「来回各确认三次再出兵」。证明这个约定仍然不能保证两人一致。

(2) 指挥官忠诚,下令撤退。三位副官里 L2 是叛徒。L1、L3 都撤退,L2 进攻。这个结局满足两个条件吗?

提示

(1) 盯住最后一条信,问它丢了以后收信人还会不会照做。(2) 先划掉叛徒,再看指挥官是否忠诚。

判分点与答案(非官方评分标准)

判分点:① (1) 要点出「最后一条信可能丢失、发送方看不到送达」;② (2) 要先排除叛徒再判两个条件。

(1) 来回各三次共 6 条信,最后一条由 B 发出。这条可能丢,B 看不到它是否送到,于是 B 不确定 A 会不会出兵。按倒推论证,任何固定条数的约定都一样。

(2) 划掉 L2。L1、L3 都撤退,Agreement 满足;指挥官忠诚、下令撤退,两人照办,Validity 满足。成功。

闪卡自测

1. 两将军问题里哪个环节不可靠?

信道:信使可能被抓、消息会丢。两位将军本身都忠诚(p.3)。

2. 为什么多发确认解决不了两将军问题?

每条确认本身也会丢,最后一条的发送方总看不到送达,不确定性只是在两人之间来回推(p.6)。

3. 崩溃故障和拜占庭故障差在哪?

崩溃节点只会停下、沉默;拜占庭节点可以任意行为,对不同的人说不同的话(p.10)。

4. 写出 Agreement 和 Validity。

Agreement:所有忠诚副官服从同一条命令。Validity:如果指挥官忠诚,每个忠诚副官服从他发出的命令(p.9)。

5. 指挥官是叛徒时,哪条条件仍需满足?

Agreement。Validity 只在指挥官忠诚时约束(p.9)。

6. 为什么只研究「一位指挥官下令」的版本就够?

让每个人轮流当一次指挥官,把自己的值可靠地发出去,就能得到所有人对所有值的一致(p.8)。

7. 课件 10 位将军的例子里,什么是坏计划?

不超过 5 位忠诚将军进攻、其余撤退,进攻的人送死(p.9)。

下一讲

这一页定好了验收标准。下一页回答:只靠口头转述时,至少要多少人才能压住 m 个叛徒。见 L07b。

下一讲 →
L07b L07b 3m+1 下界:为什么 3 个人压不住 1 个叛徒

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。