A Lower Bound for Distributed Averaging Algorithms on the Line Graph

作者：Olshevsky Alex^*; Tsitsiklis John N

来源：IEEE Transactions on Automatic Control, 2011, 56(11): 2694-2698.

DOI：10.1109/TAC.2011.2159652

• Cooperative control
• distributed averaging
• load balancing

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 state consists of a single real number and whose (possibly nonlinear) update function satisfies a natural smoothness condition has a worst case running time of at least on the order of n(2) on a line network of n nodes. Our results suggest that increased memory or expansion of the state space is crucial for improving the running times of distributed averaging algorithms.

• 出版日期2011-11