纠错码拜占庭容错Quorum中错误检测机制

摘要在大规模存储系统中,拜占庭存储节点的容错显得越来越重要。传统拜占庭Quorum通过复制可以容忍拜占庭失效,但是它们有两个主要缺点：低的存储空间利用率和静态quorum参数。我们提出纠错码拜占庭容错Quorum（Erasure-code Byzantine Fault-tolerance Quorum, E-BFQ）,E-BFQ采用纠错码作为冗余策略,可以提供高可靠性,同时比复制占用更少存储空间。通过客户端读／写操作和管理器诊断操作,E-BFQ可以检测拜占庭节点,动态调整系统规模和故障闽值。结果显示本文方法可以达到动态调整的目的。     

P2P存储系统拜占庭容错机制研究*

综述了近年来P2P存储系统拜占庭错误冗余相关技术的研究成果;概述了P2P存储系统容错的要求与技术,对现有拜占庭错误冗余技术进行了总结;详细分析对比了目前各种典型拜占庭容错系统的容错方式,探讨了P2P存储系统中拜占庭容错技术需要改进的关键问题,并对未来的研究方向进行了讨论;最后,给出了一个实际环境下的解决方案框架。     

基于Quorum系统容错技术综述

Quorum系统是一种新型冗余拓扑的集合系统。在“冗余”设计的基础上,quorum通过交叉的结点把有效数据复制到其他quorum的结点中,增加了Quorum系统数据冗余性。当某些结点发生故障或者错误时,通过选举协议,从含有故障结点quorum的有效结点中选举出有效数据;或者采用互斥协议,从不含故障或者错误结点的有效quorum的结点中获得有效数据,系统仍能可靠运行。分析了各种Quorum肌系统的容错方式、性能比较,探讨了Quorum系统发展中需要改进的关键问题,并展望了未来的研究方向。     

结构化P2P系统中副本一致性管理的一种新算法

结构化P2P系统通常使用数据复制来提高数据可用性,但P2P环境中的节点搅动、多节点并发更新以及恶意节点的存在也为副本的一致性管理带来了新的挑战.基于协商的算法要求节点间以全交换的方式通讯,在P2P环境中其可伸缩性不够理想.本文针对结构化P2P系统提出一种基于Quorum的副本管理算法:使用混合失效模型降低容错开销,利用DHT服务处理节点搅动,将数据存储与其元信息管理分离,使数据可靠性和数据可用性得以独立调整.模拟实验表明该算法可以明显改善系统的可伸缩性,减少系统的容错开销.     

基于拜占庭故障模式的空天飞行器GNC系统架构研究

针对空天飞行器对GNC系统的高可靠性需求,开展了基于拜占庭故障模式的GNC系统架构研究,采用四机三总线架构设计方案,通过系统内总线实现输入数据及输出数据多机冗余比对,防止拜占庭故障的发生,提升了系统可靠性,实现了系统自检测和故障的准确定位及隔离,并具有在线故障诊断、故障自修复功能,同时解决了高动态、强干扰环境下系统自主性较差的问题,提升了GNC系统可靠性和容错性;经分析,该系统架构能够满足空天飞行器在轨、再入复杂任务需求。     

分布式WSN系统中的拜占庭故障算法研究

在分布式WSN系统中,簇内有相当多的无线传感器节点,这些节点可能会部署在各种环境中,采用从单个传感器上所获取信息可靠性不高。为了提高系统的可靠性,需要对多个传感器节点采集数据进行综合,这样就可以有效地提高所获得数据的精度和可信度。研究了在系统节点发生拜占庭故障的情况下,利用现有WSN的数据融合方法以及安全系统中的拜占庭将军问题,提出了一种新的基于OM算法与贝叶斯检测算法的容错检测算法,合理而有效的进行数据融合,减小拜占庭故障对系统的影响,从而使所有节点做出一致决定。通过仿真得出该算法可以保证节点决策具有较高一致性的情况下仍有较高的故障节点减少率。     

WMN中拜占庭容错网络结构及算法

