Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links

Summary.  We consider agreement and leader election on asynchronous complete networks when the processors are reliable, but some of the channels are subject to failure. Fischer, Lynch, and Paterson have already shown that no deterministic algorithm can solve the agreement problem on asynchronous networks if any processor fails during the execution of the algorithm. Therefore, we consider only channel failures. The type of channel failure we consider in this paper is Byzantine failure, that is, channels fail by altering messages, sending false information, forging messages, losing messages at will, and so on. There are no restrictions on the behavior of a faulty channel. Therefore, a faulty channel may act as an adversary who forges messages on purpose to prevent the successful completion of the algorithm. Because we assume an asynchronous network, the channel delays are arbitrary. Thus, the faulty channels may not be detectable unless, for example, the faulty channels cause garbage to be sent. We present the first known agreement and leader election algorithm for asynchronous complete networks in which the processors are reliable but some channels may be Byzantine faulty. The algorithm can tolerate up to [n−22] faulty channels, where n is the number of processors in the network. We show that the bound on the number of faulty channels is optimal. When the processors terminate their corresponding algorithms, all the processors in the network will have the same correct vector, where the vector contains the private values of all the processors. Received: May 1994/Accepted: July 1995     

P systems and the Byzantine agreement

We first propose a modular framework for recursive composition of P systems. This modular approach provides encapsulation and information hiding, facilitating the design of P programs for complex algorithms. Using this framework, we developed a P program that solves the classical version of the Byzantine agreement problem, for N participants connected in a complete graph, according to the well known Byzantine agreement algorithm based on EIG trees. We prove the correctness of this modular composition and conclude with a list of open problems.     

量子拜占庭协议中的纠缠态探测

在分布式计算系统中,拜占庭协议是解决其容错问题的一种实用方法。拜占庭问题有一种演变形式,称之为检测的拜占庭协议。这类协议在经典世界中无法解决容错问题,但在量子系统中利用纠缠态却可以。GBKCW协议是一种典型的量子检测拜占庭协议。针对GBKCW协议中数据列表的生成和分发部分,利用量子纠缠态的确定性,探测了参与者共享的量子态,以抵御针对GBKCW的截获重发攻击。     

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.     

Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement

We describe several new algorithms for Byzantine agreement. The first of these is a simplification of the original exponential-time Byzantine agreement algorithm due to Pease, Shostak, and Lamport, and is of comparable complexity to their algorithm. However, its proof is very intuitively appealing. A technique of shifting between algorithms for solving the Byzantine agreement problem is then studied. We present two families of algorithms obtained by applying a shift operator to our first algorithm. These families obtain the same rounds to message length trade-off as do Coan's families but do not require the exponential local computation time (and space) of his algorithms. We also describe a modification of an -resilient algorithm for Byzantine agreement of Dolev, Reischuk, and Strong. Finally, we obtain a hybrid algorithm that dominates all our others, by beginning execution of an algorithm in one family, first shifting into an algorithm of the second family, and finally shifting into an execution of the adaptation of the Dolev, Reischuk, and Strong algorithm.     

Consensus in the presence of mortal Byzantine faulty processes

We consider the problem of reaching agreement in distributed systems in which some processes may deviate from their prescribed behavior before they eventually crash. We call this failure model “mortal Byzantine”. After discussing some application examples where this model is justified, we provide matching upper and lower bounds on the number of faulty processes, and on the required number of rounds in synchronous systems. We then continue our study by varying different system parameters. On the one hand, we consider the failure model under weaker timing assumptions, namely for partially synchronous systems and asynchronous systems with unreliable failure detectors. On the other hand, we vary the failure model in that we limit the occurrences of faulty steps that actually lead to a crash in synchronous systems.     

Connectivity requirements for Byzantine agreement under restricted types of failures

We investigate the problem of reaching Byzantine Agreement in arbitrary networks where both processors and communication links are subject to omission or stopping faults. For the case of deterministic, synchronous algorithms we give a necessary and sufficient condition relating the solvability of the problem to the connectivity of the network. In particular, we show that an algorithm resilient to at mostt faulty processors andk faulty links subject to omission or stopping faults exist, if and only if the network has a connectivity pair (t, k)>(t, k).Vassos Hadzilacos received his BSE from Princeton in 1980 and his PhD from Harvard in 1984, both in Computer Science. He is presently an Assistant Professor at University of Toronto. His research interests are synchronisation and reliability in distributed computing. He is a co-author of a book on Concurrency Control and Reliability in Database Systems.     

