English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Quasirandom Rumor Spreading on the Complete Graph is as Fast as Randomized Rumor Spreading

MPS-Authors
/persons/resource/persons44649

Huber,  Anna
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44437

Fountoulakis,  Nikolaos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Huber, A., & Fountoulakis, N. (2009). Quasirandom Rumor Spreading on the Complete Graph is as Fast as Randomized Rumor Spreading. SIAM Journal on Discrete Mathematics, 23(4), 1964-1991. doi:10.1137/09075768X.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-18C4-2
Abstract
In this paper, we provide a detailed comparison between a fully randomized protocol for rumour spreading on a complete graph and a quasirandom protocol introduced by Doerr, Friedrich and Sauerwald (2008). In the former, initially there is one vertex which holds a piece of information and during each round every one of the informed vertices chooses one of its neighbours uniformly at random and independently and informs it. In the quasirandom version of this method (cf. Doerr et al.) each vertex has a cyclic list of its neighbours. Once a vertex has been informed, it chooses uniformly at random only one neighbour. In the following round, it informs this neighbour and at each subsequent round it picks the next neighbour from its list and informs it. We give a precise analysis of the evolution of the quasirandom protocol on the complete graph with $n$ vertices and show that it evolves essentially in the same way as the randomized protocol. In particular, if $S(n)$ denotes the number of rounds that are needed until all vertices are informed, we show that for any slowly growing function $\omega (n)$ $$\log_2 n + \ln n - 4\ln \ln n \leq S(n) \leq \log_2 n + \ln n + \omega (n),$$ with probability $1-o(1)$.