A lower bound for distributed averaging algorithms

Alex Olshevsky, John N. Tsitsiklis

We derive lower bounds on the convergence speed of a widely used class of distributed averaging algorithms. In particular, we prove that any distributed averaging algorithm whose s…