Accelerated Gossip Algorithms for Distributed Computation
Ming Cao, Daniel A. Spielman, Edmund M. Yeh · 2006
Abstract — We introduce a technique for accelerating the gossip algorithm of Boyd et. al. (INFOCOM 2005) for distributed averaging in a network. By employing memory in the form of a small shift-register in the computation at each node, we can speed up the algorithm’s convergence by a factor of 10. Our accelerated algorithm is inspired by the observation that the original gossip algorithm is analogous to the power method in Numerical Analysis, which can be accelerated by a shift-register based recurrence. I.