Convergence Speed in Distributed Consensus and Averaging

By Alexander Olshevsky, John N. Tsitsiklis. 2009

744 citations recorded by the source corpus.

We study the convergence speed of distributed iterative algorithms for the consensus and averaging problems, with emphasis on the latter. We first consider the case of a fixed communication topology. We show that a simple adaptation of a consensus algorithm leads to an averaging algorithm. We prove lower bounds on the worst-case convergence time for various classes of linear, time-invariant, distributed consensus methods, and provide an algorithm that essentially matches those lower bounds. We then consider the case of a time-varying topology, and provide a polynomial-time averaging algorithm.

Subfields: Artificial Intelligence, 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 Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination (2012, methodology): “Other than the smallest nonzero eigenvalue of the Laplacian m trix, another commonly used measure for the convergence speed is the following ratio, introduce d in [156], [157]:”
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization (2008, neutral): “The work in this paper is also related at a much broader level to the distributed consensus algorithms [7, 20–29].”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, background): “s and cooperative control, where the goal is to design local deterministic 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 ”
Distributed subgradient methods and quantization effects (2008, background): “Closely related is also the work in [10] and [7], [6], which study the effects of quantization on the performance of averaging algorithms.”
Accelerated Distributed Nesterov Gradient Descent (2017, background): “As a result, ∃σ ∈ (0, 1) being the second largest singular value of W , such that for any ω ∈ Rn×1 , we have the “averaging property,” ‖Wω − 1ω̄‖ ≤ σ‖ω − 1ω̄‖ where ω̄ = 1 n 1 ω (the average of the entries in ω) [22].”
On the Convergence Time of Asynchronous Distributed Quantized Averaging Algorithms (2010, methodology): “Here, we assume that the communication graph be undirected and satisfies the following connectivity assumption also used in [3], [11], [14], [16].”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, neutral): “See also [15, 4, 64, 29, 30].”
Distributed Subgradient Methods for Convex Optimization Over Random Networks (2011, background): “[6], Olshevsky and Tsitsiklis [17], [18], and Nedić et al.”
Distributed stochastic optimization for deep learning (thesis) (2016, neutral): “nceptually decentralized. It is based on the idea of consensus averaging [57]. A classical problem is to compute the average value of the local clocks in a sensor network (aka. clock synchronization) [41]. In such setting, one needs to consider how to optimize the design of the averaging network [59”
Convergence Speed of Unsteady Distributed Consensus: Decay Estimate Along the Settling Spanning-Trees (2006, methodology): “To the best of our knowledge, previous results are centrally based on the existence of a lower bound of the nonzero entries associated to such matrices, and most of them on the existence of self-loops, see [9] and the surveys in [6, 29] (see however the contributions in [31, 32] where the assumption”
Distributed dual averaging for convex optimization under communication delays (2012, methodology): “1This re-weighting trick is also used in the agreement algorithm [10] for average consensus with non-doubly stochastic matrices.”
On distributed averaging algorithms and quantization effects (2007, background): “on optimal time-invariant algorithms may be found in [13].”
Asynchronous Gossip-Based Random Projection Algorithms Over Networks (2013, background): “On a broader scale, the work in this paper is related to the literature on the consensus prob lem (see for example [8], [10], [18]).”
Discrete-time dynamic average consensus (2010, background): “Key words: Consensus algorithms, multi-agent systems, cooperative control”