分布式协议与算法——拜占庭将军问题

这篇具有很好参考价值的文章主要介绍了分布式协议与算法——拜占庭将军问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

拜占庭将军问题

背景:以战国时期为背景

战国时期,齐、楚、燕、韩、赵、魏、秦七雄并立,后来秦国的势力不断强大起来,成了东方六国的共同威胁。于是,这六个国家决定联合,全力抗秦,免得被秦国各个击破。一天,苏秦作为合纵长,挂六国相印,带着六国的军队叩关函谷,驻军在了秦国边境,为围攻秦国作准备。但是,因为各国军队分别驻扎在秦国边境的不同地方,所以军队之间只能通过信使互相联系,这时,苏秦面临了一个很严峻的问题:如何统一大家的作战计划?

万一一些诸侯国在暗通秦国,发送误导性的作战信息,怎么办?如果信使被敌人截杀,甚至被敌人间谍替换,又该怎么办?这些都会导致自己的作战计划被扰乱,然后出现有的诸侯国在进攻,有的诸侯国在撤退的情况,而这时,秦国一定会趁机出兵,把他们逐一击破的。

问题:二忠一叛的难题

现有三个国家攻打秦国,分别叫齐、楚、燕。同时,又因为秦国很强大,所以只有半数以上的将军参与进攻,才能击败敌人。此时,将军们需要通过信使传递消息,然后协商一致之后,才能在同一时间发动进攻。

正常的情况:

例如:

  1. 齐根据侦查情况决定撤退。
  2. 楚和燕根据侦查信息,决定进攻。

这样最终进攻和撤退的二者的占比为2:1,因此最终会执行进攻的命令。

不正常的情况,存在叛军(恶意节点):

假设齐和燕为忠诚将军,楚为叛将。现在齐决定撤退、燕决定进攻。而由于楚已经叛变,他向齐传达“撤退”的命令,向燕传达“进攻”的命令。因此齐看到的结果为:进攻:撤退 = 1:2;燕看到的结果为:进攻:撤退 = 2:1。最终就燕自己去进攻秦军了,被灭了。

解决方法一:口信消息型拜占庭问题之解

三位将军分拨一部分军队,由苏秦带领。这样3位将军的作战讨论,变成了4位将军的作战讨论,这样可以增加讨论中忠诚将军的数量。

然后,四位将军约定了,如果没有收到命令,就执行预设的默认命令,例如撤退。需要进行多轮作战信息协商(协商的轮次与叛将的数量有关):

第一轮:

  • 先发送作战信息的将军作为指挥官,其他的将军作为副官;
  • 指挥官将他的作战信息发送给每位副官;
  • 每位副官,将从指挥官处收到的作战信息,作为他的作战指令;如果没有收到作战信息,将把默认的“撤退”作为作战指令。

第二轮:

  • 除了第一轮的指挥官外,剩余的 3 位将军将分别作为指挥官,向另外 2 位将军发送作战信息;
  • 然后,这 3 位将军按照“少数服从多数”,执行收到的作战指令。

如果这里需要协商多轮,那么除了前面几轮的指挥官外,剩余的将军作为指挥官将作战信息发送每位副官。

具体协商过程:

分别以忠诚将军和叛将先发送作战信息为例:

1、忠诚将军先发送作战信息:

假设忠将苏秦先发送作战信息,作战指令是“进攻”。那么在第一轮作战协商中,苏秦向齐、楚、燕发送作战指令“进攻”,意味着齐、楚、燕分别收到了“进攻”的信息,并作为自己的作战指令

分布式协议与算法——拜占庭将军问题,分布式协议与算法,分布式,算法

第二轮作战信息协商中,齐、楚、燕分别作为指挥官,分别向另外两位(第一轮指挥官苏秦除外)发送作战信息“进攻”。由于楚已经叛变,他为了干扰作战计划,向另外两位将军发送了“撤退”作战命令。

分布式协议与算法——拜占庭将军问题,分布式协议与算法,分布式,算法

最终,齐和燕收到的作战信息都是“进攻、进攻、撤退”。按照少数服从多数的原则,执行“进攻”指令,实现了作战计划的一致性。

2、叛将先发送作战信息:

当叛将先发送作战消息,干扰作战计划时。在第一轮协商中,楚向苏秦发送“进攻作战指令”,向齐、燕发送“撤退”作战指令。苏秦、齐、燕收到后并将其作为自己的作战指令

分布式协议与算法——拜占庭将军问题,分布式协议与算法,分布式,算法

在第二轮作战信息协商中,苏秦、齐、燕分别作为指挥官,向另外两位发送作战信息。

分布式协议与算法——拜占庭将军问题,分布式协议与算法,分布式,算法

最终苏秦、齐、燕收到的信息都是“撤退、撤退、进攻”,按照少数服从多数的原则,执行“撤退”指令,实现了作战计划的一致性。

