前面几篇文章介绍了解决拜占庭将军问题的算法——OM(m)算法和SM(m)算法。但这个两种算法都是在一个将军能够直接与所有其他将军通信的情况下，进行讨论的。这篇文章将移除这个假设，阐述并非所有的将军都能直接通信的情况下，拜占庭将军问题算法的演变。

建模

所有将军组成一个有限简单无向图，图的两个节点的边以为着这两个将军可以直接发消息。现在将OM(m)算法和SM(m)算法从全连接的图扩展到多连接的图。

正则邻居集

为了扩展算法，定义如下概念

定义 1.
(a) 节点的集合{i1,...,ip}$\{i_1,...,i_p\}$被称作节点i$i$的正则邻居集，如果满足：

(i) 每个ij$i_j$是节点i$i$的邻居；
(ii) 对于每个不同于i$i$的节点k$k$，存在开始于ij$i_j$且不经过i$i$的路径rj,k$r_{j,k}$，且任意两个不同的路径除了k$k$之外没有公共节点。

(b) 图G$G$是一个p-正则的，如果每个节点都拥有包含p$p$个不同节点的正则邻居集。

如下图所示，图6是一个3-正则图，而图7不是3-正则图，因为中心的节点不存在包含3个节点的正则邻居集。

OM(m)算法扩展

现在将OM(m)算法进行处理，来解决如果3m$3m$-正则的图G$G$中存在m$m$个叛徒的情况。

注： 3m$3m$-正则的图至少包含3m+1$3m+1$个节点。

算法描述

对于正整数m$m$和p$p$，当图G$G$是p$p$-正则的是，定义算法OM(m, p)

算法： OM(m, p)

(0) 选取司令的一个正则邻居集N$N$，其中N$N$包含p$p$个副官；
(1) 司令发送他的值给N$N$中的每个副官；
(2) 对于N$N$中的每个i$i$，令vi$v_i$为副官i$i$从司令接收到的值；如果没有从司令收到指令，默认选择RETREAT。副官i$i$发送vi$v_i$给每个其他的副官k$k$，如下：

(A) 如果m=1$m=1$，按照路径ri,k$r_{i,k}$发送值。其中，路径的存在由定义1的(a)(ii)部分保证。
(B) 如果m>1$m>1$，副官i$i$当作司令，在除去原来司令的图中运行OM(m−1,p−1)$OM(m-1,p-1)$算法。

(3) 对于每个k$k$和N$N$中的每个i$i$，且i≠k$i\ne k$，令vi$v_i$为副官k$k$在第(2)步中从副官i$i$处收到的值；如果没收到值，则为RETREAT。副官k$k$使用majority(vi1,...,vip)$majority(v_{i_1},...,v_{i_p})$作为他的值，其中N={i1,...,ip}$N=\{i_1,...,i_p\}$。

证明

接下来，要证明OM(m,3m)$OM(m,3m)$可以解决最多只有m个叛徒的拜占庭将军问题。证明过程和OM(m)$OM(m)$算法的证明过程类似。

引理 2 对于任意m>0$m>0$和p≥2k+m$p\ge 2k+m$，当最多有m$m$个叛徒时，算法OM(m,p)$OM(m,p)$满足条件IC2。

证明： 当m=1$m=1$时，一个副官通过majority(v1,...,vp)$majority(v_1,...,v_p)$获得值，其中每个vi$v_i$是由司令通过与发送别的值的路径互斥的路径发送过来的(即每个vi$v_i$的路径互斥)。因为至多有k$k$个叛徒且p≥2k+1$p\ge 2k+1$，因此，一半以上的路径是全部由忠诚的副官组成。因此，如果司令是忠诚的，那么，多于一半的vi$v_i$值是和司令发送的值一致，故满足条件IC2。

当m>1$m>1$时，首先假设在m−1$m-1$时，引理成立，下面证明在m$m$时引理也成立。如果司令是忠诚的，那么N$N$中的每个副官p$p$则会获得正确的值。因为p>2k$p>2k$,所以他们中的多数是忠诚的，根据假设，他们会发送正确的值给每个忠诚的副官。因此，在第(3)步中，每个忠诚的副官将获得的值超过半数是正确的，因此，满足条件IC2$IC2$。引理得证。

定理 3 对于任意m>0$m>0$和p≥3m$p\ge 3m$，当最多有m$m$个叛徒时，算法OM(m,p)$OM(m,p)$能解决拜占庭将军问题。

