{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,3]],"date-time":"2026-09-03T19:01:34Z","timestamp":1788462094480,"version":"build-2803163510"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Control Optim."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/060678324","type":"journal-article","created":{"date-parts":[[2009,2,11]],"date-time":"2009-02-11T23:04:59Z","timestamp":1234393499000},"page":"33-55","source":"Crossref","is-referenced-by-count":416,"title":["Convergence Speed in Distributed Consensus and Averaging"],"prefix":"10.1137","volume":"48","author":[{"given":"Alex","family":"Olshevsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John N.","family":"Tsitsiklis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,2,11]]},"reference":[{"key":"R1","unstructured":"P.A. Bliman and D. Angeli,\n                      Convergence Speed of Unsteady Distributed Consensus: Decay Estimate Along the Settling Spanning-Trees\n                      , http:\/\/arxiv.org\/abs\/math.OC\/0610854 (2007)."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874516"},{"key":"R3","unstructured":"D. Bertsekas and J. N. Tsitsiklis,\n                      Parallel and Distributed Computation: Numerical Methods\n                      , Prentice-Hall, Englewood Cliffs, NJ, 1989."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"V. D. Blondel, J. M. Hendrickx, A. Olshevsky, and J. N. Tsitsiklis,\n                      Convergence in multiagent coordination, consensus, and flocking\n                      , in Proceedings of the Joint 44th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC'05), Seville, Spain, 2005, pp. 2996\u20133000.","DOI":"10.1109\/CDC.2005.1582620"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2006.06.015"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"M. Cao, A. S. Morse, and B. D. O. Anderson,\n                      Coordination of an asynchronous, multi-agent system via averaging\n                      , in Proceedings of the 16th International Federation of Automatic Control World Congress (IFAC), Prague, Czech Republic, 2005.","DOI":"10.3182\/20050703-6-CZ-1902.01081"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Cao, D. A. Spielman, and A. S. Morse,\n                      A lower bound on convergence of a distributed network consensus algorithm\n                      , in Proceedings of the Joint 44th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC'05), Seville, Spain, 2005, pp. 2356\u20132361.","DOI":"10.1109\/CDC.2005.1582514"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2007.12.017"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(89)90021-X"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1974.10480137"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. G. Dimakis, A. D. Sarwate, and M. J. Wainwright,\n                      Geographic gossip: Efficient aggregation for sensor networks\n                      , in Proceedings of the Fifth International Conference on Information Processing in Sensor Networks (IPSN), Nashville, TN, 2006, pp. 69\u201376.","DOI":"10.1145\/1127777.1127791"},{"key":"R12","first-page":"17","volume":"5","author":"Erd\u00f6s P.","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"L. Fang and P. Antsaklis,\n                      On communication requirements for multi-agent consensus seeking\n                      , in Proceedings of the Workshop on Networked Embedded Sensing and Control, Lecture Notes in Control and Inform. Sci. 331, Springer, Berlin, 2006, pp. 53\u201367.","DOI":"10.1007\/11533382_4"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"A. Ganguli, S. Susca, S. Martinez, F. Bullo, and J. Cortes,\n                      On collective motion in sensor networks: Sample problems and distributed algorithms\n                      , in Proceedings of the Joint 44th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC'05), Seville, Spain, 2005, pp. 4239\u20134244.","DOI":"10.1109\/CDC.2005.1582828"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"D. Gr\u00fcnbaum, S. Viscido, and J. K. Parrish,\n                      Extracting interactive control algorithms from group dynamics of schooling fish\n                      , in Cooperative Control, V. Kumar, N. Leonard, and A. S. Morse, eds., Lecture Notes in Control and Inform. Sci. 309, Springer, New York, 2005, pp. 103\u2013117.","DOI":"10.1007\/978-3-540-31595-7_6"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"N. Higham,\n                      Accuracy and Stability of Numerical Algorithms\n                      , 2nd ed., SIAM, Philadelphia, 2002.","DOI":"10.1137\/1.9780898718027"},{"key":"R17","unstructured":"J. M. Hendrickx and V. D. Blondel,\n                      Convergence of linear and non-linear versions of Vicsek model\n                      , in Proceedings of 17th International Symposium on Mathematical Theory of Networks and Systems (MTNS'06), Kyoto, Japan, pp. 1229\u20131240. Available online at http:\/\/www-ics.acs.i.kyoto-u.ac.jp\/mtns06\/papers\/0156.pdf."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2003.812781"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2005.861710"},{"key":"R20","unstructured":"S. Li and H. Wang,\n                      Multi-Agent Coordination Using Nearest-Neighbor Rules: Revisiting the Vicsek Model\n                      , http:\/\/arxiv.org\/abs\/cs.MA\/0407021 (2004)."},{"key":"R21","unstructured":"L. Lov\u00e1sz,\n                      Random walks on graphs: A survey\n                      , in Combinatorics, Paul Erd\u00f6s is Eighty, Vol. 2, D. Mikl\u00f3s, V. T. S\u00f3s, and T. Sz\u00f5nyi, eds., J\u00e1nos Bolyai Mathematical Society, Budapest, 1996, pp. 353\u2013398."},{"key":"R22","unstructured":"Y. Liu and Y. R. Yang,\n                      Reputation propagation and agreement in mobile ad hoc networks\n                      , in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), 2003, pp. 1510\u20131515."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(81)90003-3"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"M. Mehyar, D. Spanos, J. Pongsajapan, S. H. Low, and R. M. Murray,\n                      Distributed averaging on asynchronous communication networks\n                      , in Proceedings of the Joint 44th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC'05), Seville, Spain, 2005, pp. 7446\u20137451.","DOI":"10.1109\/CDC.2005.1583363"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2004.841888"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.883539"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2004.834113"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2006.887293"},{"key":"R29","unstructured":"S. Treil,\n                      Linear Algebra Done Wrong\n                      , http:\/\/www.math.brown.edu\/~treil\/papers\/LADW\/ LADW.html."},{"key":"R30","unstructured":"J. N. Tsitsiklis,\n                      Problems in Decentralized Decision Making and Computation\n                      , Ph.D. Thesis, Department of EECS, MIT, Cambridge, MA, 1984."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1986.1104412"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.75.1226"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysconle.2004.02.022"}],"container-title":["SIAM Journal on Control and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060678324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:08:34Z","timestamp":1787317714000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060678324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/060678324"],"URL":"https:\/\/doi.org\/10.1137\/060678324","relation":{},"ISSN":["0363-0129","1095-7138"],"issn-type":[{"value":"0363-0129","type":"print"},{"value":"1095-7138","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}