这个算法的前提:

  1. 如果叛将人数为m,将军人数不能少于3m+1(也就是:n位将军,最多能容忍(n-1)/3 位叛将)。
  2. 叛将数m决定递归循环的次数(进行多少轮作战信息协商),即m+1轮。

二忠一叛问题中,在存在1位叛将的情况下,必须增加1位将军。那么有没有办法在不增加将军人数的时候,直接解决二忠一叛的难题?可以通过签名消息型拜占庭问题之解进行解决。

解决办法二:签名消息型拜占庭问题之解

还可以通过签名的方式,在不增加将军人数的情况下,解决二忠一叛的难题。签名具有如下的特性:

  • 忠诚将军的签名无法伪造,而且对他签名消息的内容进行任何更改都会被发现;
  • 任何人都能验证将军签名的真伪。

与口信消息型拜占庭问题之解类似,签名消息型拜占庭问题之解同样需要多轮协商。协商的过程也与口信消息型拜占庭问题之解类似,但最终执行作战计划时并不是使用少数服从多数的原则。下面同样以忠诚将军和叛将分别先发送消息为例。

忠诚将军先发送消息

第一轮协商中,忠诚将军齐分别向楚和燕发送“进攻”的作战信息,燕和楚收到进攻的作战信息后将其作为自己的作战消息。

分布式协议与算法——拜占庭将军问题,分布式协议与算法,分布式,算法

第二轮协商中,楚和燕分别作为指挥官分别向另一位将军(第一轮将军除外)发送作战信息。叛将楚修改或伪造作战信息,将“撤退”信息发送给了燕。那么燕在收到楚的作战信息的时候,会发现齐的作战信息被修改,楚已经叛变,这是燕会忽视来自楚的作战信息,最终执行齐发送的作战信息。

分布式协议与算法——拜占庭将军问题,分布式协议与算法,分布式,算法

叛将先发送消息

第一轮协商中,叛将楚向齐发送“撤退”的作战消息,向燕发送“进攻”的作战消息。

分布式协议与算法——拜占庭将军问题,分布式协议与算法,分布式,算法

第二轮协商中,燕和齐分别作为指挥官分别向另一位将军(第一轮将军除外)发送作战信息。此时齐收到了[撤退、进攻]两个作战消息,燕收到了[进攻、撤退]两个作战消息。但是齐和燕会按照一定的规则在排序后的所有已接受的指令中选取一个(例如按照排序规则后的作战顺序为[进攻,撤退],都选择第一个作战计划)作战计划进行执行。最终执行一致的作战计划。

齐、燕收到的信息列表是内容是一样的,只是顺序不一样,使用相同的排序算法,选取策略,可以保证选取的指令时一样的

分布式协议与算法——拜占庭将军问题,分布式协议与算法,分布式,算法

这个算法的前提是:

1、n位将军,最多允许 (n-2)位叛将。

2、同样需要多轮协商,如果叛将数位m,那么需要m + 1轮协商。

那如何实现签名消息呢?

可以使用非对称加密算法(如RSA),发送方使用哈希算法(如MD5)进行摘要,然后使用私钥对摘要进行加密,生成数字签名。然后将加密摘要和消息一起发送给接受方。接受方收到消息和加密摘要后,会用公钥对加密摘要进行解密,并对消息内容进行摘要,将两个摘要进行对比,以判断消息是否被篡改。

私钥加密,公钥解密。可以保证消息不会被冒充,因为私钥是不可泄漏的。如果公钥能正常解密出私钥加密的内容,就能证明这个消息是来源于持有私钥身份的人发送的。

感觉使用签名消息型拜占庭问题之解会更消耗算力一点。

小结

将将军作战中的场景与计算机世界的分布式场景进行对应:

  • 故事里的将军,可以理解为计算机节点。
  • 忠诚将军,可以理解为正常运行的计算机节点。
  • 叛变将军,可以理解为出现故障并会发送误导信息的计算机节点。
  • 信使被杀,可以理解为通讯故障、信息丢失。
  • 信使被间谍替换,可以理解为通讯被中间人攻击,攻击者在恶意伪造信息和劫持通讯。

拜占庭将军问描述的是最困难的,也是最复杂的一种分布式故障场景,除了存在故障行为,还存在恶意行为的场景。因此在存在恶意行为的场景中(如数字货币的区块链技术中),必须使用拜占庭容错算法(Byzantine Fault Tolerance,BFT)。除了上面提到的两种算法(口信消息型拜占庭问题之解、签名消息型拜占庭问题之解),常用的拜占庭容错算法还有:PBFT算法,PoW算法。

