On the Convergence of Perturbed Non-Stationary Consensus Algorithms
- 1 April 2009
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE INFOCOM 2009 - The 28th Conference on Computer Communications
- p. 2132-2140
- https://doi.org/10.1109/infcom.2009.5062137
Abstract
We consider consensus algorithms in their most general setting and provide conditions under which such algorithms are guaranteed to converge, almost surely, to a consensus. Let {A(t),B(t)} isin RN times N be (possibly) random, non-stationary matrices and {x(t),m(t)} isin RN times 1 be state and perturbation vectors, respectively. For any consensus algorithm of the form x(t + 1) = A(t)x(t) + B(t)m(t), we provide conditions under which consensus is achieved almost surely, i.e., Pr {limtrarrinfin x(t) = c1} = 1 for some c isin R. Moreover, we show that this general result subsumes recently reported results for specific consensus algorithms classes, including sum-preserving, non-sum-preserving, quantized and noisy gossip algorithms. Also provided are the e-converging time for any such converging iterative algorithm, i.e., the earliest time at which the vector x(t) is e close to consensus, and sufficient conditions for convergence in expectation to the initial node measurements average.Keywords
This publication has 23 references indexed in Scilit:
- Distributed Average Consensus With Dithered QuantizationIEEE Transactions on Signal Processing, 2008
- Broadcast gossip algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Randomized consensus algorithms over large scale networksIEEE Journal on Selected Areas in Communications, 2008
- Geographic Gossip: Efficient Averaging for Sensor NetworksIEEE Transactions on Signal Processing, 2008
- Broadcast gossip algorithms: Design and analysis for consensusPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Distributed Average Consensus using Probabilistic QuantizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Randomized gossip algorithmsIEEE Transactions on Information Theory, 2006
- Fast linear iterations for distributed averagingSystems & Control Letters, 2004
- Coordination of groups of mobile autonomous agents using nearest neighbor rulesIEEE Transactions on Automatic Control, 2003
- A theory of nonsubtractive ditherIEEE Transactions on Signal Processing, 2000