Linear time average consensus on fixed graphs

Alex Olshevsky

Research output: Contribution to journalConference articlepeer-review


We describe a protocol for the average consensus problem on any fixed undirected graph whose convergence time scales linearly in the total number nodes n. More precisely we provide a protocol which results in each node having a value within an e of the initial average after O (Equation presented) iterations. The protocol is completely distributed, with the exception of requiring all nodes to know the same upper bound U on the total number of nodes which is correct within a. constant multiplicative factor.

Original languageEnglish (US)
Pages (from-to)94-99
Number of pages6
Issue number22
StatePublished - Oct 1 2015


  • Consensus and gossip algorithms
  • Cooperative control
  • Distributed algorithms
  • Markov chains
  • Multi-agent systems

ASJC Scopus subject areas

  • Control and Systems Engineering

Cite this