Fast Linear Iterations for Distributed Averaging

Lin Xiao; Stephen Boyd

Fast Linear Iterations for Distributed Averaging

Lin Xiao, Stephen Boyd

Research output: Contribution to journal › Conference article › peer-review

212 Scopus citations

Abstract

We consider the problem of finding a linear iteration that yields distributed averaging consensus over a network, i.e., that asymptotically computes the average of some initial values given at the nodes. When the iteration is assumed symmetric, the problem of finding the fastest converging linear iteration can be cast as a semidefinite program, and therefore efficiently and globally solved. These optimal linear iterations are often substantially faster than several simple heuristics that are based on the Laplacian matrix of the associated graph.

Original language	English
Pages (from-to)	4997-5002
Number of pages	6
Journal	Proceedings of the IEEE Conference on Decision and Control
Volume	5
State	Published - 2003
Externally published	Yes
Event	42nd IEEE Conference on Decision and Control - Maui, HI, United States Duration: Dec 9 2003 → Dec 12 2003

Keywords

Distributed consensus
Linear system
Semidefinite program
Spectral radius

Cite this

@article{a4bf5984d14e494cb4b61f2cd06a09a9,

title = "Fast Linear Iterations for Distributed Averaging",

abstract = "We consider the problem of finding a linear iteration that yields distributed averaging consensus over a network, i.e., that asymptotically computes the average of some initial values given at the nodes. When the iteration is assumed symmetric, the problem of finding the fastest converging linear iteration can be cast as a semidefinite program, and therefore efficiently and globally solved. These optimal linear iterations are often substantially faster than several simple heuristics that are based on the Laplacian matrix of the associated graph.",

keywords = "Distributed consensus, Linear system, Semidefinite program, Spectral radius",

author = "Lin Xiao and Stephen Boyd",

year = "2003",

language = "English",

volume = "5",

pages = "4997--5002",

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

issn = "0191-2216",

note = "null ; Conference date: 09-12-2003 Through 12-12-2003",

}

TY - JOUR

T1 - Fast Linear Iterations for Distributed Averaging

AU - Xiao, Lin

AU - Boyd, Stephen

PY - 2003

Y1 - 2003

N2 - We consider the problem of finding a linear iteration that yields distributed averaging consensus over a network, i.e., that asymptotically computes the average of some initial values given at the nodes. When the iteration is assumed symmetric, the problem of finding the fastest converging linear iteration can be cast as a semidefinite program, and therefore efficiently and globally solved. These optimal linear iterations are often substantially faster than several simple heuristics that are based on the Laplacian matrix of the associated graph.

AB - We consider the problem of finding a linear iteration that yields distributed averaging consensus over a network, i.e., that asymptotically computes the average of some initial values given at the nodes. When the iteration is assumed symmetric, the problem of finding the fastest converging linear iteration can be cast as a semidefinite program, and therefore efficiently and globally solved. These optimal linear iterations are often substantially faster than several simple heuristics that are based on the Laplacian matrix of the associated graph.

KW - Distributed consensus

KW - Linear system

KW - Semidefinite program

KW - Spectral radius

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

M3 - Conference article

AN - SCOPUS:1542289981

SN - 0191-2216

VL - 5

SP - 4997

EP - 5002

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

Y2 - 9 December 2003 through 12 December 2003

ER -

Fast Linear Iterations for Distributed Averaging

Abstract

Keywords

Other files and links

Fingerprint

Cite this