TY - JOUR
T1 - Convergence Time for Unbiased Quantized Consensus over Static and Dynamic Networks
AU - Etesami, Seyed Rasoul
AU - Başar, Tamer
N1 - Funding Information:
This work was supported in part by the "Cognitive & Algorithmic Decision Making" project grant through the College of Engineering of the University of Illinois, and in part by AFOSR MURI Grant FA 9550-10-1-0573 and National Science Foundation (NSF) Grant CCF 11-11342.
Publisher Copyright:
© 2015 IEEE.
PY - 2016/2
Y1 - 2016/2
N2 - In this paper, the question of expected time to convergence is addressed for unbiased quantized consensus on undirected connected graphs, and some strong results are obtained. The paper first provides a tight expression for the expected convergence time of the unbiased quantized consensus over general but fixed networks. It is shown that the maximum expected convergence time lies within a constant factor of the maximum hitting time of an appropriate lazy random walk, using the theory of harmonic functions for reversible Markov chains. Following this, and using electric resistance analogy of the reversible Markov chains, the paper provides an upper bound of O(nmD log n) for the expected convergence time to consensus, where n, m and D, denote, respectively, the number of nodes, the number of edges, and the diameter of the network. Moreover, the paper shows that the above upper bound is tight up to a factor of log n for some simple graphs such as line graph and cycle. Finally, the results are extended to bound the expected convergence time of the underlying dynamics in time-varying networks. Modeling such dynamics as the evolution of a time inhomogeneous Markov chain, the paper derives an upper bound for the expected convergence time of the dynamics using the spectral representation of the networks. This upper bound is significantly better than earlier ones given for different quantized consensus protocols over time-varying graphs.
AB - In this paper, the question of expected time to convergence is addressed for unbiased quantized consensus on undirected connected graphs, and some strong results are obtained. The paper first provides a tight expression for the expected convergence time of the unbiased quantized consensus over general but fixed networks. It is shown that the maximum expected convergence time lies within a constant factor of the maximum hitting time of an appropriate lazy random walk, using the theory of harmonic functions for reversible Markov chains. Following this, and using electric resistance analogy of the reversible Markov chains, the paper provides an upper bound of O(nmD log n) for the expected convergence time to consensus, where n, m and D, denote, respectively, the number of nodes, the number of edges, and the diameter of the network. Moreover, the paper shows that the above upper bound is tight up to a factor of log n for some simple graphs such as line graph and cycle. Finally, the results are extended to bound the expected convergence time of the underlying dynamics in time-varying networks. Modeling such dynamics as the evolution of a time inhomogeneous Markov chain, the paper derives an upper bound for the expected convergence time of the dynamics using the spectral representation of the networks. This upper bound is significantly better than earlier ones given for different quantized consensus protocols over time-varying graphs.
KW - Convergence time
KW - Markov chains
KW - quantized consensus
KW - random walk
KW - spectral representation
KW - time varying networks
UR - http://www.scopus.com/inward/record.url?scp=84961999208&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84961999208&partnerID=8YFLogxK
U2 - 10.1109/TAC.2015.2440568
DO - 10.1109/TAC.2015.2440568
M3 - Article
AN - SCOPUS:84961999208
SN - 0018-9286
VL - 61
SP - 443
EP - 455
JO - IRE Transactions on Automatic Control
JF - IRE Transactions on Automatic Control
IS - 2
M1 - 7117385
ER -