Output details
11 - Computer Science and Informatics
University of Derby
Quasirandom Rumor Spreading on the Complete Graph is as Fast as Randomized Rumor Spreading
<12>
In this paper we show that Quasirandom Rumor Spreading uses less randomness then Randomized Rumor Spreading while maintaining performance. The use of random bits is computationally expensive and therefore reducing the amount needed is beneficial for applications. Applications lie for example in peer-to-peer systems and social networks.
This tight comparison of randomized rumour spreading and a quasirandom variant on the Complete Graph has contributed to further research on this model on other graph classes. See http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=13042 for an overview of applications and more recent developments.