The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
Gossip-based computation of aggregate information
Abstract
Over the last decade, we have seen a revolution in connectivity between computers, and a resulting paradigm shift from centralized to highly distributed systems. With massive scale also comes massive instability, as node and link failures become the norm rather than the exception. For such highly volatile systems, decentralized gossip-based protocols are emerging as an approach to maintaining simplicity and scalability while achieving fault-tolerant information dissemination. In this paper, we study the problem of computing aggregates with gossip-style protocols. Our first contribution is an analysis of simple gossip-based protocols for the computation of sums, averages, random samples, quantiles, and other aggregate functions, and we show that our protocols converge exponentially fast to the true answer when using uniform gossip. Our second contribution is the definition of a precise notion of the speed with which a node's data diffuses through the network. We show that this diffusion speed is at the heart of the approximation guarantees for all of the above problems. We analyze the diffusion speed of uniform gossip in the presence of node and link failures, as well as for flooding-based mechanisms. The latter expose interesting connections to random walks on graphs.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“As previously remarked, our protocol is a perturbation of the so-called 'push-sum' protocol for averaging studied in [1], [4], [10].”
From Distributed Optimization Over Time-Varying Directed Graphs (2015) · cites this paper as [10]
In the citing paper
“Instead, if every agent knows its out-degree, it is possible for the agents to construct a column stochastic matrix C and perform the following recursions with initialization u (0) = x (0) and v (0) = 1 to achieve the average (push-sum protocol [27]):”
From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [27]
Citations
Cites
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
Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems
Rowstron, A., & Druschel, P. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45518-3_18 · Cited by 7,276
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Wireless integrated network sensors
Pottie, G. J., & Kaiser, W. J. (2000) · Communications of the ACM · doi:10.1145/332833.332838 · Cited by 3,219
Chord: a scalable peer-to-peer lookup protocol for internet applications
Stoica, I., Morris, R., Liben-Nowell, D., Karger, D. R., Kaashoek, M. F., Dabek, F., & Balakrishnan, H. (2003) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2002.808407 · Cited by 3,133
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
Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing
Zhao, B. Y., Kubiatowicz, J. D., & Joseph, A. D. (2001) · Cited by 2,146
Freenet: A Distributed Anonymous Information Storage and Retrieval System
Clarke, I., Sandberg, O., Wiley, B., & Hong, T. W. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44702-4_4 · Cited by 2,109
The Mathematical Theory of Infectious Diseases and its applications
Ling, N. R. (1978) · Immunology · Cited by 1,934
Epidemic algorithms for replicated database maintenance
Demers, A., Greene, D., Hauser, C., Irish, W., & Larson, J. (1987) · Proceedings of the sixth annual ACM Symposium on Principles of distributed computing - PODC '87 · doi:10.1145/41840.41841 · Cited by 1,673
Research works printed but not linked: 2
- fong, 2000, An approximate lp-difference algorithm for massive data streams, Proc 17th STACS, 193
- feigenbaum, 1999, An approximate l1-difference algorithm for massive data streams, Proc of 40th IEEE FOCS, 501
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
Boyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874516 · Cited by 2,439
Distributed Optimization Over Time-Varying Directed Graphs
Nedic, A., & Olshevsky, A. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2364096 · Cited by 1,187
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
Nedić, A., Olshevsky, A., & Shi, W. (2017) · SIAM Journal on Optimization · doi:10.1137/16m1084316 · Cited by 1,069
“Instead, if every agent knows its out-degree, it is possible for the agents to construct a column stochastic matrix C and perform the following recursions with initialization u(0) = x(0) and v(0) = 1 to achieve the average (push-sum protocol [27]):”
BackgroundMethodInfluentialA survey of distributed optimization
Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., & Johansson, K. H. (2019) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2019.05.006 · Cited by 913
Metadata
- Authors
- Kempe, D., Dobra, A., & Gehrke, J.
- Affiliations
- Cornell University (US)
- Venue
- 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.
- Publisher
- IEEE Computer. Soc
- Published
- 2004-03-01
- Pages
- 482-491
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2110100895
- Cited by
- 1,480
- References
- 43
- Citations by year
- 2026: 13 · 2025: 34 · 2024: 46 · 2023: 38 · 2022: 40 · 2021: 71 · 2020: 66 · 2019: 70 · 2018: 75 · 2017: 79 · 2016: 80 · 2015: 76 · 2014: 75 · 2013: 88 · 2012: 100
- FWCI
- 26.31
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Annual Symposium on Foundations of Computer Science (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed systems and fault tolerance
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Keywords
- gossip protocols, distributed aggregation, diffusion rate, fault tolerance, node and link failures, floods, random walks on graphs, approximation guarantees, exponential convergence, random sampling, quantile estimation, distributed computing
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Gossip-based computation of aggregate information. https://app.cochat.ai/papers/10.1109/sfcs.2003.1238221
- The paper
- Kempe, D., Dobra, A., & Gehrke, J. (2004). Gossip-based computation of aggregate information. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. https://doi.org/10.1109/sfcs.2003.1238221
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.