Consensus Algorithms and the Decomposition-Separation Theorem

DOI10.1109/TAC.2015.2504480zbMATH Open1359.60090arXiv1303.6674MaRDI QIDQ2980384FDOQ2980384

Authors: Sadegh Bolouki, Roland P. Malhamé 

Publication date: 3 May 2017

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: Convergence properties of time inhomogeneous Markov chain based discrete and continuous time linear consensus algorithms are analyzed. Provided that a so-called infinite jet flow property is satisfied by the underlying chains, necessary conditions for both consensus and multiple consensus are established. A recenet extension by Sonin of the classical Kolmogorov-Doeblin decomposition-separation for homogeneous Markov chains to the inhomogeneous case is then employed to show that the obtained necessary conditions are also sufficient when the chain is of Class P*, as defined by Touri and Nedic. It is also shown that Sonin's theorem leads to a rediscovery and generalization of most of the existing related consensus results in the literature.

Full work available at URL: https://arxiv.org/abs/1303.6674

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Continuous-time Markov processes on discrete state spaces (60J27)

Cited In (13)

• Alternating projection method for intersection of convex sets, multi-agent consensus algorithms, and averaging inequalities
• Quorum tree abstractions of consensus protocols
• A zero-one law for Markov chains
• A Unified Framework for Continuous-Time Unconstrained Distributed Optimization
• Paxos consensus, deconstructed and abstracted
• Probabilistic consensus via polling and majority rules
• Removal independent consensus methods for closed \(\beta \)-systems of sets
• The deformed consensus protocol
• General resilient consensus algorithms
• The Complexity Gap between Consensus and Safe-Consensus
• A hierarchy of conditions for consensus solvability
• MinMax algorithms for stabilizing consensus
• Cutoff bounds for consensus algorithms

This page was built for publication: Consensus Algorithms and the Decomposition-Separation Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2980384)