Liu, JiAnderson, BrianCao, MingMorse, A Stephen2015-12-10December 19781424438723http://hdl.handle.net/1885/54793This paper investigates accelerated gossip algorithms for distributed computations in networks where shiftregisters are utilized at each node. By using tools from matrix analysis, we prove the existence of the desired acceleration and establish the fastest rate of convergence in expectation for two-register symmetric gossip. Some classes of networks with regular graph topologies are studied in detail to validate the analytical results by comparison with existing empirical data. We also analyze convergence of second moment and provide a necessary condition for convergence in multi-register symmetric gossip. The proposed approach has the potential to be applied to the more challenging open problem of asymmetric gossip.Keywords: Analytical results; Distributed computations; Empirical data; Gossip algorithms; In-network; Matrix analysis; Open problems; Rate of convergence; Regular graphs; Second moments; Approximation theory200910.1109/CDC.2009.53995662016-02-24