# Order optimal information spreading using algebraic gossip Academic Article

•
• Overview
•
• Research
•
• Additional Document Info
•
• View All
•

### abstract

• In this paper we study gossip based information spreading with bounded message sizes. We use algebraic gossip to disseminate $$k$$ distinct messages to all $$n$$ nodes in a network. For arbitrary networks we provide a new upper bound for uniform algebraic gossip of $$O((k+\log n + D)\varDelta )$$ rounds with high probability, where $$D$$ and $$\varDelta$$ are the diameter and the maximum degree in the network, respectively. For many topologies and selections of $$k$$ this bound improves previous results, in particular, for graphs with a constant maximum degree it implies that uniform gossip is order optimal and the stopping time is $$\varTheta (k + D)$$. To eliminate the factor of $$\varDelta$$ from the upper bound we propose a non-uniform gossip protocol, TAG, which is based on algebraic gossip and an arbitrary spanning tree protocol $$\mathcal{S }$$. The stopping time of TAG is $$O(k+\log n +d(\mathcal{S })+t(\mathcal{S }))$$, where $$t(\mathcal{S })$$ is the stopping time of the spanning tree protocol, and $$d(\mathcal{S })$$ is the diameter of the spanning tree. We provide two general cases in which this bound leads to an order optimal protocol. The first is for $$k=\varOmega (n)$$, where, using a simple gossip broadcast protocol that creates a spanning tree in at most linear time, we show that TAG finishes after $$\varTheta (n)$$ rounds for any graph. The second uses a sophisticated, recent gossip protocol to build a fast spanning tree on graphs with large weak conductance. In turn, this leads to the optimally of TAG on these graphs for $$k=\varOmega (\text{ polylog }(n))$$. The technique used in our proofs relies on queuing theory, which is an interesting approach that can be useful in future gossip analysis.

### publication date

• January 1, 2013