Groupe d’études et de recherche en analyse des décisions

Linear Consensus Algorithms and the Infinite Jet-Flow Property of Markov Chains

Sadegh Bolouki

In a multi-agent system, consensus is the process of agents reaching agreement through an iterative data exchange process, constrained by the edges of a fixed, or time varying directed communication graph. It is essential for example in sensor systems (ocean sensing, forests sensing, rainfall collection, etc.) as sensing agents tend to measure different values of the same quantity, because of their large geographical spread. Consensus algorithms are also an important component of distributed estimation schemes in large scale systems. Unconditional consensus refers to the property of convergence to consensus irrespective of the instant and values at which agent states are initialized.

In this talk, we consider discrete time linear consensus algorithms based on time non homogeneous Markov chains, and analyze their convergence properties. For linear algorithms, occurrence of unconditional consensus turns out to be equivalent to ergodicity of the underlying Markov chain. With the help of a new definition, the so-called infinite jet-flow property, we identify a necessary condition for the ergodicity of Markov chains. We then present Sonin’s Theorem, which is a recent extension to non homogeneous Markov chains, of the classical Kolmogorov-Doeblin decomposition-separation for homogeneous Markov chain results (closed recurrent classes of states), and illustrate its relationship with linear consensus algorithms.

Building on Sonin’s Theorem, we show that for a class of chains of stochastic matrices, the class P*, as defined by Touri and Nedic, the infinite jet-flow property is also sufficient for the ergodicity of a Markov chain. The obtained necessary and sufficient condition leads us to a rediscovery and generalization of most of the existing results on linear consensus algorithms in the literature. We also present applications of our theorems to well-known consensus models such as the JLM model, the Krause model, and the Cucker-Smale model.