Message and time efficient consensus protocols for synchronous distributed systems

For a synchronous distributed system of n processes with up to t potential and f   actual crash failures, where (t<n-1,f≤t)$(t<n-1,f\le t)$, the time lower bound for a protocol to achieve consensus is min(t+1,f+2)$\min (t+1,f+2)$ rounds. Currently, most researches in this field focus on the time efficiency of consensus protocols. This paper proposes consensus protocols for synchronous distributed systems that achieve both message and time   efficiency. Based on an early stopping consensus protocol for synchronous distributed system with crash failures, we propose a rotating coordinator scheme that significantly reduces message complexity. However, this protocol is not time efficient because it requires min(t+1,f+3)$\min (t+1,f+3)$ rounds to reach consensus. Thus, to achieve both time and message efficiency, we propose another protocol in which (t+1)$(t+1)$ coordinators are used to send messages in each round. Furthermore, we show that the proposed consensus protocol with crash failures can be revised to be more message-efficient with orderly crash failures. When a process is able to send more than one message to another in a round, we propose an optimal message efficient early stopping consensus protocol for synchronous distributed systems with orderly crash failures.     

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.     

A note on atomicity: Boosting Test&Set to solve consensus

This short note shows how a simple extension of object types with consensus number 2 boosts them to an infinite consensus number. This extension is a simple embedding of a shared memory write within the base operation defining the corresponding type with consensus number 2. The style of this note is voluntarily informal.     

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].     

Robust consensus of multi-agent systems with diverse input delays and asymmetric interconnection perturbations

The consensus problem of second-order multi-agent systems with diverse input delays is investigated. Based on the frequency-domain analysis, decentralized consensus conditions are obtained for the multi-agent system with symmetric coupling weights. Then, the robustness of the symmetric system with asymmetric perturbation is studied. A bound of the largest singular value of the perturbation matrix is obtained as the robust consensus condition. Simulation examples illustrate the design procedure of consensus protocols and validate the correctness of the results.     

Asynchronous bounded lifetime failure detectors

A failure detector provides processes with a single primitive that, each time it is invoked, returns to the invoking process information related to failures. This research note extends failure detectors by allowing processes to invoke an additional primitive whose effect is to limit the time scope of some properties offered by the failure detector. This simple addition makes possible to weaken the definition of failure detector classes without weakening their power. Two distributed computing problems are used to illustrate the benefit of such an approach, namely the consensus problem and the construction of an atomic register.     

具有时延的多个体系统的一致性问题综述

考察了具有时延的多个体系统的一致性问题．根据不同的分析方法,介绍了关于具有通信时延的多个体系统一致性问题的结果,并对各种分析方法的特点进行了比较．此外,对具有输入时延的多个体系统的现有一致性结果也作了介绍．最后评述了该研究领域存在的问题以及今后的研究方向．     

The gap in circumventing the impossibility of consensus

The impossibility of reaching deterministic consensus in an asynchronous and crash prone system was established for a weak variant of the problem, usually called weak consensus, where a set of processes need to decide on a common value in {0,1}, so that both 0 and 1 are possible decision values. On the other hand, approaches to circumventing the impossibility focused on a stronger variant of the problem, called consensus, where the processes need to decide on one of the values they initially propose (0 or 1). This paper studies the computational gap between the two problems. We show that any set of deterministic object types that, combined with registers, implements weak consensus, also implements consensus. Then we exhibit a non-deterministic type that implements weak consensus, among any number of processes, but, combined with registers, cannot implement consensus even among two processes. In modern terminology, this type has consensus power 1 and weak consensus power ∞.     

封装机系统中的送料过程同步控制研究

在卷纸封装机中，存在送料过程中的同步控制问题。我们提出了一套送料过程中的同步控制方案。我们在卷纸供送系统的驱动轴上安装一个半圆形金属片，在侧面装上接近开关探头，通过判断每次光电传感器检测到色标时接近开关的输出状态，就能知道包装纸供送系统是滞后还是超前于卷纸供送系统，从而使伺服电机正、反转或不动，实现了送料过程中的同步控制。     

Fast and simple distributed consensus

