The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Gossip algorithms: design, analysis and applications
Abstract
Motivated by applications to sensor, peer-to-peer and ad hoc networks, we study distributed asynchronous algorithms, also known as gossip algorithms, for computation and information exchange in an arbitrarily connected network of nodes. Nodes in such networks operate under limited computational, communication and energy resources. These constraints naturally give rise to "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for arbitrary network, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Using recent results of Boyd, Diaconis and Xiao (2003), we show that minimizing this quantity to design the fastest averaging algorithm on the network is a semi-definite program (SDP). In general, SDPs cannot be solved distributedly; however, exploiting problem structure, we propose a subgradient method that distributedly solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities that are derived from the gossip algorithm. We use this connection to study the performance of gossip algorithm on two popular networks: wireless sensor networks, which are modeled as geometric random graphs, and the Internet graph under the so-called preferential connectivity model.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Self-citationConsensus 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
Optimization and Nonsmooth Analysis
Clarke, F. H. (1990) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971309 · Cited by 10,264
Chord: A scalable peer-to-peer lookup service for internet applications
Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., & Balakrishnan, H. (2001) · Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/383059.383071 · Cited by 9,623
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
The capacity of wireless networks
Gupta, P., & Kumar, P. R. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.825799 · Cited by 8,292
A scalable content-addressable network
Ratnasamy, S., Francis, P., Handley, M., Karp, R., & Shenker, S. (2001) · Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/383059.383072 · Cited by 6,372
Large Deviations Techniques and Applications
Schmock, U., Dembo, A., & Zeitouni, O. (2000) · Journal of the American Statistical Association · doi:10.2307/2669805 · Cited by 3,524
TAG: a Tiny AGgregation service for ad-hoc sensor networks
Madden, S., Franklin, M. J., Hellerstein, J. M., & Hong, W. (2002) · ACM SIGOPS Operating Systems Review · doi:10.1145/844128.844142 · Cited by 2,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
Self-citationNext century challenges: scalable coordination in sensor networks
Estrin, D., Govindan, R., Heidemann, J., & Kumar, S. (1999) · Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking · doi:10.1145/313451.313556 · Cited by 2,703
Penrose, M. (2003) · doi:10.1093/acprof:oso/9780198506263.001.0001 · Cited by 2,480
Convex Analysis and Minimization Algorithms I
Hiriart-Urruty, J.-B., & Lemaréchal, C. (1993) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-662-02796-7 · Cited by 2,378
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
The impact of data aggregation in wireless sensor networks
Krishnamachari, L., Estrin, D., & Wicker, S. (2003) · Proceedings 22nd International Conference on Distributed Computing Systems Workshops · doi:10.1109/icdcsw.2002.1030829 · Cited by 1,448
A survey of gossiping and broadcasting in communication networks
Hedetniemi, S. M., Hedetniemi, S. T., & Liestman, A. L. (1988) · Networks · doi:10.1002/net.3230180406 · Cited by 1,243
TAG: a Tiny AGgregation service for Ad-Hoc sensor networks
Madden, S., Franklin, M. J., Hellerstein, J. M., & Hong, W. (2002) · Proceedings of the 5th symposium on Operating systems design and implementation - OSDI '02 · doi:10.1145/1060289.1060303 · Cited by 1,065
Local Control Strategies for Groups of Mobile Autonomous Agents
Lin, Z., Broucke, M., & Francis, B. (2004) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.825639 · Cited by 850
Handbook of Semidefinite Programming
(2000) · International Series in Operations Research & Management Science · doi:10.1007/978-1-4615-4381-7 · Cited by 781
Fastest Mixing Markov Chain on a Graph
Boyd, S., Diaconis, P., & Xiao, L. (2004) · SIAM Review · doi:10.1137/s0036144503423264 · Cited by 744
Self-citationKarp, 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
Impact of network density on data aggregation in wireless sensor networks
Intanagonwiwat, C., Estrin, D., Govindan, R., & Heidemann, J. (2003) · Proceedings 22nd International Conference on Distributed Computing Systems · doi:10.1109/icdcs.2002.1022289 · Cited by 696
Throughput-delay trade-off in wireless networks
El Gamal, A., Mammen, J., Prabhakar, B., & Shah, D. (2004) · IEEE INFOCOM 2004 · doi:10.1109/infcom.2004.1354518 · Cited by 585
Self-citationHandbook of semidefinite programming : theory, algorithms, and applications
Wolkowicz, H., Saigal, R., & Vandenberghe, L. (2000) · Cited by 568
Convex Analysis and Nonlinear Optimization
Borwein, J. M., & Lewis, A. S. (2000) · Springer eBooks · doi:10.1007/978-1-4757-9859-3 · Cited by 394
Spatial gossip and resource location protocols
Kempe, D., Kleinberg, J., & Demers, A. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380796 · Cited by 224
Large-Scale Optimization of Eigenvalues
Overton, M. L. (1992) · SIAM Journal on Optimization · doi:10.1137/0802007 · Cited by 209
Lewis, A. S., & Overton, M. L. (1996) · Acta Numerica · doi:10.1017/s0962492900002646 · Cited by 190
Overton, M. L., & Womersley, R. S. (1993) · Mathematical Programming · doi:10.1007/bf01585173 · Cited by 189
Convex Analysis on the Hermitian Matrices
Lewis, A. S. (1996) · SIAM Journal on Optimization · doi:10.1137/0806009 · Cited by 187
Convergence of Approximate and Incremental Subgradient Methods for Convex Optimization
Kiwiel, K. C. (2004) · SIAM Journal on Optimization · doi:10.1137/s1052623400376366 · Cited by 182
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
Scalable fault-tolerant aggregation in large process groups
Gupta, I., van Renesse, R., & Birman, K. (2002) · IEEE/IFIP International Conference on Dependable Systems and Networks (DSN) · doi:10.1109/dsn.2001.941427 · Cited by 144
Protocols and impossibility results for gossip-based communication mechanisms
Kempe, D., & Kleinberg, J. M. (2003) · doi:10.1109/sfcs.2002.1181971 · Cited by 129
A decentralized algorithm for spectral analysis
Kempe, D., & McSherry, F. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007438 · Cited by 123
Nonsmooth analysis of eigenvalues
Lewis, A. S. (1999) · Mathematical Programming · doi:10.1007/s10107980004a · Cited by 104
Mixing Times for Random Walks on Geometric Random Graphs.
Boyd, S., Ghosh, A., Prabhakar, B., et al. (2005) · Cited by 91
Self-citationLeaderless coordination via bidirectional and unidirectional time-dependent communication
Moreau, L. (2004) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2003.1273094 · Cited by 79
Analysis 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
Self-citationSynchronization of Information in Distributed Multiple Vehicle Coordinated ControlPreprint
Beard, R. W., & Stepanyan, V. (2003) · Cited by 58
Scalable and secure resource location
van Renesse, R. (2005) · Proceedings of the ... Annual Hawaii International Conference on System Sciences/Proceedings of the Annual Hawaii International Conference on System Sciences · doi:10.1109/hicss.2000.926742 · Cited by 55
Nonsmooth analysis of eigenvalues: A summary
Lewis, A. S. (1996) · Rendiconti del Seminario Matematico e Fisico di Milano · doi:10.1007/bf02925352 · Cited by 8
Cited by
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
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
Vicsek, T., & Zafeiris, A. (2012) · Physics Reports · doi:10.1016/j.physrep.2012.03.004 · Cited by 2,923
Boyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874516 · Cited by 2,439
Self-citationConstrained 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
Metadata
- Authors
- Boyd, S., Ghosh, A., Prabbakar, B., & Shah, D.
- Venue
- Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies.
- Publisher
- IEEE
- Published
- 2005-08-24
- Volume
- 3
- Pages
- 1653-1664
- OpenAlex
- W2101517602
- Cited by
- 558
- References
- 42
- FWCI
- 30.79
- Type
- conference paper
- Language
- en
- Open access
- closed
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.