A simple proof of the uniform consensus synchronous lower bound

We give a simple and intuitive proof of an f+2 round lower bound for uniform consensus. That is, we show that for every uniform consensus algorithm tolerating t failures, and for every f?t−2, there is an execution with f failures that requires f+2 rounds.     

Implementing uniform reliable broadcast with binary consensus in systems with fair-lossy links

When implementing multivalued consensus using binary consensus, previous algorithms assume the availability of uniform reliable broadcast, which is not implementable in systems with fair-lossy links. In this paper, we show that with binary consensus we can implement uniform reliable broadcast directly in systems with fair-lossy links, and thus the separate assumption of the availability of uniform reliable broadcast is not necessary. We further prove that, when binary consensus instances are available only as black boxes, any implementation of uniform reliable broadcast in the fair-lossy link model requires the invocation of an infinite number of binary consensus instances even if no process ever broadcasts any messages, and this is true even when multivalued consensus is used.     

Bounded cost algorithms for multivalued consensus using binary consensus instances

In this paper, we present two bounded cost algorithms that solve multivalued consensus using binary consensus instances. Our first algorithm uses log₂n number of binary consensus instances where n is the number of processes, while our second algorithm uses at most binary consensus instances, where is the maximum length of the binary representation of all proposed values in the run. Both algorithms are significant improvements over the previous algorithm in [A. Mostefaoui, M. Raynal, F. Tronel, From binary consensus to multivalued consensus in asynchronous message-passing systems, Information Processing Letters 73 (5–6) (2000) 207–212], where the number of binary consensus instances needed to solve one multivalued consensus is unbounded.     

Design of consensus and adaptive consensus filters for distributed parameter systems

This work establishes an abstract framework that considers the distributed filtering of spatially varying processes using a sensor network. It is assumed that the sensor network consists of groups of sensors, each of which provides a number of state measurements from sensing devices that are not necessarily identical and which only transmit their information to their own sensor group. A modification to the local spatially distributed filters provides the non-adaptive case of spatially distributed consensus filters which penalize the disagreement amongst themselves in a dynamic manner. A subsequent modification to this scheme incorporates the adaptation of the consensus gains in the disagreement terms of all local filters. Both the well-posedness of these two consensus spatially distributed filters and the convergence of the associated observation errors to zero in appropriate norms are presented. Their performance is demonstrated on three different examples of a diffusion partial differential equation with point measurements.     

A constructive proof for FLP

We present a simple elementary proof for the result of Fischer, Lynch, and Paterson (FLP) [J. ACM 32 (2) (April 1985) 374-382] that the consensus problem cannot be solved deterministically in an asynchronous system where a single process may fail by crashing. Our proof is, in contrast to the original, constructive in its crucial lemma, showing not only that a non-terminating execution does exist but also how it can be constructed. Our proof is based on the new notion of non-uniformity of a configuration. Non-uniformity is different from bivalency, which is the central notion in the original proof as well as in proofs of related results.     

Implementing the weakest failure detector for solving the consensus problem

The concept of unreliable failure detector was introduced by Chandra and Toueg as a mechanism that provides information about process failures. This mechanism has been used to solve several agreement problems, such as the consensus problem. In this paper, algorithms that implement failure detectors in partially synchronous systems are presented. First two simple algorithms of the weakest class to solve the consensus problem, namely the Eventually Strong class (?S), are presented. While the first algorithm is wait-free, the second algorithm is f-resilient, where f is a known upper bound on the number of faulty processes. Both algorithms guarantee that, eventually, all the correct processes agree permanently on a common correct process, i.e. they also implement a failure detector of the class Omega (Ω). They are also shown to be optimal in terms of the number of communication links used forever. Additionally, a wait-free algorithm that implements a failure detector of the Eventually Perfect class (?P) is presented. This algorithm is shown to be optimal in terms of the number of bidirectional links used forever.     

A lower bound on the period length of a distributed scheduler

Ad-scheduling of a graphG is a sequence of rounds, each consisting of some of the nodes of the graph, such that the distance between any two nodes participating in the same round is greater thand. Ad-scheduler is a protocol that determines ad-scheduling ofG. A 1-scheduler is applicable to process scheduling in a resource-sharing system, and to proper communication scheduling of the half-duplex model in communication networks. A 2-scheduler can be used as a collision-free protocol for radio networks.In this paper a simpled-scheduler is analyzed. We first discuss basic properties of this scheduling, and give a complete characterization of this scheduling for trees and cycles. We study the period length of this scheduling, and the main result is a worst-case exponential lower bound for this length.The research of Shmuel Zaks was supported by the Fund for Research in Electronics, Computers, and Communications adminstered by the Israeli Academy of Sciences and Humanities.     

