Distributed Average Consensus with Bounded Quantizer and Unbounded Input

Shengyu Zhu, Biao Chen

Abstract

In distributed systems such as sensor networks or autonomous swarms, achieving a consensus on the average of local measurements is a fundamental requirement. While traditional algorithms often assume infinite precision for communication, real-world hardware is constrained by finite bandwidth and limited power. This paper investigates distributed average consensus using finite-bit bounded quantizers, even when the underlying data is potentially unbounded. By leveraging the Alternating Direction Method of Multipliers (ADMM) framework, we propose algorithms where nodes reach consensus or enter predictable cycles using only local information and quantized outputs. We establish error bounds and propose adaptive parameter strategies to optimize convergence speed and accuracy.

Introduction

Distributed average consensus is the process by which a network of agents reaches an agreement on the mean value of their initial private data. In practical deployments, communication occurs over digital channels with finite capacity, necessitating the quantization of exchanged messages. Most existing literature assumes either an infinite number of quantization levels (unbounded quantizers) or that the input data is strictly confined within a known range (bounded input).

However, in many physical applications, data can be intrinsically unbounded—for instance, sensor readings affected by heavy-tailed noise or Gaussian spikes. If a standard bounded quantizer is used, data exceeding the quantization range is "clipped," which typically introduces significant bias. This paper addresses the challenge of achieving accurate consensus using a fixed, finite-bit budget even when the data average may lie outside the initial quantizer range.

Methodology: BQ-CADMM and EBQ-CADMM

BQ-CADMM (Bounded Quantizer CADMM)

The core of the proposed approach is the Bounded Quantizer Consensus Alternating Direction Method of Multipliers (BQ-CADMM). In this framework, each node maintains a local variable that it projects onto a compact convex set (the bounded range) before rounding it to the nearest quantization level.

Mathematically, the authors demonstrate that BQ-CADMM is equivalent to solving a constrained least-squares problem. This equivalence is vital because it allows the application of convex optimization theory to prove that the system will not diverge. Instead, because the quantizer has a finite number of states, the system is guaranteed to reach a steady state or a periodic cycle within finite time.

EBQ-CADMM (Extended BQ-CADMM)

To handle scenarios where the true global average is significantly outside the quantizer’s representable range, the authors introduce an iterative "shifting" mechanism called EBQ-CADMM. If nodes reach a consensus at the boundary of their range, they treat this value as a baseline, subtract it from their local measurements, and re-run the algorithm on the remainder. This effectively allows the network to "walk" toward the true average through successive approximations.

Theoretical Insights

Convergence and Cycling

A unique finding of this research is the behavior of nodes under finite-bit constraints. The authors prove that agents will either converge to the same quantization level or enter a cycle between adjacent levels. Interestingly, the time-average of these cycles provides a highly accurate estimate of the true data average.

Error Bounds

One of the most significant theoretical contributions is the proof that the error bound for BQ-CADMM is identical to that of an unbounded rounding quantizer, provided the ADMM step size ($\rho$) is sufficiently small. This suggests that the "clipping" effect of a bounded quantizer does not necessarily degrade the final consensus accuracy compared to more resource-intensive quantization methods.

Parameter Selection and Performance

The performance of ADMM-based algorithms is highly sensitive to the penalty parameter $\rho$. The authors propose a heuristic selection strategy: $$\rho = \frac{n}{m}$$ where $n$ is the number of nodes and $m$ is the number of edges in the network.

In numerical simulations across various topologies—including star, random, and complete graphs—this strategy allowed the network to reach consensus in approximately 10 iterations. The simulations confirmed that the consensus error remains independent of the network size and the magnitude of the initial data, validating the robustness of the EBQ-CADMM approach for unbounded inputs.

Conclusion

This work provides a robust framework for distributed consensus in resource-constrained environments. By combining ADMM with bounded quantization, the proposed algorithms offer a practical solution for networks where communication bits are at a premium and data ranges are unpredictable. Future research directions include extending these proofs to dynamic networks with link failures and investigating the impact of additive communication noise on the stability of the quantization cycles.

Summary updated

Abstract

This paper considers distributed average consensus using finite-bit bounded quantizer with possibly unbounded data. Under the framework of the alternating direction method of multipliers (ADMM), we develop distributed averaging algorithms where each node iteratively updates using only the local information and finitely quantized outputs from its neighbors. It is shown that all the agent variables either converge to the same quantization level or cycle around the data average after finite iterations. An error bound for the consensus value is established, which turns out to be the same as that of using the unbounded rounding quantizer provided that an algorithm parameter (i.e., ADMM step size) is small enough. We also analyze the effect of the algorithm parameter and propose an adaptive parameter selection strategy that only requires knowledge of the number of agents in order to accelerate the algorithm with certain consensus accuracy guarantee. Finally, simulations are performed to illustrate the effectiveness of the proposed algorithms.
BibTeX
@misc{zhu2016distributed,
  author = {Shengyu Zhu and Biao Chen},
  title = {{Distributed Average Consensus with Bounded Quantizer and Unbounded Input}},
  year = {2016},
  eprint = {1602.04193},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1602.04193},
}
Figure