公司网站备案,网站建设工作动态,wordpress分类页获取分类名称,设计类专业就业前景怎么样拜占庭将军问题 背景#xff1a;以战国时期为背景 战国时期#xff0c;齐、楚、燕、韩、赵、魏、秦七雄并立#xff0c;后来秦国的势力不断强大起来#xff0c;成了东方六国的共同威胁。于是#xff0c;这六个国家决定联合#xff0c;全力抗秦#xff0c;免得被秦国各个…拜占庭将军问题 背景以战国时期为背景 战国时期齐、楚、燕、韩、赵、魏、秦七雄并立后来秦国的势力不断强大起来成了东方六国的共同威胁。于是这六个国家决定联合全力抗秦免得被秦国各个击破。一天苏秦作为合纵长挂六国相印带着六国的军队叩关函谷驻军在了秦国边境为围攻秦国作准备。但是因为各国军队分别驻扎在秦国边境的不同地方所以军队之间只能通过信使互相联系这时苏秦面临了一个很严峻的问题如何统一大家的作战计划 万一一些诸侯国在暗通秦国发送误导性的作战信息怎么办如果信使被敌人截杀甚至被敌人间谍替换又该怎么办这些都会导致自己的作战计划被扰乱然后出现有的诸侯国在进攻有的诸侯国在撤退的情况而这时秦国一定会趁机出兵把他们逐一击破的。 问题二忠一叛的难题
现有三个国家攻打秦国分别叫齐、楚、燕。同时又因为秦国很强大所以只有半数以上的将军参与进攻才能击败敌人。此时将军们需要通过信使传递消息然后协商一致之后才能在同一时间发动进攻。
正常的情况
例如
齐根据侦查情况决定撤退。楚和燕根据侦查信息决定进攻。
这样最终进攻和撤退的二者的占比为2:1因此最终会执行进攻的命令。
不正常的情况存在叛军恶意节点
假设齐和燕为忠诚将军楚为叛将。现在齐决定撤退、燕决定进攻。而由于楚已经叛变他向齐传达“撤退”的命令向燕传达“进攻”的命令。因此齐看到的结果为进攻:撤退 1:2燕看到的结果为进攻:撤退 2:1。最终就燕自己去进攻秦军了被灭了。
解决方法一口信消息型拜占庭问题之解
三位将军分拨一部分军队由苏秦带领。这样3位将军的作战讨论变成了4位将军的作战讨论这样可以增加讨论中忠诚将军的数量。
然后四位将军约定了如果没有收到命令就执行预设的默认命令例如撤退。需要进行多轮作战信息协商协商的轮次与叛将的数量有关
第一轮
先发送作战信息的将军作为指挥官其他的将军作为副官指挥官将他的作战信息发送给每位副官每位副官将从指挥官处收到的作战信息作为他的作战指令如果没有收到作战信息将把默认的“撤退”作为作战指令。
第二轮
除了第一轮的指挥官外剩余的 3 位将军将分别作为指挥官向另外 2 位将军发送作战信息然后这 3 位将军按照“少数服从多数”执行收到的作战指令。 如果这里需要协商多轮那么除了前面几轮的指挥官外剩余的将军作为指挥官将作战信息发送每位副官。 具体协商过程
分别以忠诚将军和叛将先发送作战信息为例
1、忠诚将军先发送作战信息
假设忠将苏秦先发送作战信息作战指令是“进攻”。那么在第一轮作战协商中苏秦向齐、楚、燕发送作战指令“进攻”意味着齐、楚、燕分别收到了“进攻”的信息并作为自己的作战指令。 在第二轮作战信息协商中齐、楚、燕分别作为指挥官分别向另外两位第一轮指挥官苏秦除外发送作战信息“进攻”。由于楚已经叛变他为了干扰作战计划向另外两位将军发送了“撤退”作战命令。 最终齐和燕收到的作战信息都是“进攻、进攻、撤退”。按照少数服从多数的原则执行“进攻”指令实现了作战计划的一致性。
2、叛将先发送作战信息
当叛将先发送作战消息干扰作战计划时。在第一轮协商中楚向苏秦发送“进攻作战指令”向齐、燕发送“撤退”作战指令。苏秦、齐、燕收到后并将其作为自己的作战指令。 在第二轮作战信息协商中苏秦、齐、燕分别作为指挥官向另外两位发送作战信息。 最终苏秦、齐、燕收到的信息都是“撤退、撤退、进攻”按照少数服从多数的原则执行“撤退”指令实现了作战计划的一致性。 这个算法的前提 如果叛将人数为m将军人数不能少于3m1也就是n位将军最多能容忍n-1/3 位叛将。叛将数m决定递归循环的次数进行多少轮作战信息协商即m1轮。 二忠一叛问题中在存在1位叛将的情况下必须增加1位将军。那么有没有办法在不增加将军人数的时候直接解决二忠一叛的难题可以通过签名消息型拜占庭问题之解进行解决。
解决办法二签名消息型拜占庭问题之解
还可以通过签名的方式在不增加将军人数的情况下解决二忠一叛的难题。签名具有如下的特性
忠诚将军的签名无法伪造而且对他签名消息的内容进行任何更改都会被发现任何人都能验证将军签名的真伪。
与口信消息型拜占庭问题之解类似签名消息型拜占庭问题之解同样需要多轮协商。协商的过程也与口信消息型拜占庭问题之解类似但最终执行作战计划时并不是使用少数服从多数的原则。下面同样以忠诚将军和叛将分别先发送消息为例。
忠诚将军先发送消息
第一轮协商中忠诚将军齐分别向楚和燕发送“进攻”的作战信息燕和楚收到进攻的作战信息后将其作为自己的作战消息。 第二轮协商中楚和燕分别作为指挥官分别向另一位将军第一轮将军除外发送作战信息。叛将楚修改或伪造作战信息将“撤退”信息发送给了燕。那么燕在收到楚的作战信息的时候会发现齐的作战信息被修改楚已经叛变这是燕会忽视来自楚的作战信息最终执行齐发送的作战信息。 叛将先发送消息
第一轮协商中叛将楚向齐发送“撤退”的作战消息向燕发送“进攻”的作战消息。 第二轮协商中燕和齐分别作为指挥官分别向另一位将军第一轮将军除外发送作战信息。此时齐收到了[撤退、进攻]两个作战消息燕收到了[进攻、撤退]两个作战消息。但是齐和燕会按照一定的规则在排序后的所有已接受的指令中选取一个例如按照排序规则后的作战顺序为[进攻撤退]都选择第一个作战计划作战计划进行执行。最终执行一致的作战计划。 齐、燕收到的信息列表是内容是一样的只是顺序不一样使用相同的排序算法选取策略可以保证选取的指令时一样的 这个算法的前提是 1、n位将军最多允许 n-2位叛将。 2、同样需要多轮协商如果叛将数位m那么需要m 1轮协商。 那如何实现签名消息呢
可以使用非对称加密算法如RSA发送方使用哈希算法如MD5进行摘要然后使用私钥对摘要进行加密生成数字签名。然后将加密摘要和消息一起发送给接受方。接受方收到消息和加密摘要后会用公钥对加密摘要进行解密并对消息内容进行摘要将两个摘要进行对比以判断消息是否被篡改。
私钥加密公钥解密。可以保证消息不会被冒充因为私钥是不可泄漏的。如果公钥能正常解密出私钥加密的内容就能证明这个消息是来源于持有私钥身份的人发送的。 感觉使用签名消息型拜占庭问题之解会更消耗算力一点。 小结
将将军作战中的场景与计算机世界的分布式场景进行对应
故事里的将军可以理解为计算机节点。忠诚将军可以理解为正常运行的计算机节点。叛变将军可以理解为出现故障并会发送误导信息的计算机节点。信使被杀可以理解为通讯故障、信息丢失。信使被间谍替换可以理解为通讯被中间人攻击攻击者在恶意伪造信息和劫持通讯。
拜占庭将军问描述的是最困难的也是最复杂的一种分布式故障场景除了存在故障行为还存在恶意行为的场景。因此在存在恶意行为的场景中如数字货币的区块链技术中必须使用拜占庭容错算法Byzantine Fault ToleranceBFT。除了上面提到的两种算法口信消息型拜占庭问题之解、签名消息型拜占庭问题之解常用的拜占庭容错算法还有PBFT算法PoW算法。
在计算机分布式系统中最常用的是非拜占庭容错算法即故障容错算法Crash Fault ToleranceCFT。CFT 解决的是分布式的系统中存在故障但不存在恶意节点的场景下的共识问题。 也就是说这个场景可能会丢失消息或者有消息重复但不存在错误消息或者伪造消息的情况。常见的算法有 Paxos 算法、Raft 算法、ZAB 协议。
参考
分布式协议与算法实战 学习笔记
