Average Consensus with Dynamic Quantization Framing and Finite-Time Termination over Limited-Bandwidth Directed Networks

Evagoras Makridis, Gabriele Oliva, Apostolos I. Rikos, Themistoklis Charalambous · 2025

Read Average Consensus with Dynamic Quantization Framing and Finite-Time Termination over Limited-Bandwidth Directed Networks by Evagoras Makridis, Gabriele Oliva, Apostolos I. Rikos, Themistoklis Charalambous (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-24700.txt.

Introduction

Evagoras Makridis, Gabriele Oliva, Apostolos Rikos, and Themistoklis Charalambous design a distributed algorithm that lets a network of agents agree on their exact average while sending only a few bits per message. Directed links may be unbalanced, which makes averaging hard. Their method mixes push-pull consensus dynamics with a moving quantization frame that zooms and shifts.

Agents keep the true average while steadily refining precision, and a shared stopping rule ends the process in finite time once they are close enough. Proofs cover strongly connected directed graphs. Readers in control and networks get exact averaging under strict bandwidth limits, with formal guarantees.

Catalog record

CREATOREvagoras Makridis, Gabriele Oliva, Apostolos I. Rikos, Themistoklis Charalambous
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-24700

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Average Consensus with Dynamic Quantization Framing and Finite-Time Termination over Limited-Bandwidth Directed Networks Evagoras Makridis, Gabriele Oliva, Apostolos I. Rikos, Themistoklis Charalambous Abstract This paper proposes a deterministic distributed algorithm, referred to as pp-acdc , that achieves exact average consensus over possibly unbalanced directed graphs using only a fixed and a priori specified number of quantization bits. The method integrates Push–Pull (surplus) consensus dynamics with a dynamic quantization framing scheme combining zooming and midpoint shifting, enabling agents to preserve the true global average while progressively refining their quantization precision. We establish a rigorous convergence theory showing that pp-acdc achieves asymptotic (exact) average consensus on any strongly connected digraph under appropriately chosen quantization parameters. Moreover, we develop a fully distributed and synchronized finite-time termination mechanism, and we provide a formal proof on the detection of ϵ \epsilon -convergence to the average within a finite number of iterations. Numerical simulations corroborate the theoretical results and demonstrate that pp-acdc achieves reliable, communication-efficient, and precise average consensus even under very tight bit budgets, underscoring its suitability for large-scale and resource-constrained multi-agent systems operating over directed networks. K eywords quantized average consensus, finite-rate communication, dynamic framing, directed graphs, surplus consensus, finite-time termination 1 Introduction Distributed consensus algorithms are essential components of modern applications that involve the cooperation of a group of networked agents (often referred to as multi-agent systems ) such as robotic networks, distributed power networks, and wireless sensor networks. Some of these applications include distributed optimization [ 6 , 26 ] , distributed estimation and control [ 25 , 13 ] , and distributed learning [ 2 ] . In such problems, the agents in a network aim at reaching agreement on a common decision by iteratively updating their values based on information received by their immediate neighbors via information exchange. When the agreed common value is the average of the initial values of all agents in the network, we say that the agents reach average consensus . Although there exist several average consensus schemes considering network abnormalities (such as packet delays [ 17 , 7 ] or drops [ 18 , 23 ] ) and malfunctioning agents (e.g., curious, malicious, or faulty agents) [ 8 ] , they require agents to be able to send and receive real values with infinite precision. In multi-agent systems where the communication is often established over wireless channels, several constraints, such as limited bandwidth, power, and memory, arise. Such limitations often require that the information that is exchanged between agents is quantized. Quantization enables information compression such that a number in a continuous set ( i.e., real-valued number x\in\mathbb{R} ), can be mapped to a value in a finite set. This mapping is done with a quantizer, denoted by Q(\cdot) . In this work, we define the quantizer given a positive integer number of bits b<\infty available for quantization, the step-size \Delta which defines the spacing between the quantization intervals, and the quantizer’s symmetry point (or midpoint) \sigma (which is not necessarily at 0 ) as follows: \displaystyle Q\big(x,b,\Delta,\sigma\big) \displaystyle=\begin{cases}\hfil\sigma+\Delta(2^{b-1}-1),&\text{if}~x>\overline{x},\\ \hfil\sigma-\Delta(2^{b-1}-1),&\text{if}~x\leq\bar{x},\\ \hfil\sigma+\Delta\bigl\lfloor\frac{x-\sigma}{\Delta}+\frac{1}{2}\bigr\rfloor,&\text{otherwise},\end{cases} (1) where the upper and lower input quantization limits are given respectively by \displaystyle\overline{x}:=\sigma+\Delta\big(2^{b-1}-0.5\big), (2a) \displaystyle\underline{x}:=\sigma-\Delta\big(2^{b-1}-0.5\big). (2b) An illustrative example of the input-to-output relation of a uniform quantizer with b=3 , \Delta=1 , and \sigma=0 , is shown in Fig. . Figure 1: A uniform quantizer of b=3 bits with \sigma=0 and \Delta=1 . Although quantization reduces the precision of the original information, it enables mapping to a finite set of discrete values that are often representable using bits. This mapping is necessary for transmissions over channels with limited bandwidth and transmitters with power limitations. Bandwidth limits the number of symbols sent per second, while power constraints limit the number of bits per symbol that the modulation scheme can reliably encode. Increasing the number of bits per symbol requires higher transmission power to maintain reliable decoding at the receiver in the presence of noise. Consequently, quantization encodes real-valued information into sequence of bits aligned with the modulation scheme and constrained by the channel capacity. Communicating quantized values in multi-agent systems has attracted significant interest due to its essential role in overcoming practical constraints like bandwidth and power limitations [ 22 , 21 , 32 , 11 , 12 ] . However, in the context of distributed average consensus, quantized communication can negatively impact both the accuracy and overall performance of the system. Specifically, it affects the system behavior as follows. First, saturation occurs when the signal exceeds the quantization range, leading to large errors that can destabilize the system, if the consensus algorithm was originally designed for a non-quantized system. Second, as the system state gets closer to its target value, performance degradation arises because higher precision is required. Finally, each time an agent quantizes a value before sending it to its neighbors, some information is lost due to rounding and discretization. Over time, these small errors can accumulate, leading to biased consensus, i.e., agents converge to a value that is far from the true average. These errors are even amplified when agents interact over a directed network, where the information flow is not balanced, since the errors may propagate asymmetrically within the network. Since this work focuses on average consensus in directed graphs, the discussion of related work is limited to literature specifically addressing possibly unbalanced directed graphs. To minimize quantization errors, agents can use a dynamic quantization strategy, such as zooming in / zooming out (ZIZO) [ 3 ] , where the quantization step size changes based on the range of values being exchanged. However, since the links are not bidirectional, it is difficult to synchronize the nodes to simultaneously update the size of the quantization step. In the same spirit, the authors in [ 14 ] , proposed a distributed algorithm in which the exact average is computed asymptotically. Their method works for balanced directed graphs, where each node maintains real-valued states but transmits quantized values, adapting the quantization step as needed to refine the estimates. The majority of algorithms designed for quantized average consensus for unbalanced directed graphs achieve convergence in a probabilistic manner (see, e.g., [ 28 ] and references therein), meaning that nodes reach consensus on the quantized average with probability one or through other probabilistic guarantees. Nevertheless, either residual quantization errors persist indefinitely or the average consensus is approximate, the convergence is slow and depends on the network size. With only a few exceptions [ 30 , 1 , 20 , 31 , 29 ] , the development of deterministic distributed strategies for achieving quantized average consensus in unbalanced directed graphs remains largely unexplored. Baldan and Zambieri [ 1 ] proposed distributed algorithms that achieve average consensus with quantized transmissions and the algorithm’s parameters can be chosen in a distributed fashion without knowing the number of agents composing the network. Since they only adopt the ZIZO strategy without any adaptation on the symmetry point \sigma of the quantizer, there is a minimum number of bits required for the algorithm to converge which depends on the parameter choice. Rikos et al. [ 29 ] proposed a distributed algorithm that is able to calculate the exact average of the initially quantized values (in the form of a quantized fraction)

Read the complete text