L07b 3m+1 下界:为什么 3 个人压不住 1 个叛徒
从三将军的两种情形讲起,说明忠诚副官为什么分不清谁在撒谎,再用「每人扮演一组」把结论推广成 n ≥ 3m+1。
一句话版
只靠口头转述时,3 个人里只要有 1 个叛徒,忠诚的人就分不清是谁在撒谎,问题无解。把每个人换成一组 m 个人,结论变成:总人数至少要 3m+1,才可能压住 m 个叛徒。
上一页定好了两个验收条件 Agreement 和 Validity,见 L07a。这一页证明,人数不够时,任何口头消息算法都满足不了它们。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 口头消息 | oral message | 内容全由发送者决定,转述时可以随便改,收信人没法验证 |
| m | 叛徒个数 | 最多有几个人会撒谎 |
| n ≥ 3m+1 | 读「n 大于等于 3m 加 1」 | 总人数至少是叛徒数的 3 倍再多 1 |
| 下界 | lower bound | 少于这个数,什么算法都不行 |
| 不可区分 | indistinguishable | 两个不同的世界,在某人眼里看到的消息一模一样 |
| 反证法 | proof by contradiction | 先假设结论不成立,推出矛盾 |
一个类比:两个同事给你传话
你是小林。老板说「明天上线」,同事小王却告诉你:「老板跟我说的是不上线。」
有两种可能。一种是老板两头说了不同的话,小王只是如实转告。另一种是老板说得清清楚楚,小王在编。
你手机里看到的聊天记录,两种可能下一个字都不差。你只能凭这些记录做决定,所以两种可能下你必须做同一个决定。
如果群里有更多同事,你可以多问几个人。多数人说的版本更可信。可是只有你、小王、老板三个人时,你找不到第三个说法来对质。
类比在哪里失效:
- 现实里你可以打电话给老板核实,本讲的副官只能看收到的消息。
- 本讲假设消息一定送达、能认出是谁发的,聊天记录也不会丢。
- 下面的论证还要求对称地考虑小王的处境,日常传话不会这么严格地推。
从零讲起
1. 先补一块:反证法(补充)
它解决什么问题
这一页要证明「不存在任何算法能做到某件事」。算法有无穷多种,没法一个一个试。反证法换个方向:假设有一个算法做到了,然后推出一件不可能的事,于是假设错了。
直觉
你想证明「抽屉里没有红袜子」。先假设有一只。再从别的事实推出:如果有,它一定被洗衣机染过颜色,可是洗衣机这周没开过。矛盾出现了,所以没有红袜子。
本讲用到的矛盾是:同一个副官,在两个他分不清的世界里,被要求做两个不同的决定。
一步一步看
目标:看反证法的五步怎么走,以及本页每一步对应什么。
- 写下要证的结论:3 位将军对付 1 个叛徒,没有算法能同时满足 Agreement 和 Validity。
- 反过来假设:有这样一个算法。
- 用这个算法跑两种情形,看每个忠诚副官被逼着做什么。
- 发现某处冲突,比如两位忠诚副官做了不同决定。
- 冲突说明第 2 步的假设站不住,原结论成立。
| 步 | 做什么 | 本页里对应什么 |
|---|---|---|
| 1 | 写结论 | 3 人对付 1 叛徒无解 |
| 2 | 假设相反 | 有算法能解 |
| 3 | 推后果 | 情形 1 和情形 2 里 L1 的决定 |
| 4 | 找矛盾 | 情形 1 里 L1、L2 分道扬镳 |
| 5 | 下结论 | 假设错,无解 |
怎么判断
一个证明是不是反证法,看它开头有没有「假设……成立」,结尾有没有「矛盾,所以假设不成立」。两头都有就是。
常见误解
以为举一个算法失败的例子就证明了无解
举一个算法失败,只说明那个算法不行。要证明「所有算法都不行」,得像反证法这样,假设任意一个算法成功,再推出矛盾。
试一下
用反证法的格式写一句:「两将军问题没有确定能成功的办法」怎么证?
假设有一个办法发 k 条信就能保证一致。最后一条可能丢,收信人不能依赖它,于是 k−1 条也够。一路倒推到 0 条,两人不发信也能一致,矛盾。所以这样的办法不存在。
2. 三将军:L1 为什么分不清
它解决什么问题
最小的有意思的情形是 3 个人:一位指挥官 C、两位副官 L1 和 L2,其中 1 个是叛徒。这一节证明,这种情形下没有口头消息算法能满足两个条件。
一个人自己和自己当然一致。两个人里有一个叛徒,就只剩一个忠诚者,两个条件自动满足,谈不上难。真正的不可能从 3 个人开始。
直觉
站在 L1 的位置看。L1 手里永远只有两样东西:C 直接给它的命令,和 L2 转述的「C 跟我说的是……」。
叛徒可能是 C,也可能是 L2。两种情况下,只要叛徒做得巧,L1 收到的东西可以一模一样。L1 分不清,就只能在两种情况下做同一个决定。麻烦在于,两个条件在两种情况下要的东西不一样。
一步一步看
目标:看 L1 在两种情形里收到的消息为什么一模一样,并由此推出三将军无解。
-
情形 1:C 是叛徒(虚线圈)。C 对 L1 说 attack,对 L2 说 retreat。L2 忠诚,照实告诉 L1「C 说 retreat」。
-
情形 2:C 忠诚,对两人都说 attack。L2 是叛徒,它把 attack 改成 retreat,告诉 L1「C 说 retreat」。
-
把两种情形里 L1 收到的东西并排放。两边都是「C 说 attack」加「L2 说 C 说 retreat」,一字不差。
-
看情形 2。C 忠诚、下令 attack,Validity 要求忠诚的 L1 执行 attack。
-
L1 分不清两种情形,所以在情形 1 里也只能 attack。
-
对称地看 L2。把 L1 和 L2 的角色互换,同样的论证说明:L2 收到 C 的 retreat 时必须执行 retreat。
-
回到情形 1:L1 attack,L2 retreat。两位忠诚副官做了不同决定,违反 Agreement。
怎么判断
想判断「某个人数下有没有解」,这一节给了一个可复用的检查:
- 找一位忠诚副官,列出他在某个世界里收到的全部消息。
- 再构造另一个世界,换一个人当叛徒,让这位副官收到同样的消息。
- 如果两个世界对他的要求不同,比如一个世界 Validity 要他 attack,另一个世界 Agreement 要他跟着别人 retreat,就说明无解。
关键词是不可区分。忠诚节点只能根据自己看到的消息做决定,看到的一样,决定就必须一样。
常见误解
以为让 L1 多问几轮就能分清
L2 是叛徒时,它每一轮都可以一致地撒同样的谎;C 是叛徒时,它也可以一致地两头说。轮数加多,L1 看到的两个世界依然一样。
以为 L1 可以随便选一个,碰运气
协议要在叛徒采取最坏做法时也成立。只要存在一种叛徒的做法让条件失败,这个人数下就算无解。
试一下
把情形 1 改成 C 对 L1 说 retreat、对 L2 说 attack,L2 如实转告。再构造一个让 L1 分不清的情形 2。
情形 2:C 忠诚,对两人都说 retreat;L2 是叛徒,谎报「C 说 attack」。两种情形下 L1 收到的都是「C 说 retreat」加「L2 说 C 说 attack」,L1 分不清。情形 2 里 Validity 要 L1 retreat,于是情形 1 里 L1 也 retreat,而 L2 执行 attack,违反 Agreement。
3. 推广:3m 个人压不住 m 个叛徒
它解决什么问题
三将军只说明了 1 个叛徒的情形。真实系统要对付的叛徒可能有好几个。这一节把结论推广:总人数是 3m 或更少时,压不住 m 个叛徒。
直觉
把三将军里的每个人,换成一组 m 个人。
假设真有一个算法,能让 3m 位将军对付 m 个叛徒。那就让三位将军每人在脑子里模拟一组:一个人扮演 m 个人,替他们收发消息、做决定。
叛徒那一组恰好对应一位叛徒将军。于是这个算法就变成了「3 个人对付 1 个叛徒」的算法。上一节已经证明这种算法不存在,所以开头那个算法也不存在。
一步一步看
目标:看把每个人换成一组 m 人后,3m 人对 m 个叛徒怎样退回三将军的情形。
-
把 3m 位将军分成三组,每组 m 人:上组含指挥官,另外是左下组和右下组。
-
让上组整组叛变(图里虚线),向左下组发一个值,向右下组发另一个值。
-
右下组忠诚,把收到的值如实转告左下组。
-
把每组当成一个人看,这就是三将军的情形 1。换成右下组叛变、上组忠诚,就是情形 2。左下组在两种情形下收到的消息一样,分不清。
-
课件的图画的是 m = 6:每组 6 个人,共 18 位将军。叛徒组 6 人,正好是总数的三分之一。
怎么算
下界写成式子:
- 口头消息下可解,当且仅当 n ≥ 3m+1
意思是:总人数要比叛徒数的 3 倍还多至少 1 个。换个说法,忠诚的人要超过三分之二。
n > 3m 和 n ≥ 3m+1 是同一个条件。人数是整数,大于 3m 就是至少 3m+1。
反过来,已知人数 n,最多能容忍几个叛徒?从 3m+1 ≤ n 解出 m:
- 3m ≤ n − 1,所以 m ≤ (n − 1) / 3,再向下取整
意思是:先减 1,再除以 3,舍掉小数。
几个例子:
- n = 4:(4 − 1) / 3 = 1,容忍 1 个
- n = 7:(7 − 1) / 3 = 2,容忍 2 个
- n = 10:(10 − 1) / 3 = 3,容忍 3 个
- n = 18:(18 − 1) / 3 = 5.67,向下取整为 5;所以 18 人对 6 个叛徒不够,要 3 × 6 + 1 = 19 人
常见误解
以为忠诚者过半就够了
课件有一页写的是「忠诚将军占多数」。口头消息下过半不够,要超过三分之二。答题按 n ≥ 3m+1 写。
以为 3m+1 是某个算法的要求,换个算法也许能少几个人
3m+1 是下界:少于它,任何口头消息算法都不行。换算法降不下来,要降只能换假设,比如加上签名,见本讲最后一页。
试一下
13 位将军最多容忍几个叛徒?再多 1 个叛徒,至少要几位将军?
(13 − 1) / 3 = 4,最多容忍 4 个。5 个叛徒要 3 × 5 + 1 = 16 位将军。
把它们串起来
论证从最小的情形开始。3 个人里 1 个叛徒,忠诚的 L1 只能看到两条消息,而叛徒是 C 还是 L2,这两条消息可以一模一样。
L1 分不清,就只能在两个世界里做同一个决定。Validity 在一个世界里逼它 attack,Agreement 在另一个世界里要它跟 L2 一致。两头没法同时满足,于是无解。
推广只用一个技巧:每个人扮演一组 m 个人。3m 人对 m 个叛徒的算法,会变成 3 人对 1 个叛徒的算法,而后者不存在。所以口头消息下至少要 3m+1 人。
下界只说人少了不行,没说人够了就行。下一页的 OM 算法证明:人数达到 3m+1,确实能做到。
课件里的坑
- [读图提醒] p.12「2 generals, 1 traitor, no consensus」:原论文脚注说两位将军的情形是平凡的,只剩一位忠诚者时两个条件自动满足。真正的不可能性从 3 个人开始(p.12)。
- [读图提醒] p.10 末行只说「忠诚将军占多数」,口头消息下要超过 2/3,以 p.11 和 p.13 为准(p.10–11)。
- [读图提醒] p.13 的图里,点的颜色表示身份(红 = 叛徒、蓝 = 忠诚),箭头颜色表示传的值(蓝 = 1、红 = 0)。两种颜色含义不同,读图时别混(p.13)。
- [等价写法] 老师课上写了「n > 3m ⇔ n ≥ 3m+1」,两种写法等价,后一种更常用(p.14)。
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,在纸上画出 p.12 的两张三角图,标出谁是叛徒、每条箭头传什么;然后口述一遍「L1 分不清 → Validity 逼它 attack → 违反 Agreement」;最后用 (n − 1) / 3 算几个人数能容忍多少叛徒。
必背
- 口头消息下可解当且仅当超过 2/3 忠诚,即 n ≥ 3m+1;3 人对付 1 个叛徒无解,因为 L1 分不清谁在撒谎
- 三将军论证:情形 1 指挥官叛变,情形 2 副官 L2 叛变,L1 两次收到的消息完全一样(不可区分)
- Validity 逼 L1 在情形 2 选 attack,于是情形 1 里 L1 也 attack、L2 retreat,违反 Agreement
- 推广:少于 3m+1 位将军无法应对 m 个叛徒,证法是让 3 人各模拟一组 m 人,归约回三将军
- n > 3m 和 n ≥ 3m+1 是同一个条件;10 位将军最多容忍 3 个叛徒,18 位将军对 6 个叛徒无解
课件例题
例 1(课件 p.12):3 个将军、1 个叛徒
情形 1 指挥官叛变,给 L1 发 attack、给 L2 发 retreat,L2 转告 L1「retreat」;情形 2 指挥官忠诚发 attack,L2 叛变转告 L1「retreat」。L1 能分辨吗?
提示
把两种情形里 L1 收到的消息逐条列出来比一比。
解答
两种情形下 L1 收到的都是「指挥官说 attack、L2 说 retreat」,无法分辨谁在撒谎。情形 2 里 Validity 要 L1 attack,所以情形 1 里 L1 也 attack;对称地 L2 retreat,违反 Agreement。所以 3 人对付 1 个叛徒无解。
例 2(课件 p.13):18 位将军、6 个叛徒
课件的图画了三个椭圆,每个装 6 位将军。为什么这 18 位将军对付不了 6 个叛徒?
提示
把每个椭圆当成一个人看,图会变成哪一页的哪张图?
解答
18 = 3 × 6,即 n = 3m、m = 6,不满足 n ≥ 3m+1 = 19。左图顶部一组是叛徒,给两组发不同的值,右下组如实转告;右图顶部忠诚、右下组叛变谎报。左下组在两张图里收到的一样,分不清。每组看成一个人,就是 p.12 的情形 1 和情形 2。推广的结论:少于 3m+1 位将军无法应对 m 个叛徒。
完整例题
题目:(1) 课件 p.9 说 10 位将军时「4 个及以上叛徒」就可能出坏计划。用下界验证这句话。(2) 用推广论证说明 9 位将军对付不了 3 个叛徒。
解:
- (1) 已知 n = 10,求最大的 m。由 3m+1 ≤ 10 得 m ≤ 3,所以最多容忍 3 个叛徒。
- 叛徒有 4 个时,3 × 4 + 1 = 13 > 10,人数不够,可能出坏计划,和课件一致。
- (2) 9 = 3 × 3,把 9 人分成三组,每组 3 人。
- 假设有算法能让这 9 人对付 3 个叛徒。让三位将军各模拟一组 3 人,叛徒组对应一位叛徒将军。
- 这就得到一个「3 人对付 1 个叛徒」的算法,与三将军的结论矛盾。所以 9 人对付不了 3 个叛徒。
要点:算最大叛徒数用 (n − 1) / 3 向下取整;证明无解时说清「每人模拟一组」这一步。
答题格式:先写不等式 n ≥ 3m+1 并代数,再一句话说明归约到三将军。
变式题(先自己做)
(1) 7 位将军最多容忍几个叛徒?如果叛徒有 3 个,至少要几位将军?
(2) 三将军里,叛徒 L2 改成「什么都不转告」。L1 还会分不清吗?结合「能察觉谁没发消息」的假设回答。
提示
(1) 代公式 (n − 1) / 3。(2) 叛徒的最坏做法是哪一种?协议要对最坏做法成立。
判分点与答案(非官方评分标准)
判分点:① (1) 两问都要写出计算式;② (2) 要指出「不转告」不是叛徒的最坏做法,下界论证用的是谎报。
(1) (7 − 1) / 3 = 2,最多 2 个。3 个叛徒要 3 × 3 + 1 = 10 位将军。
(2) 不转告会被察觉,L1 按默认值处理,这种做法反而容易对付。下界论证里叛徒选的是谎报,L1 在两个世界里看到的一样。只要存在一种做法让 L1 分不清,问题就无解。
闪卡自测
1. 口头消息下,可解的条件是什么?
超过 2/3 的将军忠诚,即 n ≥ 3m+1(p.11)。
2. p.12 里 L1 为什么分不清两种情形?
两种情形下 L1 收到的都是「指挥官说进攻」加「L2 说指挥官让撤退」,它看到的消息完全一样(p.12)。
3. 三将军论证最后违反的是哪个条件?
Agreement:情形 1 里 L1 attack、L2 retreat,两位忠诚副官不一致(p.12)。
4. 10 位将军用口头消息最多容忍几个叛徒?
3 个,因为 3m+1 ≤ 10 时 m 最大为 3(p.9)。
5. 怎么把三将军的结论推广到 m 个叛徒?
让 3 位将军各模拟一组 m 人,叛徒组对应一位叛徒,归约回三将军(p.13)。
6. n > 3m 和 n ≥ 3m+1 有区别吗?
没有。n 是整数,两种写法等价,老师课上画了等号(p.14)。
7. 口头消息的含义是什么?
消息内容完全由发送者控制,转述时可以随意改,接收者无法验证「某某确实说过这句话」(p.11)。
下一讲
下界说人少了不行。下一页的 OM 算法说明,人数达到 3m+1 时确实能做到,代价是一层套一层的转述。见 L07c。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。