证明： 根据引理2，令k=m$k=m$，可知OM(m,p)$OM(m,p)$算法满足条件IC2。当司令是忠诚的时，满足条件IC2必然满足条件IC1。所以，只需证明当司令是叛徒时，算法满足条件IC1，也就是说，需要证明在第(3)步时，所有忠诚的副官获得相同的值集。当m=1$m=1$时，因为所有的副官都是忠诚的，且所有路径ri,k$r_{i,k}$不通过司令，所以满足条件IC1。当m>1$m>1$时，因为p≥3m$p\ge 3m$意味着p−1≥3(m−1)$p-1\ge 3(m-1)$，通过简单的归纳即可证明。

可以看出，如果只有3m+1$3m+1$个将军，那么3m-正则的图其实是全连接的图，因此，OM(m)$OM(m)$即OM(m,3m)$OM(m,3m)$，也就是说，OM(m)$OM(m)$算法是OM(m,p)$OM(m,p)$算法的一个特例。

SM(m)算法的扩展

与OM(m)$OM(m)$算法不同，SM(m)$SM(m)$算法可以很容易地扩展到最弱的连接假设。首先来分析如果拜占庭将军问题是可解的需要多少连接。

可解条件分析

因为条件IC2要求忠诚的副官遵守司令的命令，所以，如果司令不能与副官通信时，问题是无解的。尤其是，当司令官发向副官的消息经过叛徒，也是无法保证副官都能收到司令官的命令。同样，如果两个忠诚副官无法通信或者只能通过叛徒进行通信，那么条件IC1也是满足不了的。

对于拜占庭将军问题，如果问题可解那么最弱的连接假设是，由忠诚将军组成的子图是连通的。那么，在这个假设下，无论有多少个叛徒，SM(n−1)$SM(n-1)$都能解决拜占庭将军问题，其中，n$n$为将军的数量。当然，需要将算法修改为将军只发送消息给他的邻居将军。

证明

令图的直径为d$d$，即连接图中任意两点的路径至多包含d$d$条边。

定理 4 对于任意m$m$和d$d$，如果最多存在m个叛徒，且由忠诚将军组成子图的直径为d$d$，那么SM(m+d−1)$SM(m+d-1)$算法能解决拜占庭将军问题。

证明：定理4的证明与SM(m)$SM(m)$算法的证明类似。对于条件IC2，根据假设可知从忠诚的司令到副官i$i$至多经过d−1$d-1$个忠诚副官，这些将军会正确转发消息直到副官i$i$。条件A4保证了叛徒无法仿制一个不同的指令。

对于条件IC1，假设司令是叛徒，需要证明由忠诚副官i$i$收到的指令也会被忠诚的副官j$j$收到。假设副官i$i$收到指令v:0:j1:...:jk$v:0:j_1:...:j_k$，且指令没有被副官j$j$签名。如果k<m$k<m$，那么副官i$i$会将指令发送给他的没有收到指令v$v$邻居，通过至多d−1$d-1$步最终会把值转发给副官j$j$。如果k≥m$k\ge m$，那么消息中j1:...:jk$j_1:...:j_k$中至少有一个副官是忠诚的，那么这个忠诚的副官会将值v$v$发送给副官j$j$。因此，每个忠诚的副官收到的指令集是相同的，通过运行相同的行动函数，忠诚的副官会采取相同的行动。故满足条件IC1。

推论 如果忠诚将军组成的图是连通的，那么SM(n−2)$SM(n-2)$算法能解决拜占庭将军问题。

证明：令d$d$为忠诚将军图的直径。因为一个连通的图的直径小于图的节点的个数，因此，肯定有多于d$d$个的忠诚的将军，有少于n−d$n-d$个的叛徒。令m=n−d−1$m=n-d-1$，根据定理4，推论则成立。

定理4假设忠诚将军组成的子图是连通的。可以很容易将他的证明进行扩展，得出如下结论：即使不是这种情况，如果至多有m$m$个叛徒，算法SM(m+d−1)$SM(m+d-1)$拥有如下属性：

1. 如果任意两个忠诚的将军通过长度至多为d$d$的路径连接，且这个路径只包含忠诚将军，那么这两个忠诚将军遵从相同的指令。
2. 如果司令是忠诚的，任意忠诚将军通过长度至多为m+d$m+d$的路径与司令连接，且路径只包含忠诚将军，那个这个忠诚将军遵从司令的指令。

小结

本文对Leslie经典论文《The Byzantine Generals Problem》的第5部分进行了介绍，讨论了并不是所有的将军都能直接通信的情况下，对OM(m)$OM(m)$和SM(m)$SM(m)$算法的扩展。

论文的第6部分针对构建可靠系统，对假设进行了分析。在此不作介绍，感兴趣的读者可以参考Leslie的原文1。