Average Consensus with Dynamic Compression in Bandwidth-Limited Directed Networks
Evagoras Makridis, Gabriele Oliva, Apostolos I. Rikos, Themistoklis Charalambous · 2025
Read Average Consensus with Dynamic Compression in Bandwidth-Limited 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-2508-06893.txt.
Introduction
Evagoras Makridis, Gabriele Oliva, Apostolos Rikos, and Themistoklis Charalambous tackle average consensus on directed networks whose links carry only a few bits, in a 2025 paper. Their algorithm, PP-ACDC, pairs a push-pull consensus scheme with dynamic compression: nodes adaptively quantize the values they send, squeezing them to fit the bandwidth. The method needs no global information about the network, yet the authors show it still converges to the exact average of all node values. Early numerical analysis and simulations back the design.
Catalog record
| CREATOR | Evagoras Makridis, Gabriele Oliva, Apostolos I. Rikos, Themistoklis Charalambous |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-06893
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 Compression in Bandwidth-Limited Directed Networks Evagoras Makridis, Gabriele Oliva, Apostolos I. Rikos, Themistoklis Charalambous Abstract In this paper, the average consensus problem has been considered for directed unbalanced networks under finite bit-rate communication. We propose the Push-Pull Average Consensus algorithm with Dynamic Compression ( pp-acdc ) algorithm, a distributed consensus algorithm that deploys an adaptive quantization scheme and achieves convergence to the exact average without the need of global information. A preliminary numerical convergence analysis and simulation results corroborate the performance of pp-acdc . I 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 [ 1 , 2 ] , distributed estimation and control [ 3 , 4 ] , and distributed learning [ 5 ] . 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 or drops) [ 6 ] and malfunctioning agents (e.g., curious, malicious, or faulty agents) [ 7 ] , 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 be 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+\left(2^{b-1}-1\right)\Delta,&\text{if}~x\geq\sigma+\bar{x},\\ \hfil\sigma-\left(2^{b-1}-1\right)\Delta,&\text{if}~x\leq\sigma-\bar{x},\\ \hfil\sigma+\Delta\bigl\lfloor\frac{x-\sigma}{\Delta}\bigr\rceil,&\text{otherwise},\end{cases} (1) where the quantization range limit is given by \displaystyle\bar{x}={\left(2^{b-1}-\dfrac{1}{2}\right)\Delta}, (2) and \lfloor x\rceil represents the round function for a value x . An example of the input/output relation of a quantizer with b=3 and \Delta=1 is shown in Fig. 1 . Fig. 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 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 its essential role in overcoming practical constraints like bandwidth and power limitations [ 8 , 9 , 10 , 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 will be 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) [ 13 ] , 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. The majority of algorithms designed for quantized average consensus for unbalanced directed graphs achieve convergence in a probabilistic manner (see, e.g., [ 14 ] 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 [ 15 , 16 , 17 ] , the development of deterministic distributed strategies for achieving quantized average consensus in unbalanced directed graphs remains largely unexplored. Baldan and Zambieri [ 15 ] 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. [ 17 ] proposed a distributed algorithm that is able to calculate the exact average of the initially quantized values (in the form of a quantized fraction) in a deterministic fashion after a finite number of iterations. However, the average consensus is approximate (due to the initial quantization), the number of bits for each message is not necessarily bounded by a certain value, and the convergence is slow and depends on the network size. In this paper, our aim is to address the aforementioned challenges and thus we propose a distributed average consensus algorithm for possibly unbalanced directed graphs under limited communication bandwidth. The algorithm integrates an adaptive quantization mechanism, enabling agents to converge to the exact average without requiring global knowledge of the network (see § IV ). Our algorithm adopts a surplus consensus structure suited for unbalanced directed graphs and avoids the division operations used in ratio consensus methods (see [ 6 ] ), making it robust to quantization. We introduce a design that integrates dynamic quantization (zooming and midpoint shifting) directly into the consensus updates, ensuring robustness to finite-bit communication constraints and enabling the consensus error to be driven to zero. We analyze the convergence properties