基于树形拓扑结构的拜占庭容错系统设计

doi:10.11959/j.issn.1000-436x.2017261

通信学报 ›› 2017, Vol. 38 ›› Issue (Z2): 139-146.doi: 10.11959/j.issn.1000-436x.2017261

基于树形拓扑结构的拜占庭容错系统设计

吕伟栋,周学广,袁志民

海军工程大学信息安全系，湖北武汉430033

出版日期:2017-11-01 发布日期:2018-06-07
作者简介:吕伟栋（1993-），男，湖北襄阳人，海军工程大学硕士生，主要研究方向为信息系统与决策支持。|周学广（1966-），男，江苏高邮人，博士，海军工程大学教授、博士生导师，主要研究方向为信息安全与密码学。|袁志民（1964-），男，河南淮阳人，博士，海军工程大学讲师，主要研究方向为通信安全。
基金资助:
国家自然科学基金资助项目(61672531);海军工程大学科研自主立项课题基金资助项目(20161606)

Design of tree topology based Byzantine fault tolerance system

Wei-dong LYU,Xue-guang ZHOU,Zhi-min YUAN

Department of Information Security,Naval University of Engineering,Wuhan 430033,China

Online:2017-11-01 Published:2018-06-07
Supported by:
The National Natural Science Foundation of China(61672531);The Scientific Research Project of Naval University of Engineering(20161606)

摘要/Abstract

摘要：

提出了一种能够应用于树形结构的拜占庭容错系统，并给出了基于深度与广度的拜占庭节点上限算法。通过对树进行群组划分，设计了一致性协议，保障了系统的安全性；通过联合签名机制决定节点的权限；通过视图转换协议将高层拜占庭节点置换到叶子节点，保证了系统的活性。在传统协议的基础上，该系统支持多任务同时执行，减少了节点间通信量，较大地降低了系统的空间复杂度，提高了系统的可行性，进一步缩小了与非拜占庭系统的差距。

关键词: 拜占庭容错, 树形拓扑结构, 一致性协议, 视图转换协议, 检查点协议

Abstract:

A tree topology based Byzantine fault tolerance system was designed and the calculation of the Byzantine node bound based on depth and width was given.The consistency protocol was designed through divide the tree into groups by communication and work,which guaranteed the safety of system.The access of a node was determined with joint signature mechanism.The Byzantine nodes were placed to the leaves by view change protocol,which guaranteed the liveness of the system.On the foundation of traditional protocol,the new protocol support multiple tasks operating at the same time,and communication between nodes is largely decreased,as well as the space complexity,hence the feasibility being promoted,and the gap between Byzantine fault tolerance system and the non-Byzantine systems being narrowed.

Key words: Byzantine fault tolerance, tree topology, consistency protocol, view change protocol, checkpoint protocol

中图分类号:

TP302

吕伟栋,周学广,袁志民. 基于树形拓扑结构的拜占庭容错系统设计[J]. 通信学报, 2017, 38(Z2): 139-146.

Wei-dong LYU,Xue-guang ZHOU,Zhi-min YUAN. Design of tree topology based Byzantine fault tolerance system[J]. Journal on Communications, 2017, 38(Z2): 139-146.

图/表 4

表1

协议中的全局变量"

变量	含义
D	叶子节点的深度
w	节点的度
N_d	深度为d的服务器的数量
N	树中节点的总数量
f	树中拜占庭节点的总数量
l_d,a	树中G_d,a(d≤D)的任意一个节点，d表示该节点的深度，a表示该节点同层节点集合中的序号
l_1,1	系统初始状态下的主节点
G_{d ,a}(d≤D)	其G_d,a(d≤D)所有的孩子所构成的群组
n'	群组中节点的数量
f'	群组中拜占庭节点的数量
${〈 M 〉}_{σ_{l_{d, a}}}$	节点l_d,a发出的带有签名的消息M
${〈 M 〉}_{σ_{G_{d, a}}}$	由节点l_d,a发出的带有群组G_d,a中 f′+1个节点联合签名的消息M
D(m)	消息m的摘要

表1

图1

图2

表2

本系统与不同拜占庭系统各参数比较"

算法	服务器数量	单一请求所需阶段数	单一请求所需计算数
本文算法	$\frac{3 w f - 1}{w - 1}$	4d?2	4(N?1)(d?1)(2w?1)
PBFT	3f+1	4	2N(N?1)
HQ	3f+1	4	2N(N?1)
Zyzzyva	3f+1	3	$\frac{3 N (N - 1)}{2}$

