Gossip-based computation of aggregate information
The DOI matches its Crossref record; 45 of the 45 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
Zhao, B. Y., Kubiatowicz, J. D., & Joseph, A. D. (2001) · UC Berkeley · Cited by 2,266
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
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
Items 601–700 of 1,004
A Service-Oriented Peer-to-Peer Architecture for a Digital Ecosystem
Sacha, J., Biskupski, B., Dahlem, D., Cunningham, R., Dowling, J., & Meier, R. (2007) · IEEE International Conference on Digital Ecosystems and Technologies · doi:10.1109/dest.2007.371971 · Cited by 15
Stopping Amplified DNS DDoS Attacks through Distributed Query Rate Sharing
Verma, S., Hamieh, A., Huh, J. H., Holm, H., Rajagopalan, S. R., Korczyński, M., & Fefferman, N. H. (2016) · International Conference on Availability, Reliability and Security (ARES) · doi:10.1109/ares.2016.93 · Cited by 15
Verification of Distributed Epistemic Gossip Protocols
Apt, K. R., & Wojtczak, D. (2018) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.11204 · Cited by 15
A model-based control method for decentralized calibration of wireless sensor networks
Buadhachain, S. O., & Provan, G. M. (2013) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2013.6580870 · Cited by 15
Brownian Gossip: Exploiting Node Mobility to Diffuse Information in Ad Hoc Networks
Choudhury, R. R. (2006) · International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom) · doi:10.1109/colcom.2005.1651262 · Cited by 15
Digest: Fast and communication efficient decentralized learning with local updates
Gholami, P., & Seferoglu, H. (2024) · IEEE Transactions on Machine Learning in Communications and Networking · doi:10.1109/tmlcn.2024.3354236 · Cited by 14
“Decentralized algorithms have been extensively studied in the literature, with Gossip algorithms receiving the lion’s share of research attention [10], [11], [12], [13], [14], [15], [16].”
BackgroundBertier, M., Busnel, Y., & Kermarrec, A.-M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-11476-2_7 · Cited by 14
ASY-SONATA: Achieving Geometric Convergence for Distributed Asynchronous Optimization.
Tian, Y., Sun, Y., Du, B., & Scutari, G. (2018) · Cited by 14
Fenchel dual gradient methods for distributed convex optimization over time-varying networks
Wu, X., & Lu, J. (2017) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2017.8264079 · Cited by 14
Naderi, S., & Blondin, M. J. (2023) · IEEE Access · doi:10.1109/access.2023.3341295 · Cited by 14
A Fast Finite-Time Consensus based Gradient Method for Distributed Optimization over Digraphs
Jiang, W., & Charalambous, T. (2022) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc51059.2022.9992389 · Cited by 14
Liang, L., Huang, X., Xin, R., & Yuan, K. (2025) · SIAM Journal on Optimization · doi:10.1137/24m1657341 · Cited by 14
Decentralized Optimization on Time-Varying Directed Graphs Under Communication Constraints
Chen, Y., Hashemi, A., & Vikalo, H. (2021) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp39728.2021.9415052 · Cited by 14
Distributed optimization of strongly convex functions on directed time-varying graphs
Nedić, A., & Olshevsky, A. (2013) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2013.6736882 · Cited by 14
Stochastic learning in multi-agent optimization: Communication and payoff-based approaches
Tatarenko, T. (2018) · Automatica · doi:10.1016/j.automatica.2018.10.001 · Cited by 14
Extending Gossip Algorithms to Distributed Estimation of U-StatisticsPreprint
Colin, I., Bellet, A., Salmon, J., & Clémençon, S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.05464 · Cited by 14
Structure and Dynamics of Information in Networks
Kempe, D. (2010) · Cited by 14
Self-citationComplexity and Emergence in Engineering Systems
Chen, C., Nagl, S., & Clack, C. D. (2008) · Studies in computational intelligence · doi:10.1007/978-3-540-88075-2_5 · Cited by 14
Robust Gossip-Based Aggregation: A Practical Point of View
Niederbrucker, G., & Gansterer, W. N. (2013) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972931.12 · Cited by 14
Decentralized Adaptive Clustering of Deep Nets is Beneficial for Client Collaboration
Zec, E. L., Ekblom, E., Willbo, M., Mogren, O., & Girdzijauskas, Š. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-28996-5_5 · Cited by 14
Asynchronous gossip principal components analysis
Fellus, J., Picard, D., & Gosselin, P.-H. (2015) · Neurocomputing · doi:10.1016/j.neucom.2014.11.076 · Cited by 14
Vaidya, N. H., Hadjicostis, C. N., & Domínguez-García, A. D. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1109.6392 · Cited by 14
Scalable, asynchronous, distributed eigen monitoring of astronomy data streams
Bhaduri, K., Das, K., Borne, K. D., Giannella, C. R., Mahule, T., & Kargupta, H. (2011) · Statistical Analysis and Data Mining The ASA Data Science Journal · doi:10.1002/sam.10120 · Cited by 14
Randomized rumor spreading in poorly connected small-world networks
Mehrabian, A., & Pourmiri, A. (2015) · Random Structures and Algorithms · doi:10.1002/rsa.20624 · Cited by 14
ASH: Tackling Node Mobility in Large-Scale Networks
Pruteanu, A., Dulman, S., & Langendoen, K. G. (2010) · IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO) · doi:10.1109/saso.2010.33 · Cited by 14
Time and Communication Complexity of Leader Election in Anonymous Networks
Kowalski, D. R., & Mosteiro, M. A. (2021) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs51616.2021.00050 · Cited by 14
How to Spread a Rumor: Call Your Neighbors or Take a Walk?
Giakkoupis, G., Mallmann-Trenn, F., & Saribekyan, H. (2019) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/3293611.3331622 · Cited by 14
Hierarchical Spatial Gossip for Multiresolution Representations in Sensor Networks
Sarkar, R., Zhu, X., & Gao, J. (2011) · ACM Transactions on Sensor Networks · doi:10.1145/1993042.1993046 · Cited by 14
Push-Sum-Enabled Resilient Microgrid Control
Babahajiani, P., Wang, L., Liu, J., & Zhang, P. (2021) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2021.3058853 · Cited by 14
Dynamic data allocation with replication in distributed systems
Kamali, S., Ghodsnia, P., & Daudjee, K. (2011) · IEEE International Performance, Computing, and Communications Conference · doi:10.1109/pccc.2011.6108075 · Cited by 14
Analyzing Network Coding (Gossip) Made Easy
Haeupler, B. (2016) · Journal of the ACM · doi:10.1145/2629696 · Cited by 14
Epidemic failure detection and consensus for extreme parallelism
Katti, A. P., Fatta, G. D., Naughton, T. J., & Engelmann, C. (2017) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342017690910 · Cited by 14
A Distributed Algorithm for Multi-Armed Bandit with Homogeneous Rewards over Directed Graphs
Zhu, J., & Liu, J. (2021) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc50511.2021.9483267 · Cited by 14
Practical Private Information Aggregation in Large Networks
Kreitz, G., Dam, M., & Wikström, D. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-27937-9_7 · Cited by 14
Distributed selection: a missing piece of data aggregation
Kühn, F., Locher, T., & Wattenhofer, R. P. (2008) · Communications of the ACM · doi:10.1145/1378727.1378749 · Cited by 14
Exploiting Spatio-temporal Correlations for Data Processing in Sensor Networks
Deligiannakis, A., & Kotidis, Y. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-79996-2_4 · Cited by 14
Liu, Y., Li, B., Anderson, B. D. O., & Shi, G. (2019) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2019.2952082 · Cited by 14
Distributed estimation of global parameters in delay-tolerant networks
Guerrieri, A., Carreras, I., Pellegrini, F. D., Montresor, A., & Miorandi, D. (2009) · IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM) · doi:10.1109/wowmom.2009.5282449 · Cited by 14
Gossip-Based Dissemination of Time
Iwanicki, K. (2005) · Cited by 14
BubbleStorm: Analysis of Probabilistic Exhaustive Search in a Heterogeneous Peer-to-Peer System
Terpstra, W. W., Leng, C., & Buchmann, A. (2007) · TUbilio (Technical University of Darmstadt) · Cited by 14
On Spatial Gossip Algorithms for Average Consensus
Rabbat, M. (2007) · IEEE Statistical Signal Processing Workshop (SSP) · doi:10.1109/ssp.2007.4301350 · Cited by 13
Distributed Optimization Over Networks
Nedić, A. (2018) · Lecture notes in mathematics · doi:10.1007/978-3-319-97142-1_1 · Cited by 13
Noise Resilient Distributed Average Consensus Over Directed Graphs
Khatana, V., & Salapaka, M. V. (2023) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2023.3324583 · Cited by 13
Asymmetrically Decentralized Federated Learning
Li, Q., Zhang, M., Yin, N., Yin, Q., Shen, L., & Cao, X. (2025) · IEEE Transactions on Computers · doi:10.1109/tc.2025.3569185 · Cited by 13
Success and failure of adaptation-diffusion algorithms for consensus in multi-agent networks
Morral, G., Bianchi, P., & Fort, G. (2014) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2014.7039609 · Cited by 13
Melbourne, J., Saraswat, G., Khatana, V., Patel, S., & Salapaka, M. V. (2020) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2020.12.971 · Cited by 13
Function Computation over Linear Channels
Keller, L., Karamchandani, N., & Fragouli, C. (2010) · International Symposium on Network Coding (NetCod) · doi:10.1109/netcod.2010.5487679 · Cited by 13
D-Cliques: Compensating NonIIDness in Decentralized Federated Learning with Topology.Preprint
Bellet, A., Kermarrec, A.-M., & Lavoie, E. (2021) · arXiv (Cornell University) · Cited by 13
Straggler-Resilient Distributed Machine Learning with Dynamic Backup WorkersPreprint
Xiong, G., Yan, G., Singh, R., & Li, J. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.06280 · Cited by 13
Manitara, N. E., & Hadjicostis, C. N. (2014) · International Symposium on Communications, Control and Signal Processing · doi:10.1109/isccsp.2014.6877918 · Cited by 13
Distributed Acoustic Beamforming With Blockchain Protection
Wang, Q., Guo, S., & Yiu, K. F. C. (2020) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2020.2975899 · Cited by 13
Find Your Place: Simple Distributed Algorithms for Community Detection
Becchetti, L., Clementi, A. E. F., Natale, E., Pasquale, F., & Trevisan, L. (2020) · SIAM Journal on Computing · doi:10.1137/19m1243026 · Cited by 13
An early-stopping protocol for computing aggregate functions in Sensor Networks
Anta, A. F., Mosteiro, M. A., & Thraves, C. (2012) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2012.09.013 · Cited by 13
Decentralized Personalized Federated Learning for Min-Max ProblemsPreprint
Borodich, E. D., Beznosikov, A. N., Sadiev, A., Sushko, V., Savelyev, N., Takáč, M., & Gasnikov, A. V. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.07289 · Cited by 13
Fast Gossip via Non-reversible Random Walk
Jung, K., & Shah, D. (2006) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2006.1633783 · Cited by 13
Decentralized K-Means Using Randomized Gossip Protocols for Clustering Large Datasets
Fellus, J., Picard, D., & Gosselin, P.-H. (2013) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw.2013.58 · Cited by 13
Optimal Discrete-Time Distributed Kalman Filter With Reduced Communication
Battilotti, S., Borri, A., Cacace, F., & d’Angelo, M. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3496577 · Cited by 13
GDE: a distributed gradient-based algorithm for distance estimation in large-scale networks
Liu, Q., Pruteanu, A., & Dulman, S. (2011) · ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM) · doi:10.1145/2068897.2068925 · Cited by 13
Ramírez‐Llanos, E., & Martínez, S. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402405 · Cited by 13
Noisy Rumor Spreading and Plurality Consensus
Fraigniaud, P., & Natale, E. (2016) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/2933057.2933089 · Cited by 13
Aggregation Techniques for the Internet of Things: An Overview
Guidi, B., & Ricci, L. (2018) · Internet of things · doi:10.1007/978-3-319-96550-5_7 · Cited by 13
A Distributed Eigensolver for Loosely Coupled Networks
Straková, H., & Gansterer, W. N. (2013) · Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP) · doi:10.1109/pdp.2013.18 · Cited by 13
Identifying Frequent Items in P2P Systems
Li, M., & Lee, W.-C. (2008) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2008.78 · Cited by 13
Flat and hierarchical epidemics in P2P systems: Energy cost models and analysis
Özkasap, Ö., Çem, E., Cebeci, S. E., & Koc, T. (2013) · Future Generation Computer Systems · doi:10.1016/j.future.2013.09.009 · Cited by 13
Robust distributed orthogonalization based on randomized aggregation
Gansterer, W. N., Niederbrucker, G., Straková, H., & Grotthoff, S. S. (2011) · doi:10.1145/2133173.2133177 · Cited by 13
Bounds for algebraic gossip on graphs
Borokhovich, M., Avin, C., & Lotker, Z. (2012) · Random Structures and Algorithms · doi:10.1002/rsa.20480 · Cited by 13
Duplicate-Insensitive Order Statistics Computation over Data Streams
Zhang, Y., Lin, X., Yuan, Y., Kitsuregawa, M., Zhou, X., & Yu, J. X. (2009) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2009.68 · Cited by 13
Bandwidth-constrained queries in sensor networks
Deligiannakis, A., Kotidis, Y., & Roussopoulos, N. (2006) · The VLDB Journal · doi:10.1007/s00778-006-0016-z · Cited by 13
On collaborative content distribution using multi-message gossip
Fernandess, C., & Malkhi, D. (2006) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2006.1639258 · Cited by 13
Zimmermann, J., Tatarenko, T., Willert, V., & Adamy, J. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9304360 · Cited by 12
A Unified Framework for Continuous-Time Unconstrained Distributed Optimization
Touri, B., & Gharesifard, B. (2023) · SIAM Journal on Control and Optimization · doi:10.1137/21m1442711 · Cited by 12
Momentum methods for stochastic optimization over time-varying directed networks
Cui, Z., Fan, Q., & Jia, C. (2020) · Signal Processing · doi:10.1016/j.sigpro.2020.107614 · Cited by 12
Distributed subgradient-push online convex optimization on time-varying directed graphs
Akbari, M. A., Gharesifard, B., & Linder, T. (2014) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2014.7028465 · Cited by 12
Distributed Saddle-Point Problems: Lower Bounds, Optimal and Robust AlgorithmsPreprint
Beznosikov, A. N., Samokhin, V., & Gasnikov, A. V. (2020) · arXiv (Cornell University) · Cited by 12
Gossip-Based Reputation Management for Unstructured Peer-to-Peer Networks
Zhou, R., Hwang, K., & Cai, M. (2007) · Cited by 12
Domínguez-García, A. D., Hadjicostis, C. N., & Vaidya, N. H. (2011) · Defense Technical Information Center (DTIC) · doi:10.21236/ada558911 · Cited by 12
Finite Rate Distributed Weight-Balancing and Average Consensus Over Digraphs
Lee, C.-S., Michelusi, N., & Scutari, G. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3030871 · Cited by 12
Supervised Average Consensus in Anonymous Dynamic Networks
Kowalski, D. R., & Mosteiro, M. A. (2021) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3409964.3461811 · Cited by 12
Exploiting heterogeneity in peer-to-peer systems using gradient topologies
Šácha, J. (2009) · Cited by 12
Gossip-Based Greedy Gaussian Mixture Learning
Vlassis, N. A., Sfakianakis, Y., & Kowalczyk, W. (2005) · Lecture notes in computer science · doi:10.1007/11573036_33 · Cited by 12
Discrete-Time distributed secondary control of DC microgrids with communication delays
Moradi, M., Heydari, M., Zarei, S. F., & Oshnoei, A. (2023) · Electric Power Systems Research · doi:10.1016/j.epsr.2023.109935 · Cited by 12
A Faster Exact-Counting Protocol for Anonymous Dynamic Networks
Chakraborty, M., Milani, A., & Mosteiro, M. A. (2017) · Algorithmica · doi:10.1007/s00453-017-0367-4 · Cited by 12
Chen, X., Jiang, W., Charalambous, T., & Shi, L. (2023) · IEEE Control Systems Letters · doi:10.1109/lcsys.2023.3292463 · Cited by 12
Finite-time distributed averaging
Mou, S., & Morse, A. S. (2014) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2014.6859261 · Cited by 12
Dynamic-Based Privacy Preservation for Distributed Economic Dispatch of Microgrids
Cheng, H., Liao, X., Li, H., & Lü, Q. (2024) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2024.3431730 · Cited by 12
A gossip-based approach to exascale system services
Soltero, P., Bridges, P. G., Arnold, D. C., & Lang, M. (2013) · International Workshop on Runtime and Operating Systems for Supercomputers · doi:10.1145/2491661.2481428 · Cited by 12
A comparative study of spanning tree and gossip protocols for aggregation
Nyers, L., & Jelasity, M. (2015) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.3549 · Cited by 12
Distributed Optimal Control of Discrete-Time Linear Systems Over Networks
Battilotti, S., Cacace, F., & d’Angelo, M. (2023) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2023.3295346 · Cited by 12
The asynchronous DeGroot dynamics
Elboim, D., Peres, Y., & Peretz, R. (2024) · Random Structures and Algorithms · doi:10.1002/rsa.21248 · Cited by 12
Convergence Detection in Epidemic Aggregation
Poonpakdee, P., Orhon, N. G., & Fatta, G. D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-54420-0_29 · Cited by 12
RASN: Resist on-off Attack for Wireless Sensor Networks
Shi, P., & Chen, H. (2012) · International Conference on Computer Application and System Modeling · doi:10.2991/iccasm.2012.175 · Cited by 12
Radio cover time in hyper-graphs
Avin, C., Lando, Y., & Lotker, Z. (2012) · Ad Hoc Networks · doi:10.1016/j.adhoc.2012.08.010 · Cited by 12
Mobi-G: Gossip-based monitoring in MANETs
Stingl, D., Retz, R., Richerzhagen, B., Groß, C., & Steinmetz, R. (2014) · IEEE/IFIP Network Operations and Management Symposium (NOMS) · doi:10.1109/noms.2014.6838313 · Cited by 12
Space Pseudorandom Generators by Communication Complexity Lower Bounds
Ganor, A., & Raz, R. (2014) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.approx-random.2014.692 · Cited by 12
A Faster Counting Protocol for Anonymous Dynamic Networks
Milani, A., & Mosteiro, M. A. (2015) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.opodis.2015.28 · Cited by 12
Strong Robustness of Randomized Rumor Spreading Protocols
Doerr, B., Huber, A. L., & Levavi, A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10631-6_82 · Cited by 12
Radio cover time in hyper-graphs
Avin, C., Lando, Y., & Lotker, Z. (2010) · Foundations of Mobile Computing · doi:10.1145/1860684.1860689 · Cited by 12
An empirical comparison of multi-agent optimization algorithms
Assran, M., & Rabbat, M. (2017) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2017.8309024 · Cited by 11
An introduction to decentralized stochastic optimization with gradient trackingPreprint
Xin, R., Kar, S., & Khan, U. A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.09648 · Cited by 11
Hamedani, E. Y., & Aybat, N. S. (2017) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2017.8262781 · Cited by 11
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
- 45
- 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.