{
  "id": "math/0612682",
  "version": "v2",
  "published": "2006-12-22T06:45:41.000Z",
  "updated": "2009-01-14T22:01:01.000Z",
  "title": "Convergence Speed in Distributed Consensus and Control",
  "authors": [
    "Alex Olshevsky",
    "John N. Tsitsiklis"
  ],
  "categories": [
    "math.OC",
    "cs.SY"
  ],
  "abstract": "We study the convergence speed of distributed iterative algorithms for the consensus and averaging problems, with emphasis on the latter. We first consider the case of a fixed communication topology. We show that a simple adaptation of a consensus algorithm leads to an averaging algorithm. We prove lower bounds on the worst-case convergence time for various classes of linear, time-invariant, distributed consensus methods, and provide an algorithm that essentially matches those lower bounds. We then consider the case of a time-varying topology, and provide a polynomial-time averaging algorithm.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2009-01-14T22:01:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "93C85",
      "93B60"
    ],
    "keywords": [
      "lower bounds",
      "worst-case convergence time",
      "distributed consensus methods",
      "fixed communication topology"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math.....12682O"
    }
  }
}