The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Convergence Speed in Distributed Consensus and Averaging
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
Olfati-Saber, R., & Murray, R. M. (2004) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.834113 · Cited by 12,788
Consensus and Cooperation in Networked Multi-Agent Systems
Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007) · Proceedings of the IEEE · doi:10.1109/jproc.2006.887293 · Cited by 10,522 · cited 1×
“The distributed consensus problem has historically appeared in many diverse areas, such as parallel computation [30, 31, 3], control theory [18, 28], and communication networks [24, 22].”
Coordination of groups of mobile autonomous agents using nearest neighbor rules
Jadbabaie, A., Lin, J., & Morse, A. S. (2003) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2003.812781 · Cited by 8,339
Novel Type of Phase Transition in a System of Self-Driven Particles
Vicsek, T., Czirók, A., Ben-Jacob, E., Cohen, I., & Shochet, O. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.1226 · Cited by 7,380
Degroot, M. H. (1974) · Journal of the American Statistical Association · doi:10.1080/01621459.1974.10480137 · Cited by 4,004
Accuracy and Stability of Numerical Algorithms: Second Edition
Higham, N. J. (2002) · doi:10.1137/1.9780898718027 · Cited by 3,803
Distributed Subgradient Methods for Multi-Agent Optimization
Nedic, A., & Ozdaglar, A. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2008.2009515 · Cited by 3,719
Fast linear iterations for distributed averaging
Xiao, L., & Boyd, S. (2004) · Systems & Control Letters · doi:10.1016/j.sysconle.2004.02.022 · Cited by 2,706
Stability of multiagent systems with time-dependent communication links
Moreau, L. (2005) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.841888 · Cited by 2,706
Boyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874516 · Cited by 2,439
Cited by
Distributed Subgradient Methods for Multi-Agent Optimization
Nedic, A., & Ozdaglar, A. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2008.2009515 · Cited by 3,719
An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination
Cao, Y., Yu, W., Ren, W., & Chen, G. (2013) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2012.2219061 · Cited by 2,399
Constrained Consensus and Optimization in Multi-Agent Networks
Nedic, A., Ozdaglar, A., & Parrilo, P. A. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2041686 · Cited by 2,086
Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms
Bullo, F., Cortés, J., & Martínez, S. (2009) · Princeton University Press eBooks · doi:10.1515/9781400831470 · Cited by 1,509
Consensus-Based Decentralized Auctions for Robust Task Allocation
Choi, H.-L., Brunet, L., & How, J. P. (2009) · IEEE Transactions on Robotics · doi:10.1109/tro.2009.2022423 · Cited by 1,128
Naïve Learning in Social Networks and the Wisdom of Crowds
Golub, B., & Jackson, M. O. (2010) · American Economic Journal: Microeconomics · doi:10.1257/mic.2.1.112 · Cited by 979
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization
Sundhar Ram, S., Nedić, A., & Veeravalli, V. V. (2010) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-010-9737-7 · Cited by 814
“The work in this paper is also related at a much broader level to the distributed consensus algorithms [7, 20–29].”
ResultOn Distributed Convex Optimization Under Inequality and Equality Constraints
Zhu, M., & Martinez, S. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2167817 · Cited by 759
Opinion Dynamics and Learning in Social Networks
Acemoglu, D., & Ozdaglar, A. (2011) · Dynamic Games and Applications · doi:10.1007/s13235-010-0004-1 · Cited by 705
“12 10 The DeGroot model and variations have also been studied extensively in the cooperative control literature as natural algorithms for achieving cooperative behavior with local information in networked-systems (see [18, 33, 62, 67, 71, 72, 87–89]).”
BackgroundBattistelli, G., & Chisci, L. (2014) · Automatica · doi:10.1016/j.automatica.2013.11.042 · Cited by 588
Harnessing Smoothness to Accelerate Distributed Optimization
Qu, G., & Li, N. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2017.2698261 · Cited by 565
On Distributed Averaging Algorithms and Quantization Effects
Nedic, A., Olshevsky, A., Ozdaglar, A., & Tsitsiklis, J. N. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2009.2031203 · Cited by 557
Self-citationConvex Optimization in Signal Processing and Communications
(2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511804458 · Cited by 554
A tutorial on modeling and analysis of dynamic social networks. Part I
Proskurnikov, A. V., & Tempo, R. (2017) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2017.03.002 · Cited by 553
Discrete-time dynamic average consensus
Zhu, M., & Martínez, S. (2010) · Automatica · doi:10.1016/j.automatica.2009.10.021 · Cited by 488
Distributed Consensus-Based Economic Dispatch With Transmission Losses
Binetti, G., Davoudi, A., Lewis, F. L., Naso, D., & Turchiano, B. (2014) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2014.2299436 · Cited by 477
Spread of (mis)information in social networks
Acemoglu, D., Ozdaglar, A., & ParandehGheibi, A. (2010) · Games and Economic Behavior · doi:10.1016/j.geb.2010.01.005 · Cited by 444
Interval Bipartite Consensus of Networked Agents Associated With Signed Digraphs
Meng, D., Du, M., & Jia, Y. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2528539 · Cited by 401
Opinion Fluctuations and Disagreement in Social Networks
Acemoğlu, D., Como, G., Fagnani, F., & Ozdaglar, A. (2013) · Mathematics of Operations Research · doi:10.1287/moor.1120.0570 · Cited by 371
D-ADMM: A Communication-Efficient Distributed Algorithm for Separable Optimization
Mota, J. F. C., Xavier, J. M. F., Aguiar, P. M. Q., & Puschel, M. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2254478 · Cited by 363
Distributed Subgradient Methods for Convex Optimization Over Random Networks
Lobel, I., & Ozdaglar, A. (2011) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2091295 · Cited by 351
“[6], Olshevsky and Tsitsiklis [17], [18], and Nedić et al.”
BackgroundOpinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate
Ghaderi, J., & Srikant, R. (2014) · Automatica · doi:10.1016/j.automatica.2014.10.034 · Cited by 325
Consensus-Based Energy Management in Smart Grid With Transmission Losses and Directed Communication
Zhao, C., He, J., Cheng, P., & Chen, J. (2017) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2015.2513772 · Cited by 311
A tutorial on modeling and analysis of dynamic social networks. Part II
Proskurnikov, A. V., & Tempo, R. (2018) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2018.03.005 · Cited by 294
Robust Networked Control Scheme for Distributed Secondary Control of Islanded Microgrids
Shafiee, Q., Stefanovic, C., Dragicevic, T., Popovski, P., Vasquez, J. C., & Guerrero, J. M. (2014) · IEEE Transactions on Industrial Electronics · doi:10.1109/tie.2013.2293711 · Cited by 264
Distributed particle filtering in agent networks: A survey, classification, and comparison
Hlinka, O., Hlawatsch, F., & Djuric, P. M. (2013) · IEEE Signal Processing Magazine · doi:10.1109/msp.2012.2219652 · Cited by 259
Convergence rate for consensus with delays
Nedić, A., & Ozdaglar, A. (2010) · Journal of Global Optimization · doi:10.1007/s10898-008-9370-2 · Cited by 198
Distributed multi-agent optimization with state-dependent communication
Lobel, I., Ozdaglar, A., & Feijer, D. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0467-x · Cited by 162
“One strand focuses on reaching consensus on a particular scalar value or computing exact averages of the initial values of the agents, as natural models of cooperative behavior in networked-systems (for deterministic models, see [8,13,21] and [22]); for randomized models, where the randomness may be due to the choice…”
BackgroundHarnessing smoothness to accelerate distributed optimization
Qu, G., & Li, N. (2016) · 2016 IEEE 55th Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798263 · Cited by 72
Metadata
- Authors
- Olshevsky, A., & Tsitsiklis, J. N.
- Venue
- SIAM Journal on Control and Optimization
- Published
- 2009-01
- Volume
- 48
- Issue
- 1
- Pages
- 33-55
- ISSN
- 0363-0129 (ISSN-L)
- 1095-7138
- OpenAlex
- W1593331236
- Cited by
- 692
- References
- 36
- FWCI
- 60.98
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.