Analysis and Optimization of Randomized Gossip Algorithms

S. Boyd, A. Ghosh, B. Prabhakar, D. Shah (alphabetical order)

Proceedings IEEE Conference on Decision and Control, pages 5310–5315, Atlantis, Paradise Island, Bahamas, December 2004.

We study the distributed averaging problem on an arbitrary network with a gossip constraint, which means that no node communicates with more than one neighbour in every time slot. We consider algorithms which are linear iterations, where each iteration is described by a random matrix picked i.i.d. from some distribution. We derive conditions that this distribution must satisfy so that the sequence of iterations converges to the vector of averages in different senses. We then analyze a simple asynchronous randomized gossip algorithm for averaging, and show that the problem of optimizing the parameters of this algorithm for fastest convergence is a semi-definite program. Finally we study the relation between Markov chains and the averaging problem, and relate the averaging time of the algorithm to the mixing time of a related Markov chain on the graph.