拜占庭将军问题最终想解决的是什么（拜占庭将军问题图解）
2022-12-20
拜占庭将军问题（Byzantine Generals Problem，是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错问题。
在分布式计算中，不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。
莱斯利·兰波特在其论文中描述了如下问题：
一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。
系统的问题在于，将军中可能出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。
由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。
假始那些忠诚（或是没有出错）的将军仍然能通过多数决定来决定他们的战略，便称达到了拜占庭容错。在此，票都会有一个默认值，若消息（票）没有被收到，则使用此默认值来投票。
上述的故事映射到计算机系统里，将军便成了计算机，而信差就是通信系统。虽然上述的问题涉及了电子化的决策支持与信息安全，却没办法单纯的用密码学与数字签名来解决。因为不正常的电压仍可能影响整个加密过程，这不是密码学与数字签名算法在解决的问题。因此计算机就有可能将错误的结果提交去，亦可能导致错误的决策。在分布式对等网络中需要按照共同一致策略协作的成员计算机即为问题中的将军，而各成员计算机赖以进行通讯的网络链路即为信使。拜占庭将军问题描述的就是某些成员计算机或网络链路出现错误、甚至被蓄意破坏者控制的情况。
求解拜占庭将军问题，隐含要满足以下两个条件：
1）每个忠诚的将军必须收到相同的命令值vi（vi是第i个将军的命令）。
2）如果第i个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的vi相同。
于是，拜占庭将军问题的可以描述为：一个发送命令的将军要发送一个命令给其余n-1个将军，使得：
IC1.所有忠诚的接收命令的将军遵守相同的命令；
IC2.如果发送命令的将军是忠诚的，那么所有忠诚的接收命令的将军遵守所接收的命令。
兰波特对拜占庭将军问题的研究表明 ，当n>3m时，即叛徒的个数m小于将军总数n的1/3时，通过口头同步通信（假设通信是可靠的），可以构造同时满足IC1和IC2的解决方案，即将军们可以达成一致的命令。但如果通信是可认证、防篡改伪造的（如采用PKI认证，消息签名等），则在任意多的叛徒（至少得有两个忠诚将军）的情况下都可以找到解决方案。
而在异步通信情况下，情况就没有这么乐观。
菲舍尔·林奇·帕特森定理证明了，只要有一个叛徒存在，拜占庭将军问题就无解 。翻译成分布式计算语言，在一个多进程异步系统中，只要有一个进程不可靠，那么就不存在一个协议，此协议能保证有限时间内使所有进程达成一致。
由此可见，拜占庭将军问题在一个分布式系统中，是一个非常有挑战性的问题。因为分布式系统不能依靠同步通信，否则性能和效率将非常低。因此寻找一种实用的解决拜占庭将军问题的算法一直是分布式计算领域中的一个重要问题。
在这里，我们先给出分布式计算中有关拜占庭缺陷和故障的两个定义：
定义1： 拜占庭缺陷（Byzantine Fault）：
任何观察者从不同角度看，表现出不同症状的缺陷。
定义2： 拜占庭故障（Byzantine Failure）：
在需要共识的系统中由于拜占庭缺陷导致丧失系统服务。
在分布式系统中，不是所有的缺陷或故障都能称作拜占庭缺陷或故障。像死机、丢消息等缺陷或故障不能算为拜占庭缺陷或故障。拜占庭缺陷或故障是最严重缺陷或故障，拜占庭缺陷有不可预测、任意性的缺陷，例如遭黑客破坏，中木马的服务器就是一个拜占庭服务器。
在一个有拜占庭缺陷存在的分布式系统中，所有的进程都有一个初始值。在这种情况下，共识问题（Consensus Problem），就是要寻找一个算法和协议，使得该协议满足以下三个属性。
1）一致性（Agreement）：所有的非缺陷进程都必须同意同一个值。
2）正确性（Validity）：如果所有的非缺陷的进程有相同的初始值，那么所有非缺陷的进程所同意的值必须是同一个初始值。
3）可结束性（Termination）：每个非缺陷的进程必须最终确定一个值。
根据菲舍尔·林奇·帕特森的理论，在异步通信的分布式系统中，只要有一个拜占庭缺陷的进程，就不可能找到一个共识算法，可同时满足上述要求的一致性、正确性和可结束性要求。在实际情况下，根据不同的假设条件，有很多不同的共识算法被设计出来。这些算法各有优势和局限。算法的假设条件有以下几种情况：
1）故障模型：非拜占庭故障/拜占庭故障。
2）通信类型：同步/异步。
3）通信网络连接：节点间直连数。
4）信息发送者身份：实名/匿名。
5）通信通道稳定性：通道可靠/不可靠。
6）消息认证性：认证消息/非认证消息。
