Gossip consensus algorithms via quantized communication

This paper considers the average consensus problem on a network of digital links, and proposes a set of algorithms based on pairwise “gossip” communications and updates. We study the convergence properties of such algorithms with the goal of answering two design questions, arising from the literature: whether the agents should encode their communication by a deterministic or a randomized quantizer, and whether they should use, and how, exact information regarding their own states in the update.     

A distributed algorithm for average consensus on strongly connected weighted digraphs

In this work we propose a distributed algorithm to solve the discrete-time average consensus problem on strongly connected weighted digraphs (SCWDs). The key idea is to couple the computation of the average with the estimation of the left eigenvector associated with the zero eigenvalue of the Laplacian matrix according to the protocol described in Qu et al. (2012). The major contribution is the removal of the requirement of the knowledge of the out-neighborhood of an agent, thus paving the way for a simple implementation based on a pure broadcast-based communication scheme.     

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.     

Hybrid feedback stabilization of systems with quantized signals

This paper is concerned with global asymptotic stabilization of continuous-time systems subject to quantization. A hybrid control strategy originating in earlier work (Brockett and Liberzon, IEEE Trans. Automat. Control 45 (2000) 1279) relies on the possibility of making discrete on-line adjustments of quantizer parameters. We explore this method here for general nonlinear systems with general types of quantizers affecting the state of the system, the measured output, or the control input. The analysis involves merging tools from Lyapunov stability, hybrid systems, and input-to-state stability.     

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 average consensus with least-mean-square deviation

We consider a stochastic model for distributed average consensus, which arises in applications such as load balancing for parallel processors, distributed coordination of mobile autonomous agents, and network synchronization. In this model, each node updates its local variable with a weighted average of its neighbors’ values, and each new value is corrupted by an additive noise with zero mean. The quality of consensus can be measured by the total mean-square deviation of the individual variables from their average, which converges to a steady-state value. We consider the problem of finding the (symmetric) edge weights that result in the least mean-square deviation in steady state. We show that this problem can be cast as a convex optimization problem, so the global solution can be found efficiently. We describe some computational methods for solving this problem, and compare the weights and the mean-square deviations obtained by this method and several other weight design methods.     

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.     

Distributed consensus over digital networks with limited bandwidth and time-varying topologies

In this paper, we consider discrete-time distributed average-consensus with limited communication data-rate and time-varying communication topologies. We design a distributed encoding-decoding scheme based on quantization of scaled innovations and a control protocol based on a symmetric compensation method. We develop an adaptive scheme to select the numbers of quantization levels according to whether the associated channel is active or not. We prove that if the network is jointly connected, then under the protocol designed, average-consensus can be asymptotically achieved, and the convergence rate is quantified. Especially, if the duration of any link failure in the network is bounded, then the control gain and the scaling function can be selected properly such that 5-level quantizers suffice for asymptotic average-consensus with an exponential convergence rate.     

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.     

Necessary and sufficient conditions of stationary average consensus for second-order multi-agent systems

This paper investigates the stationary average consensus problem for second-order discrete-time multi-agent systems (SDMAS). A stationary consensus problem is to find a control algorithm that brings the state of a group of agents to a common constant value which is called the collective decision. We introduce the concept of stationary average consensus of SDMAS and propose a consensus algorithm. Based on the polynomial stability and the graph theory, we obtain two necessary and sufficient conditions of stationary average consensus of SDMAS. The last theorem provides an algebraic criterion of stationary average consensus, and can help us to determine the parameters in the consensus algorithm. Furthermore, in this consensus algorithm, only the states of the agents are transferred among the agents. Therefore, this algorithm can not only solve the stationary average consensus problem but also reduce the amount of transferred data. A numerical example is provided to illustrate the efficiency of our results.