Randomization and Quantization for Average Consensus

Many problems in distributed control reduce to the distributed computation of the average of initial values in a networked system of autonomous agents, known as the average consensus problem. We present a randomized algorithm that solves this problem in networks with directed, time-varying communication topologies, in linear time in the size of the network. This algorithm leverages properties of exponential random variables, which allows for approximating sums by computing minima. It is completely decentralized, in the sense that it does not rely on agent identifiers or global information of any kind. Besides, the agents do not need to know their out-degree; hence, our algorithm demonstrates how randomization can be used to circumvent the impossibility result established in [1]. Using a logarithmic rounding rule, we show that this algorithm can be used under the additional constraints of finite memory and channel capacity. We furthermore extend the algorithm with a termination test, by which the agents can decide irrevocably in finite time — rather than simply converge — on an estimate of the average.