Modular construction of an efficient 1-bit Byzantine agreement protocol

This paper presents a new Byzantine agreement protocol that toleratest processor faults usingO(t·logt) processors,t + 1 rounds,O(t ² +o·t) total message bits (whereo is the number of processors that must decide), and messages of maximum size 1 bit. It is the first Byzantine agreement protocol that is simultaneously optimal in rounds, message bits, and message size. The new Byzantine agreement protocol is actually a protocol for the (slightly) more general Byzantine relay problem—a problem which we formulate in this paper. The Byzantine relay protocol is the result of a general recursive construction. Each step of the construction combines two smaller (in terms of number of faults tolerated) Byzantine relay protocols into one larger Byzantine relay protocol. The base case is a collection of very simple Byzantine relay protocols, each tolerant of a small constant number of processor faults. A key new feature of the protocol construction technique presented in this paper is that it does not add unproductive overhead rounds: given two constituent protocols that are optimal in the number of rounds, the composite protocol that is constructed is also optimal in the number of rounds.The work of Jennifer Welch was supported in part by NSF Grant CCR-9010730 and an IBM Faculty Development Award. This work was done while she was at the University of North Carolina at Chapel Hill.     

Optimal agreement protocol in malicious faulty processors andfaulty links

Traditionally, the problems of Byzantine agreement, consensus, and interactive consistency are studied in a fully connected network with processors in malicious failure only. Such problems are reexamined with the assumption of malicious faults on both processors and links. The proposed protocols use the minimum number of message exchanges and can tolerate the maximum number of allowable faulty components to make each fault-free processor reach a common agreement for the cases of processor failure, link failure, or processor and link failure     

Characterization of catastrophic faults in two-dimensional reconfigurable systolic arrays with unidirectional links

The catastrophic fault pattern is a pattern of faults occurring at strategic locations that may render a system unusable regardless of its component redundancy and of its reconfiguration capabilities. In this paper, we extend the characterization of catastrophic fault patterns known for linear arrays to two-dimensional VLSI arrays in which all links are unidirectional. We determine the minimum number of faults required for a fault pattern to be catastrophic and give algorithm for the construction of catastrophic fault patterns with minimum number of faults.     

Consensus of second-order multi-agent systems in the presence of locally bounded faults

We propose an algorithm for consensus of second-order sampled-data multi-agent systems in the presence of misbehaving agents. Each normal agent updates its states following a predetermined control law based on local information while some malicious agents make updates arbitrarily. The normal agents do not know the global topology of the network, but have prior knowledge on the maximum number of malicious agents in their neighborhood. Under the assumption that the network has sufficient connectivity in terms of robustness, we develop a resilient algorithm where each agent ignores the neighbors which have large and small position values to avoid being influenced by malicious agents.     

Adaptive timeliness of consensus in presence of crash and timing faults

