Randomized consensus algorithms over large scale networks

By Fabio Fagnani, Sandro Zampieri. 2007

383 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Networks and Communications

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): “…there are work on the consensus problem for which decentralized algorithms are studied 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].”
Gossip consensus algorithms via quantized communication (2009, background): “From [5], we know that in the case of no quantization the system converges almost surely to consensus.”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, background): “eterministic or random update rules to achieve global coordination (for deterministic update rules, see [4], [7], [15], [23], [27], [38], [39], [40], [44]; for random update rules, see [1], [5], [9], [14]). August 1, 2013 DRAFT 5 methods typically have a convergence rate of O(1/ √ k). The more recen”
Broadcast Gossip Algorithms for Consensus (2009, background): “Probabilistic concentration results on a general class of such random consensus algorithms can be found in [28] and some results reported here to make the paper self-contained can be derived as special cases.”
Gossip Algorithms for Distributed Signal Processing (2010, methodology): “:: ( P kx(t) xave~1k kx(0)k ! ) : (7) Observe that the convergence time is deﬁned for the worst case over the initial vector of measurements x(0). This deﬁnition was ﬁrst used in [25] (see also [31] for a related analysis). DIMAKIS ET AL.: GOSSIP ALGORITHMS FOR DISTRIBUTED SIGNAL PROCESSING 6 The ”
Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate (2014, neutral): “, [13], [14], [15], [16], [17], [37], [38], [39], [41].”
Consensus Over Ergodic Stationary Graph Processes (2010, background): “[ 8 ] F. Chyzak, A. Quadrat, and D. Robertz, “Effective algorithms for”
A tutorial on modeling and analysis of dynamic social networks. Part I (2017, background): “statement of Lemma 20 and the implication (a)=⇒(b) has been established in [188] under the additional assumption that W(k) have strictly positive diagonal; the latter assumption can also be discarded [177] (formally, [177] establishes the implication (a)=⇒(b) only for the case of irreducible W¯ , bu”
Decentralized Consensus Optimization With Asynchrony and Delays (2016, background): “Gossip [15], [16] Reduced No Yes Average Consensus Yes Randomized Consensus [17], [18] Reduced No Yes Average Consensus Yes Randomized DGD [19], [26] Reduced No Yes Aggregate Optimization No Asynchronous Diffusion [27]–[29] Reduced No Yes Aggregate stochastic Optimization No Randomized ADMM [20], [2”
Decentralized consensus optimization with asynchrony and delays (2016, background): “Likewise, our setting is different from randomized multi-activation such as [17], [18] for consensus averaging, and [19]–[22] for consensus optimization, which activate multiple edges each time and still do not allow any delay.”
Heterophilious Dynamics Enhances Consensus (2013, methodology): “Classified by the tools of the trade, we mention statistical mechanics [10, 23, 101], clustering and spectral theory of graphs [15, 31, 32, 70, 90], optimization and control [39, 43, 44, 71, 72, 91, 112], game theory [5, 65], jump processes, nonlinear Markov chains, and stochastic analysis [15, 52, ”
Opinion Fluctuations and Disagreement in Social Networks (2010, neutral): “Our work is also related to work on consensus and gossip algorithms, which is motivated by diﬀerent problems, but typically leads to a similar mathematical formulation (Tsitsiklis [48], Tsit-siklis, Bertsekas and Athans [49], Jadbabaie, Lin and Morse [28], Olfati-Saber and Murray [42], Olshevsky and”
Distributed Asynchronous Constrained Stochastic Optimization (2011, background): “Another relevant paper which considers the unconstrained random network model for consensus is [29].”