Byzantine Generals Problem

论文：Lamport L, Shostak R, Pease M. The Byzantine generals problem[M]//Concurrency: the works of leslie lamport. 2019: 203-226.

拜占庭将军问题

在分布式计算的场景下，不同的处理器计算出不同的结果，但最终需要使得各个处理器达成一致。

拜占庭帝国的将军们在开疆拓土，将军们各领一军。目前他们正在对一个城池商量行动方案，将军们分别观察敌情，利用无噪声信道通信。仅当半数以上的将军同时发起进攻时才会取得胜利，否则应当集体撤退避免失败。

同时，在将军们内部可能会有一些叛徒，叛徒会通过发送一些矛盾的信息来干扰忠诚将军的判断。我们不限制叛徒的能力，他们可以做任何事情。

我们想要解决如下问题：所有的忠诚将军需要确定一致的行动计划，且少量叛徒无法使得忠诚的将军们采取糟糕的行动。我们使用少数服从多数策略进行投票。为了满足上述条件，需要

1. 每个忠诚将军维护相同的消息列表$v(1),\cdots ,v(n)$，这里$v(i)$表示第$i$个将军的决策（注意，$v(i)$不一定从将军$i$处获得，因为叛徒会给出矛盾的信息）。只有消息列表完全一致，在执行$majorty(v(1),\cdots ,v(n))$时得到一致的决策。
2. 如果第$i$个将军是忠诚的，那么他发送的消息$v$应当被其他的忠诚将军用作$v(i)$。实际上，只要忠诚的将军们都采取一致行动，谈不上“attack”和“retreat”哪个更糟。但至少应当避免少量叛徒扭转忠诚将军们的行动计划。

下面，我们考虑简化版本的拜占庭将军问题：$1$个主将发送指令给$n-1$个副将，并满足 the interactive consistency conditions，

• IC1. 所有的忠诚副将获得相同的指令。如果不相同，那么就不满足原始问题的第一个条件。
• IC2. 如果主将是忠诚的，那么所有忠诚副将将获得他的指令。z这就是原始问题的第二个条件。此时，IC1 可由 IC2 自然推出。

原始版本的拜占庭将军问题，可以通过调用$n$次上述问题的解，使得所有的忠诚将军$j\ne i$对某个将军$i$所发送的行动$v(i)$达成一致。然后，将军们各自根据$v(1),\cdots ,v(n)$进行少数服从多数的投票。由于消息列表一致，因此投票结果相同，忠诚的将军们对军事行动达成一致。

口头消息算法

我们先定义口头消息（oral message）通信系统，它满足以下假设

• A1. 消息能够被正确传递（不可篡改）
• A2. 接收者直到某条消息的来源（不可伪造）
• A3. 消息的缺失能够被发现

另外，针对叛徒主将不发送消息的情形，忠诚副将也必须采取某种行动，默认“retreat”。

不可解的情形

首先，我们证明：对于拜占庭三将军问题（即$1$个叛徒$2$个忠诚将军）无解。

如图所示，

1. 如果主将是忠诚的，叛徒副将可以欺诈，使得忠诚的副将$1$接受到矛盾的指令。
2. 如果主将是叛徒，那么另一个忠诚的副将$2$诚实地传递指令，但忠诚副将$1$依然接收到了矛盾的指令。

于是，在图2中的副将$1$无法区分谁是叛徒，他只能选择“attack”。同样的，副将$2$也无法区分谁是叛徒，他只能选择“retreat”。这与 IC1 矛盾。

我们将证明：如果存在$m$个叛徒，那么$n\le 3m$个将军的问题无解。