为提高无线Mesh网络(WMN)的可靠性,以可信计算领域中的拜占庭容错原理为基础,引入拜占庭单元概念,构建一个WMN拜占庭容错网络结构,并提出一种拜占庭算法,用以改进现有WMN路由协议.仿真结果表明,改进的路由协议能对异常节点信息进行容错处理,获得正确的节点信息,增强网络的容错能力,达到提升WMN可靠性的目的.     

面向服务计算的拜占庭容错方案及其正确性证明

针对现有拜占庭容错协议的假设(要求被保护的对象是被动的和独立的)不适用于服务计算等新兴计算模型的问题,提出一种面向服务计算的拜占庭容错协议。该协议在服务请求方和服务提供方两端均创建服务复制品,采用基于状态机的主动复制技术,在服务复制品间进行三轮通信,就该请求的编号和内容达成一致,随后该请求被提交给上层应用逻辑处理;收到应答后,服务请求方的复制品进行三轮通信就应答的编号和内容达成一致后接受该应答。针对现有面向服务计算的拜占庭容错协议只有简单的正确性推理缺乏形式化验证的问题,采用I/O自动机和模拟关系方法进行正确性证明,更加严谨和正式。构造一个高度抽象的简单I/O自动机S,此自动机满足安全性和及时性;将协议中的各方分解成若干简单I/O自动机:前端自动机、后端自动机和多播通道自动机;最后用模拟关系方法证明各成员自动机构成的系统实现了自动机S,从而证明协议的正确性。使用I/O自动机可以精确描述协议,以此为基础进行证明比感性推理的证明方法更加规范。     

基于拜占庭容错提高SDN控制层可靠性的研究

软件定义网络(software defined network, SDN)提出了控制与转发分离的设计结构,实现了开放的可编程网络接口,为网络提供了更细粒度的管理.然而,SDN在为网络应用带来创新与便利的同时,也面临着一些新的问题.针对SDN网络中控制层的可靠性问题,提出了一种容忍拜占庭错误的方法.首先,结合SDN网络的特性,具体阐述了在应用拜占庭容错算法时的网络结构、工作流程和异常处理等,并对其中的多控制器位置部署问题建立分析模型;然后,针对该多控制器部署问题,设计了启发式求解算法;最后,通过仿真实验对该容错方法和部署算法进行验证.实验结果表明:该容错方法能够有效处理控制器中的错误,提高控制层的可靠性,但对系统的性能会造成一定程度的影响.同时,该部署算法能够有效降低处理OpenFlow请求的传输延迟.     

实用拜占庭容错算法的改进研究

针对实用拜占庭容错算法(PBFT)存在的通信复杂度高、主节点选取简单、对拜占庭节点缺乏惩罚机制的不足,提出了一种基于节点可靠性评估的改进拜占庭容错算法(reliability-based Byzantine fault tolerant algorithm,RB-PBFT),引入节点基础配置评分机制及信誉评分机制,得到...     

Extending binary Byzantine agreement to multivalued Byzantine agreement

A binary Byzantine agreement algorithm can be extended to produce a multivalued Byzantine agreement algorithm. The resulting multivalued algorithm is cheaper than previously published algorithms when the cost of transmitting values from the multivalued domain is significant.     

面向边缘计算应用的拜占庭式容错分布式一致性算法

为解决边缘计算中边缘节点易于被攻击或俘获产生拜占庭错误,从而破坏边缘计算应用可用性的问题,设计一种面向边缘计算应用的拜占庭容错分布式一致性算法Edge-Raft。该算法在现有的经典Raft算法基础上,针对边缘环境中潜在的拜占庭错误进行重新设计,通过引入数字签名、同步日志检测、轮询选举、惰性投票、三阶段日志同步等机制,使其具有拜占庭容错特性的同时,将消息传递的复杂度限制至线性级,保证小于1/3的集群总数的边缘节点发生拜占庭错误时仍能为用户提供有效服务。基于不同节点规模的实验结果表明,与现有Raft算法相比,该算法在保留Raft算法可理解性的基础上,保证算法在边缘环境中的可用性与活性。相比于现有的实用拜占庭容错算法,所提算法将消息传递的时间复杂度限定在线性级,保证该算法在多节点边缘环境中的可拓展性。     

基于推荐信任模型改进拜占庭容错共识算法

