Degree fluctuations and the convergence time of consensus algorithms

Alex Olshevsky, John N. Tsitsiklis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(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.

Original languageEnglish (US)
Title of host publication2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
Pages6602-6607
Number of pages6
DOIs
StatePublished - Dec 1 2011
Event2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 - Orlando, FL, United States
Duration: Dec 12 2011Dec 15 2011

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0191-2216

Other

Other2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
CountryUnited States
CityOrlando, FL
Period12/12/1112/15/11

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'Degree fluctuations and the convergence time of consensus algorithms'. Together they form a unique fingerprint.

  • Cite this

    Olshevsky, A., & Tsitsiklis, J. N. (2011). Degree fluctuations and the convergence time of consensus algorithms. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 (pp. 6602-6607). [6160945] (Proceedings of the IEEE Conference on Decision and Control). https://doi.org/10.1109/CDC.2011.6160945