Information Dissemination via Gossip: Applications to Averaging and Coding

Damon Mosk-Aoyama, Devavrat ShaharXiv 2005 · arXiv

Abstract

We study distributed algorithms, also known as gossip algorithms, for information dissemination in arbitrary connected networks. These algorithms are critical for peer-to-peer, sensor, and ad hoc networks where nodes operate under limited computational and communication resources. By modeling gossip as a randomized process where nodes repeatedly communicate with neighbors, we distribute the computational burden across the entire network. Our analysis reveals that information dissemination time is fundamentally linked to the isoperimetric properties (conductance) of the underlying graph. This characterization allows us to formulate the search for the fastest gossip algorithm as a concave maximization problem. Furthermore, we apply these insights to distributed averaging and network coding, demonstrating that while coding is highly effective in dense networks, it offers no asymptotic advantage in sparse, grid-like topologies.

Introduction

In decentralized systems such as sensor networks or peer-to-peer overlays, the absence of a central authority necessitates robust, localized communication protocols. Gossip algorithms have emerged as a primary solution: nodes periodically contact randomly chosen neighbors to exchange data. While simple to implement, predicting the "spreading time"—the time required for a message to reach every node—has historically been difficult for arbitrary network topologies. This paper provides a unified theoretical framework to analyze and optimize gossip algorithms across any connected graph, moving beyond the well-studied cases of complete or highly symmetric graphs.

The Theoretical Framework: Conductance and Spreading

We model the network as an asynchronous system where each node $i$ possesses an independent Poisson clock. When a node's clock ticks, it contacts a neighbor $j$ with a probability defined by a communication matrix $P_{ij}$. The efficiency of this process is dictated by the network's bottlenecks.

Uniform Conductance

A key contribution of this work is the definition of uniform conductance ($\Phi^u_P$), a metric that quantifies how easily information flows across the network's most restrictive cuts. We prove that the $\epsilon$-spreading time—the time until all nodes receive the information with high probability—is bounded by:

$$T_{spread} = O\left(\frac{n \log n}{\Phi^u_P}\right)$$

This relationship shows that the speed of gossip is fundamentally limited by the graph's isoperimetric properties. If a network has a "thin" cut (a bottleneck), the spreading time increases proportionally.

Optimizing the Gossip Strategy

Because the spreading time is tied to the matrix $P$, we can optimize the communication probabilities to maximize dissemination speed. We demonstrate that finding the optimal doubly stochastic matrix $P$ is a concave maximization problem. This is a significant result for network designers, as it means the most efficient gossip strategy for any specific, fixed topology can be computed efficiently using standard convex optimization techniques.

Applications and Case Studies

Distributed Averaging via Probabilistic Counting

Traditional distributed averaging requires nodes to iteratively exchange and average values with neighbors. However, this can be slow in high-diameter networks. We propose an alternative based on the Flajolet-Martin Algorithm (FMA), originally used for counting distinct elements in database streams. By treating the averaging problem as a "counting" task using bit-maps, we achieve significant speedups. For example, on a ring graph, the FMA-based approach takes $O(n^2)$ time, whereas optimal traditional iterative averaging requires $\Omega(n^3 \log \epsilon^{-1})$.

The Limits of Network Coding

Network coding, specifically Random Linear Coding (RLC), allows nodes to send linear combinations of messages rather than raw data. While previous research showed RLC drastically reduces dissemination time in complete graphs by preventing redundant transmissions, our analysis shows this benefit is topology-dependent.

In sparse, grid-like graphs, the delay is not caused by message "collisions" or redundancy, but by the physical distance (diameter) the information must traverse. Consequently, for a $d$-dimensional grid, the spreading time remains $O(dn^{1+1/d} \log n)$ regardless of whether coding is used. Our results confirm that for a large class of graphs, coding does not improve asymptotic performance over simple randomized gossip.

Conclusion

This research establishes a rigorous link between graph conductance and the efficiency of gossip-based information dissemination. By providing a method to optimize communication matrices and identifying the topological limits of network coding, we offer a toolkit for designing more efficient decentralized systems. Future work remains in extending these proofs to dynamic topologies where links may appear or disappear, and exploring the impact of finite link capacities on these theoretical bounds.

Summary updated

Abstract

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. 1
BibTeX
@misc{moskaoyama2005information,
  author = {Damon Mosk-Aoyama and Devavrat Shah},
  title = {{Information Dissemination via Gossip: Applications to Averaging and Coding}},
  year = {2005},
  eprint = {cs/0504029},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cs/0504029},
}
Figure