A lower bound for distributed averaging algorithms on the line graph

Alex Olshevsky, John N. Tsitsiklis

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

Abstract

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)
Title of host publication2010 49th IEEE Conference on Decision and Control, CDC 2010
Pages4523-4528
Number of pages6
DOIs
StatePublished - 2010
Event2010 49th IEEE Conference on Decision and Control, CDC 2010 - Atlanta, GA, United States
Duration: Dec 15 2010Dec 17 2010

Publication series

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

Other

Other2010 49th IEEE Conference on Decision and Control, CDC 2010
CountryUnited States
CityAtlanta, GA
Period12/15/1012/17/10

ASJC Scopus subject areas

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

Fingerprint 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