TY - GEN
T1 - Convergence time for unbiased quantized consensus
AU - Etesami, Seyed Rasoul
AU - Başar, Tamer
PY - 2013
Y1 - 2013
N2 - We revisit the quantized consensus problem on undirected connected graphs, and obtain some strong results on expected time to convergence. This is unbiased consensus, because the edges emanating from a node have equal probability of being selected. The paper first develops an approach that bounds the expected convergence time of the underlying discrete-time dynamics. The bounds are tight for some simple networks when there exists some symmetry in the network. Following this, the paper provides a tight expression for the expected convergence time of unbiased quantized consensus over general networks. Finally, the paper shows that the expected convergence time can be expressed in terms of the effective resistances of the associated Cartesian product graph. The approach adopted in the paper uses the theory of harmonic functions for reversible Markov chains.
AB - We revisit the quantized consensus problem on undirected connected graphs, and obtain some strong results on expected time to convergence. This is unbiased consensus, because the edges emanating from a node have equal probability of being selected. The paper first develops an approach that bounds the expected convergence time of the underlying discrete-time dynamics. The bounds are tight for some simple networks when there exists some symmetry in the network. Following this, the paper provides a tight expression for the expected convergence time of unbiased quantized consensus over general networks. Finally, the paper shows that the expected convergence time can be expressed in terms of the effective resistances of the associated Cartesian product graph. The approach adopted in the paper uses the theory of harmonic functions for reversible Markov chains.
UR - http://www.scopus.com/inward/record.url?scp=84902336471&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902336471&partnerID=8YFLogxK
U2 - 10.1109/CDC.2013.6760867
DO - 10.1109/CDC.2013.6760867
M3 - Conference contribution
AN - SCOPUS:84902336471
SN - 9781467357173
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 6190
EP - 6195
BT - 2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 52nd IEEE Conference on Decision and Control, CDC 2013
Y2 - 10 December 2013 through 13 December 2013
ER -