The impossibility of boosting distributed service resilience

We study f-resilient services, which are guaranteed to operate as long as no more than f of the associated processes fail. We prove three theorems asserting the impossibility of boosting the resilience of such services. Our first theorem allows any connection pattern between processes and services but assumes these services to be atomic (linearizable) objects. This theorem says that no distributed system in which processes coordinate using f-resilient atomic objects and reliable registers can solve the consensus problem in the presence of f+1 undetectable process stopping failures. In contrast, we show that it is possible to boost the resilience of some systems solving problems easier than consensus: for example, the 2-set-consensus problem is solvable for 2n processes and 2n-1 failures (i.e., wait-free) using n-process consensus services resilient to n-1 failures (wait-free). Our proof is short and self-contained.We then introduce the larger class of failure-oblivious services. These are services that cannot use information about failures, although they may behave more flexibly than atomic objects. An example of such a service is totally ordered broadcast. Our second theorem generalizes the first theorem and its proof to failure-oblivious services.Our third theorem allows the system to contain failure-aware services, such as failure detectors, in addition to failure-oblivious services. This theorem requires that each failure-aware service be connected to all processes; thus, f+1 process failures overall can disable all the failure-aware services. In contrast, it is possible to boost the resilience of a system solving consensus using failure-aware services if arbitrary connection patterns between processes and services are allowed: consensus is solvable for any number of failures using only 1-resilient 2-process perfect failure detectors.As far as we know, this is the first time a unified framework has been used to describe both atomic and non-atomic objects, and the first time boosting analysis has been performed for services more general than atomic objects.     

多智能体系统分布式一致性算法研究现状

综述了多智能体系统分布式一致性问题的研究现状。从理论层面介绍了一致性问题的几种常见定义及与特性相关的主要参数;总结归纳了近年来几种一致性协议及其理论分析结果;分析和阐述了一致性问题的主要应用领域的进展。展望了未来的研究方向。     

A weakest failure detector-based asynchronous consensus protocol for f<n

has been shown to be the weakest realistic failure detector class needed to solve the consensus problem in an asynchronous distributed system prone to f<n process crashes in which communication is by message-passing. However, the only protocol that is known to meet this bound is based on three layers of protocol construction, and is therefore not efficient. This paper presents a surprisingly simple and very efficient direct message-passing implementation of a -based consensus protocol, and proves its correctness.     

Early consensus in an asynchronous system with a weak failure detector

Summary.  Consensus is one of the most fundamental problems in the context of fault-tolerant distributed computing. The problem consists, given a set Ω of processes having each an initial value v _i , in deciding among Ω on a common value v. In 1985, Fischer, Lynch and Paterson proved that the consensus problem is not solvable in an asynchronous system subject to a single process crash. In 1991, Chandra and Toueg showed that, by augmenting the asynchronous system model with a well defined unreliable failure detector, consensus becomes solvable. They also give an algorithm that solves consensus using the ◊? failure detector. In this paper we propose a new consensus algorithm, also using the ◊? failure detector, that is more efficient than the Chandra-Toueg consensus algorithm. We measure efficiency by introducing the notion of latency degree, which defines the minimal number of communication steps needed to solve consensus. The Chandra-Toueg algorithm has a latency degree of 3 (it requires at least three communication steps), whereas our early consensus algorithm requires only two communication steps (latency degree of 2). We believe that this is an interesting result, which adds to our current understanding of the cost of consensus algorithms based on ◊?. Received: April 1995 / Accepted: October 1996     

Necessary and sufficient conditions for broadcast consensus protocols

