Fast linear iterations for distributed averaging

Lin Xiao, Stephen Boyd

Research output: Contribution to journalArticlepeer-review

1858 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 common heuristics that are based on the Laplacian of the associated graph. We show how problem structure can be exploited to speed up interior-point methods for solving the fastest distributed linear iteration problem, for networks with up to a thousand or so edges. We also describe a simple subgradient method that handles far larger problems, with up to 100000 edges. We give several extensions and variations on the basic problem.

Original languageEnglish
Pages (from-to)65-78
Number of pages14
JournalSystems and Control Letters
Volume53
Issue number1
DOIs
StatePublished - Sep 2004
Externally publishedYes

Keywords

  • Distributed consensus
  • Graph Laplacian
  • Linear system
  • Semidefinite programming
  • Spectral radius

Fingerprint

Dive into the research topics of 'Fast linear iterations for distributed averaging'. Together they form a unique fingerprint.

Cite this