Convergence Rates in Distributed Consensus and Averaging
Alex Olshevsky, John N. Tsitsiklis · 2006
We propose three new algorithms for the distributed averaging and consensus problems: two for the fixed-graph case, and one for the dynamic-topology case. The convergence rates of our fixed-graph algorithms compare favorably with other known methods, while our algorithm for the dynamic-topology case is the first to be accompanied by a polynomial-time bound on the convergence time