Summary We consider consensus protocols in asynchronous distributed systems that are based on broadcast communication. We show that a necessary and sufficient condition for the existence of a deterministic consensus protocol is delivery of each broadcast message to at least (n+k+1)/2 processes in ann-process system subject tok crash failures with either eventual fair broadcasting or eventual full broadcasting. The broadcast model captures the idea of a broadcast communication medium, such as the Ethernet, in which messages, if delivered, are delivered immediately and in order but not necessarily to all processes. Louise E. Moser received the Ph.D. degree in mathematics from the University of Wisconsin, Madison, in 1970. From 1970 to 1987 she was a professor of mathematics and computer science at California State University, Hayward. In 1987 she moved to the University of California, Santa Barbara, where is currently on the faculty of the Department of Electrical and Computer Engineering. Her current research interests include parallel and distributed systems, network architectures and communication protocols, and formal methods in software engineering. P.M. Melliar-Smith received the Ph.D. degree in computer science from the University of Cambridge, Cambridge, England, in 1987. He was a senior research scientist and program director at SRI International in Menlo Park (1976–1987), senior research associate at the University of Newcastle Upon Tyne (1973–1976), and principal designer for GEC Computers Ltd. in England (1964–1973). He is currently a professor in the Department of Electrical and Computer Engineering at the University of California, Santa Barbara. His research interests include fault-tolerant distributed systems, high-speed communication networks and protocols, and formal specification and verification. Vivek Agrawala received the B.Tech. degree in chemical engineering in 1984 and the M. Tech. degree in computer technology in 1986, both from the Indian Institute of Technology, Delhi, and a Ph.D. in computer science in 1991 from the University of California, Santa Barbara. Since then he has been a Research Scientist at Siemens Corporate Research, Princeton, New Jersey. His major research interests are distributed algorithms, software design methods, and distributed systems.This research was supported by the National Science Foundation, Grant Numbers CCR-8908515 and NCR-9016361. V. Agrawala's current address is Siemens Corporate Research, 755 College Road East, Princeton, NJ 08540, USA     

A review of soft consensus models in a fuzzy environment

In the consensus reaching processes developed in group decision making problems we need to measure the closeness among experts’ opinions in order to obtain a consensus degree. As it is known, to achieve a full and unanimous consensus is often not reachable in practice. An alternative approach is to use softer consensus measures, which reflect better all possible partial agreements, guiding the consensus process until high agreement is achieved among individuals. Consensus models based on soft consensus measures have been widely used because these measures represent better the human perception of the essence of consensus. This paper presents an overview of consensus models based on soft consensus measures, showing the pioneering and prominent papers, the main existing approaches and the new trends and challenges.     

An impossibility about failure detectors in the iterated immediate snapshot model

The Iterated Immediate Snapshot model (IIS) is an asynchronous computation model where processes communicate through a sequence of one-shot Immediate Snapshot (IS) objects. It is known that this model is equivalent to the usual asynchronous read/write shared memory model, for wait-free task solvability. Its interest lies in the fact that its runs are more structured and easier to analyze than the runs in the shared memory model. As the IIS model and the shared memory model are equivalent for wait-free task solvability, a natural question is the following: Are they still equivalent for wait-free task solvability, when they are enriched with the same failure detector? The paper shows that the answer to this question is “no”.     

Condition-based consensus solvability: a hierarchy of conditions and efficient protocols

The condition-based approach for consensus solvability consists of identifying sets of input vectors, called conditions, for which there exists an asynchronous protocol solving consensus despite the occurrence of up to f process crashes. This paper investigates , the largest set of conditions which allow us to solve the consensus problem in an asynchronous shared memory system.The first part of the paper shows that is made up of a hierarchy of classes of conditions, where d is a parameter (called degree of the condition), starting with and ending with d = 0, where . We prove that each one is strictly contained in the previous one: . Various properties of the hierarchy are also derived. It is shown that a class can be characterized in two equivalent but complementary ways: one is convenient for designing protocols while the other is for analyzing the class properties. The paper also defines a linear family of conditions that can be used to derive many specific conditions. In particular, for each d, two natural conditions are presented.The second part of the paper is devoted to the design of efficient condition-based protocols. A generic condition-based protocol is presented. This protocol can be instantiated with any condition C, , and requires at most shared memory read/write operations per process in the synchronization part of the protocol. Thus, the value (f-d) represents the difficulty of the class . An improvement of the protocol for the conditions in is also presented.Received: 15 November 2001, Accepted: 15 April 2003, Published online: 6 February 2004Parts of it have previously appeared in [23] and [25].     

