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 201–300 of 1,004
Moment-based quantile sketches for efficient high cardinality aggregation queries
Gan, E., Ding, J., Tai, K. S., Sharan, V., & Bailis, P. D. (2018) · Proceedings of the VLDB Endowment · doi:10.14778/3236187.3236212 · Cited by 66
ExtraPush for convex smooth decentralized optimization over directed networks
Zeng, J., & Yin, W. (2015) · arXiv · doi:10.48550/arxiv.1511.02942 · Cited by 65
D-Cliques: Compensating for Data Heterogeneity with Topology in Decentralized Federated Learning
Bellet, A., Kermarrec, A.-M., & Lavoie, E. (2022) · IEEE Symposium on Reliable Distributed Systems (SRDS) · doi:10.1109/srds55811.2022.00011 · Cited by 65
Spiridonoff, A., Olshevsky, A., & Paschalidis, I. C. (2018) · PubMed · doi:10.48550/arxiv.1811.03982 · Cited by 65
Graph balancing for distributed subgradient methods over directed graphs
Makhdoumi, A., & Ozdaglar, A. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402401 · Cited by 64
Ding, L., Lin, Z., Shi, X., & Yan, G. (2022) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2022.3159825 · Cited by 64
Accelerated $AB$/Push–Pull Methods for Distributed Optimization Over Time-Varying Directed Networks
Nguyen, D. T. A., Nguyen, D. T., & Nedić, A. (2023) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2023.3338236 · Cited by 63
Distributed Dynamic Speed Scaling
Stanojević, R., & Shorten, R. N. (2010) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2010.5462197 · Cited by 63
Gossip along the way: order-optimal consensus through randomized path averaging
Bénézit, F., Dimakis, A. G., Thiran, P., & Vetterli, M. (2007) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 62
Distributed Nesterov Gradient and Heavy-Ball Double Accelerated Asynchronous Optimization
Li, H., Cheng, H., Wang, Z., & Wu, G. (2020) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.3027381 · Cited by 62
Broadcast and Gossip Stochastic Average Consensus Algorithms in Directed Topologies
Silvestre, D., Hespanha, J. P., & Silvestre, C. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2018.2839341 · Cited by 62
On the Cover Time of Random Geometric Graphs
Avin, C., & Ercal, G. (2005) · Lecture notes in computer science · doi:10.1007/11523468_55 · Cited by 61
S-ADDOPT: Decentralized Stochastic First-Order Optimization Over Directed Graphs
Qureshi, M. I., Xin, R., Kar, S., & Khan, U. A. (2020) · IEEE Control Systems Letters · doi:10.1109/lcsys.2020.3006420 · Cited by 61
Asymptotically optimal consensus-based distributed filtering of continuous-time linear systems
Battilotti, S., Cacace, F., d’Angelo, M., & Germani, A. (2020) · Automatica · doi:10.1016/j.automatica.2020.109189 · Cited by 61
A Generic Local Algorithm for Mining Data Streams in Large Distributed Systems
Wolff, R., Bhaduri, K., & Kargupta, H. (2008) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2008.169 · Cited by 61
Geographic gossip: efficient aggregation for sensor networks
Dimakis, A. G., Sarwate, A. D., & Wainwright, M. J. (2006) · ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN) · doi:10.1109/ipsn.2006.244081 · Cited by 61
Decentralized Directed Collaboration for Personalized Federated Learning
Liu, Y., Shi, Y., Wu, B., Li, Q., Wang, X., & Shen, L. (2024) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52733.2024.02186 · Cited by 61
FlashMob: distributed adaptive self-assembly
Sykes, D., Magee, J., & Kramer, J. (2011) · International Symposium on Software Engineering for Adaptive and Self-Managing Systems (SEAMS) · doi:10.1145/1988008.1988023 · Cited by 61
A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks
Pu, S. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9303917 · Cited by 60
A Distributed ADMM-like Method for Resource Sharing over Time-Varying Networks
Aybat, N. S., & Hamedani, E. Y. (2019) · SIAM Journal on Optimization · doi:10.1137/17m1151973 · Cited by 60
Distributed computation of coverage in sensor networks by homological methods
Dłotko, P., Ghrist, R., Juda, M., & Mrożek, M. (2012) · Applicable Algebra in Engineering Communication and Computing · doi:10.1007/s00200-012-0167-7 · Cited by 58
A Polylogarithmic Gossip Algorithm for Plurality Consensus
Ghaffari, M., & Parter, M. (2016) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/2933057.2933097 · Cited by 57
Distributed optimization for deep learning with gossip exchange
Blot, M., Picard, D., Thome, N., & Cord, M. (2018) · Neurocomputing · doi:10.1016/j.neucom.2018.11.002 · Cited by 56
How Agreement and Disagreement Evolve over Random Dynamic Networks
Shi, G., Johansson, M., & Johansson, K. H. (2013) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2013.130608 · Cited by 56
Cross-Gradient Aggregation for Decentralized Learning from Non-IID dataPreprint
Esfandiari, Y., Tan, S. Y., Jiang, Z., Balu, A., Herron, E., Hegde, C., & Sarkar, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.02051 · Cited by 56
An Assertion-Based Program Logic for Probabilistic Programs
Barthe, G., Espitau, T., Gaboardi, M., Grégoire, B., Hsu, J., & Strub, P.-Y. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-89884-1_5 · Cited by 56
Towards worst-case churn resistant peer-to-peer systems
Kühn, F., Schmid, S., & Wattenhofer, R. P. (2010) · Distributed Computing · doi:10.1007/s00446-010-0099-z · Cited by 56
The power of choice in random walks: An empirical study
Avin, C., & Krishnamachari, B. (2007) · Computer Networks · doi:10.1016/j.comnet.2007.09.012 · Cited by 56
Battilotti, S., Cacace, F., & d’Angelo, M. (2021) · Automatica · doi:10.1016/j.automatica.2021.109589 · Cited by 55
Analysis of Sum-Weight-Like Algorithms for Averaging in Wireless Sensor Networks
Iutzeler, F., Ciblat, P., & Hachem, W. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2256904 · Cited by 55
The Impact of Mobility on Gossip Algorithms
Sarwate, A. D., & Dimakis, A. G. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2177753 · Cited by 55
Federated Bandit: A Gossiping Approach
Zhu, Z., Zhu, J., Liu, J., & Liu, Y. (2021) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/3410220.3453919 · Cited by 55
Federated Bandit: A Gossiping Approach
Zhu, Z., Zhu, J., Liu, J., & Liu, Y. (2021) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3447380 · Cited by 55
Parsimonious flooding in dynamic graphs
Baumann, H., Crescenzi, P., & Fraigniaud, P. (2011) · Distributed Computing · doi:10.1007/s00446-011-0133-9 · Cited by 55
Networked Computing in Wireless Sensor Networks for Structural Health Monitoring
Jindal, A., & Liu, M. (2011) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2011.2175450 · Cited by 55
Analysis of accelerated gossip algorithms
Liu, J., Anderson, B. D. O., Cao, M., & Morse, A. S. (2013) · Automatica · doi:10.1016/j.automatica.2013.01.001 · Cited by 55
Aggregation methods for large-scale sensor networks
Chitnis, L., Dobra, A., & Ranka, S. (2008) · ACM Transactions on Sensor Networks · doi:10.1145/1340771.1340775 · Cited by 55
Self-citationHERO: Online Real-Time Vehicle Tracking
Zhu, H., Li, M., Zhu, Y., & Ni, L. M.-S. (2008) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2008.147 · Cited by 55
Gossip-based aggregation of trust in decentralized reputation systems
Bachrach, Y., Parnes, A., Procaccia, A. D., & Rosenschein, J. S. (2008) · Autonomous Agents and Multi-Agent Systems · doi:10.1007/s10458-008-9073-6 · Cited by 54
Design of a multi-hop dynamic consensus algorithm over wireless sensor networks
Manfredi, S. (2013) · Control Engineering Practice · doi:10.1016/j.conengprac.2012.12.001 · Cited by 54
A Novel Wireless Sensor Network Frame for Urban Transportation
Hu, X., Yang, L., & Xiong, W. (2015) · IEEE Internet of Things Journal · doi:10.1109/jiot.2015.2475639 · Cited by 54
Robust Distributed Consensus Using Total Variation
Ben‐Ameur, W., Bianchi, P., & Jakubowicz, J. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2471755 · Cited by 53
Conscious and Unconscious Counting on Anonymous Dynamic Networks
Luna, G. A. D., Baldoni, R., Bonomi, S., & Chatzigiannakis, I. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-45249-9_17 · Cited by 53
Ignore or Comply? On Breaking Symmetry in Consensus
Berenbrink, P., Clementi, A. E. F., Elsässer⋆, R., Kling, P., Mallmann-Trenn, F., & Natale, E. (2017) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/3087801.3087817 · Cited by 53
A distributed algorithm for average consensus on strongly connected weighted digraphs
Priolo, A., Gasparri, A., Montijano, E., & Sagüés, C. (2014) · Automatica · doi:10.1016/j.automatica.2013.12.026 · Cited by 52
Privacy-Preserving Average Consensus on Directed Graphs Using Push-Sum
Gao, H. B., Zhang, C., Ahmad, M., & Wang, Y. (2018) · IEEE Conference on Communications and Network Security · doi:10.1109/cns.2018.8433217 · Cited by 52
Tight bounds for distributed selection
Kühn, F., Locher, T., & Wattenhofer, R. P. (2007) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1248377.1248401 · Cited by 52
Distributed Averaging on Asynchronous Communication Networks
Mehyar, M., Spanos, D. P., Pongsajapan, J., Low, S. H., & Murray, R. M. (2006) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2005.1583363 · Cited by 51
Chen, W., Wang, Z., Dong, H., Mao, J., & Liu, G. P. (2023) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2023.3321027 · Cited by 51
Asymmetric Randomized Gossip Algorithms for Consensus
Fagnani, F., & Zampieri, S. (2008) · IFAC Proceedings Volumes · doi:10.3182/20080706-5-kr-1001.01528 · Cited by 51
Adaptive Peer Sampling with Newscast
Tölgyesi, N., & Jelasity, M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03869-3_50 · Cited by 51
Counting in Anonymous Dynamic Networks under Worst-Case Adversary
Luna, G. A. D., Baldoni, R., Bonomi, S., & Chatzigiannakis, I. (2014) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2014.42 · Cited by 50
Gossip-based distribution estimation in peer-to-peer networks
Haridasan, M., & van Renesse, R. (2008) · International Workshop on Peer-to-Peer Systems · Cited by 50
The power of choice in random walks: an empirical study
Avin, C., & Krishnamachari, B. (2006) · ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM) · doi:10.1145/1164717.1164757 · Cited by 50
Reaching Consensus on Social Networks
Mossel, E., & Schoenebeck, G. R. (2010) · ScholarlyCommons (University of Pennsylvania) · Cited by 49
Detecting Outliers in Sensor Networks Using the Geometric Approach
Burdakis, S., & Deligiannakis, A. (2012) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2012.85 · Cited by 48
Chen, W., Wang, Z., Liu, Q., Yue, D., & Liu, G. P. (2024) · Automatica · doi:10.1016/j.automatica.2024.111715 · Cited by 48
Continuous-time distributed convex optimization on time-varying directed networks
Touri, B., & Gharesifard, B. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402315 · Cited by 48
Robust monitoring of network-wide aggregates through gossiping
Wuhib, F., Dam, M., Stadler, R., & Clem, A. (2009) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2009.090603 · Cited by 48
Partial information spreading with application to distributed maximum coverage
Censor-Hillel, K., & Shachnai, H. (2010) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/1835698.1835739 · Cited by 48
Fenchel Dual Gradient Methods for Distributed Convex Optimization Over Time-Varying Networks
Wu, X., & Lu, J. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2901829 · Cited by 47
Jin, B., Li, H., Yan, W., & Cao, M. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3021528 · Cited by 47
Privacy-Preserving Average Consensus in Multiagent Systems via Partial Information Transmission
Zhang, J., Lu, J., Liang, J., & Shi, K. (2022) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2022.3220578 · Cited by 47
A Wireless Sensor Network Testbed
Ho, Q., & Le‐Ngoc, T. (2010) · Annual Communication Networks and Services Research Conference (CNSR) · doi:10.1109/cnsr.2010.71 · Cited by 47
Kostoulas, D., Psaltoulis, D., Gupta, I., Birman, K., & Demers, A. J. (2007) · Journal of Systems and Software · doi:10.1016/j.jss.2007.01.014 · Cited by 47
Randomized consensus algorithms over large scale networks
Fagnani, F., & Zampieri, S. (2007) · Information Theory and Applications Workshop (ITA) · doi:10.1109/ita.2007.4357574 · Cited by 46
Coordinate Dual Averaging for Decentralized Online Optimization With Nonseparable Global Objectives
Lee, S., Nedić, A., & Raginsky, M. (2016) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2016.2573639 · Cited by 46
Streaming in a connected world: querying and tracking distributed data streams
Cormode, G., & Garofalakis, M. (2007) · International Conference on Extending Database Technology (EDBT) · doi:10.1145/1353343.1353442 · Cited by 46
A Fast Row-Stochastic Decentralized Method for Distributed Optimization Over Directed Graphs
Ghaderyan, D., Aybat, N. S., Aguiar, A. P., & Перейра, Ф. Л. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3275927 · Cited by 45
Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
Song, Z., Shi, L., Pu, S., & Yan, M. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3160238 · Cited by 45
Distributed Collaborative 3D-Deployment of UAV Base Stations for On-Demand Coverage
Kimura, T., & Ogura, M. (2020) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom41043.2020.9155283 · Cited by 45
Anytime Reliable Transmission of Real-Valued Information through Digital Noisy Channels
Como, G., Fagnani, F., & Zampieri, S. (2010) · SIAM Journal on Control and Optimization · doi:10.1137/09074601x · Cited by 45
The art of clustering bandits.
Li, S. (2016) · IrInSubria (University of Insubria) · Cited by 45
Finite-Time Convergent Gossiping
Shi, G., Li, B., Johansson, M., & Johansson, K. H. (2015) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2015.2484345 · Cited by 45
DC-DistADMM: ADMM Algorithm for Constrained Optimization Over Directed Graphs
Khatana, V., & Salapaka, M. V. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3221856 · Cited by 44
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 44
Privary Preserving Distributed Average Consensus via Homomorphic Encryption
Hadjicostis, C. N. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619120 · Cited by 44
Reaching approximate Byzantine consensus with multi-hop communication
Su, L., & Vaidya, N. H. (2016) · Information and Computation · doi:10.1016/j.ic.2016.12.003 · Cited by 44
Tight bounds for algebraic gossip on graphs
Borokhovich, M., Avin, C., & Lotker, Z. (2010) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2010.5513272 · Cited by 44
Hierarchical Spatial Gossip for Multi-Resolution Representations in Sensor Networks
Sarkar, R., Zhu, X., & Gao, J. (2007) · ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN) · doi:10.1109/ipsn.2007.4379702 · Cited by 44
GUESS: gossiping updates for efficient spectrum sensing
Ahmed, N., Hadaller, D., & Keshav, S. (2006) · doi:10.1145/1161252.1161256 · Cited by 44
A Proximal Diffusion Strategy for Multiagent Optimization With Sparse Affine Constraints
Alghunaim, S. A., Yuan, K., & Sayed, A. H. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2960265 · Cited by 43
Liang, S., Wang, L. Y., & Yin, G. (2018) · Automatica · doi:10.1016/j.automatica.2018.11.056 · Cited by 43
A simple median-based resilient consensus algorithm
Zhang, H., & Sundaram, S. (2012) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2012.6483431 · Cited by 43
Tsianos, K. I., & Rabbat, M. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2620440 · Cited by 43
A Communication-Efficient Multi-Agent Actor-Critic Algorithm for Distributed Reinforcement Learning
Lin, Y., Zhang, K., Yang, Z., Wang, Z., Başar, T., Sandhu, R., & Liu, J. (2019) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc40024.2019.9029257 · Cited by 43
Space-Optimal Counting in Population Protocols
Beauquier, J., Burman, J., Clavière, S., & Sohier, D. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48653-5_42 · Cited by 43
Cover time and mixing time of random walks on dynamic graphs
Avin, C., Koucký, M., & Lotker, Z. (2017) · Random Structures and Algorithms · doi:10.1002/rsa.20752 · Cited by 43
Kamath, G., Agnihotri, P., Valero, M., Sarker, K., & Song, W.-Z. (2016) · 2016 IEEE Global Communications Conference (GLOBECOM) · doi:10.1109/glocom.2016.7842181 · Cited by 42
Peer-to-peer evolutionary algorithms with adaptive autonomous selection
Wickramasinghe, W. R. M. U. K., van Steen, M. R., & Eiben, A. E. (2007) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/1276958.1277225 · Cited by 42
Optimal Prefetching Scheme in P2P VoD Applications With Guided Seeks
He, Y., Shen, G., Xiong, Y., & Guan, L. (2008) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2008.2008929 · Cited by 42
Convergence and Applications of a Gossip-Based Gauss-Newton Algorithm
Li, X., & Scaglione, A. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2276440 · Cited by 41
Broadcast gossip algorithms: Design and analysis for consensus
Aysal, T. C., Yildiz, M. E., Sarwate, A. D., & Scaglione, A. (2008) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2008.4739315 · Cited by 41
Local L2-Thresholding Based Data Mining in Peer-to-Peer Systems
Wolff, R., Bhaduri, K., & Kargupta, H. (2006) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972764.38 · Cited by 40
Large-scale k-means clustering with user-centric privacy-preservation
Sakuma, J., & Kobayashi, S. (2009) · Knowledge and Information Systems · doi:10.1007/s10115-009-0243-x · Cited by 40
ASY-SONATA: Achieving Linear Convergence in Distributed Asynchronous Multiagent Optimization
Tian, Y., Sun, Y., & Scutari, G. (2018) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2018.8636055 · Cited by 39
Resilient consensus‐based distributed optimization under deception attacks
Fu, W., Ma, Q., Qin, J., & Kang, Y. (2020) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.5026 · Cited by 39
Aysal, T. C., Yildiz, M. E., & Scaglione, A. (2008) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2008.4578682 · Cited by 39
Vosoughi, A., Cavallaro, J. R., & Marshall, A. (2016) · IEEE Transactions on Cognitive Communications and Networking · doi:10.1109/tccn.2016.2584080 · Cited by 39
Rumor spreading and vertex expansion on regular graphs
Sauerwald, T., & Stauffer, A. O. (2011) · Max Planck Institute for Plasma Physics · doi:10.5555/2133036.2133073 · Cited by 39
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.