Fast Byzantine Consensus

We present the first protocol that reaches asynchronous Byzantine consensus in two communication steps in the common case. We prove that our protocol is optimal in terms of both number of communication steps and number of processes for two--step consensus. The protocol can be used to build a replicated state machine that requires only three communication steps per request in the common case. Further, we show a parameterized version of the protocol that is safe despite f Byzantine failures and, in the common case, guarantees two-step execution despite some number t of failures (tle f). We show that this parameterized two-step consensus protocol is also optimal in terms of both number of communication steps and number of processes.     

Synchronous Byzantine quorum systems

Summary. Quorum systems have been used to implement many coordination problems in distributed systems such as mutual exclusion, data replication, distributed consensus, and commit protocols. Malkhi and Reiter recently proposed quorum systems that can tolerate Byzantine failures; they called these systems Byzantine quorum systems and gave some examples of such quorum systems. In this paper, we propose a new definition of Byzantine quorums that is appropriate for synchronous systems. We show how these quorums can be used for data replication and propose a general construction of synchronous Byzantine quorums using standard quorum systems. We prove tight lower bounds on the load of synchronous Byzantine quorums for various patterns of failures and we present synchronous Byzantine quorums that have optimal loads that match the lower bounds for two failure patterns. Received: June 1998 / Accepted: August 1999     

Global consensus for discrete-time multi-agent systems with input saturation constraints

In this paper, we consider the global consensus problem for discrete-time multi-agent systems with input saturation constraints under fixed undirected topologies. We first give necessary conditions for achieving global consensus via a distributed protocol based on relative state measurements of the agent itself and its neighboring agents. We then focus on two special cases, where the agent model is either neutrally stable or a double integrator. For the neutrally stable case, any linear protocol of a particular form, which solves the consensus problem for the case without input saturation constraints, also solves the global consensus problem for the case with input saturation constraints. For the double integrator case, we show that a subset of linear protocols, which solve the consensus problem for the case without saturation constraints, also solve the global consensus problem for the case with input saturation constraints. The results are illustrated by numerical simulations.     

Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems

This paper is on the consensus problem in asynchronous distributed systems where (up to f) processes (among n) can exhibit a Byzantine behavior, i.e., can deviate arbitrarily from their specification. One way to solve the consensus problem in such a context consists of enriching the system with additional oracles that are powerful enough to cope with the uncertainty and unpredictability created by the combined effect of Byzantine behavior and asynchrony. This paper presents two kinds of Byzantine asynchronous consensus protocols using two types of oracles, namely, a common coin that provides processes with random values and a failure detector oracle. Both allow the processes to decide in one communication step in favorable circumstances. The first is a randomized protocol for an oblivious scheduler model that assumes n > 6f. The second one is a failure detector-based protocol that assumes n > tif. These protocols are designed to be particularly simple and efficient in terms of communication steps, the number of messages they generate in each step, and the size of messages. So, although they are not optimal in the number of Byzantine processes that can be tolerated, they are particularly efficient when we consider the number of communication steps they require to decide and the number and size of the messages they use. In that sense, they are practically appealing.     

Fault detection for Byzantine quorum systems

In this paper, we explore techniques to detect Byzantine server failures in asynchronous replicated data services. Our goal is to detect arbitrary failures of data servers in a system where each client accesses the replicated data at only a subset (quorum) of servers in each operation. In such a system, some correct servers can be out-of-date after a write and can therefore, return values other than the most up-to-date value in response to a client's read request, thus complicating the task of determining the number of faulty servers in the system at any point in time. We initiate the study of detecting server failures in this context, and propose two statistical approaches for estimating the risk posed by faulty servers based on responses to read requests     

Byzantine Agreement in a generalized connected network

