← COMP5567 全部讲次
L07c · 第 7 周

L07c 口头消息算法 OM(m):转述一层套一层,最后数票

从多数函数和默认值 RETREAT 讲起,一帧一帧走完四将军的 OM(1),再展开 OM(m) 的递归,算清转发给几个人、表决时有几个值、要跑几轮。

一句话版

OM(m) 让每位副官把自己收到的命令,再当一次指挥官转述给其他人,这样递归 m 层,最后每人对手里的值数票。人数达到 3m+1 时,忠诚的转述总能压过叛徒的谎言。

上一页证明了人数少于 3m+1 时无解,见 L07b。这一页给出人数够了时的算法,OM 是 Oral Messages 的缩写。

先认识这几个词

词 全称 / 读法 一句人话
OM(m) Oral Messages,口头消息算法 靠层层转述加多数表决,容忍 m 个叛徒
多数函数 majority 一组值里过半数是谁就取谁
RETREAT 撤退,默认值 没有多数、或收不到消息时用它
A / R Attack / Retreat 进攻 / 撤退,课件也写成 1 / 0
递归 recursion 大问题里调用同一个算法的小一号版本
向量 vector 一位副官手里收集到的那一串值
同步网络 synchronous network 消息延迟有上限,超时就能判定对方没发

一个类比:群里核对老板的指令

六个下属里有两个爱撒谎。老板私聊给每人发了指令,小林想知道老板到底说了什么。

小林先看老板发给自己的。然后他挨个问其他五个人:「老板跟你说的是什么?」五个人里两个会撒谎,三个说真话。小林把这些说法和自己收到的放在一起数票,真话占多数。

麻烦是,「小王说老板说了什么」这件事本身,小林也只能听小王一个人讲。小王撒谎怎么办?所以小林还会去问别人:「小王跟你说的是什么?」这一层层的追问,就是 OM 的递归。

类比在哪里失效:

  • 本讲假设消息一定送达,没回复的人能被察觉,并按默认值撤退处理。
  • 群聊里大家可以看到彼此的发言,OM 里每条转述都是私下点对点发的。
  • 追问在 OM 里不是随兴的:要追问几层,由叛徒个数 m 事先定死。

从零讲起

1. 多数函数和默认值 RETREAT

它解决什么问题

OM 的最后一步,是每位副官对手里的一串值做决定。这串值里有真有假,需要一个固定的规则把它们变成一个命令。规则还得处理打平的情况,否则两个人可能各自往不同的方向破平局。

直觉

数票,过半就算赢。要是没人过半,比如两票对两票,就按事先约好的默认值办。课件约定的默认值是撤退。

撤退当默认值有个好处:所有忠诚副官用同一个默认值,打平时大家会一起撤退,不会分道扬镳。

一步一步看

目标:拿三串值走一遍多数函数,看过半时怎么取值、打平时怎么办。

  1. 拿到一串值,比如 (A, A, R)。
  2. 数每种值出现几次:A 两次,R 一次。
  3. 一共 3 个值,过半要至少 2 个。A 有 2 个,过半,结果是 A。
  4. 换一串 (A, R, R, R):R 有 3 个,4 个值里过半,结果是 R。
  5. 再换 (A, A, R, R):A、R 各 2 个,都没过半,结果取默认值 RETREAT。
输入 A 的个数 R 的个数 结果
(A, A, R) 2 1 A
(A, R, R, R) 1 3 R
(A, A, R, R) 2 2 RETREAT

怎么判断

规则写成一句:如果 v₁ 到 vₙ₋₁ 里过半数等于 v,结果就是 v;没有过半数,结果是 RETREAT。

意思是:严格超过一半才算多数,正好一半不算。

老师课上用 1 表示 Attack、0 表示 Retreat 演示过两次:(0, 1, 1) 里 1 过半,结果是 1;(0, 0, 1, 1) 没有多数,结果是 0,也就是撤退。

原论文还提到另一种做法:值有大小顺序时取中位数。本课按「过半数,否则 RETREAT」算。

常见误解

以为打平时取第一个值,也就是指挥官直接给的那个

本课的规则是打平取 RETREAT,和值的顺序无关。做 OM 题时,打平规则经常决定答案。

试一下

算出 (R, A, A, A, R) 和 (A, R, A, R, R, A) 的多数结果。

第一串 5 个值,A 有 3 个,过半,结果 A。第二串 6 个值,A、R 各 3 个,没有过半,结果 RETREAT。

2. OM(1):四将军走一遍

它解决什么问题

