In this work we present a new framework for the analysis and design of randomized gossip algorithms for solving the average consensus problem. We show how classical randomized iterative methods for solving linear systems can be interpreted as gossip algorithms when applied to special systems encoding the underlying network and explain in detail their decentralized nature. Our general framework recovers a comprehensive array of well-known gossip algorithms as special cases, including the pairwise randomized gossip algorithm and path averaging gossip, and allows for the development of provably faster variants. The flexibility of the new approach enables the design of a number of new specific gossip methods. For instance, we propose and analyze novel block and the first provably accelerated randomized gossip protocols, and dual randomized gossip algorithms. From a numerical analysis viewpoint, our work is the first that explores in depth the decentralized nature of randomized iterative methods for linear systems and proposes them as methods for solving the average consensus problem. We evaluate the performance of the proposed gossip protocols by performing extensive experimental testing on typical wireless network topologies.
While the gossip algorithms studied in @cite_72 @cite_59 @cite_82 are all first-order (the update of @math only depends on @math ), a faster randomized pairwise gossip protocol was proposed in @cite_61 which suggested to incorporate additional memory to accelerate convergence. The first analysis of this protocol was later proposed in @cite_47 under strong conditions. It is worth to mention that in the setting of deterministic gossip algorithms theoretical guarantees for accelerated convergence were obtained in @cite_65 @cite_25 . In we propose fast and provably accelerated randomized gossip algorithms with memory and compare them in more detail with the fast randomized algorithm proposed in @cite_61 @cite_0 .
@cite_61 @cite_65 @cite_0 @cite_72 @cite_59 @cite_47 @cite_25 @cite_82
1605258304 2105333851 2132612558 2127850304
We introduce a technique for accelerating the gos- sip 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. Gossiping is a distributed process whose purpose is to enable the members of a group of n>1 autonomous agents to asymptotically determine in a decentralized manner, the average of the initial values of their scalar gossip variables. This paper analyzes the accelerated gossip algorithms, first proposed in Cao, Spielman, and Yeh (2006), in which local memory is exploited by installing shift-registers at each agent. For the two-register case, the existence of the desired convergence is established under a symmetry assumption by separately studying the convergence in expectation and in mean square. In particular, the optimal rate of convergence in expectation is derived which is faster than that of the standard gossip algorithm, and a sufficient condition on the adjustable parameter for the convergence in mean square is provided. These theoretical results are validated for some classes of networks by comparison with existing empirical data. More general multi-register cases are also discussed. In this paper, we study two related iterative randomized algorithms for distributed computation of averages. The first algorithm is the Broadcast Gossip Algorithm, in which at each iteration one randomly selected node broadcasts its own state to its neighbors. The second algorithm is a novel variation of the former, in which at each iteration every node is allowed to broadcast: hence, this algorithm, which we call Collision Broadcast Gossip Algorithm (CBGA), is affected by interference among messages. The performance of both algorithms is evaluated in terms of rate of convergence and asymptotical error: focusing on large Abelian Cayley networks, we highlight the role of topology and of design parameters. We show that on fully connected graphs the rate of convergence is bounded away from one, whereas the asymptotical error is bounded away from zero. On the contrary, on sparse graphs the rate of convergence goes to one and the asymptotical error goes to zero, as the size of the network grows larger. Our results also show that the performance of the CBGA is close to the performance of the BGA: this indicates the robustness of broadcast gossip algorithms to interferences. Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust message-passing schemes for distributed information processing over networks. However, for many topologies that are realistic for wireless ad-hoc and sensor networks (like grids and random geometric graphs), the standard nearest-neighbor gossip converges as slowly as flooding (O(n2) messages). A recently proposed algorithm called geographic gossip improves gossip efficiency by a √n factor, by exploiting geographic information to enable multihop long-distance communications. This paper proves that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional √n factor, and is order optimal (O(n) messages) for grids and random geometric graphs with high probability. We develop a general technique (travel agency method) based on Markov chain mixing time inequalities which can give bounds on the performance of randomized message-passing algorithms operating over various graph topologies.