分布式协议与算法实战
韩健
腾讯资深工程师
立即订阅
4665 人已学习
课程目录
已更新 20 讲 / 共 22 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 想成为分布式高手?那就先把协议和算法烂熟于心吧
免费
理论篇 (4讲)
01 | 拜占庭将军问题:有叛徒的情况下,如何才能达成共识?
02 | CAP理论:分布式系统的PH试纸,用它来测酸碱度
03 | ACID理论:CAP的酸,追求一致性
04 | BASE理论:CAP的碱,追求可用性
协议和算法篇 (11讲)
05 | Paxos算法(一):如何在多个节点间确定某变量的值?
06 | Paxos算法(二):Multi-Paxos不是一个算法,而是统称
07 | Raft算法(一):如何选举领导者?
08 | Raft算法(二):如何复制日志?
09 | Raft算法(三):如何解决成员变更的问题?
10 | 一致哈希算法:如何分群,突破集群的“领导者”限制?
11 | Gossip协议:流言蜚语,原来也可以实现一致性
12 | Quorum NWR算法:想要灵活地自定义一致性,没问题!
13 | PBFT算法:有人作恶,如何达成共识?
14 | PoW算法:有办法黑比特币吗?
15 | ZAB协议:如何实现操作的顺序性?
实战篇 (4讲)
16 | InfluxDB企业版一致性实现剖析:他山之石,可以攻玉
17 | Hashicorp Raft(一):如何跨过理论和代码之间的鸿沟?
18 | Hashicorp Raft(二):如何以“集群节点”为中心使用API?
加餐 | 拜占庭将军问题:如何基于签名消息实现作战计划的一致性?
分布式协议与算法实战
登录|注册

13 | PBFT算法:有人作恶,如何达成共识?