The anatomy study of consensus agreement in MANETs

Reliability is an important research topic of distributed systems. To achieve fault-tolerance in the distributed systems, healthy processors need to reach a common agreement before performing certain special tasks, even if faults exist in many circumstances. This problem is called as the Byzantine Agreement (BA) problem and it must be addressed. In general, the traditional BA problem is solved in well-defined networks. However, the MANETs (Mobile Ad-hoc Network) are increasing in popularity and its network topology is dynamic in nature. In this paper, the BA problem is re-examined in MANETs. Our protocol uses the minimum number of message exchanges to reach an agreement within the distributed system while tolerating the maximum number of faulty processors in MANETs.     

A bivalency proof of the lower bound for uniform consensus

Bivalency argument is a widely-used technique that employs forward induction to show impossibility results and lower bounds related to consensus. However, for a synchronous distributed system of n processes with up to t potential and f actual crash failures, applying bivalency argument to prove the lower bound for reaching uniform consensus is still an open problem. In this paper, we address this problem by presenting a bivalency proof that the lower bound for reaching uniform consensus is (f+2)-rounds where 0?f?t−2.     

Disc margins of the discrete-time LQR and its application to consensus problem

This article presents a complex gain margin of discrete-time linear quadratic regulator (DLQR) and its application to a consensus problem of multi-agent higher order linear systems. Since the consensus problem can be converted into a robust control problem with perturbation expressed by complex numbers, and since the classical gain and phase margins are not enough to handle the current case, we study the so-called ‘disc margin’ which is somehow a combination of gain and phase margins. We first compute the disc margin of DLQR controller based on a Lyapunov argument, which is simple but yields a relaxed result over those previously reported in the literature. Then, it is shown that the disc margin can be enlarged arbitrarily when the system is asymptotically null controllable with bounded controls and when a low-gain feedback is employed. Based on this fact, the discrete-time consensus problem is solved by a DLQR-based consensus controller. Simulation study shows that the DLQR-based consensus controller has better robustness property against model uncertainties in the input channel.     

Failure detection and consensus in the crash-recovery model

Summary. We study the problems of failure detection and consensus in asynchronous systems in which processes may crash and recover, and links may lose messages. We first propose new failure detectors that are particularly suitable to the crash-recovery model. We next determine under what conditions stable storage is necessary to solve consensus in this model. Using the new failure detectors, we give two consensus algorithms that match these conditions: one requires stable storage and the other does not. Both algorithms tolerate link failures and are particularly efficient in the runs that are most likely in practice – those with no failures or failure detector mistakes. In such runs, consensus is achieved within time and with 4 n messages, where is the maximum message delay and n is the number of processes in the system. Received: May 1998 / Accepted: November 1999     

The proportion of leaders needed for the expected consensus

In order to have a self-organized multi-agent system exhibit some expected collective behavior, it is necessary to add some special agents with information (called leaders) to intervene the system. Then a fundamental question is: how many such leaders are needed? Naturally the answer depends on the model to be studied. In this paper a typical model proposed by Vicsek et al. is used for answering the question. By estimating the characteristics concerning the initial states of all agents and analyzing the system dynamics, we provide lower bounds on the ratio of leaders needed to guarantee the expected consensus.     

Modulus consensus in a network of singularly perturbed systems with collaborative and antagonistic interactions

This paper addresses the modulus consensus in a network of singularly perturbed systems, all of which own multi-time scales characteristics. The interactions among the agents are collaborative and antagonistic interactions, and it can been modelled by a signed directed graph. Also, the effect of time-varying delay has been taken into account when modelling the agent dynamics. Based on singularly perturbed decomposition method, Kronecker product technique and the comparison principle, several sufficient conditions are presented under which networked singularly perturbed time-varying delay systems with collaborative and antagonistic interactions achieve modulus consensus. Moreover, the upper bound of singular perturbation parameter is deduced explicitly. Two simulation examples are presented to illustrate the validity of the proposed results.     

