On quantized consensus by means of gossip algorithm - Part II: Convergence time
- 1 January 2009
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2958-2965
- https://doi.org/10.1109/acc.2009.5160568
Abstract
This paper deals with the distributed averaging problem over a connected network of agents, subject to a quantization constraint. It is assumed that at each time update, only a pair of agents can update their own numbers in terms of the quantized data being exchanged. The agents are also required to communicate with one another in a stochastic fashion. In the first part of the paper, it was shown that the quantized consensus is reached by means of a stochastic gossip algorithm proposed in a recent paper, for any arbitrary quantization. The current part of the paper considers the expected value of the time at which the quantized consensus is reached. This quantity (corresponding to the worst case) is lower and upper bounded in terms of the topology of the graph, for uniform quantization. In particular, it is shown that the upper bound is related to the principal minors of the weighted Laplacian matrix. A convex optimization is also proposed to determine the set of probabilities (used to pick a pair of agents) which leads to the fast convergence of the gossip algorithm.Keywords
This publication has 17 references indexed in Scilit:
- On quantized consensus by means of gossip algorithm - Part II: Convergence timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- Real-valued average consensus over noisy quantized channelsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- Communication constraints in the average consensus problemAutomatica, 2008
- Average consensus by gossip algorithms with quantized communicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Quantized consensusAutomatica, 2007
- Randomized gossip algorithmsIEEE Transactions on Information Theory, 2006
- Distributed and Collaborative Estimation over Wireless Sensor NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Consensus Problems in Networks of Agents With Switching Topology and Time-DelaysIEEE Transactions on Automatic Control, 2004
- Analysis and optimization of randomized gossip algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Coordination of groups of mobile autonomous agents using nearest neighbor rulesIEEE Transactions on Automatic Control, 2003