Information Dissemination via Gossip: Applications to Averaging and Coding

We study distributed algorithms, also known as gossip algorithms, for information dissemination in an arbitrary connected network of nodes. Distributed algorithms have applications to peer-to-peer, sensor, and ad hoc networks, in which nodes operate under limited computational, communication, and energy resources. These constraints naturally give rise to “gossip” algorithms: schemes in which nodes repeatedly communicate with randomly chosen neighbors, thus distributing the computational burden across all the nodes in the network. We analyze the information dissemination problem under the gossip constraint for arbitrary networks, and find that the information dissemination time of a gossip algorithm is strongly related to the isoperimetric properties of the underlying graph. This characterization allows us to formulate the problem of fastest information dissemination algorithm as a concave maximization problem over the convex set of graph-conformant doubly stochastic matrices. Next, we use these results for two seemingly unrelated important questions: distributed averaging and coding based information dissemination. For averaging, we analyze an algorithm based on a classic result of Flajolet and Martin [7]. Information dissemination based on coding was introduced by Deb and Médard [6]. They showed the virtue of coding by analyzing a coding algorithm for a complete graph. Although their scheme generalizes to arbitrary graphs, the analysis does not. We present an analysis of this algorithm for arbitrary graphs and find that for a large class of graphs, such as grid-like graphs, coding-based algorithms do not seem to improve performance. Finally, we apply our results to several classes of graphs: grid graph, expander graphs, and complete graphs.