您好,欢迎进入bet韦德官方网站!

咨询服务热线

020-88888888s

“bet韦德官方网站”一文读懂拜占庭将军问题

发布时间:2023-12-31 04:58人气:
本文摘要:拜占庭将军问题(The Byzantine Generals Problem)获取了对分布式共识问题的一种情景化叙述,由Leslie Lamport等人在1982年首次公开发表。

拜占庭将军问题(The Byzantine Generals Problem)获取了对分布式共识问题的一种情景化叙述,由Leslie Lamport等人在1982年首次公开发表。论文《The Byzantine Generals Problem 》同时获取了两种解决问题拜占庭将军问题的算法:· 口信消息型解决方案(A solution with oral message);· 亲笔签名消息型解决方案(A solution with signed message).论文:https://www-inst.eecs.berkeley.edu/~cs162/sp16/static/readings/Original_Byzantine.pdf本文之后将详尽描写这两种算法。事实上,拜占庭将军问题是分布式系统领域最简单的容错模型, 它叙述了如何在不存在蓄意不道德(如消息伪造或假造)的情况下使分布式系统达成协议完全一致。

是我们解读分布式一致性协议和算法的最重要基础。1. 拜占庭将军问题叙述拜占庭将军问题叙述了这样一个场景:拜占庭帝国(Byzantine Empire)军队的几个师驻守在敌城外,每个师都由各自的将军指挥官。将军们不能通过信使互相交流。

在仔细观察敌情之后,他们必需制订一个联合的行动计划,如反攻(Attack)或者后撤(Retreat),且只有当半数以上的将军联合发动反攻时才能取得胜利。然而, 其中一些将军有可能是叛徒,企图制止忠心的将军达成协议完全一致的行动计划。

更加差劲的是,负责管理消息传递的信使也有可能是叛徒,他们有可能伪造或假造消息,也有可能使得消息遗失。为了更为了解的解读拜占庭将军问题,我们以三将军问题为事例展开解释。

当三个将军都忠心时,可以通过投票确认完全一致的行动方案,网卓新闻网,图2展出了一种场景, 即General A,B通过观察敌军军情并融合自身情况辨别可以发动反击,而General C通过观察敌军军情并融合自身情况辨别应该后撤。最后三个将军经过投票表决获得结果为反攻:后撤=2:1, 所以将一起发动反攻取得胜利。对于三个将军,每个将军都能继续执行两种决策(反攻或后撤)的情况下, 共计不存在6中有所不同的场景,图2是其中一种,对于其他5中场景可非常简单地求出,通过投票三个将军都将达成协议完全一致的行动计划。当三个将军中不存在一个叛徒时,将有可能妨碍长时间的登陆作战计划。

图3展出了General C为叛徒的一种场景,他给General A和General B发送到了有所不同的消息,在这种场景下General A通过投票获得反攻:后撤=1:2,最后将做出后撤的行动计划;General B通过投票获得反攻:后撤=2:1,最后将做出反攻的行动计划。结果只有General B发动了反攻并战败。

事实上,对于三个将军中不存在一个叛徒的场景,想总能超过完全一致的行动方案是不有可能的。详尽的证明可参见Leslie Lamport的论文。此外,论文中得出了一个更为普适的结论:如果不存在m个叛将,那么最少必须3m+1个将军,才能最后超过完全一致的行动方案。

2. 解决方案Leslie Lamport在论文中得出了两种拜占庭将军问题的解决方案,即口信消息型解决方案(A solution with oral message)和亲笔签名消息型解决方案(A solution with signed message)。1、口信消息型解决方案首先, 对于口信消息(Oral message)的定义如下:A1. 任何早已发送到的消息都将被准确表达;A2. 消息的接收者告诉是谁发送到了消息;A3. 消息的缺席可以被检测。基于口信消息的定义,我们可以闻, 口信消息无法被伪造但是可以被假造。

基于对图3场景的推论,我们告诉不存在一个叛将时,必需再行减少3个忠将才能超过最后的行动完全一致。为加剧解读,我们将利用3个忠将1个叛将的场景对口信消息型解决方案展开推论。

在口信消息型解决方案中,首先发送到消息的将军称作指挥官,其余将军称作副官。对于3忠1叛的场景必须展开两轮登陆作战信息协商,如果没接到登陆作战信息那么配置文件后撤。

图4是指挥官为忠将的场景,在第一轮登陆作战信息协商中,指挥官向3位副官发送到了反攻的消息;在第二轮中,三位副官再度展开登陆作战信息协商,由于General A、B为忠将,因此他们根据指挥官的消息向另外两位副官发送到了反攻的消息,而General C为叛将,为了妨碍登陆作战计划,他向另外两位副官发送到了后撤的消息。最后Commanding General, General A和B达成协议了完全一致的反攻计划,可以取得胜利。


本文关键词:bet韦德官方网站

本文来源:bet韦德官方网站-www.bafajgroup.com

  • 联系方式
  • 传 真:020-99999999
  • 手 机:12497255309
  • 电 话:020-88888888
  • 地 址:台湾省台湾市台湾区都方大楼61号
友情链接
百度
搜狗
好搜
在线咨询

咨询电话:

020-88888888

  • 微信扫码 关注我们

扫一扫咨询微信客服