NDLI: Quasirandom Rumor Spreading on the Complete Graph Is as Fast as Randomized Rumor Spreading

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Fountoulakis, Nikolaos Huber, Anna
Copyright Year	2009
Abstract	In this paper, we provide a detailed comparison between a fully randomized protocol for rumor spreading on a complete graph and a quasirandom protocol introduced by Doerr, Friedrich, and Sauerwald [Quasirandom rumor spreading, in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2008, pp. 773781]. 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 uniformly at random and independently one of its neighbors and informs it. In the quasirandom version of this method (cf. Doerr, Friedrich, and Sauerwald) each vertex has a cyclic list of its neighbors. Once a vertex has been informed, it chooses uniformly at random only one neighbor. In the following round, it informs this neighbor, and at each subsequent round it picks the next neighbor 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)$, we have $\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)$.
Starting Page	1964
Ending Page	1991
Page Count	28
File Format	PDF
ISSN	08954801
DOI	10.1137/09075768X
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	4
Volume Number	23
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2009-12-11
Access Restriction	Subscribed
Subject Keyword	quasirandom broadcasting Signal detection and filtering Combinatorial probability derandomization randomized broadcasting
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Quasirandom rumour spreading on the complete graph is as fast as randomized rumour spreading (1964)

Push is Fast on Sparse Random Graphs

Quasirandom rumor spreading (2008)

Quasirandom Rumor Spreading

On the Push&Pull Protocol for Rumor Spreading

A Quasirandom Rumor Spreading: An Experimental Analysis

Quasirandom rumor spreading: An experimental analysis (2009)

Quasirandom rumor spreading

Quasirandom rumor spreading: An experimental analysis

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

Similar Documents

Quasirandom rumour spreading on the complete graph is as fast as randomized rumour spreading (1964)

Push is Fast on Sparse Random Graphs

Quasirandom rumor spreading (2008)

Quasirandom Rumor Spreading

On the Push&Pull Protocol for Rumor Spreading

A Quasirandom Rumor Spreading: An Experimental Analysis

Quasirandom rumor spreading: An experimental analysis (2009)

Quasirandom rumor spreading

Quasirandom rumor spreading: An experimental analysis

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