最简单的非平凡情形是 m = 1:一个叛徒。按下界,至少要 3 × 1 + 1 = 4 位将军,即指挥官 C 加三位副官。这一节把 OM(1) 在这四个人身上完整跑一遍。

OM 能工作,靠三条假设:

  1. 发出的消息都能正确送达。这排除了两将军问题的有损信道。
  2. 接收者知道消息是谁发的。叛徒不能冒充别人发消息,但能篡改自己转述的内容。
  3. 能检测到消息缺失。叛徒不发消息时,接收者能发现,并按默认值处理。

第 3 条实际要靠同步网络:消息延迟有上限,过了上限还没到,就认定对方没发。

直觉

OM(1) 分两轮。第一轮,指挥官把命令发给每位副官。第二轮,每位副官把自己收到的值转告另外两人。

于是每位副官手里有 3 个值:一个是指挥官直接给的,两个是别人转告的。叛徒只有一个,它最多污染其中一个值,另外两个是真的,多数就是真的。

一步一步看

目标:看 C 忠诚、L3 撒谎时,两位忠诚副官能否都照 C 的命令进攻,一共要发几条消息。

下面跑课件的第一个例子:C 忠诚、发 A,L3 是叛徒(虚线圈),转告时一律说 R。青绿色是每一步要看的东西。

  1. 第 1 轮:C 给 L1、L2、L3 各发 A,共 3 条。叛徒 L3 也收到了 A。

    OM(1) 第 1 步:上方指挥官 C 标为忠诚,三条青绿箭头都写着 A,分别指向 L1、L2 和虚线圈的叛徒 L3

  2. 第 2 轮:每位副官把收到的值转告另外两人,共 6 条。L1、L2 如实转告 A。L3 撒谎,告诉 L1 和 L2「C 跟我说的是 R」。

    OM(1) 第 2 步:第 1 轮的三条 A 变成浅灰,三位副官之间互发六条箭头;L3 发给 L1 和 L2 的两条标成青绿并写着 R,其余四条黑色箭头是如实转告的 A

  3. 决定:L1 手里是 (C 给的 A, L2 转的 A, L3 转的 R),多数为 A。L2 手里同样是 (A, A, R),也是 A。L3 是叛徒,它的决定不在考察范围内。

    OM(1) 第 3 步:所有消息箭头变成浅灰,下方三个框写着 L1 的向量 A、A、R 取多数得 A,L2 同样得 A,L3 是叛徒不考察

  4. 验收:两位忠诚副官都进攻,Agreement 满足;C 忠诚、下令 A,两人照办,Validity 满足。

  5. 数消息:第 1 轮 3 条,第 2 轮 3 × 2 = 6 条,共 9 条。

怎么判断

做 OM(1) 的题,按下面三步写:

  1. 写出每位副官从 C 直接收到的值。
  2. 写出第 2 轮每条转告的值:忠诚副官照实转告,叛徒按题目设定转告。
  3. 每位忠诚副官的向量 = 自己收到的值 + 另外两人转告的值,对它取多数。

最后用两个条件检验:忠诚副官是否一致;C 忠诚的话,是否照 C 的命令办。

指挥官是叛徒时同样这样做。课件第二个例子里,C 给 L1、L3 发 A、给 L2 发 R,三位副官都忠诚。每人手里都是两个 A、一个 R,多数都是 A,三人一致进攻。副官都忠诚时,大家拿到的是同一组值,只是顺序不同,多数结果必然一样。

常见误解

以为向量的顺序会影响结果

多数函数只数个数,不看顺序。课件把 L3 的向量写成 m(A, R, A),按「自己收到的在前」应写 (A, A, R),结果都是 A。

以为叛徒副官也要满足条件

叛徒的决定不考察。题目问「忠诚副官怎么决定」时,叛徒那一行可以直接写「叛徒,不考察」。

试一下

四将军,C 忠诚、发 R,L1 是叛徒,转告时一律说 A。L2、L3 各得到什么向量?

L2 的向量是 (C 给的 R, L1 转的 A, L3 转的 R) = (R, A, R),多数为 R。L3 的向量是 (R, A, R),也是 R。两位忠诚副官都撤退,和 C 的命令一致。

3. OM(m):一层套一层的递归

它解决什么问题

m = 1 时,一层转告就够了。叛徒多了以后,转告本身也可能被篡改。

比如 L1 想知道「L2 收到的是什么」,这个消息要经过别人转述才能确认,而转述的人里可能也有叛徒。所以「L2 说了什么」这件事,本身就需要再做一次拜占庭协议。OM(m) 用递归处理这一层层的不确定。