Traditionally, the Byzantine Agreement (BA) problem is studied either in a fully connected network or in a broadcast network. A generalized network model for BA is proposed in this paper. A fully-connected network or a broadcast network is a special case of the new network architecture. Under the new generalized network model, the BA problem is reexamined with the assumption of malicious faults on both processors and transmission medium (TM), as opposed to previous studies which consider malicious faults on processors only. The proposed algorithm uses the minimum number of message exchanges, and can tolerate the maximum number of allowable faulty components to make each healthy processor reach a common agreement for the cases of processor failures, TM failures, or processor/TM failures. The results can also be used to solve the interactive consistency problem and the consensus problem     

Approximate Byzantine consensus in sparse,mobile ad-hoc networks

We consider the problem of approximate consensus in mobile ad-hoc networks in the presence of Byzantine nodes. Due to nodes’ mobility, the topology is dynamic. We propose a protocol based on the linear iteration method. The nodes collect information during several consecutive rounds: moving gives them the opportunity to gather progressively enough values. A novel sufficient and necessary condition guarantees the final convergence: from time to time only the correct nodes that own a value equal to (or very close to) either the minimum or the maximum value have to receive enough messages (quantity constraint) with either higher or lower values (quality constraint). Of course, nodes’ motion should not prevent this requirement to be fulfilled. New concepts are introduced to prove the correctness of the protocol. Based on particular mobility scenarios, simulations are conducted to analyze the impact of some parameters on three variants of the protocol.     

The Failure Discovery problem

We define a simple variant of the Byzantine agreement (BA) problem, called the Failure Discovery (FD) problem, that roughly speaking, amounts to reaching BA provided that no failures are discovered. We show how a protocol for FD can be extended to one for BA, with no message overhead in the failure-free runs. We also show that, for so-calledbenign failures, if the FD protocol satisfies an additional property, the message-preserving extension to a BA protocol can be accomplished with minimal time overhead in the failure-free runs. Our results show that FD is a useful building block for BA; indeed, it has been used in this way in a companion paper (Hadzilacos and Halpern, 1993).The work of V. Hadzilacos was supported, in part, by a grant from the Natural Sciences and Engineering Research Council of Canada.     

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

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

Renaming in synchronous message passing systems with Byzantine failures

We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when the original namespace of the processors is unbounded, this problem cannot be solved in an a priori bounded number of rounds for , where n is the size of the network and t is the number of failures. On the other hand, for n > 3t, we present a Byzantine renaming algorithm that runs in O(lg n) rounds. In addition, we present a fast, efficient strong renaming algorithm for n > t, which runs in rounds, where N ₀ is the value of the highest identifier among all the correct processors.     

基于Gossip协议的拜占庭共识算法

区块链是一种对等网络的分布式账本系统,具备去中心化、不可篡改、安全可信等特点,因此受到了广泛关注。在区块链系统中,典型的拜占庭错误包括操作错误、网络延迟、系统崩溃、恶意攻击等。现有共识算法不仅对区块链中拜占庭节点的容错能力低,而且对区块链系统的可扩展性差。针对这一问题,文中提出了基于Gossip协议的拜占庭共识算法,使系统可以容忍小于一半的节点为拜占庭节点,能够达到XFT共识算法的容错能力。同时,因为采用了统一的数据结构,所以系统具有更好的可扩展性,并且有利于正确节点识别区块链系统中的恶意节点。在该算法中,提案节点随着区块链长度的变化而转移,系统中所有节点都处于对等的地位,从而避免了单点故障问题,进而使得系统具有更好的动态负载均衡的性能。     

Consensus of multi-agent systems based on sampled-data control

This article studies the consensus problem in directed networks, assuming that each agent is with double-integrator dynamics and only obtains the measurements of its positions relative to its neighbours at sampling instants. We propose a protocol based on sampled-data control and derive an equivalent characterisation of the solvability of the consensus problem under this protocol. In virtue of this equivalent characterisation, we further consider two cases: fixed topology and switching topology. For the first case, we present a set of sampling periods and feedback coefficients which ensure that the protocol can solve a consensus problem. For the second case, we derive sufficient conditions for the protocol to solve a consensus problem under arbitrary switching signals and under a class of switching signals, respectively. Finally, simulations are provided to illustrate the effectiveness of the theoretical results.     