针对拜占庭容错算法存在通信开销大、节点选取简单、对恶意节点缺乏惩罚机制的问题,提出了一种基于推荐信任模型的改进拜占庭容错共识算法。引入P2P网络下的推荐信任模型,根据节点在共识阶段的行为,计算各节点的全局信任值,使用节点选取机制,解决节点选取简单的问题。全局信任值高的节点进入共识组,恶意节点被踢出共识组不再参与共识,解决恶意节点缺乏惩罚机制的问题。实验表明,R-PBFT较PBFT具有更低的网络开销和更高的容错性。     

A new solution for the Byzantine agreement problem

Reliability is an important research topic in distributed computing systems consisting of a large number of processors. To achieve reliability, the fault-tolerance scheme of the distributed computing system must be revised. This kind of problem is known as a Byzantine agreement (BA) problem. It requires all fault-free processors to agree on a common value, even if some components are corrupt. Consequently, there have been significant studies of this agreement problem in distributed systems. However, the traditional BA protocols focus on running ⌊(n−1)/3⌋+1 rounds of message exchange continuously to make each fault-free processor reach an agreement. In other words, since having a large number of messages results in a large protocol overhead, those protocols are inefficient and unreasonable, especially for some network environments which have large number of processors. In this study, we propose a novel and efficient protocol to reduce the number of messages. Our protocol can collect, compare and replace the received values to find the reliable processors and replace the values sent by the unreliable processors. Subsequently, each processor can agree on a common value through three rounds of message exchange. Furthermore, the proposed protocol can use the minimum number of messages to tolerate the maximum number of faulty components in a distributed system.     

Optimistic Byzantine fault tolerance

The primary concern of traditional Byzantine fault tolerance is to ensure strong replica consistency by executing incoming requests sequentially according to a total order. Speculative execution at both clients and server replicas has been proposed as a way of reducing the end-to-end latency. In this article, we introduce optimistic Byzantine fault tolerance. Optimistic Byzantine fault tolerance aims to achieve higher throughput and lower end-to-end latency by using a weaker replica consistency model. Instead of ensuring strong safety as in traditional Byzantine fault tolerance, nonfaulty replicas are brought to a consistent state periodically and on-demand in optimistic Byzantine fault tolerance. Not all applications are suitable for optimistic Byzantine fault tolerance. We identify three types of applications, namely, realtime collaborative editing, event stream processing, and services constructed with conflict-free replicated data types, as good candidates for applying optimistic Byzantine fault tolerance. Furthermore, we provide a design guideline on how to achieve eventual consistency and how to recover from conflicts at different replicas. In optimistic Byzantine fault tolerance, a replica executes a request immediately without first establishing a total order of the message, and Byzantine agreement is used only to establish a common state synchronization point and the set of individual states needed to resolve conflicts. The recovery mechanism ensures both replica consistency and the validity of the system by identifying and removing the operations introduced by faulty clients and server replicas.     

Byzantine quorum systems

Summary. Quorum systems are well-known tools for ensuring the consistency and availability of replicated data despite the benign failure of data repositories. In this paper we consider the arbitrary (Byzantine) failure of data repositories and present the first study of quorum system requirements and constructions that ensure data availability and consistency despite these failures. We also consider the load associated with our quorum systems, i.e., the minimal access probability of the busiest server. For services subject to arbitrary failures, we demonstrate quorum systems over servers with a load of , thus meeting the lower bound on load for benignly fault-tolerant quorum systems. We explore several variations of our quorum systems and extend our constructions to cope with arbitrary client failures. Received: October 1996 / Accepted June 1998     

几种常用容错控制系统的可靠性探讨

本文探讨了几种常用的容错控制系统的可靠性，并给出了具体的指标计算方式。     

联盟链中实用拜占庭容错算法的改进

针对实用拜占庭容错算法(PBFT)中存在的通信开销大、算法效率低等问题,结合联盟链特点,提出了一种改进的PBFT算法(score-PBFT,S-PBFT).引入节点评分机制,将节点划分为共识节点、候选节点和预备节点三种类型,并根据节点行为对节点进行动态调整,最大程度上保证共识节点的可靠性.改进了主节点的选举方式,以节点...