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
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
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
Nedić, A., Olshevsky, A., & Shi, W. (2017) · SIAM Journal on Optimization · doi:10.1137/16m1084316 · Cited by 1,069
“Instead, if every agent knows its out-degree, it is possible for the agents to construct a column stochastic matrix C and perform the following recursions with initialization u(0) = x(0) and v(0) = 1 to achieve the average (push-sum protocol [27]):”
BackgroundMethodInfluentialA survey of distributed optimization
Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., & Johansson, K. H. (2019) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2019.05.006 · Cited by 913
Gossip-based aggregation in large dynamic networks
Jelasity, M., Montresor, A., & Babaoğlu, Ö. (2005) · ACM Transactions on Computer Systems · doi:10.1145/1082469.1082470 · Cited by 800
Kashyap, A., Başar, T., & Srikant, R. (2007) · Automatica · doi:10.1016/j.automatica.2007.01.002 · Cited by 749
Gossip Algorithms for Distributed Signal Processing
Dimakis, A. G., Kar, S., Moura, J. M. F., Rabbat, M. G., & Scaglione, A. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2052531 · Cited by 741
Resilient Asymptotic Consensus in Robust Networks
LeBlanc, H. J., Zhang, H., Koutsoukos, X., & Sundaram, S. (2013) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2013.130413 · Cited by 730
Gossip Algorithms for Distributed Signal Processing
Dimakis, A. G., Kar, S., Moura, J. M. F., Rabbat, M., & Scaglione, A. (2018) · doi:10.1184/r1/6468842.v1 · Cited by 692
Time-varying graphs and dynamic networks
Casteigts, A., Flocchini, P., Quattrociocchi, W., & Santoro, N. (2012) · International Journal of Parallel, Emergent and Distributed Systems · doi:10.1080/17445760.2012.668546 · Cited by 592
Gossip algorithms: design, analysis and applications
Boyd, S., Ghosh, A., Prabbakar, B., & Shah, D. (2005) · Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. · doi:10.1109/infcom.2005.1498447 · Cited by 558
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization
Nedic, A., Olshevsky, A., & Rabbat, M. G. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2817461 · Cited by 534
Synopsis diffusion for robust aggregation in sensor networks
Nath, S., Gibbons, P. B., Seshan, S., & Anderson, Z. R. (2004) · Proceedings of the 2nd international conference on Embedded networked sensor systems · doi:10.1145/1031495.1031525 · Cited by 510
Jelasity, M., Voulgaris, S., Guerraoui, R., Kermarrec, A.-M., & van Steen, M. (2007) · ACM Transactions on Computer Systems · doi:10.1145/1275517.1275520 · Cited by 494
Broadcast Gossip Algorithms for Consensus
Aysal, T. C., Yildiz, M. E., Sarwate, A. D., & Scaglione, A. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2016247 · Cited by 480
Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches
Cormode, G., Garofalakis, M., Haas, P. J., & Jermaine, C. (2011) · Foundations and Trends in Databases · doi:10.1561/1900000004 · Cited by 468
Tutorial on Dynamic Average Consensus: The Problem, Its Applications, and the Algorithms
Kia, S. S., Scoy, B. V., Cortés, J., Freeman, R. A., Lynch, K., & Martínez, S. (2019) · IEEE Control Systems · doi:10.1109/mcs.2019.2900783 · Cited by 449
Adaptation, Learning, and Optimization over Networks
Sayed, A. (2014) · now publishers, Inc. eBooks · doi:10.1561/9781601988515 · Cited by 415
Distributed computation in dynamic networks
Kuhn, F., Lynch, N., & Oshman, R. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806760 · Cited by 400
Push–Pull Gradient Methods for Distributed Optimization in Networks
Pu, S., Shi, W., Xu, J., & Nedic, A. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2972824 · Cited by 376
Trust Computations and Trust Dynamics in Mobile Adhoc Networks: A Survey
Govindan, K., & Mohapatra, P. (2012) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2011.042711.00083 · Cited by 367
Why rumors spread so quickly in social networks
Doerr, B., Fouz, M., & Friedrich, T. (2012) · Communications of the ACM · doi:10.1145/2184319.2184338 · Cited by 357
Randomized consensus algorithms over large scale networks
Fagnani, F., & Zampieri, S. (2008) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2008.080506 · Cited by 350
1Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed GraphsPreprint
Nedić, A., & Olshevsky, A. (2016) · Cited by 316
Shah, D. (2009) · Foundations and Trends® in Networking · doi:10.1561/1300000014 · Cited by 313
Push-Sum Distributed Dual Averaging for convex optimization
Tsianos, K. I., Lawlor, S., & Rabbat, M. G. (2012) · 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6426375 · Cited by 304
Design patterns from biology for distributed computing
Babaoglu, O., Canright, G., Deutsch, A., Caro, G. A. D., Ducatelle, F., Gambardella, L. M., Ganguly, N., Jelasity, M., Montemanni, R., Montresor, A., et al. (2006) · ACM Transactions on Autonomous and Adaptive Systems · doi:10.1145/1152934.1152937 · Cited by 302
Distributed Optimization for Control
Nedić, A., & Liu, J. (2018) · Annual Review of Control, Robotics, and Autonomous Systems · doi:10.1146/annurev-control-060117-105131 · Cited by 302
The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-Based Implementations
Jelasity, M., Guerraoui, R., Kermarrec, A.-M., & van Steen, M. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30229-2_5 · Cited by 301
Decentralized Federated Learning: A Survey and Perspective
Yuan, L., Wang, Z., Sun, L., Yu, P. S., & Brinton, C. G. (2024) · IEEE Internet of Things Journal · doi:10.1109/jiot.2024.3407584 · Cited by 290
A Distributed Algorithm for Solving a Linear Algebraic Equation
Mou, S., Liu, J., & Morse, A. S. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2414771 · Cited by 284
(2007) · Advances in Database Systems · doi:10.1007/978-0-387-47534-9 · Cited by 282
Decentralized Deep Learning with Arbitrary Communication CompressionPreprint
Koloskova, A., Lin, T., Stich, S. U., & Jaggi, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.09356 · Cited by 271
A Distributed Algorithm for Economic Dispatch Over Time-Varying Directed Networks With Delays
Yang, T., Lu, J., Wu, D., Wu, J., Shi, G., Meng, Z., & Johansson, K. H. (2017) · IEEE Transactions on Industrial Electronics · doi:10.1109/tie.2016.2617832 · Cited by 264
Average consensus on general strongly connected digraphs
Cai, K., & Ishii, H. (2012) · Automatica · doi:10.1016/j.automatica.2012.08.003 · Cited by 263
Shah, D. (2009) · Cited by 262
Optimized stratified sampling for approximate query processing
Chaudhuri, S., Das, G., & Narasayya, V. R. (2007) · ACM Transactions on Database Systems · doi:10.1145/1242524.1242526 · Cited by 261
Moallemi, C. C., & Roy, B. V. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.883539 · Cited by 260
Efficient Coflow Scheduling Without Prior Knowledge
Chowdhury, M., & Stoica, I. (2015) · Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication · doi:10.1145/2785956.2787480 · Cited by 250
A Linear Algorithm for Optimization Over Directed Graphs With Geometric Convergence
Xin, R., & Khan, U. A. (2018) · IEEE Control Systems Letters · doi:10.1109/lcsys.2018.2834316 · Cited by 243
Cloudburst: stateful functions-as-a-service
Sreekanti, V., Wu, C., Lin, X. C., Schleier-Smith, J., Gonzalez, J. E., Hellerstein, J. M., & Tumanov, A. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3407790.3407836 · Cited by 237
Random walks in peer-to-peer networks: Algorithms and evaluation
Gkantsidis, C., Mihail, M., & Saberi, A. (2006) · Performance Evaluation · doi:10.1016/j.peva.2005.01.002 · Cited by 232
Tributaries and deltas: efficient and robust aggregation in sensor network streams
Manjhi, A., Nath, S., & Gibbons, P. B. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066191 · Cited by 230
Geographic Gossip: Efficient Averaging for Sensor Networks
Dimakis, A. G., Sarwate, A. D., & Wainwright, M. J. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2007.908946 · Cited by 226
How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
Avin, C., Koucký, M., & Lotker, Z. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70575-8_11 · Cited by 226
Weighted Gossip: Distributed Averaging using non-doubly stochastic matrices
Benezit, F., Blondel, V., Thiran, P., Tsitsiklis, J., & Vetterli, M. (2010) · 2010 IEEE International Symposium on Information Theory · doi:10.1109/isit.2010.5513273 · Cited by 224
Tsianos, K. I., Lawlor, S., & Rabbat, M. G. (2012) · 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2012.6483403 · Cited by 223
Toward a theory of in-network computation in wireless sensor networks
Giridhar, A., & Kumar, P. R. (2006) · IEEE Communications Magazine · doi:10.1109/mcom.2006.1632656 · Cited by 220
Distributed Data Mining in Peer-to-Peer Networks
Datta, S., Bhaduri, K., Giannella, C., Wolff, R., & Kargupta, H. (2006) · IEEE Internet Computing · doi:10.1109/mic.2006.74 · Cited by 217
Linear Convergence in Optimization Over Directed Graphs With Row-Stochastic Matrices
Xi, C., Mai, V. S., Xin, R., Abed, E. H., & Khan, U. A. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2797164 · Cited by 215
Convergence of Asynchronous Distributed Gradient Methods Over Stochastic Networks
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2730481 · Cited by 214
Nedic, A. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2975210 · Cited by 211
Distributed nonconvex constrained optimization over time-varying digraphs
Scutari, G., & Sun, Y. (2019) · Mathematical Programming · doi:10.1007/s10107-018-01357-w · Cited by 210
GossipTrust for Fast Reputation Aggregation in Peer-to-Peer Networks
Zhou, R., Hwang, K., & Cai, M. (2008) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2008.48 · Cited by 205
In-network outlier detection in wireless sensor networks
Branch, J. W., Giannella, C., Szymanski, B., Wolff, R., & Kargupta, H. (2013) · Knowledge and Information Systems · doi:10.1007/s10115-011-0474-5 · Cited by 204
Xin, R., & Khan, U. A. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2942513 · Cited by 201
Cloud control with distributed rate limiting
Raghavan, B., Vishwanath, K., Ramabhadran, S., Yocum, K., & Snoeren, A. C. (2007) · Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/1282380.1282419 · Cited by 196
Smart Gossip: An Adaptive Gossip-based Broadcasting Service for Sensor Networks
Kyasanur, P., Choudhury, R., & Gupta, I. (2006) · IEEE International Conference on Mobile Ad-Hoc and Sensor Systems (MASS) · doi:10.1109/mobhoc.2006.278671 · Cited by 195
A Survey of Distributed Data Aggregation Algorithms
Jesus, P., Baquero, C., & Almeida, P. S. (2015) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2014.2354398 · Cited by 193
Distributed Online Convex Optimization on Time-Varying Directed Graphs
Akbari, M., Gharesifard, B., & Linder, T. (2017) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2015.2505149 · Cited by 190
Computing separable functions via gossip
Mosk-Aoyama, D., & Shah, D. (2006) · Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing · doi:10.1145/1146381.1146401 · Cited by 190
Gossiping in distributed systems
Kermarrec, A.-M., & van Steen, M. (2007) · ACM SIGOPS Operating Systems Review · doi:10.1145/1317379.1317381 · Cited by 189
Caramanis, M., Ntakou, E., Hogan, W. W., Chakrabortty, A., & Schoene, J. (2016) · Proceedings of the IEEE · doi:10.1109/jproc.2016.2520758 · Cited by 188
StreetSmart Traffic: Discovering and Disseminating Automobile Congestion Using VANET's
Dornbush, S., & Joshi, A. (2007) · 2007 IEEE 65th Vehicular Technology Conference - VTC2007-Spring · doi:10.1109/vetecs.2007.15 · Cited by 187
In-Network Outlier Detection in Wireless Sensor Networks
Branch, J., Szymanski, B., Giannella, C., Wolff, R., & Kargupta, H. (2006) · 26th IEEE International Conference on Distributed Computing Systems (ICDCS'06) · doi:10.1109/icdcs.2006.49 · Cited by 186
Geographic gossip: efficient aggregation for sensor networks
Dimakis, A. G., Sarwate, A. D., & Wainwright, M. J. (2006) · Proceedings of the fifth international conference on Information processing in sensor networks - IPSN '06 · doi:10.1145/1127777.1127791 · Cited by 185
Distributed Subgradient Projection Algorithm Over Directed Graphs
Xi, C., & Khan, U. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2615066 · Cited by 185
On Nonconvex Decentralized Gradient Descent
Zeng, J., & Yin, W. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2818081 · Cited by 184
The promise, and limitations, of gossip protocols
Birman, K. (2007) · ACM SIGOPS Operating Systems Review · doi:10.1145/1317379.1317382 · Cited by 182
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
Nedić, A., & Olshevsky, A. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2529285 · Cited by 181
ADD-OPT: Accelerated Distributed Directed Optimization
Xi, C., Xin, R., & Khan, U. A. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2737582 · Cited by 181
Distributed Online Optimization for Multi-Agent Networks With Coupled Inequality Constraints
Li, X., Yi, X., & Xie, L. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3021011 · Cited by 180
A decentralized algorithm for spectral analysis
Kempe, D., & McSherry, F. (2008) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.04.014 · Cited by 180
Self-citationSnapshot Queries: Towards Data-Centric Sensor Networks
Kotidis, Y. (2005) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2005.134 · Cited by 177
Decentralized Optimization Over Time-Varying Directed Graphs With Row and Column-Stochastic Matrices
Saadatniaki, F., Xin, R., & Khan, U. A. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2969721 · Cited by 172
DEXTRA: A Fast Algorithm for Optimization Over Directed Graphs
Xi, C., & Khan, U. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2672698 · Cited by 172
Nash Equilibrium Computation in Subnetwork Zero-Sum Games With Switching Communications
Lou, Y., Hong, Y., Xie, L., Shi, G., & Johansson, K. H. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2504962 · Cited by 172
Non-Convex Distributed Optimization
Tatarenko, T., & Touri, B. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2648041 · Cited by 171
Bubblestorm: resilient, probabilistic, and exhaustive peer-to-peer search
Terpstra, W. W., Kangasharju, J., Leng, C., & Buchmann, A. (2007) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/1282380.1282387 · Cited by 170
Average Consensus in the Presence of Delays in Directed Graph Topologies
Hadjicostis, C. N., & Charalambous, T. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2013.2275669 · Cited by 169
Fast Distributed Algorithms for Computing Separable Functions
Mosk-Aoyama, D., & Shah, D. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.924648 · Cited by 169
Description and composition of bio-inspired design patterns: a complete overview
Fernandez-Marquez, J. L., Di Marzo Serugendo, G., Montagna, S., Viroli, M., & Arcos, J. L. (2013) · Natural Computing · doi:10.1007/s11047-012-9324-y · Cited by 168
Decentralized compression and predistribution via randomized gossiping
Rabbat, M., Haupt, J., Singh, A., & Nowak, R. (2006) · Proceedings of the fifth international conference on Information processing in sensor networks - IPSN '06 · doi:10.1145/1127777.1127789 · Cited by 165
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
Koloskova, A., Stich, S. U., & Jaggi, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.00340 · Cited by 163
Decentralized learning works: An empirical comparison of gossip learning and federated learning
Hegedűs, I., Danner, G., & Jelasity, M. (2021) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2020.10.006 · Cited by 162
Decentralized federated learning through proxy model sharing
Kalra, S., Wen, J., Cresswell, J. C., Volkovs, M., & Tizhoosh, H. R. (2023) · Nature Communications · doi:10.1038/s41467-023-38569-4 · Cited by 160
Privacy-Preserving Distributed Averaging via Homomorphically Encrypted Ratio Consensus
Hadjicostis, C. N., & Dominguez-Garcia, A. D. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2968876 · Cited by 159
Majority dynamics and aggregation of information in social networks
Mossel, E., Neeman, J., & Tamuz, O. (2013) · Autonomous Agents and Multi-Agent Systems · doi:10.1007/s10458-013-9230-4 · Cited by 159
Approximate Distributed K-Means Clustering over a Peer-to-Peer Network
Datta, S., Giannella, C. R., & Kargupta, H. (2008) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2008.222 · Cited by 158
Distributed Clustering of Linear Bandits in Peer to Peer NetworksPreprint
Korda, N., Szörényi, B., & Li, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1604.07706 · Cited by 157
Convergence Rates of Distributed Average Consensus With Stochastic Link Failures
Patterson, S., Bamieh, B. A., & Abbadi, A. E. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2041998 · Cited by 153
Zhang, R., Liu, G., Liu, Y., Zhao, C., Wang, J., Xu, Y., Niyato, D. T., Kang, J., Li, Y., Mao, S., et al. (2026) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2026.3651702 · Cited by 152
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., & Stich, S. U. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.10422 · Cited by 151
Stabilizing consensus with the power of two choices
Doerr, B., Goldberg, L. A., Minder, L., Sauerwald, T., & Scheideler, C. (2011) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1989493.1989516 · Cited by 150
A General Framework for Decentralized Optimization With First-Order Methods
Xin, R., Pu, S., Nedić, A., & Khan, U. A. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3024266 · Cited by 149
A Methodology for Formalizing Model-Inversion Attacks
Wu, X., Fredrikson, M., Jha, S., & Naughton, J. F. (2016) · 2016 IEEE 29th Computer Security Foundations Symposium (CSF) · doi:10.1109/csf.2016.32 · Cited by 147
Asynchronous Distributed Averaging on Communication Networks
Mehyar, M., Spanos, D. P., Pongsajapan, J., Low, S. H., & Murray, R. M. (2007) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2007.893226 · Cited by 146
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.