假设存在这种解，我们称它为阿尔巴尼亚将军（Albanian generals）算法。然后我们让拜占庭将军（Byzantine generals）来模拟这些阿尔巴尼亚将军：拜占庭主将模拟$1$个阿尔巴尼亚主将以及$m-1$个阿尔巴尼亚副将，另外两个拜占庭副将各自模拟$m$个阿尔巴尼亚副将。由于只有一个拜占庭叛徒，因此至多存在$m$个阿尔巴尼亚叛徒。调用阿尔巴尼亚算法，这些阿尔巴尼亚将军是满足 IC1 和 IC2 的。那么，

1. 忠诚的拜占庭将军所模拟的那些阿尔巴尼亚将军都是忠诚的，他们有着一致的行动计划。忠诚的拜占庭副将直接就按照这个计划行动，因此满足 IC1。
2. 如果拜占庭主将是忠诚的，那么阿尔巴尼亚将军是忠诚的，因此忠诚的阿尔巴尼亚将军们的行动计划符合主将的指令。忠诚的拜占庭副将按照忠诚阿尔巴尼亚副将的计划行动，因此满足 IC2。

这就给出了拜占庭三将军问题的一个解。然而，我们已经证明拜占庭三将军问题不可解，矛盾！

解决方案

我们给出 Oral Message algorithms $OM(m)$，这里$m\in \mathbb{N}$，算法用于解决 “存在至多$m$个叛徒，且将军数量$n\ge 3m+1$” 的拜占庭将军问题。

Algorithm $OM(0)$

1. 主将发送指令（“attack”，“retreat”）给每一个副将
2. 每个副将都使用主将发送给他的值，或者在没收到消息时默认为“retreat”

Algorithm $OM(m),m\ge 1$

1. 主将发送指令（“attack”，“retreat”）给每一个副将
2. 对于每一个副将$i$，令$v_i$是他从主将哪里接收到的值（或者默认为“retreat”）。副将$i$作为算法$OM(m-1)$里的主将，将$v_i$发送给其他$n-2$个副将。
3. 对于每一个副将$i$，令$v_j,j\ne i$是第2步中从其他副将（作为主将）哪里获得的值（或默认“retreat”）。最后，副将$i$使用$majority(v_1,\cdots ,v_i,\cdots ,v_{n-1})$作为行动计划。

注意，忠诚的将军都会诚实地执行上述算法，而叛徒会以任意方式执行任何动作。

容易看出，迭代过程形成了一颗树，根节点有$n-1$个分支，第二层节点有$n-2$个分支，等等。算法$OM(m-k)$被反复调用了$(n-1)\cdots (n-k)=A_k^n$次，算法$OM(0)$被调用了$A_m^n$次，通信量还是蛮大的。但可以证明，这些通信都是必要的。

正确性

• 对于任意的$m,k$，算法$OM(m)$都满足 IC2，只要存在至多$k$个叛徒，且将军数量$n>2k+m$

Proof：

基础，当$m=0$时，不存在叛徒，主将忠诚，算法$OM(0)$明显满足 IC2。

假设，$\forall m>0,OM(m-1)$满足 IC2。

归纳，在算法$OM(m)$里的第一步，忠诚的主将下令$v$给$n-1$个副将；然后第二步，各个副将分别执行$OM(m-1)$；根据假设，如果副将$i$是忠诚的，那么其他忠诚副将$j\ne i$将会获得这个副将的命令$v_i=v$，满足 IC2（自然满足 IC1，消息列表一致）；由于$n-1>2k+(m-1)\ge 2k$，因此这些副将中忠诚的占严格多数，因此第三步中忠诚的副将计算$majority(v_1,\cdots ,v_{n-1})=v$，这就是忠诚主将的命令，满足 IC2。

• 对于任意的$m$，算法$OM(m)$都满足 IC1 和 IC2，只要存在至多$m$个叛徒，且将军数量$n>3m$

Proof：

基础，当$m=0$时，当$m=0$时，不存在叛徒，主将忠诚，算法$OM(0)$明显满足 IC2，自然也满足 IC1。

假设，$\forall m>0,OM(m-1)$满足 IC2 和 IC1。

