拜占庭将军问题
Table of Contents
定义
拜占庭共识: 解决有坏人的情况下好人如何达成共识, 是分布式计算领域的一个重要问题。
完整陈述
一个拜占庭军队有 \(n\) 个将军, 其中一个主官领导, 其余 \(n-1\) 个副官, 主官发出消息给副官, 要求:
- 每个将军要么是忠诚的, 要么是叛徒。
- 一个有两种命令: 进攻/撤退。
- 所有的将军通过接收和传递消息(进攻/撤退)通信。
- 所有的忠诚的将军最后要达成共识: 一起进攻或者一起撤退。
结论: 假设叛徒的数量是 \(m\) ,当 \(n \leq 3m\) 时, 无法达成共识, \(n>3m\) 时存在达成共识的构造算法.
很早就见过这个问题, 不过由于大部分版本的证明很容易让人误解, 所以一直没有理解证明. 最近读了一遍原论文: The Byzantine Generals Problem, 条理非常清楚, 终于弄懂了证明. 让我很吃惊的是, 这篇 paper 是发在 TOPLAS(PL/System)上而不是 Theory 相关的期刊上的, 可见"好的工作"既有应用价值也有坚实的理论基础.
算法
以下算法我们称为 OM (Oral Message) 算法,是一个递归式的消息传播算法,执行 \(m\) 轮的 OM 算法叫做 \(OM(m)\) 。 具体流程如下
- 在前向传播过程中,对于每条从根出发的消息传播路径 \(p := g_0 \rightarrow g_1 \rightarrow \cdots g_i\) , 将军 \(g_i\) 把自己当作主官,将它得到的命令发送给不在 \(p\) 中的所有其它将军,进行 \(m\) 轮。
- 在后向收集过程中,每个将军 \(g\) 取其“在前向传播过程中接收到司令的命令” 和 “在下一层中以 \(g\) 结尾的路径做出的决策” 的众数作为每条路径的决策。
最后我们取第一层每个将军的决策做为最终决策。算法图示如下:
前向实箭头表示正向传播,不忠诚的将军可以发送虚假消息(比如给不同的将军发送不同消息);反向虚箭头表示反向收集,指向自己本人。 同一个将军在不同路径下有不同的决策,同一个将军在同一层可以出现多次(前缀不同)。
模拟代码如下:
""" Byzantine Generals Problem, Oral Message(OM) Algorithm Author: expye(Zihao Ye) """ from typing import List, Tuple import argparse import numpy as np from collections import Counter def majority(lst: List): """Note that we should output the same value for [0, 0, 1, 1] and [1, 1, 0, 0]""" c = Counter(sorted(lst)) return c.most_common()[0][0] class General: def __init__(self, truthful: bool) -> None: self._truthful = truthful def __call__(self, input): """If truthful, always output input, otherwise output random value.""" if self._truthful: return input else: return np.random.randint(2) class OralMessage: def __init__(self, generals: List[General], n: int, k: int) -> None: """ Parameters ---------- generals : List[General] The general list. n : int Number of generals. k : int Number of traitors. """ self.generals = generals self.n = n self.k = k # record traces: (path, command, remaining number of rounds) self.trace = [] self.received = {} # received commands of each path started from root self.vote = {} # final vote of each path def propagate(self, ancestors: Tuple[int], command: bool, m: int): """ Regard current node as commander, propagate message for $m$ rounds, and collect traces. Parameters ---------- ancestors : Tuple[int] The message passing path from root to current node. command : bool The command current node received. m : int The remaining number of rounds. """ self.trace.append((ancestors, command, m)) # collect traces. if m > 0: # not in the last round commander = ancestors[-1] for i in range(self.n): if not i in ancestors: # send messages to other generals self.propagate(ancestors + (i,), self.generals[commander](command), m - 1) def gather(self, ordered_trace: List[Tuple[Tuple[int], bool, int]]): """ Back propagation and take majority of received commands of each path as its vote. Parameters ---------- ordered_traces : List[Tuple[Tuple[int], bool, int]] Collected traces sorted by topological order. """ for ancestors, command, m in ordered_trace[:-1]: commander = ancestors[-1] if m == 0: # in the last round, take the command received in forward phase. vote = self.generals[commander](command) # take majority of received (in forward/backward phase) commands else: vote = self.generals[commander]( majority(self.received[ancestors] + [command])) self.vote[ancestors] = vote if len(ancestors) > 1: # update received commands for m-1 level paths j = ancestors[: -2] + (commander,) if not j in self.received: self.received[j] = [] self.received[j].append(vote) if __name__ == '__main__': parser = argparse.ArgumentParser("Byzantine generals simulator.") parser.add_argument('--n', '-n', type=int, help='number of generals') parser.add_argument('--m', '-m', type=int, help='number of runs') parser.add_argument('--k', '-k', type=int, help='number of traitors') args = parser.parse_args() traitors = np.random.choice(args.n, args.k) is_truthful = np.ones(args.n, dtype=np.int32) is_truthful[traitors] = 0 generals = [] for i in range(args.n): generals.append(General(is_truthful[i])) om = OralMessage(generals, args.n, args.k) om.propagate((0,), 1, args.m + 1) om.gather(sorted(om.trace, key=lambda _: _[2])) print('t' if is_truthful[0] else 'f') for i in range(1, args.n): print('t' if is_truthful[i] else 'f', end='') print() for i in range(1, args.n): print(om.vote[(0, i)], end='') print() """ example: python byzantine.py -n 10 -k 3 -m 3 output: t tttftttff 111011101 The commander is a loyal general, and all loyal generals made the same decision: 1. """
用 DFS 递归下去(BFS 也可以), 然后拓扑序收集回来, 时间复杂度为 \(O(n^m)\).
性质及证明
两个性质:
- (IC1): 所有忠诚的将军遵从相同命令
- (IC2): 若司令是忠诚的, 所有忠诚的将军遵从他的命令.
定理:
- \(n > 2k + m\) , 至多 \(k\) 个叛徒, \(OM(m)\) 满足 IC2.
- \(n > 3m\) , 至多 \(m\) 个叛徒, \(OM(m)\) 满足 IC1, IC2.
定理 1
对 \(m\) 使用归纳:
- \(m=0\) 时,没有后向收集过程,每个将军 \(g\) 受司令直接指挥,如果 \(g\) 是忠诚的,将遵从司令的命令。
- \(m>0\) 时,消息从司令 \(c\) 发到每个将军 \(g_i\) 之后,每个将军 \(g_i\) 将以自己为司令,在子树上进行 \(OM(m-1)\) 算法。由于 \(n-1>2k+m-1\) ,由归纳假设得 \(IC2(n-1, k, m-1)\) 是成立的。因此在后向收集过程中,对于每个忠诚的将军,至少有 \(n - k - 1\) 个接收到的指令跟 \(c\) 发送过来的指令是一致的 (一个来自 \(l\) ,至少 \(n - k - 2\) 个来自后向收集)。由前提 \(n > 2k + m\) ,可知 \(n - k - 1 > k + m - 1 \geq k\) ,求众数即可达成共识。
定理 2
定理 2 的 IC2 部分直接带入定理 1 即可, IC1 部分同样对 \(m\) 使用归纳:
- \(m=0\) 时,没有叛徒,所有将军都会遵从司令的命令。
- \(m>0\) 时
- 如果司令是忠诚的,那么由IC2,所有忠诚的将军将遵从司令的命令。
- 司令不忠诚,那么由归纳假设 \(IC1(n-1, m-1)\) 和 \(IC2(n-1, k-1, m-1)\) ,后向收集时所有忠诚将军将得到一样的指令列表,可以达成共识。
下界 1
\(n \leq 3m\)
可以证明当 \(n\leq3m\) 时是无法达成共识的, 过程非常精妙, \(m=1\) 的情况可以用这张图来说明:
2
假设每个节点初始时携带有一个信息 1(相当于主官做了第一轮广播), 其中处于两个状态的节点代表是不诚实的节点, 不带 prime 的节点向外发送 1, 带 prime 的节点向外发送 0.
- 在 case 1 中, \(A,B\) 分别收到:
\ | A | B |
---|---|---|
from A | 1 | 1 |
from B | 1 | 1 |
from C | 0 | 1 |
- 在 case 2 中, \(B',C'\) 分别收到:
\ | B' | C' |
---|---|---|
from A | 0 | 1 |
from B' | 0 | 0 |
from C' | 0 | 0 |
- 在 case 3 中, \(A, C'\) 分别收到:
\ | A | C' |
---|---|---|
from A | 1 | 1 |
from B | 1 | 0 |
from C' | 0 | 0 |
注意到:
- case 1 中 \(A,B\) 必须达成共识, 而 \(A\) 无法区分 case 1 和 case 3, 所以在 case 1 和 case 3 中, \(A\) 会做出相同决策.
- case 2 中 \(A,C\) 必须达成共识, 而 \(C'\) 无法区分 case 2 和 case 3, 所以在 case 2 和 case 3 中, \(C'\) 会做出相同决策.
因此 \(A, B, B', C'\) 均会做出相同决策, 这种情况是平凡的.
证明可以推广至 \(m>1\) 的情形:
前提: 设 \(n=3m\) 时好人可以达成共识.
假设 \(n=3m\) , 将 \(n\) 个节点分为三组 \(S_A, S_B, S_C\) , 假设每组由一个总的处理器控制, 分别为 \(A,B,C\) , 所有节点之间互相传递的消息都经过相应组的总处理器, 总处理器的输出结果为该组达成的共识. 假设 \(A\) 由坏人控制, 那么由前提得 \(S_B, S_C\) 可以达成共识. 此时 \(B,C\) 达成了共识, 与 \(n=3\) 时的结论矛盾.
Footnotes:
Update in 2017.07, after Prof. Elaine Shi's class.