分布式协议与算法实战
韩健
腾讯资深工程师
23193 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 31 讲
分布式协议与算法实战
15
15
1.0x
00:00/00:00
登录|注册

01 | 拜占庭将军问题:有叛徒的情况下,如何才能达成共识?

课堂思考
内容小结
苏秦该怎么办?
二忠一叛的难题
苏秦的困境
拜占庭将军问题

该思维导图由 AI 生成,仅供参考

你好,我是韩健。
在日常工作中,我常听到有人吐槽“没看懂拜占庭将军问题”“中文的文章看不懂,英文论文更看不下去”。想必你也跟他们一样,有类似的感受。
在我看来,拜占庭将军问题(The Byzantine Generals Problem),它其实是借拜占庭将军的故事展现了分布式共识问题,还探讨和论证了解决的办法。而大多数人觉得它难理解,除了因为分布式共识问题比较复杂之外,还与莱斯利·兰伯特(Leslie Lamport)的讲述方式有关,他在一些细节上(比如,口信消息型拜占庭问题之解的算法过程上)没有说清楚。
实际上,它是分布式领域最复杂的一个容错模型,一旦搞懂它,你就能掌握分布式共识问题的解决思路,还能更深刻地理解常用的共识算法,在设计分布式系统的时候,也能根据场景特点选择适合的算法,或者设计适合的算法了。而我把拜占庭将军的问题放到第一讲,主要是因为它很好地抽象了分布式系统面临的共识问题,理解了这个问题,会为你接下来的学习打下基础。
那么接下来,我就以战国时期六国抗秦的故事为主线串联起整篇文章,让你读懂、学透。

苏秦的困境

