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 101–200 of 1,004
A survey on fault tolerance in small and large scale wireless sensor networks
Chouikhi, S., Korbi, I. E., Ghamri-Doudane, Y. M., & Saïdane, L. A. (2015) · Computer Communications · doi:10.1016/j.comcom.2015.05.007 · Cited by 143
Network Coding for Computing: Cut-Set Bounds
Appuswamy, R., Franceschetti, M., Karamchandani, N., & Zeger, K. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2095070 · Cited by 143
Cachet: a decentralized architecture for privacy preserving social networking with caching
Nilizadeh, S., Jahid, S., Mittal, P., Borisov, N., & Kapadia, A. C. (2012) · ACM International Conference on emerging Networking EXperiments and Technologies (CoNEXT) · doi:10.1145/2413176.2413215 · Cited by 142
Chen, J.-Y., Pandurangan, G., & Xu, D. (2006) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2006.128 · Cited by 139
Distributed optimization over directed graphs with row stochasticity and constraint regularity
Mai, V. S., & Abed, E. H. (2019) · Automatica · doi:10.1016/j.automatica.2018.07.020 · Cited by 137
Almost tight bounds for rumour spreading with conductance
Chierichetti, F., Lattanzi, S., & Panconesi, A. (2010) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1806689.1806745 · Cited by 137
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 136
Self-citationSynopsis diffusion for robust aggregation in sensor networks
Nath, S., Gibbons, P. B., Seshan, S., & Anderson, Z. (2008) · ACM Transactions on Sensor Networks · doi:10.1145/1340771.1340773 · Cited by 135
Advances in Asynchronous Parallel and Distributed Optimization
Assran, M., Aytekin, A., Feyzmahdavian, H. R., Johansson, M., & Rabbat, M. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3026619 · Cited by 132
Fast and Exact Majority in Population Protocols
Alistarh, D., Gelashvili, R., & Vojnović, M. (2015) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/2767386.2767429 · Cited by 130
A Survey of Synopsis Construction in Data Streams
Aggarwal, C. C., & Yu, P. S. (2007) · Springer eBooks · doi:10.1007/978-0-387-47534-9_9 · Cited by 126
Using Three States for Binary Consensus on Complete Graphs
Perron, E., Vasudevan, D., & Vojnović, M. (2009) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2009.5062181 · Cited by 125
FROST—Fast row-stochastic optimization with uncoordinated step-sizes
Xin, R., Xi, C., & Khan, U. A. (2019) · EURASIP Journal on Advances in Signal Processing · doi:10.1186/s13634-018-0596-y · Cited by 122
Parallel and Distributed Successive Convex Approximation Methods for Big-Data Optimization
Scutari, G., & Sun, Y. (2018) · Lecture notes in mathematics · doi:10.1007/978-3-319-97142-1_3 · Cited by 121
Stochastic Gradient Push for Distributed Deep Learning
Assran, M., Loizou, N., Ballas, N., & Rabbat, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.10792 · Cited by 120
Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous DataPreprint
Lin, T., Karimireddy, S. P., Stich, S. U., & Jaggi, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.04761 · Cited by 120
Achieving Linear Convergence in Distributed Asynchronous Multiagent Optimization
Tian, Y., Sun, Y., & Scutari, G. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2977940 · Cited by 120
Dkhili, N., Eynard, J., Thil, S., & Grieu, S. (2019) · Sustainable Energy Grids and Networks · doi:10.1016/j.segan.2019.100284 · Cited by 118
On the cover time and mixing time of random geometric graphs
Avin, C., & Ercal, G. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2007.02.065 · Cited by 118
Xin, R., Kar, S., & Khan, U. A. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2974267 · Cited by 114
“A well-studied solution to this issue is based on the push-sum (type) algorithms [39] that enable consensus with non-DS weights through the help of eigenvector estimation.”
MethodGossip-based distributed stochastic bandit algorithms
Szörényi, B., Busa‐Fekete, R., Hegedűs, I., Ormándi, R., Jelasity, M., & Kégl, B. (2013) · HAL · Cited by 113
Analyzing network coding gossip made easy
Haeupler, B. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993676 · Cited by 113
Robust Distributed Average Consensus via Exchange of Running Sums
Hadjicostis, C. N., Vaidya, N. H., & Domínguez-García, A. D. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2471695 · Cited by 112
Distributed Finite-Time Computation of Digraph Parameters: Left-Eigenvector, Out-Degree and Spectrum
Charalambous, T., Rabbat, M., Johansson, M., & Hadjicostis, C. N. (2015) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2015.2428411 · Cited by 107
Consensus Control for Decentralized Deep LearningPreprint
Kong, L., Lin, T., Koloskova, A., Jaggi, M., & Stich, S. U. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.04828 · Cited by 106
Convergence Rate of Distributed Averaging Dynamics and Optimization in Networks
Nedić, A. (2015) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000004 · Cited by 105
Gossip Dual Averaging for Decentralized Optimization of Pairwise FunctionsPreprint
Colin, I., Bellet, A., Salmon, J., & Clémençon, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.02421 · Cited by 103
Gossip Coverage Control for Robotic Networks: Dynamical Systems on the Space of Partitions
Bullo, F., Carli, R., & Frasca, P. (2012) · SIAM Journal on Control and Optimization · doi:10.1137/100806370 · Cited by 103
Coalescing Random Walks and Voting on Connected Graphs
Cooper, C., Elsässer⋆, R., Ono, H., & Radzik, T. (2013) · SIAM Journal on Discrete Mathematics · doi:10.1137/120900368 · Cited by 103
Assran, M. S., & Rabbat, M. G. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2981035 · Cited by 101
Stochastic Dual Averaging for Decentralized Online Optimization on Time-Varying Communication Graphs
Lee, S., Nedić, A., & Raginsky, M. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2650563 · Cited by 100
Broadcast Gossip Algorithms for Distributed Peer-to-Peer Control in AC Microgrids
Lai, J., Lu, X., Wang, F., Dehghanian, P., & Tang, R. (2019) · IEEE Transactions on Industry Applications · doi:10.1109/tia.2019.2898367 · Cited by 100
Stabilizing Consensus with Many Opinions
Becchetti, L., Clementi, A. E. F., Natale, E., Pasquale, F., & Trevisan, L. (2015) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974331.ch46 · Cited by 99
Convergence of Consensus Models With Stochastic Disturbances
Aysal, T. C., & Barner, K. E. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2050940 · Cited by 96
Plurality Consensus in the Gossip Model
Becchetti, L., Clementi, A. E. F., Natale, E., Pasquale, F., & Silvestri, R. (2014) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973730.27 · Cited by 95
A Push-Pull Gradient Method for Distributed Optimization in Networks
Pu, S., Shi, W., Xu, J., & Nedic, A. (2018) · 2018 IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619047 · Cited by 94
Robust aggregation protocols for large-scale overlay networks
Montresor, A., Jelasity, M., & Babaoğlu, Ö. (2004) · International Conference on Dependable Systems & Networks/Proceedings · doi:10.1109/dsn.2004.1311873 · Cited by 94
Order-Optimal Consensus Through Randomized Path Averaging
Bénézit, F., Dimakis, A. G., Thiran, P., & Vetterli, M. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2060050 · Cited by 91
Randomized Consensus-Based Distributed Kalman Filtering Over Wireless Sensor Networks
Qin, J., Jie, W., Shi, L., & Kang, Y. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3026017 · Cited by 91
Decentralized Collaborative Learning of Personalized Models over Networks
Vanhaesebrouck, P., Bellet, A., & Tommasi, M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1610.05202 · Cited by 89
Distributed Optimal Dispatch of Distributed Energy Resources Over Lossy Communication Networks
Wu, J., Yang, T., Wu, D. X., Kalsi, K., & Johansson, K. H. (2017) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2017.2720761 · Cited by 89
Rumour spreading and graph conductance
Chierichetti, F., Lattanzi, S., & Panconesi, A. (2010) · IRIS Research product catalog (Sapienza University of Rome) · Cited by 89
A Tight Bound for Set Disjointness in the Message-Passing Model
Braverman, M., Ellen, F., Oshman, R., Pitassi, T., & Vaikuntanathan, V. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.77 · Cited by 88
Rumour spreading and graph conductance
Chierichetti, F., Lattanzi, S., & Panconesi, A. (2010) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973075.135 · Cited by 88
Network-Based Consensus Averaging With General Noisy Channels
Rajagopal, R., & Wainwright, M. J. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2077282 · Cited by 87
Distributed nonconvex multiagent optimization over time-varying networks
Sun, Y., Scutari, G., & Palomar, D. (2016) · 2016 50th Asilomar Conference on Signals, Systems and Computers · doi:10.1109/acssc.2016.7869154 · Cited by 86
“As a final remark, we point out that the proposed broadcast protocol is different from the renowned pushed-sum protocol [16], used in a number of papers [6], [7], [12], [17] to remove the doublestochastic requirement on the consensus matrix.”
MethodCommunication-Efficient Distributed Deep Learning: A Comprehensive Survey
Tang, Z., Shi, S., Wang, W., Li, B., & Chu, X. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.06307 · Cited by 86
Distributed Nesterov Gradient Methods Over Arbitrary Graphs
Xin, R., Jakovetić, D., & Khan, U. A. (2019) · IEEE Signal Processing Letters · doi:10.1109/lsp.2019.2925537 · Cited by 86
The price of validity in dynamic networks
Bawa, M., Gionis, A., García-Molina, H., & Motwani, R. (2004) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1007568.1007627 · Cited by 86
Distributed data mining: a survey
Zeng, L., Li, L., Duan, L., Lu, K., Shi, Z., Wang, M., Wu, W., & Luo, P. (2012) · Information Technology and Management · doi:10.1007/s10799-012-0124-y · Cited by 85
“The approach proposed by Kempe [24] relied on uniform gossip-based randomized algorithms for computing aggregate information.”
How to scale distributed deep learning?
Jin, P. H., Yuan, Q., Iandola, F., & Keutzer, K. (2016) · arXiv · doi:10.48550/arxiv.1611.04581 · Cited by 85
Peer-to-peer-based integrated grid voltage support function for smart photovoltaic inverters
Almasalma, H., Claeys, S., & Deconinck, G. (2019) · Applied Energy · doi:10.1016/j.apenergy.2019.01.249 · Cited by 85
Chain FL: Decentralized Federated Machine Learning via Blockchain
Korkmaz, C., Kocas, H. E., Uysal, A., Masry, A., Ozkasap, O., & Akgun, B. (2020) · 2020 Second International Conference on Blockchain Computing and Applications (BCCA) · doi:10.1109/bcca50787.2020.9274451 · Cited by 84
“Other fully decentralized algorithms could also be implemented, like Gossip Aggregation algorithms for sharing the model between parties in the training phase [16], [17].”
MethodOn the distributed optimization over directed networks
Xi, C., Wu, Q., & Khan, U. A. (2017) · Neurocomputing · doi:10.1016/j.neucom.2017.06.038 · Cited by 84
Accelerated Gossip Algorithms for Distributed Computation
Cao, M., Spielman, D. A., & Yeh, E. M. (2006) · University of Groningen research database (University of Groningen / Centre for Information Technology) · Cited by 84
PINTS: peer-to-peer infrastructure for tagging systems
Görlitz, O., Sizov, S., & Staab, S. (2008) · International Workshop on Peer-to-Peer Systems · Cited by 83
ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks
Zeng, J., & Yin, W. (2017) · Journal of Computational Mathematics · doi:10.4208/jcm.1606-m2015-0452 · Cited by 82
Li, H., Lü, Q., Chen, G., Huang, T., & Dong, Z. Y. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2994024 · Cited by 81
Decentralized federated learning of deep neural networks on non-iid dataPreprint
Onoszko, N., Karlsson, G., Mogren, O., & Zec, E. L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.08517 · Cited by 81
Distributed Weight Balancing Over Digraphs
Rikos, A. I., Charalambous, T., & Hadjicostis, C. N. (2014) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2014.2323771 · Cited by 80
Analysis and optimization of randomized gossip algorithms
Boyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2004) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2004.1429652 · Cited by 80
Sketches for size of join estimation
Rusu, F., & Dobra, A. (2008) · ACM Transactions on Database Systems · doi:10.1145/1386118.1386121 · Cited by 80
Self-citationDistributed Energy Resource Coordination Over Time-Varying Directed Communication Networks
Yang, T., Wu, D. X., Fang, H., Ren, W., Wang, H., Hong, Y., & Johansson, K. H. (2019) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2019.2921284 · Cited by 80
Tight bounds for the cover time of multiple random walks
Elsässer⋆, R., & Sauerwald, T. (2010) · Theoretical Computer Science · doi:10.1016/j.tcs.2010.08.010 · Cited by 80
Chen, J., Pandurangan, G., & Xu, D. (2005) · ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN) · doi:10.5555/1147685.1147741 · Cited by 80
Reducing Power Consumption in Wireless Sensor Networks Using a Novel Approach to Data Aggregation
Croce, S., Marcelloni, F., & Vecchio, M. (2007) · The Computer Journal · doi:10.1093/comjnl/bxm046 · Cited by 80
Parsimonious flooding in dynamic graphs
Baumann, H., Crescenzi, P., & Fraigniaud, P. (2009) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/1582716.1582757 · Cited by 79
Complexity of Data Collection, Aggregation, and Selection for Wireless Sensor Networks
Li, X., Wang, Y., & Wang, Y. (2010) · IEEE Transactions on Computers · doi:10.1109/tc.2010.50 · Cited by 78
Gossip training for deep learning
Blot, M., Picard, D., Cord, M., & Thome, N. (2016) · arXiv · doi:10.48550/arxiv.1611.09726 · Cited by 77
“…A = (aij)i,j a random matrix: M∑ i=1 E [ `(xi, y) + M∑ j aij ||xi − xj ||22 ] (3) In our gossip method the terms in the outer sum of (3) are sampled concurrently by different workers. aij is a random variable controlling exchanges between workers i and j with p = P(aij 6= 0) and E(aij) = ρ 4M .”
MethodModel-Based Techniques for Data Reliability in Wireless Sensor Networks
Mukhopadhyay, S., Schurgers, C., Panigrahi, D., & Dey, S. (2008) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2008.131 · Cited by 77
Consensus Dynamics: An Overview
Becchetti, L., Clementi, A. E. F., & Natale, E. (2020) · ACM SIGACT News · doi:10.1145/3388392.3388403 · Cited by 77
Quantized Decentralized Stochastic Learning over Directed GraphsPreprint
Taheri, H., Mokhtari, A., Hassani, H., & Pedarsani, R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.09964 · Cited by 76
Distributed saddle point problems: lower bounds, near-optimal and robust algorithms
Beznosikov, A. N., Samokhin, V., & Gasnikov, A. V. (2025) · Optimization methods & software · doi:10.1080/10556788.2025.2463986 · Cited by 76
MESSIF: Metric Similarity Search Implementation Framework
Batko, M., Novák, D., & Zezula, P. (2007) · Springer eBooks · doi:10.1007/978-3-540-77088-6_1 · Cited by 76
Privacy-Preserving Push-Sum Average Consensus via State Decomposition
Chen, X., Huang, L., Ding, K., Dey, S., & Shi, L. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3256479 · Cited by 75
A Decentralized Parallel Algorithm for Training Generative Adversarial NetsPreprint
Liu, M., Zhang, W., Mroueh, Y., Cui, X., Ross, J., Yang, T., & Das, P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.12999 · Cited by 75
Distributed Averaging and Balancing in Network Systems
Hadjicostis, C. N., Domínguez-García, A. D., & Charalambous, T. (2018) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000016 · Cited by 74
Gossiping on MANETs: the beauty and the beast
Friedman, R., Gavidia, D., Rodrigues, L., Viana, A. C., & Voulgaris, S. (2007) · ACM SIGOPS Operating Systems Review · doi:10.1145/1317379.1317390 · Cited by 74
Hashemi, A., Acharya, A., Das, R., Vikalo, H., Sanghavi, S., & Dhillon, I. S. (2021) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2021.3138977 · Cited by 73
Peer-to-Peer-Based Social Networks: A Comprehensive Survey
Masinde, N. W., & Graffi, K. (2020) · SN Computer Science · doi:10.1007/s42979-020-00315-8 · Cited by 73
Fault tolerant decentralised K -Means clustering for asynchronous large-scale networks
Fatta, G. D., Blasa, F., Cafiero, S., & Fortino, G. (2012) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2012.09.009 · Cited by 73
Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
Doerr, B., Friedrich, T., & Sauerwald, T. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02927-1_31 · Cited by 73
Distributed Maximum Likelihood for Simultaneous Self-Localization and Tracking in Sensor Networks
Kantas, N., Singh, S. S., & Doucet, A. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2205923 · Cited by 73
Distributed optimization over time-varying directed graphs
Nedic, A., & Olshevsky, A. (2013) · 52nd IEEE Conference on Decision and Control · doi:10.1109/cdc.2013.6760975 · Cited by 72
A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning
Suttle, W. A., Yang, Z., Zhang, K., Wang, Z., Başar, T., & Liu, J. (2020) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2020.12.2021 · Cited by 72
A Survey of Distributed Optimization Methods for Multi-Robot SystemsPreprint
Halsted, T., Shorinwa, O., Yu, J., & Schwager, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.12840 · Cited by 71
Doerr, B., Friedrich, T., & Sauerwald, T. (2014) · Apollo (University of Cambridge) · doi:10.17863/cam.34651 · Cited by 71
Asynchronous Decentralized SGD with Quantized and Local UpdatesPreprint
Nadiradze, G., Sabour, A., Davies, P. M., Li, S., & Alistarh, D. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.12308 · Cited by 70
Ordered Slicing of Very Large-Scale Overlay Networks
Jelasity, M., & Kermarrec, A.-M. (2006) · IEEE International Conference on Peer-to-Peer Computing (P2P) · doi:10.1109/p2p.2006.25 · Cited by 70
Statistical analysis of sketch estimators
Rusu, F., & Dobra, A. (2007) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1247480.1247503 · Cited by 70
Self-citationInformation Survival Threshold in Sensor and P2P Networks
Chakrabarti, D., Leskovec, J., Faloutsos, C., Madden, S. R., Guestrin, C., & Faloutsos, M. (2007) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2007.156 · Cited by 70
Proactive replication in distributed storage systems using machine availability estimation
Duminuco, A., Biersack, E. W., & En-Najjary, T. (2007) · ACM International Conference on emerging Networking EXperiments and Technologies (CoNEXT) · doi:10.1145/1364654.1364689 · Cited by 70
Gossip Learning: Off the Beaten Path
Giaretta, L., & Girdzijauskas, Š. (2019) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata47090.2019.9006216 · Cited by 69
An Improved Analysis of Gradient Tracking for Decentralized Machine LearningPreprint
Koloskova, A., Lin, T., & Stich, S. U. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2202.03836 · Cited by 68
Distributed Optimization Methods for Multi-Robot Systems: Part 2—A Survey
Shorinwa, O., Halsted, T., Yu, J., & Schwager, M. (2024) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2024.3352852 · Cited by 67
RelaySum for Decentralized Deep Learning on Heterogeneous DataPreprint
Vogels, T., He, L., Koloskova, A., Lin, T., Karimireddy, S. P., Stich, S. U., & Jaggi, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.04175 · Cited by 67
The Role of Persistent Graphs in the Agreement Seeking of Social Networks
Shi, G., & Johansson, K. H. (2013) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2013.sup.0513052 · Cited by 67
Efficient gossip-based aggregate computation
Kashyap, S., Deb, S., Naidu, K. V. M., Rastogi, R. R., & Srinivasan, A. (2006) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1142351.1142395 · Cited by 67
Gossip-based Reputation Aggregation for Unstructured Peer-to-Peer Networks
Zhou, R., & Hwang, K. (2007) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2007.370285 · Cited by 67
Extrema Propagation: Fast Distributed Estimation of Sums and Network Sizes
Baquero, C., Almeida, P. S., Menezes, R., & Jesus, P. C.-M. (2011) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2011.209 · Cited by 67
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.