在分布式计算上,不同的计算机通过信息交换尝试达成共识,但有时候,系统中的协调计算机或成员计算机可能因系统错误交换错的信息,以致影响最终的系统一致性。对于拜占庭将军问题,若根据错误计算机的数量,寻找可能的解决办法,这其实无法找到一个绝对的答案,只可以用来验证一个机制的有效程度。

而拜占庭将军问题的可能解决方法为:在N≥3F+1的情况下,一致性是可能实现的(N为计算机总数,F为有问题的计算机总数)。信息在计算机间互相交换后,各计算机列出所有得到的信息,以大多数的结果作为解决办法。

实用拜占庭容错详解

最早由卡斯特罗和利斯科夫在1999年提出的实用拜占庭容错(PBFT)是第一个得到广泛应用的拜占庭容错算法。只要系统中有2/3的节点是正常工作的,就可以保证一致性。

实用拜占庭容错算法的总体过程如下:

客户端向主节点发送请求调用服务操作,如“<REQUEST,o,t,c>”,这里客户端c请求执行操作o,时间戳t用来保证客户端请求只会执行一次。每个由副本节点发给客户端的消息都包含了当前的视图编号,使得客户端能够追踪视图编号,从而进一步推算出当前主节点的编号。客户端通过点对点消息向它自己认为的主节点发送请求,然后主节点自动将该请求向所有备份节点进行广播。

视图编号是连续编号的整数。主节点由公式p=vmod|R|计算得到,这里v是视图编号,p是副本编号,|R|是副本集合的个数。

副本发给客户端的响应为“<REPLY,v,t,c,i,r>”,v是视图编号,t是时间戳,i是副本的编号,r是请求执行的结果。

主节点通过广播将请求发送给其他副本,然后就开始执行三个阶段的任务。

1.预准备阶段。主节点分配一个序列号n给收到的请求,然后向所有备份节点群发预准备消息,预准备消息的格式为“<<PRE-PREPARE,v,n,d>,m>”,这里v是视图编号,m是客户端发送的请求消息,d是请求消息m的摘要。

2.准备阶段。如果备份节点i接受了预准备消息,则进入准备阶段。在准备的同时,该节点向所有副本节点发送准备消息“<PREPARE,v,n,d,i>”,并且将预准备消息和准备消息写入自己的消息

3.确认阶段。当“(m,v,n,i)”条件为真的时候,副本i将“<COMMIT,v,n,D(m),i>”向其他副本节点广播,于是就进入了确认阶段。所有副本都执行请求并将结果发回客户端。客户端需要等待不同副本节点发回相同的结果,作为整个操作的最终结果。

如果客户端没有在有限时间内收到回复,请求将向所有副本节点进行广播;如果该请求已经在副本节点处理过了,副本就向客户端重发一遍执行结果;如果请求没有在副本节点处理过,该副本节点将把请求转发给主节点;如果主节点没有将该请求进行广播,那么就认为主节点失效;如果有足够多的副本节点认为主节点失效,则会触发一次视图变更。

图2-85未发生主节点失效的情况下的算法

图2-85未发生主节点失效的情况下的算法

图2-85展示了在没有发生主节点失效的情况下算法的正常执行流程,其中副本0是主节点,副本3是失效节点,而c是客户端。

实用拜占庭容错机制是一种采用“许可投票、少数服从多数”来选举领导者并进行记账的共识机制,该共识机制允许拜占庭容错,允许强监管节点参与,具备权限分级能力,性能更高,耗能更低,而且每轮记账都会由全网节点共同选举领导者,允许33%的节点作恶,容错性为33%。由于特别适合联盟链的应用场景,实用拜占庭容错机制及其改进算法为目前使用最多的联盟链共识算法,其改进算法在以下方面进行了调整:修改底层网络拓扑的要求,使用P2P网络;可以动态地调整节点数量;减少协议使用的消息数量。

玖壹区块链声明

加微信:469649885区块链培训教程
还可免费获取区块链培训班试学名额

分享:

扫一扫在手机阅读、分享本文

区块链评论

玖壹区块链培训

玖壹区块链培训学院简称(玖壹学院http://www.91xiubbs.com/)提供区块链技术培训资料、区块链开发培训视频教程等下载,不过网上自学区块链技术课程必然存在一些缺陷:遇到问题易卡壳、学习周期漫长、无针对性等。区块链培训机构现场面对面的讲授区块链培训课程可以让您和团队在最短时间内掌握正确、系统、高效的区块链实战技术。