DocumentCode :
3435861
Title :
Degree fluctuations and the convergence time of consensus algorithms
Author :
Olshevsky, Alex ; Tsitsiklis, John N.
Author_Institution :
Dept. of Mech. & Aerosp. Eng., Princeton Univ., Princeton, NJ, USA
fYear :
2011
fDate :
12-15 Dec. 2011
Firstpage :
6602
Lastpage :
6607
Abstract :
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(n3ln(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.
Keywords :
computational complexity; directed graphs; time-varying systems; consensus algorithms; degree fluctuations; exponential convergence time; fixed directed graphs; inhomogeneous random walks; time-varying environments; time-varying undirected connected graph; Algorithm design and analysis; Convergence; Eigenvalues and eigenfunctions; Markov processes; Polynomials; Upper bound; Vectors;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on
Conference_Location :
Orlando, FL
ISSN :
0743-1546
Print_ISBN :
978-1-61284-800-6
Electronic_ISBN :
0743-1546
Type :
conf
DOI :
10.1109/CDC.2011.6160945
Filename :
6160945
Link To Document :
بازگشت