Gossip consensus algorithms via quantized communication
By Ruggero Carli, Fabio Fagnani, Paolo Frasca, Sandro Zampieri. 2009
238 citations recorded by the source corpus.
This paper considers the average consensus problem on a network of digital links, and proposes a set of algorithms based on pairwise ''gossip'' communications and updates. We study the convergence properties of such algorithms with the goal of answering two design questions, arising from the literature: whether the agents should encode their communication by a deterministic or a randomized quantizer, and whether they should use, and how, exact information regarding their own states in the update.
Subfields: Computer Networks and Communications, Management Science and Operations Research, 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
- Ji Liu
- Ce Zhang
- Martin Jaggi
- Sebastian U. Stich
- Xiangru Lian
- Anastasia Koloskova
- Javad Lavaei
- Tao Lin
In Management Science and Operations Research
In Algorithms & Complexity
- Richard M. Murray
- Tao Lin
- Javad Lavaei
- Ce Zhang
- Cho-Jui Hsieh
- Sebastian U. Stich
- Tamer Basar
- Martin Jaggi
In Network Science & Complex Systems
- Ce Zhang
- Xiangru Lian
- Ji Liu
- Javad Lavaei
- Richard M. Murray
- Sebastian U. Stich
- Martin Jaggi
- Anastasia Koloskova
Citations in the corpus
- Decentralized Deep Learning with Arbitrary Communication Compression (2019, background): “It has been observed that gossip averaging can diverge (or not converge to the correct solution) in the presence of quantization noise (Xiao et al., 2005; Carli et al., 2007; Nedić et al., 2008; Dimakis et al., 2010; Carli et al., 2010b; Yuan et al., 2012).”
- Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, methodology): “The proposed schemes in (Carli et al., 2007; Nedi´c et al., 2008; Aysal et al., 2008; Carli et al., 2010b; Yuan et al., 2012) do only converge to a neighborhood (whose size depends on the compression accuracy) of the solution.”
- 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, background): “…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].”
- An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination (2012, neutral): “Furth er results regarding quantized consensus were reported in [ 147]–[154], where the main research was also on studying the convergen ce time for various proposed quantized consensus algorithms as well as the quantization effects on the convergence time.”
- Design and analysis of distributed averaging with quantized communication (2014, background): “These quantizers are defined as follows [8], [25]:”
- Discontinuities and hysteresis in quantized average consensus (2010, unknown): “Moreover, quantization has been considered also in gossip consensus algorithms [16,6].”
- Quantized Consensus by Means of Gossip Algorithm (2012, background): “First, it is shown that a quantized consensus is reached under the stochastic gossip algorithm proposed in [20] and [21], for a wide range of updating parameters and an arbitrary quantizer.”