Distributed Quantized Weight-Balancing and Average Consensus Over Digraphs

By Chang-Shen Lee, Nicolò Michelusi, Gesualdo Scutari. 2018

6 citations recorded by the source corpus.

This paper studies distributed quantized weight-balancing and average consensus over fixed digraphs. A digraph with non-negative weights associated to its edges is weight-balanced if, for each node, the sum of the weights of its outgoing edges is equal to that of its incoming edges. We propose and analyze the first distributed algorithm that solves the weight-balancing problem using only quantized (one-bit) information among nodes and simplex communications (compliant to the directed nature of the graph edges). Asymptotic convergence of the scheme is proved and a convergence rate analysis is provided. Building on this result, a novel distributed algorithm is proposed that solves the average consensus problem over digraphs, using, at each iteration, only two-bit simplex communications between adjacent nodes – one bit for the weight-balancing problem, the other for the average consensus. Convergence to the average of the real (i.e., unquantized) node's initial values is proved, both almost surely and in mean square sense. Finally, numerical results validate our theoretical findings.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

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 Electrical and Electronic Engineering

Citations in the corpus

Robust and Communication-Efficient Collaborative Learning (2019, methodology): “…decentralized optimization method with quantized messages was given in (Reisizadeh et al., 2018; Zhang et al., 2018), and more recently, new techniques have been developed in this context for convex problems (Doan et al., 2018; Koloskova et al., 2019; Berahas et al., 2019; Lee et al., 2018a,b).”
Finite Rate Quantized Distributed optimization with Geometric Convergence (2018, background): “While distributed average consensus problems using quantized communications have been extensively studied in the literature–examples are [10]–[12]–distributed optimization algorithms along with their rate guarantees in the presence of quantized communications are less understood.”