归纳，在算法$OM(m)$里的第一步，主将下令$v$给$n-1$个副将，

1. 如果主将是忠诚的，那么选取$k=m$，$OM(m)$满足 IC2，自然就满足 IC1。
2. 如果主将是叛徒之一，于是副将中的叛徒至多有$m-1$个。第二步，各个副将分别执行$OM(m-1)$，可以证明任意两个忠诚副将所获得的消息$v_j$一致：如果其中一个忠诚副将是$j$，根据假设 IC2，那么另一个忠诚副将就获得了他的值$v_j$，满足IC 1；如果都不是$j$，根据假设 IC1，两个忠诚副将的值相同，也满足 IC1。因此在第二步结束后，所有的忠诚副将都拥有相同的消息列表$v_1,\cdots ,v_{n-1}$，执行$majority$后满足 IC1。

综上所述，$OM(m)$满足 IC1。

签名消息算法

容易看出，正是因为叛徒的强大欺诈能力，使得拜占庭将军问题的解决方案十分困难。下面，使用签名方案来约束其能力：

• A4. 诚实将军的签名无法被伪造，并且可以检测到消息被篡改
• A5. 任何人都可以检验签名的真实性

另外，叛徒们可以互相勾结，互相伪造签名。

这种签名消息（signed messages）在传递的过程中，被将军们不断确认并附加签名，例如$v:i:j$表示，消息$v$被将军$i$发布并签名，然后将军$j$确认接收到了消息$v$并认为$i$的签名合法。

解决方案

在约束叛徒的能力后，拜占庭三将军问题可解！事实上，算法可以处理存在$m$个叛徒的任意数量$n$的拜占庭将军问题。当然$n\ge m+2$问题才有意义。

首先，我们需要一个选择函数$choice$，针对命令集合$V$（相同元素至多出现$1$次）

1. 如果 V = { v } V = \{v\} V={v}，那么$choice(V)=v$
2. 如果$V=\varnothing$，那么$choice(V)=retreat$

一般地，$choice$选择为有序集合$V$的中位元素（the median element）。主将编号为$0$，任意的副将$i\ne 0$都维护着一个命令集合$V_i$，初始化为空集。

Algorithm $SM(m),m\ge 0$

1. 主将发送指令（“attack”，“retreat”）给每一个副将
2. 对于每一个副将$i$，
   1. 如果他接收到形如$v:0$的值，并且$V_i=\varnothing$（之前没接收到其他消息）。设置 V i = { v } V_i = \{v\} Vi​={v}，并且将$v:0:i$发送给其他的所有副将。
   2. 如果它接收到形如$v:0:j_1:\cdots :j_k$的值，并且$v\notin V$（主将是叛徒），将$v$添加到$V$里。若$k<m$，他将$v:0:j_1:\cdots :j_k:i$发送给其他的副将（副将$j_1,\cdots ,j_k$已经获得过命令$v$了）
3. 对于每一个副将$i$，如果确认自己不会再接收到更多消息，就使用$choice(V_i)$作为行动计划。

同样的，忠诚的将军都会诚实地执行上述算法，而叛徒会以任意方式（但被限制了欺诈能力）执行任何动作。

在步骤2里，副将$i$忽略任何不符合正确签名格式的值。对于不合法签名的消息，其来源一定为叛徒。对于叛徒主将不发送消息给副将$i$的情况，忠诚副将$i$不需要做任何动作（不要默认"retreat"，这与口头消息算法不同）。如果叛徒主将不给任何副将发送消息，那么忠诚副将的集合$V_i$都为空集。如果叛徒们只给某一个忠诚副将发消息，忠诚副将将会广播给其他所有副将。如果忠诚副将收到了多个有效的$v_1:0,v_2:0,\cdots$，那么主将一定是叛徒（可能是主将发送了矛盾指令给不同副将，也可以是串通的叛徒副将伪造了命令$v^{\prime }:0$），只要忠诚副将的$V$保证一致即可，来确定最终的行动一致。

