TY - GEN

T1 - Convergence time for unbiased quantized consensus

AU - Etesami, Seyed Rasoul

AU - Başar, Tamer

PY - 2013/1/1

Y1 - 2013/1/1

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 -