Gossip-based computation of aggregate information
The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
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
Random Walks on Graphs: A Survey
Lovász, L. (2001) · Cited by 1,411
The cougar approach to in-network query processing in sensor networks
Yao, Y., & Gehrke, J. (2002) · ACM SIGMOD Record · doi:10.1145/601858.601861 · Cited by 1,328
Self-citationProbabilistic 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
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
The Space Complexity of Approximating the Frequency Moments
Alon, N., Matias, Y., & Szegedy, M. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1545 · Cited by 1,140
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
Reversible Markov Chains and Random Walks on Graphs
Aldous, D., & Fill, J. A. (2014) · Cited by 946
The Mathematical Theory of Infectious Diseases and Its Applications
Giles, P., & Bailey, N. T. J. (1977) · Operational Research Quarterly (1970-1977) · doi:10.2307/3009004 · Cited by 937
A fast and simple randomized parallel algorithm for the maximal independent set problem
Alon, N., Babai, L., & Itai, A. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90019-2 · Cited by 823
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
Random walks, universal traversal sequences, and the complexity of maze problems
Aleliunas, R., Karp, R. M., Lipton, R. J., Lovasz, L., & Rackoff, C. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.34 · Cited by 692
Birman, K. P., Hayden, M., Ozkasap, O., Xiao, Z., Budiu, M., & Minsky, Y. (1999) · ACM Transactions on Computer Systems · doi:10.1145/312203.312207 · Cited by 654
Van Renesse, R., Birman, K. P., & Vogels, W. (2003) · ACM Transactions on Computer Systems · doi:10.1145/762483.762485 · Cited by 645
Query Processing in Sensor Networks
Madden, S., & Gehrke, J. (2004) · Chapman & Hall/CRC Computer & Information Science Series · doi:10.1201/9780203487068.sec6 · Cited by 460
Self-citationPittel, B. (1987) · SIAM Journal on Applied Mathematics · doi:10.1137/0147013 · Cited by 386
Lectures on finite Markov chains
Saloff-Coste, L. (1997) · Lecture Notes in Mathematics · doi:10.1007/bfb0092621 · Cited by 382
Processing complex aggregate queries over data streams
Dobra, A., Garofalakis, M., Gehrke, J., & Rastogi, R. (2002) · Proceedings of the 2002 ACM SIGMOD international conference on Management of data · doi:10.1145/564691.564699 · Cited by 319
Self-citationEpidemic algorithms for replicated database maintenance
Demers, A., Greene, D., Houser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., & Terry, D. (1988) · ACM SIGOPS Operating Systems Review · doi:10.1145/43921.43922 · Cited by 312
The shortest-path problem for graphs with random arc-lengths
Frieze, A. M., & Grimmett, G. R. (1985) · Discrete Applied Mathematics · doi:10.1016/0166-218x(85)90059-9 · Cited by 290
Randomized broadcast in networks
Feige, U., Peleg, D., Raghavan, P., & Upfal, E. (1990) · Random Structures & Algorithms · doi:10.1002/rsa.3240010406 · Cited by 239
Stable distributions, pseudorandom generators, embeddings and data stream computation
Indyk, P. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892082 · Cited by 238
Dynamic multidimensional histograms
Thaper, N., Guha, S., Indyk, P., & Koudas, N. (2002) · Proceedings of the 2002 ACM SIGMOD international conference on Management of data · doi:10.1145/564691.564741 · Cited by 206
Building low-diameter P2P networks
Pandurangan, G., Raghavan, P., & Upfal, E. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959925 · Cited by 191
Estimating Aggregates on a Peer-to-Peer Network
Bawa, M., García-Molina, H., Gionis, A., et al. (2003) · Cited by 175
An Approximate L p-Difference Algorithm for Massive Data Streams: Extended Abstract
Fong, J. H., & Strauss, M. J. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-46541-3_16 · Cited by 163
Rapid rumor ramification: approximating the minimum broadcast time
Ravi, R. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365693 · Cited by 161
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
Self-citationTracking Join and Self-Join Sizes in Limited Storage
Alon, N., Gibbons, P. B., Matias, Y., et al. (2002) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1813 · Cited by 86
Message Multicasting in Heterogeneous Networks
Bar-Noy, A., Guha, S., Naor, J. S., et al. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539798347906 · Cited by 71
Dynamic multidimensional histograms
Thaper, N., Guha, S., Indyk, P., et al. (2002) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/564740.564741 · Cited by 43
Peer Pressure: Distributed Recovery from Attacks in Peer-to-Peer Systems
Keyani, P., Larson, B., & Senthil, M. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45745-3_29 · Cited by 24
Edmonds, J. (2024) · Cambridge University Press eBooks · doi:10.1017/9781009302180.034 · Cited by 6
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
Internet of things: Vision, applications and research challenges
Miorandi, D., Sicari, S., De Pellegrini, F., & Chlamtac, I. (2012) · Ad Hoc Networks · doi:10.1016/j.adhoc.2012.02.016 · Cited by 3,578
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 Kalman filtering for sensor networks
Olfati-Saber, R. (2007) · 2007 46th IEEE Conference on Decision and Control · doi:10.1109/cdc.2007.4434303 · Cited by 1,586
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
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
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.