Performance and robustness of discrete and finite time average consensus algorithms

In this paper, we review some of the main discrete and finite time average consensus implementations in the literature, discussing their strengths and shortcomings from a theoretical and empirical point of view. In particular, we compare the computational characteristics of the different algorithms, their behaviour considering different underlying network topologies, their ability to withstand packet losses and their robustness to attacks where a malicious node aims to steer the result of the algorithm towards a desired value, without letting the other nodes detect the attack. Specifically, we will discuss synchronous approaches, where the nodes broadcast their messages, and asynchronous approaches, where the nodes need to be able to address their neighbours individually on a point-to-point basis (i.e. by direct communication between a specific sender and a specific receiver). With the aim to overcome some critical aspects of the considered methodologies, in this paper we present an asynchronous consensus algorithm based on a broadcast-only approach. The algorithm is characterised by a good trade-off between the robustness of synchronous approaches and to low computational demands of asynchronous methods.     

Distributed consensus control of unicycle agents in the presence of external disturbances

In this paper, a distributed consensus control strategy is presented for a team of unicycle agents subject to external disturbances. Bounded disturbances with unknown dynamics on both translational and angular velocities are applied to the system. The key idea is to design the control inputs of each agent in such a way that, after a finite time, agents move with an acute angle with respect to a reference vector typically used for the consensus control of disturbance-free single-integrator agents. Convergence to consensus is then proved using Lyapunov theory. Simulation results confirm the efficacy of the proposed controller.     

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.     

Iterative learning approaches to design finite-time consensus protocols for multi-agent systems

In this paper, the finite-time output consensus problem of multi-agent systems is considered by using the iterative learning control (ILC) approach. Two classes of distributed protocols are constructed from the two-dimensional system point of view (with time step and iteration number as independent variables), and are termed as iterative learning protocols. If learning gains are chosen appropriately, then all agents in a directed graph can be enabled to achieve finite-time consensus with the iterative learning protocols. Moreover, all agents in a directed graph can be guaranteed to reach finite-time consensus at any desired terminal output if the iterative learning protocols are improved by introducing the desired terminal output to some (not necessarily all) of the agents. Simulation results are finally presented to illustrate the performance and effectiveness of our iterative learning protocols.     

A uniform approach for programming distributed heterogeneous computing systems

Large-scale compute clusters of heterogeneous nodes equipped with multi-core CPUs and GPUs are getting increasingly popular in the scientific community. However, such systems require a combination of different programming paradigms making application development very challenging.In this article we introduce libWater, a library-based extension of the OpenCL programming model that simplifies the development of heterogeneous distributed applications. libWater consists of a simple interface, which is a transparent abstraction of the underlying distributed architecture, offering advanced features such as inter-context and inter-node device synchronization. It provides a runtime system which tracks dependency information enforced by event synchronization to dynamically build a DAG of commands, on which we automatically apply two optimizations: collective communication pattern detection and device-host-device copy removal.We assess libWater’s performance in three compute clusters available from the Vienna Scientific Cluster, the Barcelona Supercomputing Center and the University of Innsbruck, demonstrating improved performance and scaling with different test applications and configurations.     

Easy impossibility proofs for distributed consensus problems