Accelerating average consensus by using the information of second-order neighbours with communication delays

This article investigates the problem of accelerating average consensus in undirected and connected networks. The protocol using the information of second-order neighbours with communication delays is proposed and the delay effects on stability and the convergence speed are analysed, respectively, under an assumption about the network topologies. It is proved that, for appropriate communication delays, networks reach average consensus faster under the proposed protocol than the standard protocol using only the information of first-order neighbours. Finally, a simulation example is presented to illustrate the proposed results.     

The leader-following attitude control of multiple rigid spacecraft systems

In this paper, we consider the leader-following consensus problem for a multiple rigid spacecraft system whose attitude is represented by the unit quaternion. Most results on this problem rely on the assumption that every follower can access the state of the leader and are obtained via a decentralized control manner. By developing a nonlinear distributed observer for the leader system, we can solve this problem via a distributed control scheme under the mild assumptions that the state of the leader can reach every follower through a path and that the communication between followers is bidirectional. Moreover, our result can accommodate a class of desired angular velocities generated by a marginally stable linear autonomous system.     

Consensus Methods for Solving Inconsistency of Replicated Data in Distributed Systems

Replication of data is a popular and convenient form of data organization in distributed systems. Together with its advantages, data replication brings specific problems, which have to be solved by system designers. This paper deals with methods for resolving inconsistencies in data replication. The problem investigated in this work is: How to restore the data consistency if after some time of functioning their versions differ from each other on some sites of the system. We propose a solution of this problem by determining consensus of replicated data versions. We assume that there is a possibility to define a distance function between versions of replicated data, next different consensus choice functions are defined and analyzed. A numerical and practical example of applying these methods is also presented.     

On the use of registers in achieving wait-free consensus

Summary.  The computational power of concurrent data types has been the focus of much recent research. Herlihy showed that such power may be measured by the type’s ability to implement wait-free consensus. Jayanti argued that this ability could be measured in different ways, depending, for example, on whether or not read/write registers could be used in an implementation. He demonstrated the significance of this distinction by exhibiting a nondeterministic type whose ability to implement consensus was increased with the availability of registers. We show that registers cannot increase the ability to implement wait-free consensus of any deterministic type or of any type that can, without them, implement consensus for at least two processes. These results significantly impact the study of the wait-free hierarchies of concurrent data types. In particular, the combination of these results with other recent work suggests that Jayanti’s h _m hierarchy is robust for certain classes of deterministic types.     

Average consensus in networks of dynamic agents with switching topologies and multiple time-varying delays

In this paper, we discuss average consensus problem in undirected networks of dynamic agents with fixed and switching topologies as well as multiple time-varying communication delays. By employing a linear matrix inequality method, we prove that all the nodes in the network achieve average consensus asymptotically for appropriate communication delays if the network topology is connected. Particularly, several feasible linear matrix inequalities are established to determine the maximal allowable upper bound of time-varying communication delays. Numerical examples are given to demonstrate the effectiveness and the sharpness of the theoretical results.     

Computation of the target state and feedback controls for time optimal consensus in multi-agent systems

N identical agents with bounded inputs aim to reach a common target state (consensus) in the minimum possible time. Algorithms for computing this time-optimal consensus point, the control law to be used by each agent and the time taken for the consensus to occur, are proposed. Two types of multi-agent systems are considered, namely (1) coupled single-integrator agents on a plane and, (2) double-integrator agents on a line. At the initial time instant, each agent is assumed to have access to the state information of all the other agents. An algorithm, using convexity of attainable sets and Helly's theorem, is proposed, to compute the final consensus target state and the minimum time to achieve this consensus. Further, parts of the computation are parallelised amongst the agents such that each agent has to perform computations of O(N²) run time complexity. Finally, local feedback time-optimal control laws are synthesised to drive each agent to the target point in minimum time. During this part of the operation, the controller for each agent uses measurements of only its own states and does not need to communicate with any neighbouring agents.