@inproceedings{c627933edc5d462b90ea4024aeca3b72,
title = "A lower bound for distributed averaging algorithms on the line graph",
abstract = "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 n2 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.",
author = "Alex Olshevsky and Tsitsiklis, {John N.}",
year = "2010",
doi = "10.1109/CDC.2010.5716968",
language = "English (US)",
isbn = "9781424477456",
series = "Proceedings of the IEEE Conference on Decision and Control",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "4523--4528",
booktitle = "2010 49th IEEE Conference on Decision and Control, CDC 2010",
address = "United States",
note = "49th IEEE Conference on Decision and Control, CDC 2010 ; Conference date: 15-12-2010 Through 17-12-2010",
}