The DOI matches its Crossref record; 83 of the 83 references it cites were found in a registry or an index.
Gossip Algorithms for Distributed Signal Processing
Open accessAbstract
Gossip algorithms are attractive for in-network processing in sensor networks because they do not require any specialized routing, there is no bottleneck or single point of failure, and they are robust to unreliable wireless network conditions. Recently, there has been a surge of activity in the computer science, control, signal processing, and information theory communities, developing faster and more robust gossip algorithms and deriving theoretical performance guarantees. This paper presents an overview of recent work in the area. We describe convergence rate results, which are related to the number of transmitted messages and thus the amount of energy consumed in the network for gossiping. We discuss issues related to gossiping over wireless links, including the effects of quantization and noise, and we illustrate the use of gossip algorithms for canonical signal processing tasks including distributed estimation, source localization, and compression.
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
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
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 · cited 1×
“rly work includes that of Tsitsiklis et al. [17], [18]. Consensus problems have arisen in numerous applications including: load balancing [19]; alignment, flocking, and multi-agent collaboration [20], [21]; vehicle formation [22], tracking and data fusion [23], and distributed inference [24]. The canonical example of a…”
BackgroundConsensus 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×
“cus on characterizing conditions for convergence and stability of synchronous gossiping, as well as optimization of the algorithm parameters Pi;j; see the excellent surveys by Olfati-Saber and Murray [28], and Ren et al. [29], and references therein. B. Paper Outline Our overview of gossip algorithms begins on the the…”
MethodCoordination 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
Decoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
Candes, E. J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.885507 · Cited by 6,839
Information Flow and Cooperative Control of Vehicle Formations
Fax, J. A., & Murray, R. M. (2004) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.834433 · Cited by 4,579
Noiseless coding of correlated information sources
Slepian, D., & Wolf, J. (1973) · IEEE Transactions on Information Theory · doi:10.1109/tit.1973.1055037 · Cited by 3,952
Wireless integrated network sensors
Pottie, G. J., & Kaiser, W. J. (2000) · Communications of the ACM · doi:10.1145/332833.332838 · Cited by 3,219
Information consensus in multivehicle cooperative control
(2007) · IEEE Control Systems · doi:10.1109/mcs.2007.338264 · Cited by 3,156
Sensor networks: Evolution, opportunities, and challenges
Chong, C.-Y., & Kumar, S. P. (2003) · Proceedings of the IEEE · doi:10.1109/jproc.2003.814918 · Cited by 3,079
Locating the nodes: cooperative localization in wireless sensor networks
Patwari, N., Ash, J. N., Kyperountas, S., Hero, A. O., Moses, R. L., & Correal, N. S. (2005) · IEEE Signal Processing Magazine · doi:10.1109/msp.2005.1458287 · Cited by 3,031
The rate-distortion function for source coding with side information at the decoder
Wyner, A., & Ziv, J. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055508 · Cited by 3,023
Boyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874516 · Cited by 2,439
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 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
Stabilization of linear systems with limited information
Elia, N., & Mitter, S. K. (2001) · IEEE Transactions on Automatic Control · doi:10.1109/9.948466 · Cited by 1,687
Gossip-based computation of aggregate information
Kempe, D., Dobra, A., & Gehrke, J. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238221 · Cited by 1,480
Probabilistic counting algorithms for data base applications
Flajolet, P., & Nigel Martin, G. (1985) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(85)90041-8 · Cited by 1,269
Simulating the power consumption of large-scale sensor network applications
Shnayder, V., Hempstead, M., Chen, B.-R., Allen, G. W., & Welsh, M. (2004) · ACM Conference on Embedded Networked Sensor Systems (SenSys) · doi:10.1145/1031495.1031518 · Cited by 1,109
Diffusion Least-Mean Squares Over Adaptive Networks: Formulation and Performance Analysis
Lopes, C. G., & Sayed, A. H. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.917383 · Cited by 1,109
Distributed Kalman Filter with Embedded Consensus Filters
Olfati-Saber, R. (2006) · Proceedings of the 44th IEEE Conference on Decision and Control · doi:10.1109/cdc.2005.1583486 · Cited by 1,024
Dynamic 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
Distributed optimization in sensor networks
Rabbat, M., & Nowak, R. (2004) · Proceedings of the 3rd international symposium on Information processing in sensor networks · doi:10.1145/984622.984626 · Cited by 901
Self-citationDeVore, R. A. (1998) · Acta Numerica · doi:10.1017/s0962492900002816 · Cited by 877
Nested linear/lattice codes for structured multiterminal binning
Zamir, R., Shamai, S., & Erez, U. (2002) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.1003821 · Cited by 876
Rate-distortion methods for image and video compression
Ortego, A., & Ramchandran, K. (1998) · IEEE Signal Processing Magazine · doi:10.1109/79.733495 · Cited by 808
Computation Over Multiple-Access Channels
Nazer, B., & Gastpar, M. (2007) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.904785 · Cited by 753
Kashyap, A., Başar, T., & Srikant, R. (2007) · Automatica · doi:10.1016/j.automatica.2007.01.002 · Cited by 749
Fastest Mixing Markov Chain on a Graph
Boyd, S., Diaconis, P., & Xiao, L. (2004) · SIAM Review · doi:10.1137/s0036144503423264 · Cited by 744
Karp, R., Schindelhauer, C., Shenker, S., & Vocking, B. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892324 · Cited by 718
Sheng, X., & Hu, Y.-H. (2005) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2004.838930 · Cited by 714
Kar, S., & Moura, J. M. F. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.2007111 · Cited by 691
Self-citationConsensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
Schizas, I. D., Ribeiro, A., & Giannakis, G. B. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2007.906734 · Cited by 685
Agreement over random networks
Hatano, Y., & Mesbahi, M. (2004) · 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601) · doi:10.1109/cdc.2004.1430343 · Cited by 550
Distributed compression in a dense microsensor network
Pradhan, S. S., Kusuma, J., & Ramchandran, K. (2002) · IEEE Signal Processing Magazine · doi:10.1109/79.985684 · Cited by 537
Compressed Sensing for Networked Data
Haupt, J., Bajwa, W. U., Rabbat, M., & Nowak, R. (2008) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.914732 · Cited by 530
Self-citationDistributed Kalman filtering based on consensus strategies
Carli, R., Chiuso, A., Schenato, L., & Zampieri, S. (2008) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2008.080505 · Cited by 511
Distributing the Kalman Filter for Large-Scale Systems
Khan, U. A., & Moura, J. M. F. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.927480 · Cited by 481
Self-citationBroadcast Gossip Algorithms for Consensus
Aysal, T. C., Yildiz, M. E., Sarwate, A. D., & Scaglione, A. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2016247 · Cited by 480
Self-citationDistributed target classification and tracking in sensor networks
Brooks, R. R., Ramanathan, P., & Sayeed, A. M. (2003) · Proceedings of the IEEE · doi:10.1109/jproc.2003.814923 · Cited by 464
Distributed Consensus Algorithms in Sensor Networks: Quantized Data and Random Link Failures
Kar, S., & Moura, J. M. F. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2036046 · Cited by 435
Self-citationCollaborative signal and information processing: An information-directed approach
Zhao, F., Liu, J., Liu, J., Guibas, L., & Reich, J. (2003) · Proceedings of the IEEE · doi:10.1109/jproc.2003.814921 · Cited by 379
Distributed control applications within sensor networks
Sinopoli, B., Sharp, C., Schenato, L., Schaffert, S., & Sastry, S. S. (2003) · Proceedings of the IEEE · doi:10.1109/jproc.2003.814926 · Cited by 379
Distributed Sensor Localization in Random Environments Using Minimal Number of Anchor Nodes
Khan, U. A., Kar, S., & Moura, J. M. F. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2014812 · Cited by 351
Self-citationRandomized consensus algorithms over large scale networks
Fagnani, F., & Zampieri, S. (2008) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2008.080506 · Cited by 350
Distributed Average Consensus With Dithered Quantization
Aysal, T. C., Coates, M. J., & Rabbat, M. G. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.927071 · Cited by 315
Self-citationCommunication constraints in the average consensus problem
Carli, R., Fagnani, F., Speranzon, A., & Zampieri, S. (2008) · Automatica · doi:10.1016/j.automatica.2007.07.009 · Cited by 301
Energy-based sensor network source localization via projection onto convex sets
Blatt, D., & Hero, A. O. (2006) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.879312 · Cited by 295
Sensor Networks With Random Links: Topology Design for Distributed Consensus
Kar, S., & Moura, J. M. F. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.920143 · Cited by 261
Self-citationSynchronization and Convergence of Linear Dynamics in Random Directed Networks
Wu, C. W. (2006) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2006.878783 · Cited by 250
Fast linear iterations for distributed averaging
Xiao, L., & Boyd, S. (2004) · 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475) · doi:10.1109/cdc.2003.1272421 · Cited by 218
Distributed fusion in sensor networks
Cetin, M., Chen, L., Fisher, J. W., Ihler, A. T., Moses, R. L., Wainwright, M. J., & Willsky, A. S. (2006) · IEEE Signal Processing Magazine · doi:10.1109/msp.2006.1657816 · Cited by 204
Geographic gossip: efficient aggregation for sensor networks
Dimakis, A. G., Sarwate, A. D., & Wainwright, M. J. (2006) · Proceedings of the fifth international conference on Information processing in sensor networks - IPSN '06 · doi:10.1145/1127777.1127791 · Cited by 185
Self-citationFast Distributed Algorithms for Computing Separable Functions
Mosk-Aoyama, D., & Shah, D. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.924648 · Cited by 169
Decentralized compression and predistribution via randomized gossiping
Rabbat, M., Haupt, J., Singh, A., & Nowak, R. (2006) · Proceedings of the fifth international conference on Information processing in sensor networks - IPSN '06 · doi:10.1145/1127777.1127789 · Cited by 165
Self-citationLifting Markov chains to speed up mixing
Chen, F., Lovász, L., & Pak, I. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301315 · Cited by 158
Distributed Detection in Sensor Networks With Packet Losses and Finite Capacity Links
Saligrama, V., Alanyali, M., & Savas, O. (2006) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.880227 · Cited by 158
Local divergence of Markov chains and the analysis of iterative load-balancing schemes
Rabani, Y., Sinclair, A., & Wanka, R. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743520 · Cited by 147
Distributed Average Consensus using Probabilistic Quantization
Aysal, T. C., Coates, M., & Rabbat, M. (2007) · IEEE/SP Workshop on Statistical Signal Processing (SSP) · doi:10.1109/ssp.2007.4301337 · Cited by 137
Self-citationDistributed and Recursive Parameter Estimation in Parametrized Linear State-Space Models
Ram, S. S., Veeravalli, V. V., & Nedić, A. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2009.2037460 · Cited by 119
Optimization and Analysis of Distributed Averaging With Short Node Memory
Oreshkin, B. N., Coates, M., & Rabbat, M. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2043127 · Cited by 113
Self-citationGeneralized consensus computation in networked systems with erasure links
Rabbat, M., Nowak, R. D., & Bucklew, J. A. (2005) · IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC) · doi:10.1109/spawc.2005.1506308 · Cited by 110
Self-citationTopology for Distributed Inference on Graphs
Kar, S., Aldosari, S. A., & Moura, J. M. F. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.923536 · Cited by 107
Self-citationImproved bounds for mixing rates of Markov chains and multicommodity flow
Sinclair, A. (1992) · Lecture notes in computer science · doi:10.1007/bfb0023849 · Cited by 94
Distributed pose averaging in camera networks via consensus on SE(3)
Tron, R., Vidal, R., & Terzis, A. (2008) · ACM/IEEE International Conference on Distributed Smart Cameras (ICDSC) · doi:10.1109/icdsc.2008.4635701 · Cited by 93
Robust Decentralized Source Localization via Averaging
Rabbat, M., Nowak, R. M., & Bucklew, J. A. (2006) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2005.1416489 · Cited by 80
Self-citationAnalysis and optimization of randomized gossip algorithms
Boyd, S., Ghosh, A., Prabhakar, B., et al. (2004) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc.2004.1429652 · Cited by 76
Coding With Side Information for Rate-Constrained Consensus
Yildiz, M. E., & Scaglione, A. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.919636 · Cited by 72
Self-citationWeight Optimization for Consensus Algorithms With Correlated Switching Topology
Jakovetić, D., Xavier, J., & Moura, J. M. F. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2046635 · Cited by 64
Self-citationDecentralized parameter estimation by consensus based stochastic approximation
Stanković, S. S., Stanković, M. S., & Stipanović, D. M. (2007) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2007.4434812 · Cited by 56
On quantized consensus by means of gossip algorithm - Part II: Convergence time
Lavaei, J., & Murray, R. M. (2009) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2009.5160568 · Cited by 51
The Impact of Mobility on Gossip Algorithms
Sarwate, A. D., & Dimakis, A. G. (2009) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2009.5062132 · Cited by 39
Self-citationOn quantized consensus by means of gossip algorithm - Part I: Convergence proof
Lavaei, J., & Murray, R. M. (2009) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2009.5160485 · Cited by 29
Scalable distributed Kalman filtering through consensus
Kirti, S., & Scaglione, A. (2008) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2008.4518212 · Cited by 27
Self-citationDas, A., & Mesbahi, M. (2006) · doi:10.1109/sahcn.2006.288500 · Cited by 24
Neighborhood gossip: Concurrent averaging through local interference
Nazer, B., Dimakis, A. G., & Gastpar, M. (2009) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2009.4960419 · Cited by 21
Self-citationDistributed consensus with link failures as a structured stochastic uncertainty problem
Patterson, S., & Bamieh, B. A. (2008) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2008.4797616 · Cited by 16
Stochastic consensus over weighted directed networks
Porfiri, M., & Stilwell, D. J. (2007) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2007.4282571 · Cited by 13
Efficient In-Network Processing Through Local Ad-Hoc Information Coalescence
Savas, O., Alanyali, M., & Saligrama, V. (2006) · Lecture notes in computer science · doi:10.1007/11776178_16 · Cited by 10
A distributed sensor fusion algorithm for the inversion of sparse fields
Schmidt, A., & Moura, J. M. F. (2009) · 2018 52nd Asilomar Conference on Signals, Systems, and Computers · doi:10.1109/acssc.2009.5469908 · Cited by 8
Self-citationModel-based pose estimation by consensus
Jorstad, A., Burlina, P., Wang, I.-J., Lucarelli, D. G., & Dementhon, D. F. (2008) · International Conference on Intelligent Sensors, Sensor Networks and Information Processing · doi:10.1109/issnip.2008.4762050 · Cited by 6
Cited by
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
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
Shi, W., Ling, Q., Wu, G., & Yin, W. (2015) · SIAM Journal on Optimization · doi:10.1137/14096668x · Cited by 1,261
On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
Shi, W., Ling, Q., Yuan, K., Wu, G., & Yin, W. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2304432 · Cited by 820
Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks
Chen, J., & Sayed, A. H. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2198470 · Cited by 680
Sayed, A. H. (2014) · Proceedings of the IEEE · doi:10.1109/jproc.2014.2306253 · Cited by 587
Metadata
- Authors
- Dimakis, A. G., Kar, S., Moura, J. M. F., Rabbat, M. G., & Scaglione, A.
- Venue
- Proceedings of the IEEE
- Published
- 2010-11
- Volume
- 98
- Issue
- 11
- Pages
- 1847-1864
- ISSN
- 0018-9219 (ISSN-L)
- 1558-2256
- OpenAlex
- W2120286056
- Cited by
- 741
- References
- 83
- FWCI
- 67.62
- 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.