前言
在分布式系统中交换信息, 部分成员可能出错导致发送了错误的信息, 在这种情况下如何达成共识. 这就是拜占庭将军问题所要解决的.
问题的简要描述如下:
- 3个军队协同作战(为了简单易懂, 以3个军队描述)
- 每支军队的作战策略有两种"进攻"和"撤退"
- 每个军队之间通过信使传递消息
- 问: 如何达成共识制定统一的作战策略呢?
简单, 只要他们两两交换信息, 然后少数服从多数就可以咯.
交换信息之后, 每人收到的进攻:撤退=2:1
, 则最终统一策略进攻.
但是, 在拜占庭将军问题中, 可能会有错误信息, 也就是叛军的出现. 如果B
发送信息时做了手脚, 分别发送不同的策略:
这样一来, A
收到的进攻:撤退=2:1
, 最终决定进攻
. 而C
收到的进攻:撤退=1:2
, 最终决定撤退
. 就会导致最终行为不一致了.
上面这个行为对应到计算机系统中, 将军
就是计算机, 消息的传递对应了通讯系统, 叛军
则对应了恶意节点.
那么对应到计算机领域中, 描述的就是这样一个问题: 在分布式系统中, 可能存在故障节点, 也可能存在恶意节点, 如何保证系统行为的一致性.
如何解决这个困境呢?
口信消息
在这篇论文中描述了这个问题并给出了作者的解决方案(全英文我也没咋看懂).
在这里就是再增加一个军队, 然后首先发出指令的是指挥官, 指挥官负责下发作战指令, 下属部队接收后再进行信息交换, 判断大家接收到的指令是否一致. 流程大致如下:
其中在第二步交换少数服从多数, 是为了防止指挥官是叛军, 给大家发送了不同的指令.
如此一来, 无论ABCD 哪个出现问题, 另外3个都可以保持相同的策略. (你可以尝试着令其中任意一个叛变).
为什么要4个军队??
如果是3个军队的话, 其中C
是叛军, 那么可能出现这样的情况:
当C
收到进攻的命令后, 故意在信息交换时发送撤退. 此时, B
收到的命令就是进攻:撤退=1:1
. 无法抉择A
和C
哪个有问题, 最终会导致A
和B
采用不同的策略. (若A
是叛军同理)
从这里可以看出, 当军队数量为4时, 叛军数量不能大于1. 或者用论文中的结论: 若叛军数量为 m
, 则将军数量需大于3m
.
2个叛军的情况
根据之前的描述, 若叛军数量为2, 则将军数量最少为7. 在这种情况下如何保证行为的一致性呢?
第一步: 指挥官先下发本次作战指令:
但是很不幸, 其中A/B
都是叛军. 此时, 若仍然按照上面所述进行在下属不对中进行情报交换, 则可能出现这样的情况(其中B
也是叛军, 会传递错误情报):
C
收到的情报, 进攻的:A/B/D/G
, 撤退的:E/F
, 则最终进攻E
收到的情报, 进攻的:C/D/G
, 撤退的:A/B/F
. 票数持平- 最终会导致
C
和E
的决策不一致.
那么如何处理这种情况呢? 嵌套交换情报, 这里拿C
举例, C
为了确保D
发送给自己的情报准确, 会询问每个人D
发出的情报是什么:
在C
获取D
的情报时, 其实就相当于将D
当做了指挥官, 下属又交换了一轮情报.
如此一来, C
获取到的情报中, B
可能是进攻, 也可能是撤退, 如果B=进攻
, 则进攻:撤退=4:2
(还有 A 的一票为进攻), 最终进攻. 若B=撤退
, 则进攻:撤退=3:3
. 未选出结果. 可以重新选择指挥官再次投票.
那么每个人收到的命令可能不一致么? 依据少数服从多数, DEFG
的结果可能是正确的. 对于B
来说, 无论他发送给他人的策略是什么, 经过这一轮协商, 大家最终会得到一个统一的策略.
如果叛军不是指挥官呢?, 你可以尝试一下, 结果更为清晰, 且不会出现平票的情况.
多个叛军的情况
在2个叛军的情况下, 进行了2轮协商拿到了最终的决策. 如果叛军数量是 m, 则需要协商 m 轮才能得出结论. 碍于篇幅, 在这里就不细述了.
从这里也能看出这个算法的效率并不高, 随着叛军数量的增加, 算法的效率也会随之变动.
消息签名
有关数字签名的原理可查看这篇文章.
思路也很简单, 在每个消息中增加签名信息, 保证消息无法伪造. 还是回到上面的消息传递场景, 交换流程大致如下:
因为消息中带有签名信息, 他人无法伪造. 因此:
- 若
B
出现问题, 篡改了A
的消息, 则C
立即会发现 - 若
A
出现问题, 发送给两人不同的指令, 则B/C
便会发现. 此时可以先解决叛军, 再重新商议. - 若
A/B
都出现问题了, 系统中超过半数都是恶意节点, 已然不正常了.
如果在环境中各个节点都是可以信赖的, 不存在篡改消息或伪造消息等恶意行为, 推荐使用非拜占庭算法, 即故障容错算法. 在这种环境中, 可能存在消息丢失/重复 等问题, 但不会发生消息的篡改. (这种算法后面有时间再研究)
但是可能存在恶意节点的系统中(比如区块链), 就必须使用拜占庭算法了.
针对拜占庭问题, 大佬们又陆续提出了些其他的解决方案, 比如FTMP, BFT
等. 不过我只是为了涉猎, 没有深入了解.
原文地址: https://hujingnb.com/archives/881
标签:叛军,将军,交换,撤退,问题,进攻,拜占庭,情报 From: https://www.cnblogs.com/hujingnb/p/17020334.html