A lower bound for distributed averaging algorithms on the line graph

Alex Olshevsky, John N. Tsitsiklis

Research output: Contribution to journalArticlepeer-review


We derive lower bounds on the convergence speed of a widely used class of distributed averaging algorithms. In particular, we prove that any distributed averaging algorithm whose state consists of a single real number and whose (possibly nonlinear) update function satisfies a natural smoothness condition has a worst case running time of at least on the order of n2 on a line network of n nodes. Our results suggest that increased memory or expansion of the state space is crucial for improving the running times of distributed averaging algorithms.

Original languageEnglish (US)
Article number5876302
Pages (from-to)2694-2698
Number of pages5
JournalIEEE Transactions on Automatic Control
Issue number11
StatePublished - Nov 2011
Externally publishedYes


  • Cooperative control
  • distributed averaging
  • load balancing

ASJC Scopus subject areas

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


Dive into the research topics of 'A lower bound for distributed averaging algorithms on the line graph'. Together they form a unique fingerprint.

Cite this