搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 君其克谢 > 将军们与分布式一致性

将军们与分布式一致性

君其克谢 2019-03-15
举报


分布式一致性是计算机理论中的一个基础专题。两军问题、拜占庭将军问题是最具代表性的两个抽象。

全文共1419字,阅读时间大约12分钟。

将军们与分布式一致性


A
两军问题

“两军问题”是计算机领域的一个思想实验,用来阐述在一个不可靠的通信链路上试图通过通信以达成一致是存在缺陷的和困难的。

这个问题可以描述成红方将军A1、A2,蓝方将军B各占据了一个山谷,而将军A1、A2恰好被将军B隔开。因为B的兵力超过了A1、A2中的任意一个,如果红方的两位将军没有在同一时间进攻,就会导致失败。

故事发生在古代,红方的两位将军只能依靠传令兵交换信息,没有其他通信设备。此外因为传令兵要穿过敌占区可能被俘虏,所以交换的信息可能会丢失。

问:是否存在一个办法,保证红方就进攻时间达成一致,从而避免失败?

将军们与分布式一致性

答:早在1975年Some Constraints and Trade-offs in the Design of Network Communications一文,就对这个问题及其不可能性做出了证明。

精确证明涉及到复杂的数学推导,我们接下来仅从逻辑上分析:

*   因为A1、A2身份是相等的。

不妨假设A1计划“9点”进攻,于是它向A2派去传令兵。

*   当A2收到传令兵的消息后。

同意了A1的计划,于是让传令兵启程复命。

*   当传令兵又回到A1时。

A1知道A2同意了他的计划,但A1仍然不能选择进攻。

*   如果A1贸然进攻。

他可能会面临孤军奋战的风险。因为A2并不知道“A1已经知道A2对消息进行了确认”,这里就像一个悖论。因为传令兵在复命途中仍然存在被拦截的可能,所以从理性的角度,A2并不会选择进攻。

*   两个将军永远没法就某个计划达成一致。



B
拜占庭将军

然后我们来看一个更为著名的拜占庭将军问题。

拜占庭将军们之间的信道是安全的,传令兵不存在被拦截的可能。但将军中间有叛徒,叛徒将军会阻止忠诚的将军们达成一致。

将军们与分布式一致性

这个问题很难,幸运的是1982年Lamport大牛已经证明:在口头消息条件下,如果m个叛徒的拜占庭问题有解,至少还要有2m+1个忠诚的将军才行。这个解决办法叫OM算法。

所谓口头消息,是指将军发送的消息内容不受任何限制,就像是说话一样。所以也没有任何办法(不能使用签名)检验消息的真伪,这种条件下的拜占庭问题是最困难的一种。

接下来我们并不打算对算法做复制粘贴,而将通过4个例子来观察其执行细节。

为了方便描述,不妨假设有一个将军0比较特殊(第一条消息总是由他发出)。

*    3个将军1个叛徒的问题不可解。

我们先考虑最简单的规则,将军们都无条件信任其他将军的信息。在有叛徒的环境中,这肯定很糟糕,因为忠诚的将军可能会被叛徒干扰决策。

将军们与分布式一致性

我们构造了这样两种情况。站在上帝视角,我们知道它们是完全不同的。但站在将军1的视角,他在两种情况下收到的消息是完全相同的,所以即使再复杂的办法也不能帮他区分出来。

*    4个将军1个叛徒的问题通过1次信息交换解决。

此种条件下最复杂的情况莫过于将军0是叛徒。正是由于叛徒的误导信息R,才导致了将军2的行为与其他将军不一致。

将军们与分布式一致性

于是我们增加一次信息交换,将军2并不直接采纳从将军0处来的信息,他还会综合考虑将军1、2处来的信息。

opnion(2)=majority(v012,v02,v032)=A

将军2的决策被多数正确将军纠正了过来!

*    7个将军2个叛徒的问题通过1次信息交换无解。

我们构造了反例如下:


*    7个将军2个叛徒的问题通过2次信息交换解决。

如果你仔细看上图中的公式,就会发现造成将军1、2决定不一致的原因在于v031与v032这两个节点的信息被叛徒3搅乱了。

于是我们再次增加一次信息交换。


仅关注叛徒3为根的这棵子树。

这颗子树其实等价于“6将军1叛徒”问题,它是“4将军1叛徒”的relax版,采取类似的方法完全可以解决。因此v031-v036是可以达成一致的,继而也消灭了将军1、2的不一致。

至此,我们可以看出该OM算法的本质其实就是不断增加信息交换次数,以减少叛徒的“误导”对决策的影响。

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《将军们与分布式一致性》的版权归原作者「君其克谢」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注君其克谢微信公众号

君其克谢微信公众号:gh_636c56542349

君其克谢

手机扫描上方二维码即可关注君其克谢微信公众号

君其克谢最新文章

精品公众号随机推荐

举报