## 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 language | English |
---|---|

Pages (from-to) | 65-78 |

Number of pages | 14 |

Journal | Systems and Control Letters |

Volume | 53 |

Issue number | 1 |

DOIs | |

State | Published - Sep 2004 |

Externally published | Yes |

## Keywords

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