Asymmetric randomized gossip algorithms for consensus

Abstract: Distributed averaging is a relevant problem in several application areas, such as decentralized computation, sensor networks, clock synchronization and coordinated control of mobile autonomous agents. Gossip randomized consensus algorithms provide a particular simple and efficient solution of such a problem. These algorithms however need bidirectional communication among agents and this can be a rather restrictive hypothesis in some contexts. In this contribution we analyze two important examples of asymmetric randomized consensus algorithms which do not need bidirectional communication and exhibit a speed of convergence comparable to the symmetric gossip. However, differently from the symmetric gossip, these algorithms do not converge to the average. We complete our analysis showing that under rather mild hypotheses, the displacement of the their final state from the average goes to zero as the number of agents goes to infinity. 1