Rates of Convergence for Distributed Average Consensus With Probabilistic Quantization

Probabilistically Quantized Distributed Averaging (PQDA) is a fully decentralized algorithm for performing average consensus in a network with finite-rate links. At each iteration, nodes exchange quantized messages with their immediate neighbors. Then each node locally computes a weighted average of the messages it received, quantizes this new value using a randomized quantization scheme, and then the whole process is repeated in the next iteration. In the authors' previous work, they introduced PQDA and demonstrated that the algorithm almost surely converges to a consensus (i.e., every node converges to the same value).