拜占庭将军问题(四)——非全连接下的算法演变
前面几篇文章介绍了解决拜占庭将军问题的算法——OM(m)算法和SM(m)算法。但这个两种算法都是在一个将军能够直接与所有其他将军通信的情况下,进行讨论的。这篇文章将移除这个假设,阐述并非所有的将军都能直接通信的情况下,拜占庭将军问题算法的演变。
建模
所有将军组成一个有限简单无向图,图的两个节点的边以为着这两个将军可以直接发消息。现在将OM(m)算法和SM(m)算法从全连接的图扩展到多连接的图。
正则邻居集
为了扩展算法,定义如下概念
定义 1.
(a) 节点的集合被称作节点的正则邻居集,如果满足:(i) 每个是节点的邻居;
(ii) 对于每个不同于的节点,存在开始于且不经过的路径,且任意两个不同的路径除了之外没有公共节点。(b) 图是一个p-正则的,如果每个节点都拥有包含个不同节点的正则邻居集。
如下图所示,图6是一个3-正则图,而图7不是3-正则图,因为中心的节点不存在包含3个节点的正则邻居集。
OM(m)算法扩展
现在将OM(m)算法进行处理,来解决如果-正则的图中存在个叛徒的情况。
注: -正则的图至少包含个节点。
算法描述
对于正整数和,当图是-正则的是,定义算法OM(m, p)
算法: OM(m, p)
(0) 选取司令的一个正则邻居集,其中包含个副官;
(1) 司令发送他的值给中的每个副官;
(2) 对于中的每个,令为副官从司令接收到的值;如果没有从司令收到指令,默认选择RETREAT。副官发送给每个其他的副官,如下:(A) 如果,按照路径发送值。其中,路径的存在由定义1的(a)(ii)部分保证。
(B) 如果,副官当作司令,在除去原来司令的图中运行算法。(3) 对于每个和中的每个,且,令为副官在第(2)步中从副官处收到的值;如果没收到值,则为RETREAT。副官使用作为他的值,其中。
证明
接下来,要证明可以解决最多只有m个叛徒的拜占庭将军问题。证明过程和算法的证明过程类似。
引理 2 对于任意和,当最多有个叛徒时,算法满足条件IC2。
证明: 当时,一个副官通过获得值,其中每个是由司令通过与发送别的值的路径互斥的路径发送过来的(即每个的路径互斥)。因为至多有个叛徒且,因此,一半以上的路径是全部由忠诚的副官组成。因此,如果司令是忠诚的,那么,多于一半的值是和司令发送的值一致,故满足条件IC2。
当时,首先假设在时,引理成立,下面证明在时引理也成立。如果司令是忠诚的,那么中的每个副官则会获得正确的值。因为,所以他们中的多数是忠诚的,根据假设,他们会发送正确的值给每个忠诚的副官。因此,在第(3)步中,每个忠诚的副官将获得的值超过半数是正确的,因此,满足条件。引理得证。
定理 3 对于任意和,当最多有个叛徒时,算法能解决拜占庭将军问题。
证明: 根据引理2,令,可知算法满足条件IC2。当司令是忠诚的时,满足条件IC2必然满足条件IC1。所以,只需证明当司令是叛徒时,算法满足条件IC1,也就是说,需要证明在第(3)步时,所有忠诚的副官获得相同的值集。当时,因为所有的副官都是忠诚的,且所有路径不通过司令,所以满足条件IC1。当时,因为意味着,通过简单的归纳即可证明。
可以看出,如果只有个将军,那么3m-正则的图其实是全连接的图,因此,即,也就是说,算法是算法的一个特例。
SM(m)算法的扩展
与算法不同,算法可以很容易地扩展到最弱的连接假设。首先来分析如果拜占庭将军问题是可解的需要多少连接。
可解条件分析
因为条件IC2要求忠诚的副官遵守司令的命令,所以,如果司令不能与副官通信时,问题是无解的。尤其是,当司令官发向副官的消息经过叛徒,也是无法保证副官都能收到司令官的命令。同样,如果两个忠诚副官无法通信或者只能通过叛徒进行通信,那么条件IC1也是满足不了的。
对于拜占庭将军问题,如果问题可解那么最弱的连接假设是,由忠诚将军组成的子图是连通的。那么,在这个假设下,无论有多少个叛徒,都能解决拜占庭将军问题,其中,为将军的数量。当然,需要将算法修改为将军只发送消息给他的邻居将军。
证明
令图的直径为,即连接图中任意两点的路径至多包含条边。
定理 4 对于任意和,如果最多存在m个叛徒,且由忠诚将军组成子图的直径为,那么算法能解决拜占庭将军问题。
证明:定理4的证明与算法的证明类似。对于条件IC2,根据假设可知从忠诚的司令到副官至多经过个忠诚副官,这些将军会正确转发消息直到副官。条件A4保证了叛徒无法仿制一个不同的指令。
对于条件IC1,假设司令是叛徒,需要证明由忠诚副官收到的指令也会被忠诚的副官收到。假设副官收到指令,且指令没有被副官签名。如果,那么副官会将指令发送给他的没有收到指令邻居,通过至多步最终会把值转发给副官。如果,那么消息中中至少有一个副官是忠诚的,那么这个忠诚的副官会将值发送给副官。因此,每个忠诚的副官收到的指令集是相同的,通过运行相同的行动函数,忠诚的副官会采取相同的行动。故满足条件IC1。
推论 如果忠诚将军组成的图是连通的,那么算法能解决拜占庭将军问题。
证明:令为忠诚将军图的直径。因为一个连通的图的直径小于图的节点的个数,因此,肯定有多于个的忠诚的将军,有少于个的叛徒。令,根据定理4,推论则成立。
定理4假设忠诚将军组成的子图是连通的。可以很容易将他的证明进行扩展,得出如下结论:即使不是这种情况,如果至多有个叛徒,算法拥有如下属性:
- 如果任意两个忠诚的将军通过长度至多为的路径连接,且这个路径只包含忠诚将军,那么这两个忠诚将军遵从相同的指令。
- 如果司令是忠诚的,任意忠诚将军通过长度至多为的路径与司令连接,且路径只包含忠诚将军,那个这个忠诚将军遵从司令的指令。
小结
本文对Leslie经典论文《The Byzantine Generals Problem》的第5部分进行了介绍,讨论了并不是所有的将军都能直接通信的情况下,对和算法的扩展。
论文的第6部分针对构建可靠系统,对假设进行了分析。在此不作介绍,感兴趣的读者可以参考Leslie的原文1。
- Lamport L, Shostak R, Pease M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 382-401. ↩