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