在计算机分布式系统中,最常用的是非拜占庭容错算法,即故障容错算法(Crash Fault Tolerance,CFT)CFT 解决的是分布式的系统中存在故障,但不存在恶意节点的场景下的共识问题。 也就是说,这个场景可能会丢失消息,或者有消息重复,但不存在错误消息,或者伪造消息的情况。常见的算法有 Paxos 算法、Raft 算法、ZAB 协议。文章来源地址https://www.toymoban.com/news/detail-626160.html

参考

  • 分布式协议与算法实战 学习笔记

到了这里,关于分布式协议与算法——拜占庭将军问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【区块链共识协议论文】【拜占庭异步通信】【Chronos: An Efficient Asynchronous Byzantine Ordered Consensus】

    1、 版权归属:牛津大学出版社(Oxford University Press) 2、 笔者为共同作者之一,联系方式:E230047@e.ntu.edu.sg 3、 引用格式: 4、 代码仓库:见GitHub 第1页 第2页 第3页 第4页 第5页 第6页 第7页 第8页

    2024年02月20日
    浏览(44)
  • 拜占庭问题

    本文为哈尔滨工程大学计算机科学与技术学院区块链技术课程附加作业 完成人: (1)学号:2019201131 姓名:周光煜 工作量:50% (2)学号:2019201120 姓名:孙世威 工作量:50% 区块链是一个基于比特币协议的不需要许可的分布式数据库,它维护了一个持续增长的不可被篡改和

    2024年01月16日
    浏览(47)
  • 无共识不区块链,一起了解拜占庭容错共识机制(BFT)

    引言 区块链技术的核心组成部分之一是共识机制。共识机制确保在分布式网络中各个节点之间达成一致,以防止双重支付和恶意行为。在讨论共识机制时,拜占庭将军问题是一个经典的思想实验,它启发了对分布式系统中共识难题的探讨。本文将通过详细解释区块链的共识机

    2024年04月15日
    浏览(64)
  • 分布式协议与算法——Paxos算法

    Paxos论文 Paxos Made Simple 、author:Leslie Lamport(兰伯特) Paxos算法是一种共识算法,一些常用的共识算法都是基于它改进的,如Fast Paxos算法、Cheep Paxos算法、Raft算法等。Paxos算法包含2个部分: Basic Paxos算法,描述的是多节点之间如何就某个值(提案 value)达成共识。 Multi-Paxos算

    2024年02月13日
    浏览(33)
  • 分布式协议与算法——CAP理论、ACID理论、BASE理论

    CAP理论,对分布式系统的特性做了高度抽象,比如抽象成了一致性、可用性和分区容错性,并对特性间的冲突(也就是CAP不可能三角)做了总结。 CAP三指标 CAP理论对分布式系统的特性做了高度抽象,形成了三个指标: 一致性(Consistency) 可用性(Availability) 分区容错性(

    2024年02月14日
    浏览(44)
  • 聊聊分布式架构09——分布式中的一致性协议

    目录 01从集中式到分布式 系统特点 集中式特点 分布式特点 事务处理差异 02一致性协议与Paxos算法 2PC(Two-Phase Commit) 阶段一:提交事务请求 阶段二:执行事务提交 优缺点 3PC(Three-Phase Commit) 阶段一:CanCommit 阶段二:PreCommit 阶段三:doCommit 优缺点 Paxos算法 拜占庭将军问题

    2024年02月08日
    浏览(51)
  • 分布式【Zookeeper ZAB协议】

    1.1 什么是Zab协议? Zab协议的全称是 Zookeeper Atomic Broadcast (Zookeeper原子广播)。 Zookeeper 是通过 Zab 协议来保证分布式事务的最终一致性 。 Zab协议是为分布式协调服务Zookeeper专门设计的一种 支持崩溃恢复 的 原子广播协议 ,是Zookeeper保证数据一致性的核心算法。Zab借鉴了Pa

    2024年02月03日
    浏览(43)
  • 分布式状态机共识协议 Copilot

      目录 前言 定义 slowdown 为什么现有的共识协议无法容忍 slowdown Copilot 如何处理 slowdown 设计 模型  排序 Client 同时发送指令至 pilot 与 copilot Pilot 提议指令与其初始依赖 节点回复 FastAccept Pilot 尝试通过 fast path 来 commit 该指令 Pilot 在 Accept 阶段最终确定依赖  执行 Copilot 最终合

    2024年02月09日
    浏览(44)
  • 分布式「走进分布式一致性协议」从2PC、3PC、Paxos 到 ZAB

    设计一个分布式系统必定会遇到一个问题—— 因为分区容忍性(partition tolerance)的存在,就必定要求我们需要在系统可用性(availability)和数据一致性(consistency)中做出权衡 。这就是著名的 CAP 一致性(Consistency)是指多副本(Replications)问题中的数据一致性。关于分布式

    2024年02月03日
    浏览(67)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包