韩健 2020-03-11
你好,我是韩健。
学完了01 讲的拜占庭将军问题之后,有同学在留言中表达了自己的思考和困惑:口信消息型拜占庭问题之解在实际项目中是如何落地的呢?先给这位同学点个赞,很棒!你能在学习的同时思考落地实战。
不过事实上,它很难在实际项目落地,因为口信消息型拜占庭问题之解是一个非常理论化的算法,没有和实际场景结合,也没有考虑如何在实际场景中落地和实现。
比如,它实现的是在拜占庭错误场景下,忠将们如何在叛徒干扰时,就一致行动达成共识。但是它并不关心结果是什么,这会出现一种情况:现在适合进攻,但将军们达成的最终共识却是撤退。
很显然,这不是我们想要的结果。因为在实际场景中,我们需要就提议的一系列值(而不是单值),即使在拜占庭错误发生的时候也能被达成共识。那你要怎么做呢?答案就是掌握 PBFT 算法。
PBFT 算法非常实用,是一种能在实际场景中落地的拜占庭容错算法,它在区块链中应用广泛(比如 Hyperledger Sawtooth、Zilliqa)。为了帮助你更好地理解 PBFT 算法,在今天的内容中,我除了带你了解 PBFT 达成共识的原理之外,还会介绍口信消息型拜占庭问题之解的局限。相信学习完本讲内容后,你不仅能理解 PBFT 达成共识的基本原理,还能理解算法背后的演化和改进。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《分布式协议与算法实战》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(15)

  • 笑若海
    如果接收到小于f+1个消息就认可服务返回结果,可能都是来自f个恶意节点的消息,导致客户端接受恶意结果。f+1保证至少一个正确结果,如果其中存在恶意消息,客户端会发现不一致性,认为请求处理失败。
    这又引发一个新问题,客户端怎么确定f值?
    2020-03-11
    1
    4
  • myrfy
    老师,可以详细解释一下视图变更是什么意思吗

    作者回复: 好,我后面补充下,具体说说和演示下。

    2020-03-11
    3
  • 右耳听海
    麻烦老师补充下pbft实现一系列共识值pbft做了些什么优化,消息数是随一系列值倍数增加吗

    作者回复: 加一颗星:),是倍数增加的,相当于一轮新的共识协商。更多细节,我后面补充说说吧。

    2020-03-15
    1
  • Purson
    如果将军数为 n、叛将数为 f,那么算法需要递归协商 f+1 轮,消息复杂度为 O(n ^ (f + 1)),是怎样算出来的,第一讲说了两轮的能看明白,但是没有说3轮的,找不到递推关系,希望老师详细说一下BFT和PBFT两者区别
    2020-03-13
    1
  • 忆水寒
    PBFT 算法通过视图变更(View Change)的方式,来处理主节点作恶,当发现主节点在作恶时,会以“轮流上岗”方式,推举新的主节点。
    老师能详细补充一下吗?

    作者回复: 好,我后面做个加餐吧,具体说说和演示下。

    2020-03-11
    1
  • EidLeung
    PBFT需要提前知道叛将的数量么?实际落地过程中不可能提前知道啊,这又该怎么落地?
    2020-03-15
  • 右耳听海
    老师能具体说下pbft实现的是一系列值的共识而不是单值的共识具体指什么吗,一系列值的共识不也可以包装成一个值吗,不如:进攻,准备粮草,这是两个值,但是也可以是在一个消息中

    作者回复: 加一颗星:),两个值,就是两个消息,放到一个消息中,就是一个值了。单值的共识,比如Basic Paxos,它只能就提议的一个值达成共识,你再提议新值,它是无法达成共识的。一系列值的共识,比如Multi-Paxos能就多值(也就是指令)达成共识,也就是你提议了一个值,可以再提议一个值,分别会达成共识,比如PBFT,客户端可以发送一个请求,再发送一个请求,请求的内容会分别达成共识,被忠诚的节点们执行。

    2020-03-15
  • Purson
    口信型的O(n ^ (f + 1))是怎样推导出来的,我看第一章说2轮,第一轮A向 B C D 分别发一个消息,记3,第二轮剩下的3个分别向对方发2消息,记6,加起来总共9,用 4^2好像不太对。除非第一轮的苏秦不是将军,或者n就是忠诚将军数,n=3,就对。但是如果是f=2,一共有7名将军,第二轮协商到底是怎样的顺序?
    2020-03-13
  • 翠羽香凝
    “口信消息型拜占庭问题之解的局限我想说的是,这个算法有个非常致命的缺陷。如果将军数为 n、叛将数为 f,那么算法需要递归协商 f+1 轮,” 这里看不懂,01讲不是说算法一共是两轮吗?
    2020-03-12
  • Fs
    这就是为什么区块链的效率提升不上去?达成共识的时间效率太低
    2020-03-12
  • 6 7 8 9 10
    最后消息数的算法,看不懂呢
    2020-03-11
  • congyh
    有一个问题想请教韩老师: PBFT算法如何处理集群节点数的变更?
    2020-03-11
  • 梁伦
    图4下面的2f应该为2f+1

    作者回复: 加一颗星:),这是很容易误解的一个点,是2f个,这2f个准备消息和预准备消息是相同的,所以,加上主节点,就是2f + 1了。

    2020-03-11
  • 沉淀的梦想
    客户端要收到 f+1 个结果,我理解这个是为了防止 f 个叛徒直接给客户端返回 ok。不太理解的是为什么准备阶段要收到 2f 个一致的包含作战指令的准备消息,提交阶段需要 2f+1 个验证通过呢?这两个也设置成 f+1,不可以吗?
    2020-03-11
  • 小晏子
    课后思考:因为有f个坏的节点,如果客户端收到的结果小于f,最坏的情况是这f个结果都是坏节点发回来的,所以这就导致了客户端判断错误。所以客户端收到的结果必须大于f个,最少就是f+1个,也就是说最少要有一个好的节点发出来的结果来做判断。
    2020-03-11
收起评论
15
返回
顶部