The Δ$\mathrm{\Delta }$-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: every correct process terminates its execution within a constant time Δ$\mathrm{\Delta }$ (Δ$\mathrm{\Delta }$-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the Δ$\mathrm{\Delta }$-timed uniform consensus problem in presence of _fc$f_{\mathrm{c}}$ crash processes and _ft$f_{\mathrm{t}}$ timing-faulty processes, and propose a Δ$\mathrm{\Delta }$-timed uniform consensus algorithm. The proposed algorithm is adaptive in the following sense: it solves the Δ$\mathrm{\Delta }$-timed uniform consensus when at least _ft+1$f_{\mathrm{t}}+1$ correct processes exist in the system. If the system has less than _ft+1$f_{\mathrm{t}}+1$ correct processes, the algorithm cannot solve the Δ$\mathrm{\Delta }$-timed uniform consensus. However, as long as _ft+1$f_{\mathrm{t}}+1$ processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ$\mathrm{\Delta }$-timed uniform consensus algorithm tolerating up to _ft$f_{\mathrm{t}}$ timing-faulty processes requires that the system has at least _ft+1$f_{\mathrm{t}}+1$ correct processes. This impossibility result implies that the proposed algorithm attains the maximum resilience about the number of faulty processes. We also show that any Δ$\mathrm{\Delta }$-timed uniform consensus algorithm tolerating up to _ft$f_{\mathrm{t}}$ timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than _ft+1$f_{\mathrm{t}}+1$ non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness.     

Can large fanin circuits perform reliable computations in the presence of faults?

For ordinary circuits with a fixed upper bound on the fanin of its gates it has been shown that logarithmic redundancy is necessary and sufficient to overcome random hardware faults (noise). Here, we consider the same question for unbounded fanin circuits which in the fault-free case can compute Boolean functions in sublogarithmic depth. Now the details of the fault model become more important. One may assume that only gates, resp. only wires may deliver wrong values, or that both gates and wires may behave faulty. The fault tolerance depends on the types of gates that are used, and whether the error probabilities are known exactly or only an upper bound for them. Concerning the first distinction the two most important models are circuits consisting of and- and or-gates with arbitrarily many inputs, and circuits built from the more general type of threshold gates. We will show that in case of faulty and/or-circuits as well as threshold circuits an increase of fanin and size cannot be traded for a depth reduction if the error probabilities are unknown. Gates with large fanin are of no use if errors may occur. Circuits of arbitrary size, but fixed depth can compute only a tiny subset of all Boolean functions reliably. Only in case of threshold circuits and exactly known error probabilities redundancy is able to compensate faults. We describe a transformation from fault-free to fault-tolerant circuits that is optimal with respect to depth keeping the circuit size polynomial.     

拜占庭系统技术研究综述

随着分布式系统规模的增大,设计复杂度也不断提升,系统可靠性所面临的问题也越来越严峻。由于拜占庭协议能够容忍包括人为失误、软件bug和安全漏洞等各种形式的错误,其系统技术和实现方法越来越受到研究者们的重视。介绍和总结了目前拜占庭系统技术的研究成果,分析了目前拜占庭系统的研究现状,并探讨了拜占庭系统的发展趋势。通过分析得出：1)拜占庭系统性能上仍然与已经实用的非拜占庭系统相距较大,占用资源数量仍然较多,需要进一步研究其性能和资源优化技术;2)通过检测错误或者定期修复来降低系统中的错误,是延长系统可持续运行时间的方法,需要研究新的、高效的全面检测拜占庭服务器、合理定期修复等保障系统可持续运行的方法;3)实际应用背景和需求及其特定错误类型的处理方法对拜占庭协议和功能等提出了不一样的要求,需要研究拜占庭系统在实际中的应用和可用性。     

Robustness in the presence of mixed parametric uncertainty andunmodeled dynamics

Continuing the development of the structured singular value approach to robust control design, the authors investigate the problem of computing μ in the case of mixed real parametric and complex uncertainty. The problem is shown to be equivalent to a smooth constrained finite-dimensional optimization problem. In view of the fact that the functional to be maximized may have several local extrema, an upper bound on μ whose computation is numerically tractable is established; this leads to a sufficient condition of robust stability and performance. A historical perspective on the development of the μ theory is included     

Simulation of an open chain of flexible links in a mixed formalism

This article presents the second part of a research work devoted to modeling and control of robots with flexible links. First, we recall the generalization of the Newton Euler equations for an open chain of flexible links. These equations constitute an original dynamic model because they represent the dynamic behavior of the chain with a mixed formalism, because it is both Lagrangian and Eulerian. This formalism allows us to find the linear intrinsic dynamic model of links. Second, we exhibit the constrained nature of these equations. We use a numerical integration method for a constrained system, and an updating procedure well suited to our particular formalism. Finally, simulation results on spatial kinematics involving up to three links are reported. (c) 1995 John Wiley & Sons, Inc.     

Fault‐tolerant formation control of multiple UAVs in the presence of actuator faults

In order to counteract actuator faults in formation flight of multiple unmanned aerial vehicles (UAVs), this paper presents a fault‐tolerant formation control (FTFC) design methodology, in which the reference generator and the finite‐time convergence of FTFC gains are explicitly considered. Feasible references in response to actuator faults can be generated by considering the health and mission conditions of an overall team of UAVs. Moreover, by applying an auxiliary integrated regressor matrix and vector method, FTFC gains can converge within a finite amount of time to facilitate the fault accommodation process. Thus, the negative effects resulting from failed actuators can be compensated by the healthy/redundant actuators in UAVs. Simulation studies of UAV formation flight are carried out to exemplify the effectiveness of this design approach. Copyright © 2015 John Wiley & Sons, Ltd.