Degree fluctuations and the convergence time of consensus algorithms

Alex Olshevsky, John N. Tsitsiklis

Research output: Contribution to journalArticle

Abstract

We consider a consensus algorithm in which every nodein a sequence of undirected, B-connected graphs assigns equal weight to each of its neighbors. Under the assumption that the degree of each node is fixed (except for times when the node has no connections to other nodes), we show that consensus is achieved within a given accuracy on nodes in time B+4n3In(2n/ε). Because there is a direct relation between consensus algorithms in time-varying environments and in homogeneous random walks, our result also translates into a general statement on such random walks.Moreover, we give a simple proof of a result of Cao, Spielman, and Morse that the worst case convergence time becomes exponentially large inthe number of nodes under slight relaxation of the degree constancy assumption.

Original languageEnglish (US)
Article number6497513
Pages (from-to)2626-2631
Number of pages6
JournalIEEE Transactions on Automatic Control
Volume58
Issue number10
DOIs
StatePublished - Oct 2 2013

Keywords

  • Consensus protocols
  • Markov chains
  • distributed control

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this