拜占庭将军问题
拜占庭将军问题
一、拜占庭将军问题
这个问题提示计算机大神 莱斯利·兰波特在1982年在他论文中描述的一个问题。问题的大概的描述是这样，一组拜占庭的将军去攻打一个城堡。由于条件限制这些将军不能集合在一起攻打城堡，但是为了能攻下城堡，他们通过信使来传递相互之间的关系。他们规定当指定进攻决策的时候只有半数以上的将军同意这个进攻方案，那么这个方案就可以通过。当他们之间可能存在内奸发出错误消息误导其他将军的判断。
二、拜占庭将军需要解决的问题
- 理想情况：
- 假如是三只军队去攻打这个城堡，分别是
A、B、C。在计算攻打城堡的前一天，他们根据各自的实际情况角色是否攻打城堡。假如A将军分别向B、C传达了他这儿是可以进攻的，将军B也根据他所在驻地的实际情况得到结论可以进攻于是分别向A、C传输了经过的命令，但是C这儿情况比较特殊是不能进攻于是C向A、B传达了不能静的命令。最终的结果是A的进攻：不进攻 = 2:1，B的最终结果是进攻：不进攻 = 2:1,C的最终的结果是进攻：不进攻 = 2:1。根据当初的预定由于半数同意进攻这个城堡，那么他们同意的进攻城堡最终攻下城堡。 - 投票示意图：
- 实际情况
- 假如这三个将军中的又一个将军叛变了，假如
C叛变了按照上图的投票过程。他给A的消息是进攻，但是给B的消息是不进攻。这样A看到自己的投票的结果是进攻：不进攻=2:1，B看到自己的结果是进攻：不进攻 = 1:2。这样就会造成状态的不一致，A一只军队去攻打城堡最终被吞没，而B却是原地不动。 - 如何解决在存在叛徒的情况下还可以一致行动呢？
- 口头协议
- 抽象出新的模型：将军-副官模型
- 没有叛变的将会都会执行同一条指令。
- 若将军是忠诚的，所有忠诚的副官都会执行他命令。
- 在论文中提到需要解决有叛变的情况下保持一致的方案是：
如果叛将人数为 m，将军人数不能少于 3m + 1 ，那么拜占庭将军问题就能解决了。这个方法虽然能解决问题但是存在如下的缺点：也就是叛将人数 m，或者说能容忍的叛将数 m，是已知的。在这个算法中，叛将数 m 决定递归循环的次数。时间复杂度是m+1的阶乘。需要进行大量的投票，在分布式环境中就会涉及到大量的网络流量。
- 抽象出新的模型：将军-副官模型
- 根据上述的算法，在军队中有一个将军叛变，为了达到一致性至少需要四只军队。那如何处理呢？把三支军队都抽出一部分组成一支新的军队
D这样就满足算法的条件。看一下算法的执行过程：- 假如
D首先发起进攻的请求，并且D是没有叛变的。D为将军向副官A B C发起进攻请求。 - 除了将军之外的其他的副官相互发起请求，
A询问B收到D给B发送的请求，B回答是进攻。A在询问C收到D给C发送的请求 ，由于C已经叛变为了干扰判断给A的回复是不进攻。这样递归的询问下来最终的结果是A,B的进攻：不进攻 = 2:1,C由于叛变的原因不会执行指令。硬刺A B D一起去攻打了城堡。 - 假如是
C 先发起的作战请求，由于他已经叛变，会分别向 A B发送撤退，D进攻的命令最终投票结果下来A B D都是撤回。
- 假如
- 分析一下出现消息不一致的原因是叛变之后的将军修改了
D发送出来的消息，假如C对消息的任何修改都会被A B察觉到，这样只要对消息进行签名。在接受到被修改之后的消息会被自动的忽略，也就不会对作战的决定造成影响。 - 总结一下：解决这个问题的方法第一增加军队的数量满足算法条件，第二对消息加密检测消息被修改直接忽略。
二、两个军队问题
- 提到拜占庭将军问题,很多小伙伴都会想到两只军队的问题。两只军队问题示意图如下
- 描述：蓝军和白军对垒，蓝军驻军在两个山头白军驻军在山脚。任意一支蓝军都对抗不过白军，但是他们联合起来可以打败白军。假如某一天蓝军打算攻击白军，排人送信给另外一个山头的蓝军。这个山头的蓝军收到之后会给回执但是他不能确定对方有没有收到，还需要等到对方的回执，这样周而复始的。总有一个回执在中间。
三、本质的区别
两军问题是由于通信的信道是不可靠的。而拜占庭将军问题是需要做到军队之间的一致性和将军决策正确性。