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,斜线是一条信。青绿色是这一步新发的那条信。
-
A 派信使送去「黎明进攻」,信送到了。可是 A 自己看不到送达,所以 A 不确定 B 收到没有。
-
B 收到了,回一条「好」,也送到了。这回轮到 B 看不到送达:B 不确定 A 收到确认没有。B 怕 A 没收到、A 不出兵,所以 B 也不敢一个人冲。
-
A 收到「好」,再发一条「很高兴你同意」,这条在半路丢了。现在 A 又陷入同样的处境:B 收到没有?
-
再发一条也一样。每多一条确认,只是把「对方收到没有」从一方推给另一方。
把三步摆成一张表,就是课件那张消息表:
| 步 | 消息 | 送到了吗 | 谁不确定 |
|---|---|---|---|
| 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 说「撤退」。转述别人的话时,它也可以改内容。
两面派比沉默可怕得多。沉默的人能被发现,两面派说的每句话单看都像正常消息。
一步一步看
目标:同样只坏一个节点,对比崩溃和拜占庭两种故障,看难度差在哪里。
-
左边是崩溃故障:X 停了,什么都不发。P、Q 只是收不到 X 的消息,它们收到的东西里没有假话。
-
右边是拜占庭故障:X 还在发消息,可是对 P 说进攻、对 Q 说撤退。P、Q 各自看到的消息都像真的。
-
从图上数,两边坏掉的节点一样多,都是一个。难度的差别全在坏节点能做什么。
怎么判断
拿到一个故障描述,问一句:坏节点会不会发出「内容不对」的消息?
- 只会停下、不发了,是崩溃故障。
- 会发错的内容、给不同人发不同的内容、转述时改内容,是拜占庭故障。
- 故意不发也算在拜占庭故障里。拜占庭节点的行为包括了崩溃节点能做的一切。
本讲的判断口径和课件一致:拜占庭节点可以任意行为。
常见误解
以为过半数诚实就能对付拜占庭故障
崩溃故障下,过半数常常就够了。拜占庭故障下,坏节点能两头说话,只用口头消息时要超过三分之二的节点诚实,下一页会推出这个门槛。
以为拜占庭节点一定会撒谎
它可以撒谎,也可以老老实实,还可以时而真时而假。协议要在它采取最坏做法时也成立,所以分析时总按最坏的情况算。
试一下
一个节点硬盘坏了,之后每次都回复「余额 0」,而真实余额不是 0。这是哪种故障?
拜占庭故障。它没有停下,还在发消息,只是内容是错的。崩溃故障的节点只会不回复。
3. Agreement 与 Validity:有叛徒时怎样算成功
它解决什么问题
一群将军要商量出一个共同行动,其中可能有叛徒。在动手设计算法之前,得先写清「什么结果算成功」。课件把它写成两个条件,本讲后面每个下界、每个算法,都拿这两条来检验。
直觉
课件先把问题简化:一位指挥官下令,其余的人是副官,负责执行。谁都可能是叛徒,指挥官自己也不例外。
「所有人对一个值达成一致」可以拆成「每个人轮流当一次指挥官,把自己的值可靠地发出去」。所以解决「一个人下令、多人执行」的版本就够了。
成功要满足两件事。第一,忠诚的副官彼此不能分道扬镳。第二,指挥官忠诚的话,忠诚副官得照他的命令办。
一步一步看
目标:用一位指挥官和三位副官,弄清 Agreement 和 Validity 各管什么,以及指挥官是叛徒时只剩哪一条。
-
画出一位指挥官 C 和三位副官 L1、L2、L3。C 给每位副官发一条命令。
-
问题只关心忠诚副官最后执行什么。叛徒执行什么不重要,它本来就不守规矩。
-
第一条要求:所有忠诚副官执行同一条命令。这一条叫 Agreement。
-
第二条要求:如果 C 忠诚,每个忠诚副官执行 C 发的那条命令。这一条叫 Validity。
-
再看 C 是叛徒的情形。C 可能给不同人发不同的命令,这时没有「C 的命令」可以服从,所以 Validity 不作要求,只看 Agreement。
| 指挥官 | 要满足的条件 |
|---|---|
| 忠诚 | Validity;满足了它,Agreement 自动成立 |
| 叛徒 | 只要 Agreement |
怎么判断
给你一个结局,按下面的顺序判:
- 先划掉所有叛徒,只看忠诚副官的决定。
- 忠诚副官的决定全都一样吗?一样,Agreement 满足。
- 指挥官忠诚吗?忠诚,再看忠诚副官是否都执行了他的命令,是就满足 Validity。
- 指挥官是叛徒,第 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,说清指挥官是叛徒时哪条不用管;最后做变式题。
必背
- 两将军问题:两人都忠诚、信道会丢消息,无论发多少条确认,最后一条的发送方总不确定
- 两将军是人可靠、信道不可靠;拜占庭将军是信道可靠(消息必达、知道发送者),人可能是叛徒
- 崩溃故障只会沉默,拜占庭故障可以任意行为:对不同的人说不同的话、转述时撒谎、故意不发
- 拜占庭将军问题两个条件:Agreement(忠诚副官服从同一命令)、Validity(指挥官忠诚时服从他的命令)
- 指挥官是叛徒时 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 撤退。
解:
- 结局一:划掉 L3。L1、L2 都进攻,Agreement 满足。C 忠诚且下令进攻,L1、L2 照办,Validity 满足。成功。
- 结局二:C 是叛徒,Validity 不作要求。三位忠诚副官都撤退,Agreement 满足。成功。虽然有人收到的是进攻,但大家一致就够了。
- 结局三: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。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。