拜占庭将军核心描述：军中可能有叛徒、却要保证进攻一致、由此发展成容错理论
问题场景：拜占庭将军想要攻打一个强大的敌人、派出十只军队去包围敌人、敌人虽不比拜占庭将军、但也足以抵御5支常规军队的同时袭击、所以十只军队必须在分开的包围状态下同时攻击、除非至少6支军队同时进攻才能攻下敌人、拜占庭军队只能依靠通信兵来协商进攻意向及进攻时间、他们却不确定是否有叛徒、他们能否找到一个分布式的协议来让他们远程协商？这就是拜占庭问题
拜占庭将军问题并不去考虑通信兵是否会截取或无法传达信息、及传递消息的信道没有问题、在研究拜占庭将军问题的时候我们假设这个信道是没有问题的、并在这个前提下 我们研究一致性和容错性、如果考虑到信道有问题就涉及到了另外一个问题：两军问题
算法推演：
定义变量vi、作为其他将军收到的第i个将军的命令值、i将军会把自己的判断作为vi、由于叛徒的存在、各将军收到的vi值肯定不同、在定义一个函数来处理向量（v1,v2...vn）、代表了多数人的意见、各将军用这个函数的结果作为自己最终采用的命令
1、一致性
条件1：每一个忠诚的将军必须得到相同的指向指令（v1,v2...vn）或者指令集合 ---意味着忠诚的将军不一定使用i将军送来的信息指令vi、i将军也可能是叛徒、但是忠诚的将军送来的信息也可能被修改、会影响正确性
因为下面的条件2是针对单个将军、这个条件针对的是所有将军、所以我们可以改写为：
条件1：无论将军i是忠诚或是叛徒、任何两个忠诚的将军都使用相同的vi
2、正确性
条件2：若i将军是忠诚的、那其他将军必须以他送出的值作为vi
综上、问题可以简化为 一个将军i如何帮别的将军接受自己送出的值vi
也可以转换成 司令---副官 模式：
LC1：所有忠诚的副官遵守一个命令、即一致性
LC2：若司令是忠诚的、每一个忠诚的副官遵守它发出的命令、即正确性
司令副官模式下达的命令得到了有效的传达、有意义的将军会作为司令发起新的司令副官模式
拜占庭问题只要满足上面的LC1 LC2就代表算法可以解决拜占庭问题
经典模式下、有两种方法：口头协议和书面协议
口头协议：
第一轮：将军会把消息发送给所有的副官、第i个副官收到的记为Vi、
第二轮：第i个副官会怀疑将军发来的消息Vi是对还是错、于是他会问其余的副官、这样他就会得到（n-2）个副官的值、从i到i-1、没个副官都会得到剩下的n-2个副官的值vi、此时、忠诚的副官j会把子集的vj发送给其他人、而叛徒则会发送假消息
OM算法
OM（m）
1、司令将他的命令发送给每个副官
2、对于每个i、vi是每个副官i从司令那里收到的命令、如果没有命令则认为撤退、副官i在OM（m-1）中作为发令者将之发送给另外n-2个副官
3、对于每个i、和每个 j != i 、vj是副官i从第二步中的副官j（使用OM（m-1）算法）发送过来的命令、如果没收到则认为撤退、最后副官使用majority(v1...vn-1)得到命令
majority代表大多数人的命令、若不存在则认为撤退
这是一个递归算法、m代表多少个叛徒、所以说对于每个将军则至少需要m+1轮的算法才能完成
该算法保证在叛徒数量达到一个最大值（总将军数量的3/1）之下时、拜占庭问题可解
解释：
当m=1 n=3时
m=1 n=4时
当 m=2 n=7时（虽然只是多了一个叛徒、但是会出现递归）分两种情况、两个副官为叛徒、一个副官和一个司令是叛徒
两个副官为叛徒
两个副官为叛徒
司令和副官各一个叛徒
司令和副官各一个叛徒
很多系统都会出现口头协议的情况、即各个节点可以把自己的消息准确的发送出去、同时可以知道消息的来源、但是这个口头协议并不能追奔朔源、必须在四模冗余以上才能保证争取、由此引出书面协议
下一节介绍书面协议
网友评论