The minimum information about failures for solving non-local tasks in message-passing systems

We first define the basic notions of local and non-local tasks for distributed systems. Intuitively, a task is local if, in a system with no failures, each process can compute its output value locally by applying some local function on its own input value (so the output value of each process depends only on the process’ own input value, not on the input values of the other processes); a task is nonlocal otherwise. All the interesting distributed tasks, including all those that have been investigated in the literature (e.g., consensus, set agreement, renaming, atomic commit, etc.) are non-local. In this paper we consider non-local tasks and determine the minimum information about failures that is necessary to solve such tasks in message-passing distributed systems. As part of this work, we also introduces weak set agreement—a natural weakening of set agreement—and show that, in some precise sense, it is the weakest nonlocal task in message-passing systems.     

基于代理的Byzantine一致性协议的研究

本文在研究了国内外Byzantine协议的基础上提出了一种新的Byzantine一致性协议,即基于代理的Byzantine一致性协议。该协议按照Byzantine容错机制将所有参与运算的进程分成很多小块,每个块设有一个代理。通过代理,块内的进程向其他块的进程发送运算结果。这样,在进程发生Byzantine错误时可以先在块的内部处理,从而可以有效地减少容错的开销和时延,提高系统的安全性。     

Continuous consensus with ambiguous failures

Continuous consensus (CC) is the problem of maintaining up-to-date and identical copies of a “core” of information about the past at all correct processes in the system (Mizrahi and Moses, 2008 [6]). This is a primitive that supports simultaneous coordination among processes, and eliminates the need for issuing separate instances of consensus for different tasks. Recent work has presented new simple and efficient optimum protocols for continuous consensus in the crash and (sending) omissions failure models. For every pattern of failures, these protocols maintain at each and every time point a core that subsumes that maintained by any other continuous consensus protocol. This paper considers the continuous consensus problem in the face of harsher failures: general omissions and authenticated Byzantine failures. Computationally efficient optimum protocols for CC do not exist in these models if $P\ne NP$. A variety of CC protocols are presented. The first is a simple protocol that enters every interesting event into the core within $t+1$ rounds (where $t$ is the bound on the number of failures), provided there are a majority of correct processes. The second is a protocol that achieves similar performance so long as $n>t$ (i.e., there is always guaranteed to be at least one correct process). The final protocol makes use of active failure monitoring and failure detection to include events in the core much faster in many runs of interest. Its performance is established based on a nontrivial property of minimal vertex covers in undirected graphs. The results are adapted to the authenticated Byzantine failure model, in which it is assumed that faulty processes are malicious, but correct processes have unforgeable signatures. Finally, the problem of uniform CC is considered. It is shown that a straightforward version of uniform CC is not solvable in the setting under study. A weaker form of uniform CC is defined, and protocols achieving it are presented.     

Distributed robust consensus control of multi-agent systems with heterogeneous matching uncertainties

This paper considers the distributed consensus problem of linear multi-agent systems subject to different matching uncertainties for both the cases without and with a leader of bounded unknown control input. Due to the existence of nonidentical uncertainties, the multi-agent systems discussed in this paper are essentially heterogeneous. For the case where the communication graph is undirected and connected, based on the local state information of neighboring agents, a fully distributed continuous adaptive consensus protocol is designed, under which the consensus error is uniformly ultimately bounded and exponentially converges to a small adjustable bounded set. For the case where there exists a leader whose control input is unknown and bounded, a distributed adaptive consensus protocol is proposed to ensure the boundedness of the consensus error. A sufficient condition for the existence of the proposed protocols is that each agent is stabilizable.     