战国时期,齐、楚、燕、韩、赵、魏、秦七雄并立,后来秦国的势力不断强大起来,成了东方六国的共同威胁。于是,这六个国家决定联合,全力抗秦,免得被秦国各个击破。一天,苏秦作为合纵长,挂六国相印,带着六国的军队叩关函谷,驻军在了秦国边境,为围攻秦国作准备。但是,因为各国军队分别驻扎在秦国边境的不同地方,所以军队之间只能通过信使互相联系,这时,苏秦面临了一个很严峻的问题:如何统一大家的作战计划?
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文通过生动的故事背景和具体的技术解决方案,帮助读者深入理解了拜占庭将军问题及其解决方法。文章以战国时期六国抗秦的故事为背景,通过苏秦面临的困境和二忠一叛的难题,生动地阐述了拜占庭将军问题的实际应用。在这个问题中,多个将军需要在可能存在叛徒的情况下达成共识,制定一致的作战计划。文章提出了两种解决办法,分别是口信消息型拜占庭问题之解和签名消息型拜占庭问题之解。通过这些解决方案,读者可以深入了解分布式系统面临的共识问题,以及如何应对这些挑战。文章还介绍了拜占庭容错算法和非拜占庭容错算法的应用场景,为读者提供了在实际场景选择合适的算法类型的建议。总的来说,本文对于理解拜占庭将军问题及其解决方法具有重要的参考价值。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《分布式协议与算法实战》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(83)

  • 最新
  • 精选
  • 洛奇
    置顶
    看了这个专栏还有必要去看兰伯特的论文吗?

    作者回复: 实战,学习的最终目的,所以,我推荐,学习完后,多实战下,在实战中,加深自己对技术的理解,另外,遇到问题时,欢迎留言,咱们一起讨论。 有时间,可以读读自己感兴趣的论文,不过,在这里,我想补充的是,有时读论文是需要方法的,我来举个例子(如果没有学习本课程的话),兰伯特的Multi-Paxos,是出了名的难理解,那么,怎么学习呢?可以先研究Raft的论文,然后再去读Paxos的论文。

    2020-02-13
    9
    20
  • 汤小高
    置顶
    签名那个不是很懂,老师后面答疑课能不能再详细说明下

    作者回复: 感谢反馈,签名消息型拜占庭问题之解,在 《加餐 | 拜占庭将军问题:如何基于签名消息实现作战计划的一致性》做了补充。

    2020-02-12
    5
    21
  • 蓝魔丶
    首先觉得叛变对于个人来说肯定是有利可图的,没有利益的事情也就不愿意叛变,现在热门的区块链技术的先驱比特币就是采用了拜占庭容错算法POW,对于这种开放式的网络环境必须使用拜占庭容错算法,因为彼此无法建立信任关系。如果是企业内部的分布式中间件,因为只需考虑故障容错,不存在恶意节点,因为企业也不想没事找事是吧

    作者回复: 加一颗星:)

    2020-02-11
    4
    32
  • 沉淀的梦想
    口信消息型的算法,按照递归一直做下去,需要 m + 1 轮,那么就要有 m! 量级消息要发送,如果 m 比较大的话,这网络通信量岂不是爆炸?

    作者回复: 赞!思考深入,这也是为什么会有种种的拜占庭容错算法,针对不同场景的。

    2020-02-11
    10
    28
  • cc
    正常的网络传输环境中,除了消息丢失和消息重复,消息出错(非恶意攻击的情况)应该也是有可能的吧?如果可能出现传输过程中的消息差错,非拜占庭式的容错是不是就不适合了?

    作者回复: 底层的协议和硬件,能保证消息不出错,比如IP checksum、TCP checksum等。在不存在恶意攻击的环境,非拜占庭容错,就可以了。

    2020-02-12
    3
    22
  • 施耀南
    签名型可能的话可以具体点,不是很明白

    作者回复: 签名消息型拜占庭问题之解,本质上而言,表达的是,通过签名机制发现恶意行为,来避免“好人”被干扰和伤害。我讲个真实的故事,很多同学都知道,我们可以通过CA证书和SSL协议,实现文中提到的签名消息的2个特性,保证通讯消息不被恶意行为干扰,但是呢,在12年时,一些网络黑客,利用IE浏览器不检测证书签名,通过SSL中间人攻击,来截获SSL消息,获取通过HTTPS传输的金融账号的用户名和密码,但,这些人却无法对使用firefox的用户,发起攻击,为什么呢,就是因为,firefox会检查证书签名,判断消息是否是伪造的,也就是说,firefox通过签名消息,找出了“恶意消息”,避免了被攻击。

    2020-02-12
    3
    11
  • 小晏子
    CFT:只容忍节点故障,不容热节点作恶。 BFT:容忍节点故障与作恶。 像bitcoin系统使用的必须是BFT算法,像现在在各企业微服务中使用的zookeeper等就是使用的CFT算法。

    作者回复: 加一颗星:)

    2020-02-14
    2
    8
  • 洛奇
    解法二: 当齐和楚都是叛将时,只有燕是忠将,有以下两种情形: 1、齐先发送作战信息(和楚先发送的情形是一样的)。 2、燕先发送作战信息。 情形 1 中, 如果齐->燕 为进攻, 则必有 齐->楚 为撤退,然后因为楚也是叛将,所以有 楚->燕 为 楚齐:进攻, 然后燕接收到楚的作战信息后发现齐的签名的信息被伪造了,并从接收到的伪造信息退出齐的作战信息原本应是撤退,与从齐直接接收到的作战信息相反,所以燕判断齐和楚都是叛将,然后燕就执行了默认的作战指令撤退。燕从齐直接收到撤退的作战信息后的结果也是一样。 情形 2 下,燕为发起作战信息者,所以不受两个叛将的任何影响,所以对于燕自己来说是共识是一致的。 经过以上分析,得出解法二“任何叛变行为都会被发现,也就会实现无论有多少忠诚的将军和多少叛将,忠诚的将军们总能达成一致的作战计划”,不知道我理解的对不对?

    作者回复: 加一颗星:)

    2020-02-13
    6
    8
  • 在组织内部可信网络,或者组织与组织之间已经通过其他方式建立信任关系,使用非拜占庭容错算法。在未建立信任的组织间使用拜占庭容错算法。

    作者回复: 加一颗星:)

    2020-02-11
    2
    6
  • 约书亚
    消息签名的第两个例子有点看不懂: 例2,齐和燕国通过对比楚的消息不一致就能发现问题,签名在其中的作用呢? 同样,例1中燕能对比自身和楚发来的关于齐的计划,签名的作用呢? 感觉这两个例子中楚都扮演着恶意i节点的作用,但似乎签名主要是解决中间人的问题(间谍)?

    作者回复: 签名保证的是消息和身份的不可伪造,并且可以通过验证签名真伪,发现恶意行为和恶意节点,也就是找出叛徒。 比如,例1中,燕对比消息,发现不一致,如果没有签名,它无法确定是齐叛变了,还是楚叛变了。 同理,在例2中,齐、燕发现消息不一致时,无法确认谁是叛徒。

    2020-02-11
    7
    6
收起评论
显示
设置
留言
83
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部