Distributed Average Consensus using Quantized ADMM: Bounded Quantizers with Unbounded Inputs

Shengyu Zhu, Biao Chen

Abstract

This paper considers distributed average consensus with bounded quantization of finite bits based on the alternating direction method of multipliers (ADMM). We do not assume any bound on the agents' data and develop a distributed averaging algorithm by modifying a distributed ADMM algorithm with bounded quantizers. It is shown that all the agent variables converge to the same quantization point within approximately $\log_{1+\eta}\Omega$ iterations where $\eta>0$ is decided by the ADMM parameter that can be any positive number and the network topology, and $\Omega$ is a polynomial fraction depending on the quantization resolution, the agents' data, the ADMM parameter and the network topology. Furthermore, iteratively running the proposed algorithm results in the same consensus error bound as using the unbounded rounding quantizer. We also study the effect of the ADMM parameter on the performance of the algorithm and propose an empirical selection using only the number of nodes and the number of edges. Simulation validates the good performance of our parameter selection.

Introduction

In distributed systems such as wireless sensor networks and mobile ad-hoc networks, agents must often agree on a common value—typically the average of their local measurements—using only local communication with their neighbors. This process, known as distributed average consensus, is fundamental to decentralized estimation and control. However, real-world implementations face two significant constraints: limited communication bandwidth requiring finite-bit quantization, and the unpredictable range of initial data.

While existing literature often assumes "infinite-rate" quantizers with an infinite range, physical hardware is inherently limited to a finite number of bits. Furthermore, most algorithms that accommodate finite bits require prior knowledge of the data's maximum possible value to set the quantizer's range. This paper addresses these gaps by proposing a robust ADMM-based framework that handles bounded quantization even when the input data is completely unbounded.

The Challenge of Bounded Quantization

Standard quantized consensus algorithms often fail when the true average of the network falls outside the predefined range of the quantizer (saturation). If the quantizer's "box" is too small, the algorithm may provide massive errors or fail to converge. Conversely, if the box is too large to accommodate all possible data, the quantization resolution (the distance between levels) becomes too coarse, leading to poor accuracy. The goal is to achieve an accurate average consensus using only a few bits of communication without knowing the data's range in advance.

Methodology: BQ-CADMM and EBQ-CADMM

The authors propose two primary algorithms based on Consensus ADMM (CADMM):

1. Bounded Quantized CADMM (BQ-CADMM)

This algorithm modifies the standard ADMM update by incorporating a bounded quantizer. The quantizer first projects a value onto a compact convex set (a "box" defined by $[-L, L]$) and then rounds it to the nearest quantization level. A key theoretical contribution of this work is the proof that BQ-CADMM is mathematically equivalent to solving a constrained least-squares problem. This allows the use of convex optimization theory to prove that even though the inputs are unbounded and the quantizer can saturate, the internal agent variables remain finitely bounded throughout the process.

2. Extended BQ-CADMM (EBQ-CADMM)

If the true average lies outside the quantizer's initial range, BQ-CADMM will converge to a value at the boundary of the box. To solve this, the Extended version runs BQ-CADMM iteratively. After each run, it "shifts" the agents' data based on the previous result, effectively moving the quantizer's focus. This multi-stage refinement allows the network to "find" the true average regardless of its initial distance from the quantizer's range, similar to adjusting a scale to weigh an item that is initially off-scale.

Theoretical Insights and Convergence

The paper provides several critical insights into the performance of these algorithms:

  • Convergence Rate: The algorithm converges to a consensus point within approximately $\log_{1+\eta} \Omega$ iterations. This logarithmic convergence represents a significant speedup over previous non-linear distributed consensus (NLC) methods, which can be prohibitively slow when data values are large.
  • Error Independence: Remarkably, the consensus error bound for BQ-CADMM does not depend on the size of the network or the magnitude of the agents' data. It is primarily determined by the quantization resolution ($\Delta$) and the ADMM tuning parameter ($\rho$). Specifically, the error bound is shown to be $(1/2 + \rho \frac{2E}{N})\Delta$.
  • Parameter Selection: To simplify deployment, the authors propose a heuristic for choosing the ADMM parameter: $\rho \approx \theta \frac{N}{E}$. This selection requires only basic knowledge of the network topology (number of nodes $N$ and edges $E$) rather than complex spectral properties.

Simulation Results

The algorithms were evaluated using synthetic simulations on connected graphs. In one scenario involving a 50-node network with a true average of 44.20, the EBQ-CADMM reached a consensus of 44.00 in just two iterative calls (approximately 50 total iterations). This validates that the algorithm can achieve high accuracy within the expected quantization error even when the initial data is far outside the quantizer's range.

Conclusion

This research provides a practical and theoretically sound approach to distributed consensus under strict communication constraints. By integrating bounded quantizers into the ADMM framework and employing an iterative shifting strategy, the proposed algorithms overcome the limitations of unknown data ranges. Future work will focus on extending these methods to asynchronous protocols, handling link failures, and accounting for noisy communication channels where bit errors may occur during transmission.

Summary updated

Abstract

This paper considers distributed average consensus with bounded quantization of finite bits based on the alternating direction method of multipliers (ADMM). We do not assume any bound on the agents' data and develop a distributed averaging algorithm by modifying a distributed ADMM algorithm with bounded quantizers. It is shown that all the agent variables converge to the same quantization point within approximately $\log_{1+\eta}\Omega$ iterations where $\eta>0$ is decided by the ADMM parameter that can be any positive number and the network topology, and $\Omega$ is a polynomial fraction depending on the quantization resolution, the agents' data, the ADMM parameter and the network topology. Furthermore, iteratively running the proposed algorithm results in the same consensus error bound as using the unbounded rounding quantizer. We also study the effect of the ADMM parameter on the performance of the algorithm and propose an empirical selection using only the number of nodes and the number of edges. Simulation validates the good performance of our parameter selection.
BibTeX
@misc{zhu2016distributed,
  author = {Shengyu Zhu and Biao Chen},
  title = {{Distributed Average Consensus using Quantized ADMM: Bounded Quantizers with Unbounded Inputs}},
  year = {2016},
  eprint = {1602.04193},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1602.04193},
}
Figure