Summary The problem of fault-tolerant agreement is fundamental to distributed computing. When agreement is to be reached in spite of arbitrary behavior by faulty processors, this problem is calledDistributed Consensus. By requiring that the number of faulty processors be , wheren is the number of processors in the system, we are able to derive two new protocols forDistributed Consensus. Both are simple and use messages that are only one bit in length, and both provide forearly stopping: the fewer failures there are, the fewer rounds of communication are required. One protocol is optimal with respect to the number of rounds of communication required, and the other is asymptotically optimal with respect to the total number of message bits exchanged. James E. Burns received the B.S. degree in mathematics from the California Institute of Technology, the M.B.I.S. degree from Georgia State University, and the M.S. and Ph.D. degrees in information and computer science from the Georgia Institute of Technology. He served on the faculty of Computer Science at Indiana University and the College of Computing at the Georgia Institute of Technology before joining Bellcore in 1993. He is currently a Member of Technical Staff in the Network Control Research Department, where he is studying the telephone control network with special interest in behavior when faults occur. He also has research interests in theoretical issues of distributed and parallel computing, especially relating to problems of synchronization and fault tolerance. Gil Neiger was born on February 19, 1957 in New York, New York. In June 1979, he received an A.B. in Mathematics and Psycholinguistics from Brown University in Proidence, Rhode Island. In February 1985, he spent two weeks picking cotton in Nicaragua in a brigade of international volunteers. In January 1986, he received an M.S. in Computer Science from Cornell University in Ithaca, New York and, in August 1988, he received a Ph.D. in Computer Science, also from Cornell University. On August 20, 1988, Dr. Neiger married Hilary Lombard in Lansing, New York. Since August 1988, he has been an Assistant Professor in the College of Computing (formely School of Information and Computer Science) at the Georgia Institute of Technology in Atlanta, Georgia. Dr. Neiger is a member of the editorial board of theChicago Journal of Theoretical Computer Science and theJournal of Parallel and Distributed Computing.This author was supported in part by the National Science Foundation under grants CCR-8909663, CCR-9106627, and CCR-9301454.     

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     

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     

Mean square consensus of stochastic multi-agent systems with nonlinear dynamics by distributed event-triggered strategy

This paper is concerned with the problem of mean square consensus for nonlinear multi-agent systems with state-dependent noise perturbations. A distributed event-triggered mechanism which can be used to reduce the number of controller updates and communication load is developed to apply in stochastic dynamical systems. By combining the tools of graph theory and stochastic analysis, the sufficient conditions are given to ensure that mean square consensus in the multi-agent systems can be achieved exponentially. The convergence rate is also analytically derived. Moreover, the feasibility of the proposed distributed event-triggered strategy is further verified by exclusion of Zeno behaviour. Finally, some numerical examples are given to demonstrate the effectiveness of the obtained results.     

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.     

Continuous-time and sampled-data-based average consensus with logarithmic quantizers

This paper considers the average consensus problem for multi-agent systems with continuous-time first-order dynamics. Logarithmic quantization is considered in the communication channels, and continuous-time and sampled-data-based protocols are proposed. For the continuous-time protocol, we give an explicit upper bound of the consensus error in terms of the initial states, the quantization density and the parameters of the network graph. It is shown that in contrast with the case with uniform quantization, the consensus error in the logarithmic quantization case is always uniformly bounded, independent of the quantization density, and the β$\beta$-asymptotic average consensus is ensured under the proposed protocol, i.e. the asymptotic consensus error converges to zero as the sector bound β$\beta$ of the logarithmic quantizer approaches zero. For the sampled-data-based protocol, we give sufficient conditions on the sampling interval to ensure the β$\beta$-asymptotic average consensus. Numerical examples are given to demonstrate the effectiveness of the protocols.     

Robust gossiping with an application to consensus

We study deterministic gossiping in synchronous systems with dynamic crash failures. Each processor is initialized with an input value called rumor. In the standard gossip problem, the goal of every processor is to learn all the rumors. When processors may crash, then this goal needs to be revised, since it is possible, at a point in an execution, that certain rumors are known only to processors that have already crashed. We define gossiping to be completed, for a system with crashes, when every processor knows either the rumor of processor v or that v has already crashed, for any processor v. We design gossiping algorithms that are efficient with respect to both time and communication. Let t<n be the number of failures, where n is the number of processors. If , then one of our algorithms completes gossiping in O(log²t) time and with O(npolylogn) messages. We develop an algorithm that performs gossiping with O(n^1.77) messages and in O(log²n) time, in any execution in which at least one processor remains non-faulty. We show a trade-off between time and communication in gossiping algorithms: if the number of messages is at most O(npolylogn), then the time has to be at least . By way of application, we show that if n−t=Ω(n), then consensus can be solved in O(t) time and with O(nlog²t) messages.     

Distributed adaptive consensus control of Lipschitz nonlinear multi-agent systems using output feedback

This paper addresses output-feedback-based distributed adaptive consensus control of multi-agent systems having Lipschitz nonlinear dynamics. Distributed dynamic protocols are designed based on the relative outputs of neighbouring agents and the adaptive coupling weights, under which consensus is reached between the nonlinear systems for all undirected connected communication topologies. Extension to the case of Lipschitz nonlinear multi-agent systems subjected to external disturbances is further studied, and a robust adaptive fully distributed consensus protocol is suggested. By application of a decoupling technique, necessary and sufficient conditions for the existence of these consensus protocols are provided in terms of linear matrix inequalities. Finally, numerical simulation results are demonstrated to validate the effectiveness of the theoretical results.     

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