A lower bound for distributed averaging algorithms on the line graph

Alex Olshevsky; John N. Tsitsiklis

doi:10.1109/CDC.2010.5716968

A lower bound for distributed averaging algorithms on the line graph

Alex Olshevsky, John N. Tsitsiklis

Industrial and Enterprise Systems Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 n² 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 language	English (US)
Title of host publication	2010 49th IEEE Conference on Decision and Control, CDC 2010
Pages	4523-4528
Number of pages	6
DOIs	https://doi.org/10.1109/CDC.2010.5716968
State	Published - 2010
Event	2010 49th IEEE Conference on Decision and Control, CDC 2010 - Atlanta, GA, United States Duration: Dec 15 2010 → Dec 17 2010

Publication series

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

Other

Other	2010 49th IEEE Conference on Decision and Control, CDC 2010
Country	United States
City	Atlanta, GA
Period	12/15/10 → 12/17/10

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Access to Document

10.1109/CDC.2010.5716968

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

Olshevsky, A & Tsitsiklis, JN 2010, A lower bound for distributed averaging algorithms on the line graph. in 2010 49th IEEE Conference on Decision and Control, CDC 2010., 5716968, Proceedings of the IEEE Conference on Decision and Control, pp. 4523-4528, 2010 49th IEEE Conference on Decision and Control, CDC 2010, Atlanta, GA, United States, 12/15/10. https://doi.org/10.1109/CDC.2010.5716968

@inproceedings{c627933edc5d462b90ea4024aeca3b72,

title = "A lower bound for distributed averaging algorithms on the line graph",

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.",

author = "Alex Olshevsky and Tsitsiklis, {John N.}",

year = "2010",

doi = "10.1109/CDC.2010.5716968",

language = "English (US)",

isbn = "9781424477456",

series = "Proceedings of the IEEE Conference on Decision and Control",

pages = "4523--4528",

booktitle = "2010 49th IEEE Conference on Decision and Control, CDC 2010",

}

TY - GEN

T1 - A lower bound for distributed averaging algorithms on the line graph

AU - Olshevsky, Alex

AU - Tsitsiklis, John N.

PY - 2010

Y1 - 2010

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

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

UR - http://www.scopus.com/inward/record.url?scp=79953157449&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79953157449&partnerID=8YFLogxK

U2 - 10.1109/CDC.2010.5716968

DO - 10.1109/CDC.2010.5716968

M3 - Conference contribution

AN - SCOPUS:79953157449

SN - 9781424477456

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 4523

EP - 4528

BT - 2010 49th IEEE Conference on Decision and Control, CDC 2010

T2 - 2010 49th IEEE Conference on Decision and Control, CDC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -