A lower bound for distributed averaging algorithms on the line graph

Alex Olshevsky; John N. Tsitsiklis

doi:10.1109/TAC.2011.2159652

A lower bound for distributed averaging algorithms on the line graph

Alex Olshevsky, John N. Tsitsiklis

Research output: Contribution to journal › Article › peer-review

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)
Article number	5876302
Pages (from-to)	2694-2698
Number of pages	5
Journal	IEEE Transactions on Automatic Control
Volume	56
Issue number	11
DOIs	https://doi.org/10.1109/TAC.2011.2159652
State	Published - Nov 2011
Externally published	Yes

Keywords

Cooperative control
distributed averaging
load balancing

ASJC Scopus subject areas

Control and Systems Engineering
Computer Science Applications
Electrical and Electronic Engineering

Online availability

10.1109/TAC.2011.2159652

Library availability

Discover UIUC Full Text

Cite this

@article{77ec700254f44505bc024ceddfd1f265,

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

keywords = "Cooperative control, distributed averaging, load balancing",

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

note = "Funding Information: Manuscript received April 01, 2010; revised November 02, 2010; accepted June 05, 2011. Date of publication June 16, 2011; date of current version November 02, 2011. This work was supported by the National Science Foundation (NSF) under grants ECCS-0701623 and CMMI-0856063. Recommended by Associate Editor Y. Hong.",

year = "2011",

month = nov,

doi = "10.1109/TAC.2011.2159652",

language = "English (US)",

volume = "56",

pages = "2694--2698",

journal = "IEEE Transactions on Automatic Control",

issn = "0018-9286",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "11",

}

TY - JOUR

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

AU - Olshevsky, Alex

AU - Tsitsiklis, John N.

N1 - Funding Information: Manuscript received April 01, 2010; revised November 02, 2010; accepted June 05, 2011. Date of publication June 16, 2011; date of current version November 02, 2011. This work was supported by the National Science Foundation (NSF) under grants ECCS-0701623 and CMMI-0856063. Recommended by Associate Editor Y. Hong.

PY - 2011/11

Y1 - 2011/11

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.

KW - Cooperative control

KW - distributed averaging

KW - load balancing

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

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

U2 - 10.1109/TAC.2011.2159652

DO - 10.1109/TAC.2011.2159652

M3 - Article

AN - SCOPUS:80455156406

SN - 0018-9286

VL - 56

SP - 2694

EP - 2698

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 11

M1 - 5876302

ER -

A lower bound for distributed averaging algorithms on the line graph

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this