直觉

OM(m) 里,每位副官在一个小一号的 OM(m−1) 里当指挥官,把自己收到的值发出去。每个小协议里,其他副官又在更小的 OM(m−2) 里当指挥官转述……一直到 OM(0),就是直接广播、不再转述。

每多一层递归,就能多容忍一个叛徒。代价是调用次数一层层乘上去,下一页会算这笔账。

一步一步看

目标:看两个叛徒时 OM(2) 怎样一层套一层地转述,L1 最后怎样得出 C 的命令。

拿 n = 7、m = 2 看递归长什么样:C 加 L1 到 L6,L5、L6 是叛徒,任何时候都发 R。C 忠诚、发 A。

  1. 第 1 层:C 当指挥官跑 OM(2),给 L1 到 L6 各发 A。

  2. 第 2 层:每位副官在自己的 OM(1) 里当指挥官,把收到的值转给其余 5 位副官。一共 6 个 OM(1)。

  3. 第 3 层:每个 OM(1) 里的每位接收者,又在 OM(0) 里把值转给剩下 4 人。

  4. 看 L1 怎么确定「L2 的值」:在 L2 那棵子树里,L1 收到 L2 直接给的 A,L3、L4 转述的 A,L5、L6 谎报的 R。

    OM(2) 递归展开示意:顶层 C 发起 OM(2);第二层 L1 到 L6 各发起一个 OM(1),L5、L6 标为叛徒,L2 那个框描成青绿;第三层展开 L2 的子树,L1 收到 L2 的 A、L3 和 L4 转述的 A、L5 和 L6 谎报的 R

  5. L1 在这棵子树里拿到 (A, A, A, R, R),多数为 A,所以 L1 认定 L2 的值是 A。L3、L4 的值同理为 A,L5、L6 的值是 R。

  6. L1 的最终向量是 (A, A, A, A, R, R),4 个 A 对 2 个 R,结果 A。

怎么算

递归定义,逐步拆开:

  • OM(0):指挥官把值发给每位副官,副官直接用收到的值。
  • OM(m),m > 0:
    1. 指挥官把值发给每位副官,副官 i 收到 vᵢ。
    2. 每位副官 i 在 OM(m−1) 里当指挥官,把 vᵢ 发给其余 n−2 位副官。
    3. 副官 i 把自己直接收到的 vᵢ,和从其他每位副官 j 的 OM(m−1) 里得到的 vⱼ 放在一起,共 n−1 个值,取 Majority(v₁, …, vₙ₋₁)。

意思是:先收一个值,再让每个人把他的值「公证」一遍,最后对公证结果数票。

两个数要记牢:

  • 转发给 n−2 人:去掉自己和原指挥官。n = 7 时是 5 人。
  • 表决时有 n−1 个值:自己收到的 1 个,加上其他 n−2 位副官各 1 个。n = 7 时是 6 个。

轮数:递归共 m+1 层,同步网络下就是 m+1 轮消息。m = 2 时是 3 轮。

常见误解

以为转发给 n−1 人

转发时要去掉自己和原指挥官,所以是 n−2 人。n−1 是表决时手里值的个数,两个数别混。

以为 OM(m) 只是多跑几轮广播,代价不大

每深一层,调用次数要再乘一个人数。n = 7、m = 2 已经要 156 条消息,下一页专门算这笔账。

试一下

n = 10、m = 3 时,第 2 层每位副官转发给几个人?表决时手里有几个值?一共几轮?

转发给 10 − 2 = 8 人;表决时有 10 − 1 = 9 个值;共 3 + 1 = 4 轮。

把它们串起来

OM 的骨架只有两样:一个数票规则,一个递归。

数票规则是多数函数,过半就取,打平取 RETREAT。所有忠诚副官用同一个规则、同一个默认值,所以手里的值一样时决定一定一样。

递归负责让忠诚副官手里的值一样。每位副官都把自己收到的值,在小一号的协议里再「公证」一遍,叛徒对别人值的篡改在这里被多数压住。递归 m 层,就能压住 m 个叛徒,前提是总人数至少 3m+1。

人数不够时,同样的递归也会失败。n = 5、m = 2 的反例里,两个叛徒在每个子协议里都占了三分之二的票,真话被压成少数。

课件里的坑

  • [读图提醒] p.18 L3 的向量按「自己收到的值在前、再按 L1、L2 顺序」应写 (A, A, R),课件写 m(A, R, A)。顺序不影响多数,结果都是 A。老师在同页 n = 5 的板书里给 L3 的向量逐项标了来源 C、L1、L2、L4,正是这个顺序(p.18)。
  • [打平规则] p.16 的多数函数在没有过半数时取 RETREAT。做 OM 题时这条规则经常决定答案,比如课堂批注版 p.18 的 n = 5 变式(p.16、p.18)。
  • [假设依赖] p.14 的第 3 条假设「能检测到消息缺失」实际依赖同步网络,p.24 的对照表里明确写成 Synchronous Network(p.14、p.24)。
  • [两个数] 转发给 n−2 人,表决时 n−1 个值。p.15 原文就是这两个数,抄定义时别写成 n−1 和 n(p.15)。

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先在纸上画四将军,按第一个例子写出第 2 轮的 6 条转告和两位忠诚副官的向量;再默写 OM(m) 的三步定义,标出 n−2 和 n−1;最后照完整例题的格式自己推一遍 n = 7、m = 2。

必背

  1. OM 的三条假设:消息正确送达、接收者知道发送者、能检测到消息缺失;默认值 Retreat
  2. 多数函数:过半数等于 v 就取 v,没有过半数取 RETREAT,例如 (A, A, R, R) → RETREAT
  3. OM(m):副官在 OM(m−1) 中把值转发给 n−2 人,对 n−1 个值取多数,无多数则 RETREAT;共 m+1 轮
  4. n = 4、m = 1 时,无论叛徒是副官还是指挥官,忠诚副官都一致;消息 9 条
  5. n = 5、m = 2 不满足下界,可构造忠诚副官一致撤退、违反 Validity 的反例
  6. n = 7、m = 2 刚好满足 3m+1,两个叛徒的谎言在每个子协议里都被忠诚转述者的多数压住

课件例题

例 1(课件 p.17,Example 1):坏副官

m = 1、n = 4,L3 是叛徒,C 给三人都发 A,L3 在 OM(0) 里转告 R。L1、L2 怎么决定?

提示

每人的向量 = 自己从 C 收到的值 + 另外两人转告的值。

解答

L1 的向量 (A, A, R),L2 同样 (A, A, R),多数都是 A,两人都进攻,与忠诚指挥官一致。总消息数 3 + 3 × 2 = 9。

例 2(课件 p.18,Example 2):坏指挥官

m = 1、n = 4,C 是叛徒,给 L1、L3 发 A,给 L2 发 R,副官如实转发。三人怎么决定?

提示

三位副官都忠诚,第 2 轮的转告全是真话。比一比三人手里的值是不是同一组。

解答

L1 = m(A, R, A) = A,L2 = m(R, A, A) = A,L3 = m(A, A, R) = A。三人的向量都由两个 A、一个 R 组成,多数都是 A,全体进攻。指挥官叛变时只要求忠诚副官一致,满足。

例 3(课堂批注版 p.18):坏指挥官,副官加到 4 个

老师在 Example 2 旁边加了一个变式:m = 1、n = 5,C 是叛徒,给 L1、L3 发 A,给 L2、L4 发 R,四个副官都忠诚、如实转发。各人怎么决定?

提示

每人的向量 = 自己从 C 收到的值 + 其余三人转告的值,共 4 个。2 比 2 时没有过半数。

解答

L1 = m(A, R, A, R),L2 = m(R, A, A, R),L3 = m(A, A, R, R),L4 = m(R, A, R, A)。四个向量都是 2 个 A 对 2 个 R,没有过半数,按规则取 RETREAT。板书结论是「L1–L4:R」,四人一致撤退,Agreement 成立。同页还写了 m = 2 时要 n = 7,即 3m+1。

例 4(课件 p.29,Take-home Exercise-2):n = 5、m = 2 为什么不行

说明为什么 n = 5、m = 2 时,OM 中忠诚将军无法达成共识。

提示

先比较 5 和 3m+1。再构造一个反例:让指挥官忠诚,两个叛徒总发 R,看 L1 怎么确定 L2 的值。

解答

5 < 7,不满足下界。设 C、L1、L2 忠诚,C 发 A,L3、L4 总发 R。L2 的子协议里,L1 收到 L2 的 A 和 L3、L4 谎报的 R,(A, R, R) → R。L1 最终向量 (A, R, R, R) → R,L2 对称也是 R。忠诚指挥官下令进攻,两个忠诚副官都撤退,违反 Validity。消息总数 4 + 4 × 3 + 12 × 2 = 40。

例 5(课件 p.30,Exercise-3):n = 7、m = 2 的完整步骤

