TY - GEN

T1 - Degree fluctuations and the convergence time of consensus algorithms

AU - Olshevsky, Alex

AU - Tsitsiklis, John N.

PY - 2011/12/1

Y1 - 2011/12/1

N2 - We consider a consensus algorithm in which every node in a time-varying undirected connected graph assigns equal weight to each of its neighbors. Under the assumption that the degree of any given node is constant in time, we show that the algorithm achieves consensus within a given accuracy ε on n nodes in time O(n 3ln(n=ε)). Because there is a direct relation between consensus algorithms in time-varying environments and inhomogeneous random walks, our result also translates into a general statement on such random walks. Moreover, we give simple proofs that the convergence time becomes exponentially large in the number of nodes n under slight relaxations of the above assumptions. We prove that exponential convergence time is possible for consensus algorithms on fixed directed graphs, and we use an example of Cao, Spielman, and Morse to give a simple argument that the same is possible if the constant degrees assumption is even slightly relaxed.

AB - We consider a consensus algorithm in which every node in a time-varying undirected connected graph assigns equal weight to each of its neighbors. Under the assumption that the degree of any given node is constant in time, we show that the algorithm achieves consensus within a given accuracy ε on n nodes in time O(n 3ln(n=ε)). Because there is a direct relation between consensus algorithms in time-varying environments and inhomogeneous random walks, our result also translates into a general statement on such random walks. Moreover, we give simple proofs that the convergence time becomes exponentially large in the number of nodes n under slight relaxations of the above assumptions. We prove that exponential convergence time is possible for consensus algorithms on fixed directed graphs, and we use an example of Cao, Spielman, and Morse to give a simple argument that the same is possible if the constant degrees assumption is even slightly relaxed.

UR - http://www.scopus.com/inward/record.url?scp=84860691686&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860691686&partnerID=8YFLogxK

U2 - 10.1109/CDC.2011.6160945

DO - 10.1109/CDC.2011.6160945

M3 - Conference contribution

AN - SCOPUS:84860691686

SN - 9781612848006

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 6602

EP - 6607

BT - 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011

T2 - 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011

Y2 - 12 December 2011 through 15 December 2011

ER -