什么是拜占庭将军问题?
含义:
简单点说: 拜占庭有 n 个将军,每次命令下发之后,将军之间都会进行信息传递 ,n个将军中会有敌军的叛徒发出误导信息来误导其他将军的判断
, 那么忠诚的将军要在什么样的条件下才能达成信息的一致性 ?
推理过程:
【什么是拜占庭将军问题?】这是前提条件 :
A1. 每个被发送的消息都能够被正确的投递
A2. 信息接收者知道是谁发送的消息
A3. 能够知道缺少的消息
假设存在 n 个叛徒 , 那么在什么情况下各个将军可以达到一致性呢?
假设一: 只有一个将军是忠诚的,那么总共有n+1 个将军 (此种情况肯定是行不通的,一个最简单的例子)
举例:一个将军 给 其他将军传递信息 那么传递信息的数量为 n-1 (自己肯定不用给自己传递信息) 如下图:
文章图片
假设 二: 那么假设最少有 n+1位将军是忠诚的,是否就可以解决了? 此时:将军总数 为 2n+1
解释: 为什么是 n +1 , 如果 是 n 的话会与假设一的情况重合.
如下图 会出现如下两种情况:
文章图片
文章图片
假设三: 最少有
2n + 1
位将军是忠诚的 那么将军的总人数就是3n + 1
解释: 为什么忠诚的将军人数不是 2n 呢? 如果是 2n 明显 会与 假设二重合.
此种情况会出现如下的情况:
文章图片
文章图片
可以明显的看到第二张图相对于第一张图来说就是换了一个位置而已,问题到此得以解决.
这里或许有的人会对第一张图有所疑问:
如果 正确的信息是进攻,而叛徒(司令官) 发的信息如果是撤退,那么结果肯定是撤退啊
对于此问题我想说的是题目的要求是 忠诚将军之间命令达成
一致性
,并不考虑错误信息的情况.总结:
如果有
n
个 叛徒
,那么只要忠诚的将军
人数 最少
为 2n + 1
, 那么忠诚的将军之间就能达成命令的一致性.最后:
能力有限,如果有什么写的不对的地方欢迎给我留言!
推荐阅读
- 热闹中的孤独
- 我要做大厨
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 爱就是希望你好好活着
- 太平之莲
- 为什么你的路演总会超时()
- 知识
- 叙述作文
- 时间老了
- 财商智慧课(六)