在步骤3里，可以使用超时机制（time-out）来确定不会再收到新的消息。

正确性

• 对于任意的$m$，算法$SM(m)$都满足 IC1 和 IC2，只要存在至多$m$个叛徒（将军数量$n\ge m+2$）。

Proof：

1. 如果主将是忠诚的，那么第一步中他发送相同的$v:0$给所有副将。而所有忠诚副将都将接受$v$并写入$V$。另外，叛徒副将无法伪造出$v^{\prime }:0$，因此忠诚副将不会再在$V$中添加指令。因此，所有忠诚副将都将在第三步执行 c h o i c e ( { v } ) = v choice(\{v\}) = v choice({v})=v，满足IC2，此时也满足 IC1。

2. 如果主将是叛徒，我们可以证：第二步结束后，任意两个忠诚副将的集合相等$V_i=V_j$，也就是如果副将$i$获得过$v$，那么副将$j$也一定获得了命令$v$。令副将$i$在接收到$v:0:j_1:\cdots :j_k$时，将$v$添加到了$V_i$里

   1. 如果 j ∈ { j 1 , ⋯   , j k } j \in \{j_1,\cdots,j_k\} j∈{j1​,⋯,jk​}，那么命令$v$曾被副将$j$签名并发布，它早已经被接收并放入$V_j$内
   2. 如果 j ∉ { j 1 , ⋯   , j k } j \not \in \{j_1,\cdots,j_k\} j∈{j1​,⋯,jk​}，
      1. 如果$k<m$，那么副将$i$将会把$v:0:j_1:\cdots :j_k:i$发送给副将$j$，副将$j$的集合$V_j$一定会包含$v$（可能已经存在，也可能新添加）
      2. 如果$k=m$，由于主将是叛徒，因此副将中存在至多$m-1$个叛徒，于是序列$j_1,\cdots ,j_m$中必然包含至少一个忠诚副将，而他一定已经把命令$v$发送给了副将$j$

   因此，所有忠诚副将的命令集合$V_i$都相同，执行$choice$后采取相同的行动计划，符合 IC1。

综上所述，$OM(m)$满足 IC1 和 IC2。

非完全图

前面的口头消息算法和签名消息算法，它们的信道都是支持任意两个将军之间的直接通信的。也就是说，它们的通信网络拓扑是完全图。

Lamport 等人在论文中也给出了针对$p-$正则图的口头消息的解决方案。大体上说，就是根据节点$i$的正则邻居集（regular set of neighbors） N = { i 1 , ⋯   , i p } N=\{i_1,\cdots,i_p\} N={i1​,⋯,ip​}，递归调用算法$OM(m,p)$，一层一层地（到主将的路程）传递命令。根据正则邻居的消息 { v i 1 , ⋯   , v i p } \{v_{i_1},\cdots,v_{i_p}\} {vi1​​,⋯,vip​​}来进行少数服从多数的投票。

具体算法不写了，诸位自行查阅原始论文 o(´^｀)o

信道的建立

在口头消息算法中，需要一个满足A1, A2, A3的信道。在签名消息算法中，额外需要满足A4, A5。

• A1. 对于口头消息算法，信道的故障与处理器的故障没有区别，且连接到同一个处理器的若干信道故障等同于一个处理器的故障。而对于签名消息算法，信道故障无法给出正确的签名，这表现为没有发送合法消息。
• A2. 对于口头消息算法，为了识别消息来源，处理器之间的通信应当为固定的走线，而非通信网络。而对于签名消息算法，A4 和 A5 取代了A2，签名算法保证了身份识别。
• A3. 为了发现消息的缺失，我们需要设置超时机制，确定最大的处理和通信时延，并确定处理器之间的时钟偏差。
• A4. A5. 我们需要一个安全的签名算法。