| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652345 | Electronic Notes in Discrete Mathematics | 2009 | 5 Pages |
Abstract
Randomized rumor spreading is an efficient way to distribute information in networks. Recently, a quasirandom version of this protocol has been proposed. It was proven that it works equally well or even better in many settings.In this work, we exhibit a natural expansion property for networks, which ensures that quasirandom rumor spreading informs all nodes of the network in logarithmic time with high probability. This expansion property is satisfied, among others, by many expander graphs, random regular graphs, and Erdős-Rényi random graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
