拜占庭将军问题 The Byzantine Generals problem（一）

拜占庭将军问题 The Byzantine Generals problem（一）

最近看到拜占庭错误和非拜占庭错误的问题，有兴趣看了下论文，做个笔记，不好请轻拍，欢迎指正错误~~
论文：The Byzantine Generals problem[https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf]

问题描述

拜占庭将军问题讲述一群拜占庭将军带兵围城后，在需要相互通信（口头信息）的情况下如何达成一个一致战斗计划的问题，具体要求如下：
A:忠诚将领要达成一致的计划（进攻或者撤退）
B:存在少部分叛徒的情况下，叛徒不能让忠诚的将领们选择了对他们不利的计划（很难形式化什么样的才算是不利的计划，不利的情形很难定义）
在B条件很难操作的情形下，关注A。即忠诚将领要达成一致的计划，且不被叛徒干扰。

定义

v(i) ：第i个将军的信息 ，v(1) ,…,v(n)
将军们观察敌人情况，然后通过互相发送信息（进攻Or撤退）来获得各自的信息，最终的共同计划可以通过 多数票，多数决议决定。

条件A的细化：
1.每个忠诚将领 获得的 v(1) ,…,v(n)相同。
针对B:
2.如果第i个将领是忠诚的，他发送的v(i)必须被每一个忠诚的将领使用。
重写条件1 为：
1’ 任意两个忠诚的将军使用相同的v(i)。

条件1’和2 针对单个将军如何发送他的value给其他人。在关注单点发送命令的情况下。将问题转换为：一个总司令将军发送命令值给其下属：
IC1.所有忠诚的将军遵守相同的命令
IC2.如果司令是忠诚的，那么每一个忠诚的将军要遵守其发送的命令。
IC1和IC2 称为 interactive consistency conditions(相互一致性条件？)。如果将军是忠诚的 IC2可推出IC1。

证明：问题只在忠诚将领人数超过三分之一下有解

证明在口头信息的情形下 3个将军里有一个叛徒（阴影为叛徒）的情况下问题无解。
图一显示了 在司令和其中一个将领是忠诚的情况下，将领1只要简单地遵循命令进攻，就能遵循IC2。

图二显示了在司令为叛徒的情况下，将领1将收到和图一一致情形的信息，将领1无法分辨谁为叛徒的情形下，他只能遵守司令的命令进攻。而将领2也是和将领1相同的情形，遵守将军的命令撤退。从而违反了IC1。

具体的证明使用了反证法（略）。非精确命令下该情形也无解（略）。

问题的解（口头信息情形下）

为了对付m个叛徒至少有3m+1个将军。
假设前提：

1. 信息的发送过程是正确的。
2. 接收信息的人知道谁发出的信息
3. 没有收到信息的情况可以被发现

口头信息算法Oral Message algorithms OM(m), ∀m∈N, m>0，司令向n-1个将领发送命令。算法遵循多数票原则，定义函数 majority（v₁ ,…,v_n-1）的值为其众数。函数majority（v₁ ,…,v_n-1）有以下两个选值情况：

1. 如果存在众数v_i,否则默认值为 撤退 。
2. 选择值中的中位数。

算法使用第一种选值方法：
Algorithm OM(0).
(1)司令发送信息给将领们。
(2)将领们遵循司令命令，如果没有收到则使用 撤退。
Algorithm OM(m)，m>0.
(1)司令发送信息给将领们。
(2)对每一个将领i,令v_i为将领i收到的命令，如果没有收到则使用 撤退。将领i作为算法OM(m-1) 的司令 发送v*_i给余下的n-2个将领。
(3)对每一个 i和j , i <>j,令v_j为第二步（2）将领i从将领j获得的信息，如果没有收到则使用 撤退。领i使用majority（v₁ ,…,v_n-1）的值作为最终命令值。

为了理解算法是如何运行的 ，举例 m=1，n=4的情形。
m=1 的情形下，执行两轮算法 OM(1) ，OM(0).迭代。
图三， OM(1) ，司令发送信息v。OM(0)，针对将领2分析，将领2获得将领1和3发送的信息 从而其确定正确的v = majority（v,v ,x）。

图四，的情况下 每一个忠诚的将领都得到majority（x,y ,z）。

该迭代算法OM(m),调用n-1次算法OM(m-1)，每一个算法OM(m-1)再分别调用n-2次的OM(m-2)，如此至m=0。