Gossip algorithms: design, analysis and applications

By Stephen P. Boyd, Arpita Ghosh, Balaji Prabhakar, Devavrat Shah. 2005

625 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

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

Citations in the corpus

Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “…studied by the control community for solving the consensus problem where the goal is to compute the mean of all the data distributed on multiple nodes [Aysal et al., 2009, Boyd et al., 2005, Carli et al., 2010, Fagnani and Zampieri, 2008, Olfati-Saber et al., 2007, Schenato and Gamba, 2007].”
Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “SGD is closely related to online learning algorithms, for example, Crammer et al. [2006], Shalev-Shwartz [2011], Yang et al. [2014]. For SGD on nonconvex optimization, an ergodic convergence rate of O(1/ √ K) is proved in Ghadimi and Lan [2013].”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, methodology): “Consensus algorithms implemented in a network using a gossip-based or a broadcast-based communications have been studied in [61]–[64], while a different consensus algorithm (so called push-sum method) have been considered in [44], [45].”
Demystifying Parallel and Distributed Deep Learning (2018, methodology): “ever, performing the parameter exchange cannot use the allreduce operation, as it incurs global synchronization. One approach to inconsistent decentralized parameter update is to use Gossip Algorithms[24], in which each node communicates with a fixed number of random nodes (typically in the order of”
Distributed subgradient methods and quantization effects (2008, background): “es of the agents, a subject motivated by natural models of cooperative behavior in 1For subgradient methods see, for example, [19], [21], [20], [8], [1], [2]. networked-systems (see, e.g., [25], [9], [4], [16], [5], and [17], [18]). Closely related is also the work in [10] and [7], [6], which study ”
Distributed Subgradient Methods for Multi-Agent Optimization (2009, background): “[6], Olfati-Saber and Murray [7], Cao et al.”
Distributed Kalman filtering for sensor networks (2007, background): “These algorithms are closely related to gossip-based algorithms in computer science literature [9], [4].”
Distributed Network Optimization With Heuristic Rational Agents (2012, methodology): “We proceed to describe how voter models [19], [20] used to study the propagation of opinions in social networks can be interpreted as a heuristic rational version of local averaging models [16], [22] (Section II-A).”
Decentralized Control of Connectivity for Multi-Agent Systems (2006, methodology): “However, contrary to [13], the supergradient cannot modify directly the entries of the Laplacian matrix, because in our framework the Laplacian is a state dependent matrix.”
Spread of (mis)information in social networks (2009, background): “(a) The kth power of the transition matrix T , T k, converges to a stochastic matrix T∞ with all rows equal to the probability vector π, i.e., lim k→∞ T k = T∞ = eπ′, where e is the n-dimensional vector of all ones.”
All your contacts are belong to us: automated identity theft attacks on social networks (2009, positive): “The key insight used in both approaches is that real-world social networks are fast mixing [15, 18] that aids to distinguish the sybil nodes from normal nodes.”
A Gossip-Based Algorithm for Discrete Consensus Over Heterogeneous Networks (2010, background): “Our goal is that of determining, using consensus algorithms based on gossip [8], [16], the solution that minimizes the maximum execution time over nodes.”
Consensus-Before-Talk: Distributed Dynamic Spectrum Access via Distributed Spectrum Ledger Technology (2018, methodology): “For the SAT dissemination, we consider a push gossip algorithm [29], where the SAT is transmitted to a randomly chosen target user, regardless of whether the target user has already received the SAT or not.”
Maximizing throughput in wireless networks via gossiping (2006, methodology): “The above algorithm is an adaptation of gossip algorithm of [4].”
A decentralized algorithm for spectral analysis (2004, methodology): “In recent work, Boyd et al. [20, 21 ] have made this connection even more explicit, showing that the two are essentially identical under additional assumptions.”