Easy proofs are given, of the impossibility of solving several consensus problems (Byzantine agreement, weak agreement, Byzantine firing squad, approximate agreement and clock synchronization) in certain communication graphs.It is shown that, in the presence ofm faults, no solution to these problems exists for communication graphs with fewer than 3m+1 nodes or less than 2m+1 connectivity. While some of these results had previously been proved, the new proofs are much simpler, provide considerably more insight, apply to more general models of computation, and (particularly in the case of clock synchronization) significantly strengthen the results.Michael J. Fischer is currently Professor of Computer Science at Yale University, New Haven, CT, where he heads the Theory of Computation Group. He is also Editor-in-Chief of the Journal of the Association for Computing Machinery. His research interests include theory of distributed systems, cryptographic protocols, and computational complexity.Dr. Fischer received the B. S. degree in matheamtics from the University of Michigan, Ann Arbor, in 1963, and the M. A. and Ph. D. degrees in applied mathematics from Harvard University, Cambridge, MA, in 1965 and 1968, respectively. He has taught previously at Carnegie-Mellon University, the Massachusetts Institute of Technology, and University of Washington.Nancy Lynch is currently Associate professor of Computer Science at M.I.T., and heads the Theory of Distributed Systems group in M.I.T.'s Laboratory for Computer Science. Her interests are in all aspects of distributed computing theory, including formal models, algorithms, analysis, and correctness proofs. Dr. Lynch received the B.S. degree in mathematics from Brooklyn College in 1968 and the Ph. D. degree in mathematics from M.I.T. in 1972. She has served on the faculty of Tufts University, the University of Southern California, Florida International University, Georgia Tech.Michael Merritt is currently a member of the technical staff with AT&T Bell Laboratories. During the 1984 –85 academic year, he was a visiting lecturer at M.I.T., sponsered by Bell Labs. His research interests include distributed computation, cryptography and security. Dr. Merritt received the B. S. degree in computer science and philosophy from Yale in 1978 and the M. Sc. and Ph. D. degrees in 1980 and 1983, respectively, both in information and computer science from Georgia Tech. He is a member of SIGACT and of Computer Professionals for Social Responsibility.This paper has appeared in the ACM Conference Proceedings of PODC 1985. © 1985, Association for Computing Machinery, reprinted by permission     

Multi-target consensus circle pursuit for multi-agent systems via a distributed multi-flocking method

This paper studies the multi-target consensus pursuit problem of multi-agent systems. For solving the problem, a distributed multi-flocking method is designed based on the partial information exchange, which is employed to realise the pursuit of multi-target and the uniform distribution of the number of pursuing agents with the dynamic target. Combining with the proposed circle formation control strategy, agents can adaptively choose the target to form the different circle formation groups accomplishing a multi-target pursuit. The speed state of pursuing agents in each group converges to the same value. A Lyapunov approach is utilised to analyse the stability of multi-agent systems. In addition, a sufficient condition is given for achieving the dynamic target consensus pursuit, and which is then analysed. Finally, simulation results verify the effectiveness of the proposed approaches.     

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.     

Diamond Quorum Consensus for High Capacity and Efficiency in a Replicated Database System

Many quorum consensus protocols have been proposed for the management of replicated data in a distributed environment. The advantages of a replicated database system over a non-replicated one include high availability and low response time. We note further that the multiple sites can act as multiple agents so that at any time, multiple requests can be handled in parallel. This feature leads to the desirable consequence of high workload capacity. In this paper, we define a new metric of read-capacity for this feature. We propose a new protocol called diamond quorum consensus which has two major properties that are superior to the previous protocols of majority, tree, grid, and hierarchical quorum consensus: (1) it has the highest read-capacity, (2) it has the smallest optimal read quorum size of 2. We show that these two features are achievable without jeopardizing the availability. The small quorum size is a significant feature because it relates to the messaging cost. Few previous work on quorum consensus has discussed the handling of partition failure, which in many cases will depend on the quorum consensus protocol, we show how we can use the generalized virtual partition protocol to handle partition failure in the case of diamond quorum consensus.     

dOpenCL: Towards uniform programming of distributed heterogeneous multi-/many-core systems

Modern computer systems become increasingly distributed and heterogeneous by comprising multi-core CPUs, GPUs, and other accelerators. Current programming approaches for such systems usually require the application developer to use a combination of several programming models (e.g., MPI with OpenCL or CUDA) in order to exploit the system’s full performance potential. In this paper, we present dOpenCL (distributed OpenCL)—a uniform approach to programming distributed heterogeneous systems with accelerators. dOpenCL allows the user to run unmodified existing OpenCL applications in a heterogeneous distributed environment. We describe the challenges of implementing the OpenCL programming model for distributed systems, as well as its extension for running multiple applications concurrently. Using several example applications, we compare the performance of dOpenCL with MPI + OpenCL and standard OpenCL implementations.     

Distributed synthesis for well-connected architectures

We study the synthesis problem for external linear or branching specifications and distributed, synchronous architectures with arbitrary delays on processes. External means that the specification only relates input and output variables. We introduce the subclass of uniformly well-connected (UWC) architectures for which there exists a routing allowing each output process to get the values of all inputs it is connected to, as soon as possible. We prove that the distributed synthesis problem is decidable on UWC architectures if and only if the output variables are totally ordered by their knowledge of input variables. We also show that if we extend this class by letting the routing depend on the output process, then the previous decidability result fails. Finally, we provide a natural restriction on specifications under which the whole class of UWC architectures is decidable.