见下方完整例题。

完整例题

题目:n = 7、m = 2,给出忠诚将军用 OM 达成共识的详细步骤。

解:先检查门槛:7 = 3 × 2 + 1,刚好满足。设指挥官 C 忠诚、发 A,L5、L6 是叛徒且任何时候都发 R。

  1. 第 1 轮:C 给 L1–L6 各发 A,共 6 条。
  2. 第 2 轮:每个副官在 OM(1) 中把收到的值转给其余 5 人,共 6 × 5 = 30 条,叛徒发 R。
  3. 第 3 轮:每个 OM(1) 再展开成 OM(0),共 30 × 4 = 120 条。
  4. 看 L1 怎么确定 L2 的值:L2 的子协议里,L1 收到 L2 的 A,L3、L4 转述的 A,L5、L6 谎报的 R,即 (A, A, A, R, R),多数为 A。L3、L4 的值同理为 A;L5、L6 的值是 R。
  5. L1 的最终向量是 (A, A, A, A, R, R),4 个 A 对 2 个 R,结果为 A。L2、L3、L4 同理。

一句话结论:四个忠诚副官都进攻,与忠诚指挥官一致;共 6 + 30 + 120 = 156 条消息、3 轮(p.19、p.30)。

和例 4 对照:同样两个叛徒,副官从 4 个变成 6 个后,每个子协议里忠诚转述者占多数,谎言被压住。

答题格式:先写门槛检查,再按轮写消息数,然后挑一位忠诚副官写出「他怎么确定某位副官的值」,最后写最终向量和多数结果。

变式题(先自己做)

(1) m = 1、n = 4,叛徒指挥官给 L1 发 A,给 L2、L3 都发 R,副官如实转发。三个忠诚副官各得到什么向量,结果一致吗?(改编自课件 p.18)

(2) m = 1、n = 4,C 忠诚、发 A,叛徒 L2 在第 2 轮对 L1 说 A、对 L3 说 R。L1、L3 怎么决定?

提示

每人的向量 = 自己从 C 收到的值 + 另外两人转告的值,再取多数。(2) 里叛徒两头说不同的话,分别写 L1 和 L3 收到了什么。

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

判分点:① 每位忠诚副官的向量都要写全;② 最后要用 Agreement / Validity 检验,并说明指挥官叛变时 Validity 不要求。

(1) L1 的向量 (A, R, R),L2 是 (R, A, R),L3 是 (R, A, R),多数都是 R,三人一致撤退,Agreement 成立。指挥官叛变时 Validity 不要求,所以不必服从哪条命令(p.18)。

(2) L1 的向量 (C 的 A, L2 的 A, L3 的 A) = (A, A, A) → A;L3 的向量 (C 的 A, L1 的 A, L2 的 R) = (A, A, R) → A。两人都进攻,Agreement 和 Validity 都满足。

闪卡自测

1. OM 的三条假设是什么?

消息正确送达;接收者知道发送者;能检测到消息缺失(p.14)。

2. 多数函数遇到 (A, A, R, R) 怎么办?

没有过半数,结果为 RETREAT。老师板书用 1 表示 Attack、0 表示 Retreat:(0, 1, 1) 多数为 1,(0, 0, 1, 1) 没有多数,取 0(p.14、p.16)。

3. OM(m) 中副官转发给几个人?表决时有几个值?

转发给 n−2 人;表决时有 n−1 个值(p.15)。

4. 为什么 OM 要递归,不能转告一次就数票?

副官 j 的转述本身也可能被篡改,「j 说了什么」也需要一次拜占庭协议来确认。每加一层递归,多容忍一个叛徒(p.15)。

5. n = 4、m = 1 的 OM 一共发几条消息?

9 条:指挥官 3 条,三个副官各转发 2 条(p.17、p.19)。

6. 叛徒指挥官、副官都忠诚时,为什么三位副官一定一致?

副官都如实转告,每人拿到的是同一组值,只是顺序不同,多数结果必然一样(p.18)。

7. n = 5、m = 2 的反例违反的是哪个条件?

Validity:忠诚指挥官下令进攻,两个忠诚副官都撤退(p.29)。

8. OM(m) 一共跑几轮?

m+1 轮,递归共 m+1 层(p.19)。

下一讲

OM 做到了下界,代价是消息一层层乘上去。下一页算清这笔账,并看 PBFT 怎样把它降到 O(n²)。见 L07d。

下一讲 →
L07d L07d OM 的代价与 PBFT 预告:消息一层层乘上去

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