提升分片规模和有效性的多轮PBFT验证方案

分片技术是解决区块链扩容难题的可行方案,但存在分片规模与分片内验证有效性的矛盾：采用PBFT共识算法,即使总体拜占庭节点数占比不超过三分之一,单个分片内拜占庭节点占比也存在一定概率会超过三分之一,无法验证共识。针对该问题,提出多轮PBFT共识的改进方案,在提高分片规模的同时,保证分片内PBFT共识的验证有效性。总结了已知项目的解决方案并分析优缺点,详细分析了分片的有效共识验证,提出并论述了多轮验证方案,给出了拜占庭比例节点较高情况下多轮轮数的合理取值。基于实验得到的数据与现有方案进行对比,验证了多轮方案在提升整体TPS方面的有效性,为分片方案的进一步研究提供有益的参考。     

Scalable and leaderless Byzantine consensus in cloud computing environments

Traditional Byzantine consensus in distributed systems requires n ≥ 3f + 1, where n is the number of nodes. In this paper, we present a scalable and leaderless Byzantine consensus implementation based on gossip, requiring only n ≥ 2f + 1 nodes. Unlike conventional distributed systems, the network topology of cloud computing systems is often not fully connected, but loosely coupled and layered. Hence, we revisit the Byzantine consensus problem in cloud computing environments, in which each node maintains some number of neighbors, called local view. The message complexity of our Byzantine consensus scheme is O(n), instead of O(n ²). Experimental results and correctness proof show that our Byzantine consensus scheme can solve the Byzantine consensus problem safely in a scalable way without a bottleneck and a leader in cloud computing environments.     

基于实用拜占庭容错的改进的多主节点共识机制

针对实用拜占庭容错（PBFT）共识协议通信复杂度高导致的共识效率低、单一主节点发生故障或存在拜占庭行为时会导致共识过程停止的问题,提出了改进的多主节点实用拜占庭容错（IMPBFT）共识机制。首先,通过节点的共识轮数、存在拜占庭行为的共识轮数以及节点被赋予的优先值,计算出节点的有效共识轮数,再依据有效共识轮数的大小选出多个主节点。其次,对原共识机制进行改进,使所有节点利用改进的机制进行共识。最后,引入流水线来实现IMPBFT共识的并发执行。在进行流水线操作时,不同轮共识的多阶段消息统一签名,并且不再使用固定周期来控制流水线。理论研究和实验结果表明,IMPBFT的多主节点结构相较单一主节点的共识结构更加安全稳定;与平方级通信量的PBFT和信用委托拜占庭容错（CDBFT）共识相比,IMPBFT将通信量降至线性级;在交易吞吐量、扩展性和交易时延方面,IMPBFT的性能要优于PBFT和CDBFT;使用“多阶段消息统一签名、无固定周期”流水线的IMPBFT,比未使用流水线的IMPBFT在交易吞吐量上提高了75.2%。     

Reach a nonlinear consensus for MAS via doubly stochastic quadratic operators

This technical note addresses the new nonlinear protocol class of doubly stochastic quadratic operators (DSQOs) for coordination of consensus problem in multi-agent systems (MAS). We derive the conditions for ensuring that every agent reaches consensus on a desired rate of the group's decision where the group decision value in its agent's initial statuses varies. Besides that, we investigate a nonlinear protocol sub-class of extreme DSQO (EDSQO) to reach a consensus for MAS to a common value with nonlinear low-complexity rules and fast time convergence if the interactions for each agent are not selfish. In addition, to extend the results to reach a consensus and to avoid the selfish case we specify a general class of DSQO for reaching a consensus under any given case of initial states. The case that MAS reach a consensus by DSQO is if each member of the agent group has positive interactions of DSQO (PDSQO) with the others. The convergence of both EDSQO and PDSQO classes is found to be directed towards the centre point. Finally, experimental simulations are given to support the analysis from theoretical aspect.