Output details
11 - Computer Science and Informatics
University of Derby
Return to search
Output 0 of 0 in the submission
Article title
Quasirandom Rumor Spreading on the Complete Graph is as Fast as Randomized Rumor Spreading
Type
D - Journal article
Title of journal
SIAM Journal on Discrete Mathematics
Article number
-
Volume number
23
Issue number
4
First page of article
1964
ISSN of journal
1095-7146
Year of publication
2010
URL
-
Number of additional authors
1
Additional information
<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.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
11
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
