Decentralised minimal-time consensus

This study considers the discrete-time dynamics of a network of agents that exchange information according to the nearest-neighbour protocol under which all agents are guaranteed to reach consensus asymptotically. We present a fully decentralised algorithm that allows any agent to compute the consensus value of the whole network in finite time using only the minimal number of successive values of its own history. We show that this minimal number of steps is related to a Jordan block decomposition of the network dynamics and present an algorithm to obtain the minimal number of steps in question by checking a rank condition on a Hankel matrix of the local observations. Furthermore, we prove that the minimal number of steps is related to other algebraic and graph theoretical notions that can be directly computed from the Laplacian matrix of the graph and from the underlying graph topology. © 2011 IEEE.

Impact of heterogeneous link qualities and network connectivity on binary consensus

In this paper we consider a network that is trying to reach consensus over the occurrence of an event while communicating over Additive White Gaussian Noise (AWGN) channels. We characterize the impact of different link qualities and network connectivity on consensus performance by analyzing both the asymptotic and transient behaviors. More specifically, we derive a tight approximation for the second largest eigenvalue of the probability transition matrix. We furthermore characterize the dynamics of each individual node. © 2009 AACC.

Decentralised minimal-time dynamic consensus

This paper considers a group of agents that aim to reach an agreement on individually received time-varying signals by local communication. In contrast to static network averaging problem, the consensus considered in this paper is reached in a dynamic sense. A discrete-time dynamic average consensus protocol can be designed to allow all the agents tracking the average of their reference inputs asymptotically. We propose a minimal-time dynamic consensus algorithm, which only utilises a minimal number of local observations of a randomly picked node in a network to compute the final consensus signal. Our results illustrate that with memory and computational ability, the running time of distributed averaging algorithms can be indeed improved dramatically as suggested by Olshevsky and Tsitsiklis. © 2012 AACC American Automatic Control Council).

Consensus in non-commutative spaces

Convergence analysis of consensus algorithms is revisited in the light of the Hilbert distance. The Lyapunov function used in the early analysis by Tsitsiklis is shown to be the Hilbert distance to consensus in log coordinates. Birkhoff theorem, which proves contraction of the Hilbert metric for any positive homogeneous monotone map, provides an early yet general convergence result for consensus algorithms. Because Birkhoff theorem holds in arbitrary cones, we extend consensus algorithms to the cone of positive definite matrices. The proposed generalization finds applications in the convergence analysis of quantum stochastic maps, which are a generalization of stochastic maps to non-commutative probability spaces. ©2010 IEEE.

Phase synchronization through entrainment by a consensus input

The paper proposes a synchronization mechanism in a set of nonlinear oscillators interconnected through a communication network. In contrast to many existing results, we do not employ strong, diffusive couplings between the individual oscillators. Instead, each individual oscillator is weakly forced by a linear resonator system. The resonator systems are synchronized using results from consensus theory. The synchronized resonator systems force the frequencies of the nonlinear oscillators to a constant frequency and thereby yield synchronization of the oscillators. We prove this result using the theory of small forcings of stable oscillators. This synchronization scheme allows for synchronization of nonlinear oscillators over uniformly connected communication graphs. ©2010 IEEE.