(12)发明专利申请
(10)申请公布号 CN 111818152 A(43)申请公布日 2020.10.23
(21)申请号 202010632851.3(22)申请日 2020.07.02
(71)申请人 电子科技大学
地址 611731 四川省成都市高新区（西区）
西源大道2006号(72)发明人 高建彬
(74)专利代理机构 电子科技大学专利中心
51203
代理人 邹裕蓉(51)Int.Cl.
H04L 29/08(2006.01)H04L 12/24(2006.01)
权利要求书2页 说明书4页 附图2页
(54)发明名称
一种基于分布式网络的领导者选举的共识方法
(57)摘要
本发明提供一种基于分布式网络的领导者选举的共识方法，包括步骤：1)初始化：设置网络中节点种类包括领导者节点、接受者节点、追随者节点；2)领导者选举步骤：通过向网络节点广播一个数学问题，网络中每个节点对于该数学问题求解，根据求解的算力来选择分布式网络中的领导者；3)共识步骤。本发明先选择所有节点中算力最强的作为领导者节点，再进行整个网络的共识过程，以解决故障节点对分布式网络的影响，保证系统在拥有部分故障节点的情况下，仍然具有安全性。CN 111818152 ACN 111818152 A
权 利 要 求 书
1/2页
1.一种基于分布式网络的领导者选举的共识方法，其特征在于，包括以下步骤：1)初始化：设置网络中节点种类包括领导者节点、接受者节点、追随者节点；网络中节点数为3f+1；
领导者节点在网络中通过领导者选举产生，用于将事务处理为块，负责监督网络中各节点达成共识以及交易；
接受者节点为指定节点，用于接收事务的状态，不参与领导者选举；追随者节点用于接收客户端请求；2)领导者选举步骤：
2-1)当网络中的追随者节点发现领导者离职时，该追随者节点作为触发领导者选举的源节点在网络中广播初始化消息；初始化消息中包含有一个待求解的数学问题；网络中除接受者节点和触发领导者选举的源节点外的每一个节点收到初始化消息Initiate后，将上一跳节点设置为父节点；
2-2)除接受者节点外的每一个节点对数学问题进行求解，并将表征本地运算能力的算力值附在响应消息Receive中发送给父节点，源节点求解数学问题后直接保存本地的；每一个父节点在收到了其所有子节点的响应消息Receive后，根据算力值在本地与其所有子节点中选择一个算力最高的节点作为并向上传递，直至触发领导者选举的源节点选择出整个网络中算力最高的节点作为领导者节点；
2-3)发领导者选举的源节点将包含了领导者节点标识符的选择消息Select向网络中所有节点进行广播；
3)共识步骤：
3-1)接收到客户端请求的追随者节点作为发起者节点向网络中所有节点广播预准备消息Pre-prepare；
3-2)领导者节点在接收到预准备消息Pre-prepare后，生成Prepare消息向网络中所有节点广播；各节点验证收到Prepare消息与预准备消息Pre-prepare中的摘要是否相同，如是，则验证通过，再次向网络中所有节点广播Prepare消息，否则，丢弃Prepare消息；
3-3)接受者节点判断是否收到2f+1个验证通过的Prepare消息，如是，则通知网络中所有节点，网络中收到2f+1个Prepare消息的节点收到通知后向网络中所有节点广播Commit消息；
3-4)发起者节点判断是否收到2f+1个验证通过的Commit消息，如是，表明全网对客户端请求达成共识，向客户端发送共识回复，否则，表示网络中未达成共识，不能为客户端提供相应服务。
2.如权利要求1所述方法，其特征在于，步骤2-2)中表征本地运算能力的算力值为本地求解数学问题的运算时长，运算时长越短，算力越强。
3.如权利要求1所述方法，其特征在于，预准备消息Pre-prepare的消息的格式为Preprepare((np,seqno,d)sigf,m)，np为发起者节点的配置参数，seqno为客户端请求的序号，m为客户端请求的内容，d是内容m的摘要，sigf是发起者节点的签名；
Prepare消息的格式为Prepare(np,seqno,d,IDv)sigv，其中，IDv是领导者节点的标识符，sigv是领导者节点的签名；
Commit消息的格式为Commit(np,seqno,m,IDa)siga，其中，IDa是接受者节点的标识符，siga
2
CN 111818152 A
权 利 要 求 书
2/2页
是接受者节点的数字签名。
4.如权利要求3所述方法，其特征在于，验证收到Prepare消息与预准备消息Pre-prepare中的摘要是否相同的具体方式为：检查Prepare消息与预准备消息Pre-prepare中seqno和d是否相同。
5.如权利要求3所述方法，其特征在于，判断验证通过的Commit消息的具体方式为：当Commit消息中的配置参数np与发起者节点的配置参数相同则验证通过。
3
CN 111818152 A
说 明 书
一种基于分布式网络的领导者选举的共识方法
1/4页
技术领域
[0001]本发明涉及分布式网络中的选举技术。
背景技术[0002]信息时代的蓬勃发展为人们的生活带来了无数便利。同时也使得数据体量急剧增加，呈现爆炸式增长，这导致大型企业和和组织往往依赖数据聚合来提高生产力。因此使得软件开发过程更加复杂，软件发生错误的可能性也随之增加，使得网络攻击行为愈演愈烈。然而，复杂性是无法避免的，因为聚合数据进行各种复杂的计算，服务于其各种需求。相对于集中式系统，这种问题在分布式系统中更加难于防范和控制，因为节点故障会破坏整个分布式网络结构，从而引发严重的后果。[0003]在分布式系统中，共识算法更多用于提高系统的容错性。所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。基于领导节点leader-based的共识算法中，网络中的节点呈3种状态：领导者leader、追随者follower、候选者candidate；网络中最多只有一个leader，如果在一段时间里发现没有leader，则大家通过选举-投票选出leader。leader会不停的给follower发心跳消息，表明自己的存活状态。如果leader故障，那么follower会转换成candidate，重新选出leader。leader负责处理所有与客户端交互，是数据唯一入口，负责创建块，协调指挥follower。[0004]在分布式网络拓扑中，除了节点验证外，节点可以在任务完成之后，自由选择离开或加入网络。由于这些特征在动态网络中始终存在，所以领导者选举成为了解决分布式网络中拜占庭问题的重要方法。[0005]因此，在一个分布式系统中选出一个独特的领导者是非常重要的。然而现有的领导者选举算法往往忽视分布式网络中频繁的拓扑变化带来的影响。
发明内容
[0006]本发明所要解决的技术问题是，提供一种分布式网络中拥有高可用性和高效性的领导者选举的共识方法。
[0007]本发明为解决上述技术问题所采用的技术方案是，一种基于分布式网络的领导者选举的共识方法，包括以下步骤：[0008]1)初始化：设置网络中节点种类包括领导者节点、接受者节点、追随者节点；网络中节点数为3f+1；
[0009]领导者节点在网络中通过领导者选举产生，用于将事务处理为块，负责监督网络中各节点达成共识以及交易；[0010]接受者节点为指定节点，用于接收事务的状态，不参与领导者选举；[0011]追随者节点用于接收客户端请求；[0012]2)领导者选举步骤：
[0013]2-1)当网络中的追随者节点发现领导者离职时，该追随者节点作为触发领导者选
4
CN 111818152 A
说 明 书
2/4页
举的源节点在网络中广播初始化消息；初始化消息中包含有一个待求解的数学问题；网络中除接受者节点和触发领导者选举的源节点外的每一个节点收到初始化消息Initiate后，将上一跳节点设置为父节点；
[0014]2-2)除接受者节点外的每一个节点对数学问题进行求解，并将表征本地运算能力的算力值附在响应消息Receive中发送给父节点，源节点求解数学问题后直接保存本地；每一个父节点在收到了其所有子节点的响应消息Receive后，根据算力值在本地与其所有子节点中选择一个算力最高的节点作为并向上传递，直至触发领导者选举的源节点选择出整个网络中算力最高的节点作为领导者节点；
[0015]2-3)发起领导者选举的源节点将包含了领导者节点标识符的选择消息Select向网络中所有节点进行广播；[0016]3)共识步骤：
[0017]3-1)接收到客户端请求的追随者节点作为发起者节点向网络中所有节点广播预准备消息Pre-prepare；
[0018]3-2)领导者节点在接收到预准备消息Pre-prepare后，生成Prepare消息向网络中所有节点广播；各节点验证收到Prepare消息与预准备消息Pre-prepare中的摘要是否相同，如是，则验证通过，再次向网络中所有节点广播Prepare消息，否则，丢弃Prepare消息；[0019]3-3)接受者节点判断是否收到2f+1个验证通过的Prepare消息，如是，则通知网络中所有节点，网络中收到2f+1个Prepare消息的节点收到通知后向网络中所有节点广播Commit消息；
[0020]3-4)发起者节点判断是否收到2f+1个验证通过的Commit消息，如是，表明全网对客户端请求达成共识，向客户端发送共识回复，否则表示网络中未达成共识，不能为客户端提供相应服务。
[0021]本发明先选择所有节点中算力最强的作为领导者节点，在网络中的完成领导人选举后，再进行整个网络的共识过程，以解决故障节点对分布式网络的影响。[0022]本发明的有益效果是，保证系统在拥有部分故障节点的情况下，仍然具有安全性。附图说明
[0023]图1为实施例中在节点之间执行领导者选举协议，演示发起和接受消息的示意图。[0024]图2为实施例网络中算力最强的节点的选择示意图。
[0025]图3为实施例将网络中算力最强的节点作为领导者的广播示意图。
具体实施方式
[0026]下面将结合本发明实例图中的附图，对本发明中的技术方案进行描述。[0027]首先，进行分布式网络中共识领导者的选举。
[0028]分布式网络的共识领导者选举协议的中节点种类包括：[0029]领导者节点在网络中通过领导者选举产生，用于将事务处理为块，负责监督网络中各节点达成共识以及交易；对块的操作范围包括创建块、将块添加到链。[0030]接受者节点为指定节点，用于接收事务的状态，不参与领导者选举。[0031]追随者节点用于接收客户端请求。
5
CN 111818152 A[0032]
说 明 书
3/4页
为确保所有非故障节点在存在部分恶意节点的情况下的安全性，分布式系统对于
节点的要求：操作状态必须是确定的。在给定状态和给定参数集下的执行必须总是产生相同的结果。节点操作必须以相同的状态启动。
[0033]领导者选举过程从启动一个选举算法开始。算法中使用的消息有：[0034]Initiate:当追随者节点发现领导者离开时，该节点触发作为源节点的选举。源节点首先向它的所有邻居发送一个初始化消息Initiate。每个节点(源节点、接受者节点除外)将初始化消息Initiate的上一跳节点设置为其父节点。初始化消息Initiate中包含有一个待求解的数学问题。
[0035]Receive:除接受者节点外的每一个节点对数学问题进行求解，并将表征本地运算能力的算力值附在响应消息Receive中发送给父节点，源节点求解数学问题后直接保存本地；每一个父节点在收到了其所有子节点的响应消息Receive后，根据算力值在本地与其所有子节点中选择一个算力最高的节点作为并向上传递，直至触发领导者选举的源节点选择出整个网络中算力最高的节点作为领导者节点。每一个父节点在收到了其所有子节点的响应消息Receive后，才生成包含了领导者选举信息的响应消息Receive到其父节点。这个过程是一个生成树，从源到源的生成和收缩。可以本地求解数学问题的运算时长作为表征本地运算能力的算力值，运算时长越短，算力越强。父节点在所有子节点的响应消息Receive中选择运算时长最小的节点标识符向上传递。
[0036]Select:发起领导者选举的源节点将包含了领导者节点标识符的选择消息Select向网络中所有节点进行广播。网络中所有节点确认领导者节点。[0037]图1演示了节点A、B、C、D、E、G之间执行领导者选举的过程。以A10节点举例，其表示一个标识为A，算力值为10的节点，其他节点意义以此类推。其中initiate消息表示该节点发送了一个初始化消息的分布式计算，Ack消息表示该节点收到了initiate消息，将发送initiate消息给自己的节点标识为父节点，向该父节点发送应答。Receive消息表示该节点向目标节点回复自己已经接受过了来自其他节点initiate消息。[0038]图2展示了网络中算力最强的节点的选择。网络节点经过分布式计算与消息发送之后的生成树网络，分布式节点数值从叶子结点依次向上比较传递，将网络中算力最高的节点与其分布式计算的数值传递给源节点。
[0039]图3展示了网络中算力最强的节点作为领导者的广播，源节点将领导者节点的信息通过生成树传遍整个分布式网络。
[0040]基于本发明设计的分布式网络领导者选举算法，进行分布式网络的共识过程，以解决故障节点对于分布式网络的影响。假设在一个网络或集群中，非故障节点的数量是故障节点数量的三倍。消息在网络节点之间发送，以维护和激活网络上用户(客户端)的服务交付协议。共识算法的具体工作流程如下：
[0041]客户端通过向网络发送一个有效负载来发送一个请求服务执行的客户端请求Request，客户端请求Request的消息格式为Req(Payload,t,IDc)sigc，t为客户端时钟的本地时间戳，IDc为客户端标识符，sigc为客户端签名。客户端请求Request可以从客户端发送到指定了配置参数的追随者节点。
[0042]接收到客户端请求的追随者节点作为发起者节点向网络中所有节点广播预准备消息Pre-prepare；预准备消息Pre-prepare的消息的格式为Preprepare((np,seqno,d)sigf,m)，
6
CN 111818152 A
说 明 书
4/4页
np为发起者节点的配置参数，seqno为客户端请求的序号，m为客户端请求的内容，d是内容m的摘要，sigf是发起者节点的签名。
[0043]领导者节点在接收到预准备消息Pre-prepare后，生成Prepare消息向网络中所有节点广播；各节点验证收到Prepare消息与预准备消息Pre-prepare中的摘要是否相同，如是，则验证通过，再次向网络中所有节点广播Prepare消息，否则，丢弃Prepare消息。Prepare消息的格式为Prepare(np,seqno,d,IDv)sigv，其中，IDv是领导者节点的标识符，sigv是领导者节点的签名；Prepare消息的格式为Prepare(np,seqno,d,IDv)sigv，其中，IDv是领导者节点的标识符，sigv是领导者节点的签名。
[0044]接受者节点判断是否收到2f+1个验证通过的Prepare消息，如是，则通知网络中所有节点，网络中各收到2f+1个Prepare消息的节点收到通知后向网络中所有节点广播Commit消息；Commit消息的格式为Commit(np,seqno,m,IDa)siga，其中，IDa是接受者节点的标识符，siga是接受者节点的数字签名。
[0045]发起者节点判断是否收到2f+1个验证通过的Commit消息，如是，表明全网对客户端请求达成共识，向客户端发送共识回复Reply，否则，丢弃Commit消息。共识回复Reply的消息格式为Rep(np,t,IDc,IDf,Sr)sigf，IDf为发起者节点标识符，Sr为请求的服务执行结果。
7
CN 111818152 A
说 明 书 附 图
1/2页
图1
图2
8
CN 111818152 A
说 明 书 附 图
2/2页
图3
9
因篇幅问题不能全部显示，请点此查看更多更全内容