表2

参考文献 15

[1]	SCHROEDER B , GIBSON G A . A large-scale study of failures in high-performance computing systems[C]// IEEE Trans on Dependable and Secure Computing. 2010: 337-350.
[2]	范捷, 易乐天, 舒继武 . 拜占庭系统技术研究综述[J]. 软件学报, 2013,24(6): 1346-1360.
	FAN J , YI L T , SHU J W . Research on the technology of Byzantine system[J]. Journal of Software, 2013,24(60): 1346-1360.
[3]	袁勇, 王飞跃 . 区块链技术发展现状与展望[J]. 自动化学报, 2016,42(4): 481-493.
	YUAN Y , WANG F Y . Blockchain:the state of the art and future trends[J]. Acta Automatic Sinica, 2016,42(4): 481-494.
[4]	夏清, 张凤军, 左春 . 加密数字货币系统共识机制综述[J]. 计算机系统应用, 2017,26(4): 1-8.
	XIA Q , ZHANG F J , ZUO C . Review for consensus mechanism of cryptocurrency system[J]. Computer Science ＆ Application, 2017,26(4): 1-8.
[5]	LISKOV B , GHEMAWAT S , GRUBER R ,et al. Replication in the harp file system[C]// 13th ACM Symp on Operating System Principles(SOSP). 1991: 226-238.
[6]	OKI B , LISKOV B . Viewstamped replication:a new primary copy method to support highly-available distributed systems[C]// ACM Symposium on Principles of Distributed Computing. 1988: 8-17.
[7]	LAMPORT L , SHOSTAK R , PEASE M . The Byzantine generals problem[C]// ACM Trans. on Programming Languages and Systems, 1982,4(3): 382-401.
[8]	CASTRO M , LISKOV B . Practical Byzantine fault tolerance and proactive recovery[C]// ACM Trans on Computer Systems. 2002: 398-461
[9]	WOOD T , SINGH R , VENKATARAMANI A ,et al. ZZ and the art of practical BFT execution[C]// 6th Conf on Computer Systems. 2011: 123-138.
[10]	HENDRICKS J , SINNAMOHIDEEN S , GANGER G R ,et al. Zzyzx:scalable fault tolerance through Byzantine locking[C]// 2010 IEEE/IFIP Int’1 Conf on Dependable Systems and Networks. 2010: 363-372.
[11]	SERAFINI M , NOKOR P , DOBRE D ,et al. Scrooge:Reducing the costs of fast Byzantine replication in presence of unresponsive replicas[C]// 2010 IEEE/IFIP Int’1 Conf on Dependable Systems and Networks. 2010: 353-362.
[12]	RAMAKRISHNA K , LORENZO A , MIKE D ,et al. Zyzzyva:speculative byzantine fault tolerance[C]// ACM SIGOPS Symposium on Operating Systems Principles. 2007: 45-48.
[13]	CLEMENT A , KAPRITSOS M , LEE S ,et al. Upright cluster services[C]// ACM SIGOPS 22nd Symp on Operating Systems Principles. 2009: 277-290.
[14]	DANNY D . The Byzantine generals strike again[J]. Journal of Algorithms, 1982,3(1): 14-30.
[15]	LAMPORT L , . Proving the correctness of multiprocess programs[C]// IEEE Transactions on Software Engineering, 1977, SE-3(2): 125-143.

基于树形拓扑结构的拜占庭容错系统设计

Design of tree topology based Byzantine fault tolerance system

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 15

相关文章 4

Metrics

推荐阅读 0

[1]	陈宇, 贾连兴. 面向无人机集群的双层分组拜占庭容错算法[J]. 通信学报, 2022, 43(1): 96-103.
[2]	刘玉红, 杨亮, 朴春慧, 张志国. 基于区块链的铁路工程施工安全监测数据共享关键技术研究[J]. 通信学报, 2021, 42(8): 206-216.
[3]	黄冬艳, 李浪, 陈斌, 王波. RBFT：基于Raft集群的拜占庭容错共识机制[J]. 通信学报, 2021, 42(3): 209-219.
[4]	窦全胜,厉玉蓉,姜平. 线性离散一致性系统均方偏差上界[J]. 通信学报, 2016, 37(10): 33-39.