Quasirandom Rumor Spreading: An Experimental Analysis

DOI10.1137/1.9781611972894.14MaRDI QIDQ5233573zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald

Publication date 11 September 2019

Published in 2009 Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.5357

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10) Network protocols (68M12) Distributed systems (68M14) Communication networks in operations research (90B18)

Abstract: We empirically analyze two versions of the well-known "randomized rumor spreading" protocol to disseminate a piece of information in networks. In the classical model, in each round each informed node informs a random neighbor. In the recently proposed quasirandom variant, each node has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the list. While for sparse random graphs a better performance of the quasirandom model could be proven, all other results show that, independent of the structure of the lists, the same asymptotic performance guarantees hold as for the classical model. In this work, we compare the two models experimentally. This not only shows that the quasirandom model generally is faster, but also that the runtime is more concentrated around the mean. This is surprising given that much fewer random bits are used in the quasirandom process. These advantages are also observed in a lossy communication model, where each transmission does not reach its target with a certain probability, and in an asynchronous model, where nodes send at random times drawn from an exponential distribution. We also show that typically the particular structure of the lists has little influence on the efficiency.

Recommendations

• Quasirandom rumor spreading, an experimental analysis
• Quasi-random rumor spreading: reducing randomness can be costly
• Randomized rumor spreading revisited
• Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
• A time-randomness tradeoff for quasi-random rumour spreading
• Robustness of randomized rumour spreading
• scientific article; zbMATH DE number 7525473
• scientific article; zbMATH DE number 6783407
• Tight bounds for quasirandom rumor spreading

Cited in

(17)

• Quasi-random rumor spreading: reducing randomness can be costly
• Strong robustness of randomized rumor spreading protocols
• Communication complexity of quasirandom rumor spreading
• Tight bounds for quasirandom rumor spreading
• Quasirandom rumor spreading on expanders
• A time-randomness tradeoff for quasi-random rumour spreading
• Quasirandom broadcasting on the complete graph is as fast as randomized broadcasting
• The worst case behavior of randomized gossip
• Quasirandom rumor spreading on the complete graph is as fast as randomized rumor spreading
• Communication complexity of quasirandom rumor spreading
• Introducing Quasirandomness to Computer Science
• The worst case behavior of randomized gossip protocols
• Quasirandom rumor spreading
• scientific article; zbMATH DE number 7525473 (Why is no real title available?)
• Probabilistic Analysis of Rumor-Spreading Time
• scientific article; zbMATH DE number 6783407 (Why is no real title available?)
• Quasirandom rumor spreading, an experimental analysis

This page was built for publication: Quasirandom Rumor Spreading: An Experimental Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233573)