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
Accuracy and stability of numerical algorithms
(1996) · Choice Reviews Online · doi:10.5860/choice.34-0981 · Cited by 2,072
Distributed asynchronous deterministic and stochastic gradient optimization algorithms
Tsitsiklis, J., Bertsekas, D., & Athans, M. (1986) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1986.1104412 · Cited by 1,967
Self-citationDynamic load balancing for distributed memory multiprocessors
Cybenko, G. (1989) · Journal of Parallel and Distributed Computing · doi:10.1016/0743-7315(89)90021-x · Cited by 997
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
Persuasion Bias, Social Influence, and Unidimensional Opinions
DeMarzo, P. M., Vayanos, D., & Zwiebel, J. (2003) · The Quarterly Journal of Economics · doi:10.1162/00335530360698469 · Cited by 958
Finite-time convergent gradient flows with applications to network consensus
Cortés, J. (2006) · Automatica · doi:10.1016/j.automatica.2006.06.015 · Cited by 818
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 · cited 1×
“We note that the available convergence time estimates for distributed subgradient methods [48, 24, 54] typically involve two contributions: one reflecting the convergence time of a centralized subgradient algorithm, and one reflecting the convergence time of the underlying averaging algorithm.”
On Maximizing the Second Smallest Eigenvalue of a State-Dependent Graph Laplacian
Kim, Y., & Mesbahi, M. (2006) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2005.861710 · Cited by 593
Reaching a Consensus in a Dynamically Changing Environment: A Graphical Approach
Cao, M., Morse, A. S., & Anderson, B. D. O. (2008) · SIAM Journal on Control and Optimization · doi:10.1137/060657005 · Cited by 563
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-citationSpread 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
Cao, M., Morse, A. S., & Anderson, B. D. O. (2008) · SIAM Journal on Control and Optimization · doi:10.1137/060657029 · Cited by 329
Quantized average consensus via dynamic coding/decoding schemes
Carli, R., Bullo, F., & Zampieri, S. (2010) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.1463 · Cited by 213
Bounds for eigenvalues of certain stochastic matrices
Landau, H. J., & Odlyzko, A. M. (1981) · Linear Algebra and its Applications · doi:10.1016/0024-3795(81)90003-3 · Cited by 88
Optimal strategies in the average consensus problem
Delvenne, J., Carli, R., & Zampieri, S. (2009) · Systems & Control Letters · doi:10.1016/j.sysconle.2009.08.005 · Cited by 72
Angeli, D., & Bliman, P. (2009) · SIAM Journal on Control and Optimization · doi:10.1137/060673527 · Cited by 70
Nonuniform Coverage and Cartograms
Lekien, F., & Leonard, N. E. (2009) · SIAM Journal on Control and Optimization · doi:10.1137/070681120 · Cited by 68
Multi-agent coordination using nearest neighbor rules: revisiting the Vicsek modelPreprint
Li, S., & Wang, H. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0407021 · Cited by 65
On collective motion in sensor networks: sample problems and distributed algorithms
Ganguli, A., Susca, S., Martínez, S., Bullo, F., & Cortés, J. (2006) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2005.1582828 · Cited by 64
On Conditions for Convergence to Consensus
Lorenz, J., & Lorenz, D. A. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2046086 · Cited by 52
Distributed Averaging on Asynchronous Communication Networks
Mehyar, M., Spanos, D. P., Pongsajapan, J., et al. (2006) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc.2005.1583363 · Cited by 49
Notes on averaging over acyclic digraphs and discrete coverage control
Gao, C., Cortés, J., & Bullo, F. (2008) · Automatica · doi:10.1016/j.automatica.2007.12.017 · Cited by 49
On Communication Requirements for Multi-agent Consensus Seeking
Fang, L., & Antsaklis, P. J. (2006) · Springer eBooks · doi:10.1007/11533382_4 · Cited by 48
COORDINATION OF AN ASYNCHRONOUS MULTI-AGENT SYSTEM VIA AVERAGING
Cao, M., Morse, A. S., & Anderson, B. D. O. (2005) · IFAC Proceedings Volumes · doi:10.3182/20050703-6-cz-1902.01081 · Cited by 38
Tight estimates for convergence of some non-stationary consensus algorithms
Angeli, D., & Bliman, P. (2008) · Systems & Control Letters · doi:10.1016/j.sysconle.2008.06.005 · Cited by 25
Notes on averaging over acyclic digraphs and discrete coverage control
Gao, C., Bullo, F., Cortés, J., & Jadbabaie, A. (2006) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2006.377456 · Cited by 12
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
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.