Average consensus on digital noisy networks*

We propose a class of distributed algorithms for computing arithmetic averages (average consensus) over networks of agents connected through digital noisy broadcast channels. Our algorithms do not require the agents to have knowledge of the network structure, nor do they assume any noiseless feedback to be available. We prove convergence to consensus, with both number of channel uses and computational complexity which are poly-logarithmic in the desired precision.