一文读懂拜占庭将军问题
文章图片
文章图片
作者 | Yu Liebing
责编 | Carol
出品 | 区块链大本营(ID:blockchain_camp)
拜占庭将军问题(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中场景可简单地推得,通过投票三个将军都将达成一致的行动计划。
文章图片
图2. 三个将军均为忠诚的场景
当三个将军中存在一个叛徒时,将可能扰乱正常的作战计划。图3展示了General C为叛徒的一种场景,他给General A和General B发送了不同的消息,在这种场景下General A通过投票得到进攻:撤退=1:2,最终将作出撤退的行动计划;General B通过投票得到进攻:撤退=2:1,最终将作出进攻的行动计划。结果只有General B发起了进攻并战败。
文章图片
图3. 二忠一叛的场景
事实上,对于三个将军中存在一个叛徒的场景,想要总能达到一致的行动方案是不可能的。详细的证明可参看Leslie Lamport的论文。此外,论文中给出了一个更加普适的结论:如果存在m个叛将,那么至少需要3m+1个将军,才能最终达到一致的行动方案。
文章图片
解决方案
Leslie Lamport在论文中给出了两种拜占庭将军问题的解决方案,即口信消息型解决方案(A solution with oral message)和签名消息型解决方案(A solution with signed message)。
1、口信消息型解决方案
首先, 对于口信消息(Oral message)的定义如下:
- A1. 任何已经发送的消息都将被正确传达;
- A2. 消息的接收者知道是谁发送了消息;
- A3. 消息的缺席可以被检测。
文章图片
图4. 指挥官为忠将的场景
图5是指挥官为叛将的场景,在第一轮作战信息协商中,指挥官向General A、B发送了撤退的消息,但是为了扰乱General C的决定向其发送了进攻的消息。在第二轮中,由于所有副官均为忠将,因此都将来自指挥官的消息正确地发送给其余两位副官。最终所有忠将都能达成一致撤退的计划。
文章图片
图5. 指挥官为叛将的场景
如上所述,对于口信消息型拜占庭将军问题,如果叛将人数为m,将军人数不少于3m+1,那么最终能达成一致的行动计划。值的注意的是,在这个算法中,叛将人数m是已知的,且叛将人数m决定了递归的次数,即叛将数m决定了进行作战信息协商的轮数,如果存在m个叛将,则需要进行m+1轮作战信息协商。这也是上述存在1个叛将时需要进行两轮作战信息协商的原因。
2、签名消息型解决方案
同样,对签名消息的定义是在口信消息定义的基础上增加了如下两条:
- A4. 忠诚将军的签名无法伪造,而且对他签名消息的内容进行任何更改都会被发现;
- A5. 任何人都能验证将军签名的真伪。
文章图片
图6. 忠将率先发起作战协商
图7是叛将率先发起作战协商的场景,叛将General C率先发送了误导的作战信息,那么General A、B将发现General C发送的作战信息不一致,因此判定其为叛将。可对其进行处理后再进行作战信息协商。
文章图片
图7. 叛将率先发起作战协商
签名消息型解决方案可以处理任何数量叛将的场景。
文章图片
总 结
在分布式系统领域, 拜占庭将军问题中的角色与计算机世界的对应关系如下:
- 将军, 对应计算机节点;
- 忠诚的将军, 对应运行良好的计算机节点;
- 叛变的将军, 被非法控制的计算机节点;
- 信使被杀, 通信故障使得消息丢失;
- 信使被间谍替换, 通信被攻击, 攻击者篡改或伪造信息。
一类是故障容错算法(Crash Fault Tolerance, CFT), 即非拜占庭容错算法,解决的是分布式系统中存在故障,但不存在恶意攻击的场景下的共识问题。也就是说,在该场景下可能存在消息丢失,消息重复,但不存在消息被篡改或伪造的场景。一般用于局域网场景下的分布式系统,如分布式数据库。属于此类的常见算法有Paxos算法、Raft算法,、ZAB协议等。
一类是拜占庭容错算法,可以解决分布式系统中既存在故障,又存在恶意攻击场景下的共识问题。一般用于互联网场景下的分布式系统,如在数字货币的区块链技术中。属于此类的常见算法有PBFT算法、PoW算法。
文章图片
看完本文,你对这两种解决方案有什么看法?欢迎在评论区跟我们讨论!
文章图片
技术战“疫”,贾扬清、李飞飞要给程序员直播讲AI技术!
2月18日、2月20日,阿里云CIO学院攻“疫”技术课程正式开启。您将获得与达摩院数据库首席科学家 、阿里巴巴集团副总裁、ACM 杰出科学家李飞飞,Caffe之父、ONNX创始人、阿里巴巴集团副总裁贾扬清,阿里巴巴集团副总裁、阿里 CIO 学院院长胡臣杰等顶级技术专家直播互动的机会。
文章图片
推荐阅读
- 比特币技术栈的演进
- 2019年度区块链安全复盘总结
- 教你如何编写第一个爬虫
- “夸夸机器人” App 来了:变身百万粉丝大 V,48 万人给你的帖子点赞
- 几行代码构建全功能的对象检测模型,他是如何做到的?
- 早期文献中的关系抽取论文整理,赶紧 Mark 起来!
【一文读懂拜占庭将军问题】猛戳“阅读原文”,填写中国远程办公-调查问卷
推荐阅读
- mysql|一文深入理解mysql
- 数据技术|一文了解Gauss数据库(开发历程、OLTP&OLAP特点、行式&列式存储,及与Oracle和AWS对比)
- 一文弄懂MySQL中redo|一文弄懂MySQL中redo log与binlog的区别
- c语言|一文搞懂栈(stack)、堆(heap)、单片机裸机内存管理malloc
- 读《一本书读懂财报》
- 网络|一文彻底搞懂前端监控
- 【SpringCloud-Alibaba系列教程】8.一文学会使用sentinel
- 读懂新冠,更爱汁法
- 凯迪克金奖绘本《外公的旅程》读懂故乡与远方
- 2020买重疾险看这篇就够了,一文明白重疾险怎么买|2020买重疾险看这篇就够了,一文明白重疾险怎么买,更划算