Gossip-based computation of aggregate information

By David Kempe, Alin Dobra, Johannes Gehrke. 2003

1,713 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics, Algorithms & Complexity, Network Science & Complex Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

In Algorithms & Complexity

In Network Science & Complex Systems

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “For instance the push-sum algorithm (Kempe et al., 2003), based on the intuition of mixing in Markov chains and allowing for asymmetric communication, or the symmetric randomized gossip protocol for averaging over arbirary graphs (Xiao & Boyd, 2004; Boyd et al., 2006) that we follow closely in this…”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, background): “We here in particular focus on approached based on gossip averaging (Kempe et al., 2003; Xiao and Boyd, 2004; Boyd et al., 2006) whose convergence rate typically depends on the spectral gap ρ ≥ 0 of the mixing matrix (Xiao and Boyd, 2004).”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “Gossip-type algorithms converge linearly for average consensus (Kempe et al., 2003; Xiao & Boyd, 2004; OlfatiSaber & Murray, 2004; Boyd et al., 2006).”
Stochastic Gradient Push for Distributed Deep Learning (2018, background): “State-of-the-art consensus optimization methods build on the PUSHSUM algorithm for approximate distributed averaging [6, 11], which allows for non-blocking, time-varying, and directed (asymmetric) communication.”
Decentralized Collaborative Learning of Personalized Models over Networks (2016, methodology): “Several peer-to-peer algorithms have been developed for decentralized averaging (Kempe et al., 2003; Boyd et al., 2006; Colin et al., 2015) and optimization (Nedic and Ozdaglar, 2009; Ram et al., 2010; Duchi et al., 2012; Wei and Ozdaglar, 2012, 2013; Iutzeler et al., 2013; Colin et al., 2016).”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, neutral): “In contrast, gossip algorithms (Tsitsiklis, 1984; Boyd et al., 2006; Kempe et al., 2003; Shah, 2009) are tailored to this setting because they only rely on simple peer-to-peer communication: each agent only exchanges information with one neighbor at a time.”
How to scale distributed deep learning? (2016, methodology): “Push-gossiping SGD can be interpreted as an interleaving of a gradient step and a simplified push-sum gossip step [16].”
Distributed optimization over time-varying directed graphs (2013, methodology): “We refer the reader to [7], [3], [1] for more details.”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “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]):”
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs (2014, background): “Our starting point is an analysis of a perturbation of the so-called push-sum protocol of [17] for computing averages in directed networks.”
On Nonconvex Decentralized Gradient Descent (2016, methodology): “Remark 3: A related algorithm is the perturbed push-sum algorithm, also called subgradient-push, which was proposed in [25] for average consensus problem over time-varying network.”
Toward a theory of in-network computation in wireless sensor networks (2006, background): “It is further shown in [13] that the above push algorithm requires”
Distributed Online Convex Optimization on Time-Varying Directed Graphs (2017, methodology): “DISTRIBUTED ONLINE SUBGRADIENT PUSH-SUM ALGORITHM In this section, we introduce a distributed online subgradient push-sum algorithm motivated by [23], [25], which allows the agents to have a sublinear average individual regret.”
Randomized consensus algorithms over large scale networks (2007, background): “On the other hand random linear schemes have been studied for instance in [5], [21], [9] under the name of gossip algorithms.”
Clique Gossiping (2017, background): “For random gossip algorithms, various results reveal that the network structure plays a critical role in shaping the convergence speed in the asymptotic sense [16], [21], [22].”
Consensus and Cooperation in Networked Multi-Agent Systems (2007, background): “To understand the role of cooperation in performing coordinated tasks, we need to distinguish between unconstrained and constrained consensus problems.”
Hiding in the Crowd: A Massively Distributed Algorithm for Private Averaging with Malicious Adversaries (2018, background): “The problem of computing the average value X avg of a set of users in a fully decentralized network without a central coordinator has been extensively studied (see for instance Tsitsiklis, 1984; Kempe et al., 2003; Boyd et al., 2006).”