research-article

On the randomness requirements of rumor spreading

Authors:

George Giakkoupis,

Philipp WoelfelAuthors Info & Claims

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

Pages 449 - 461

Published: 23 January 2011 Publication History

Abstract

We investigate the randomness requirements of the classical rumor spreading problem on fully connected graphs with n vertices. In the standard random protocol, where each node that knows the rumor sends it to a randomly chosen neighbor in every round, each node needs O((log n)²) random bits in order to spread the rumor in O(log n) rounds with high probability (w.h.p.). For the simple quasirandom rumor spreading protocol proposed by Doerr, Friedrich, and Sauerwald (2008), [log n] random bits per node are sufficient. A lower bound by Doerr and Fouz (2009) shows that this is asymptotically tight for a slightly more general class of protocols, the so-called gate-model.

In this paper, we consider general rumor spreading protocols. We provide a simple push-protocol that requires only a total of O(n log log n) random bits (i.e., on average O(log log n) bits per node) in order to spread the rumor in O(log n) rounds w.h.p. We also investigate the theoretical minimal randomness requirements of efficient rumor spreading. We prove the existence of a (non-uniform) push-protocol for which a total of 2 log n + log log n + o(log log n) random bits suffice to spread the rumor in log n + ln n + O(1) rounds with probability 1 − o(1). This is contrasted by a simple time-randomness tradeoff for the class of all rumor spreading protocols, according to which any protocol that uses log n − log log n − ω(1) random bits requires ω(log n) rounds to spread the rumor.

References

[1]

S. Angelopoulos, B. Doerr, A. Huber, and K. Panagiotou. Tight bounds for quasi-random rumor spreading. The Electronic Journal of Combinatorics, 16(1), 2009.

[2]

P. Berenbrink, R. Elsässer, and T. Friedetzky. Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. In Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pages 155--164, 2008.

Digital Library

[3]

A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In Proceedings of the 6th ACM Symposium on Principles of Distributed Computing (PODC), pages 1--12, 1987.

Digital Library

[4]

B. Doerr and M. Fouz. A time-randomness tradeoff for quasi-random rumour spreading. Electronic Notes in Discrete Mathematics, 34:335--339, 2009.

[5]

B. Doerr and M. Fouz. Quasi-random rumor spreading: Reducing randomness can be costly. CoRR, abs/1008.0501, 2010.

[6]

B. Doerr, T. Friedrich, M. Künnemann, and T. Sauerwald. Quasirandom rumor spreading: An experimental analysis. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), pages 145--153, 2009.

[7]

B. Doerr, T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 773--781, 2008.

Digital Library

[8]

B. Doerr, T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading: Expanders, push vs. pull, and robustness. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 366--377, 2009.

Digital Library

[9]

B. Doerr, A. Huber, and A. Levavi. Strong robustness of randomized rumor spreading protocols. CoRR, abs/1001.3056, 2010.

Digital Library

[10]

R. Elsässer. On the communication complexity of randomized broadcasting in random-like graphs. In Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 148--157, 2006.

Digital Library

[11]

R. Elsässer, U. Lorenz, and T. Sauerwald. On randomized broadcasting in star graphs. Discrete Applied Mathematics, 157(1):126--139, 2009.

Digital Library

[12]

R. Elsässer and T. Sauerwald. Broadcasting vs. mixing and information dissemination on Cayley graphs. In Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science (STACS), pages 163--174, 2007.

Digital Library

[13]

R. Elsässer and T. Sauerwald. The power of memory in randomized broadcasting. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 218--227, 2008.

Digital Library

[14]

R. Elsässer and T. Sauerwald. On the runtime and robustness of randomized broadcasting. Theoretical Computer Science, 410(36):3414--3427, 2009.

Digital Library

[15]

U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Random Structures and Algorithms, 1(4):447--460, 1990.

[16]

N. Fountoulakis and A. Huber. Quasirandom rumor spreading on the complete graph is as fast as randomized rumor spreading. SIAM Journal on Discrete Mathematics, 23(4):1964--1991, 2009.

Digital Library

[17]

P. Fraigniaud and G. Giakkoupis. On the bit communication complexity of randomized rumor spreading. In Proceedings of the 22nd ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 134--143, 2010.

Digital Library

[18]

A. Frieze and G. Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics, 10:57--77, 1985.

[19]

R. Karp, C. Schindelhauer, S. Shenker, and B. Vöcking. Randomized rumor spreading. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS), pages 565--574, 2000.

Digital Library

[20]

M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.

Digital Library

[21]

B. Pittel. On spreading a rumor. SIAM Journal on Applied Mathematics, 47(1):213--223, 1987.

Digital Library

[22]

T. Sauerwald. On mixing and edge expansion properties in randomized broadcasting. In Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC), pages 196--207, 2007.

Digital Library

Cited By

Korman AVacus RMilani AWoelfel P(2022)Early Adapting to Trends: Self-Stabilizing Information Spread using Passive CommunicationProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538415(235-245)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538415
Guo ZSun HIndyk P(2015)Gossip vs. Markov chains, and randomness-efficient rumor spreadingProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722158(411-430)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722158
Haeupler B(2015)Simple, Fast and Deterministic Gossip and Rumor SpreadingJournal of the ACM10.1145/276712662:6(1-18)Online publication date: 10-Dec-2015
https://dl.acm.org/doi/10.1145/2767126
Show More Cited By

On the randomness requirements of rumor spreading
1. Computing methodologies
  1. Symbolic and algebraic manipulation
2. Theory of computation

Recommendations

Gossip vs. Markov chains, and randomness-efficient rumor spreading
SODA '15: Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms

We study gossip algorithms for the rumor spreading problem which asks one node to deliver a rumor to all nodes in an unknown network, and every node is only allowed to call one neighbor in each round. In this work we introduce two fundamentally new ...
On the bit communication complexity of randomized rumor spreading
SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

We study the communication complexity of rumor spreading in the random phone-call model. Suppose nplayers communicate in parallel rounds, where in each round every player calls a randomly selected communication partner. A player u is allowed to exchange ...
On the Push&Pull Protocol for Rumour Spreading: [Extended Abstract]
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

The asynchronous push&pull protocol, a randomized distributed algorithm for spreading a rumour in a graph G, is defined as follows. Independent exponential clocks of rate 1 are associated with the vertices of G, one to each vertex. Initially, one vertex ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

January 2011

1785 pages

Program Chair:
Dana Randall
Georgia Institute of Technology

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2011

Check for updates

Qualifiers

Research-article

Conference

SODA '11

Sponsor:

SIGACT

SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms

January 23 - 25, 2011

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
112
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Korman AVacus RMilani AWoelfel P(2022)Early Adapting to Trends: Self-Stabilizing Information Spread using Passive CommunicationProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538415(235-245)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538415
Guo ZSun HIndyk P(2015)Gossip vs. Markov chains, and randomness-efficient rumor spreadingProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722158(411-430)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722158
Haeupler B(2015)Simple, Fast and Deterministic Gossip and Rumor SpreadingJournal of the ACM10.1145/276712662:6(1-18)Online publication date: 10-Dec-2015
https://dl.acm.org/doi/10.1145/2767126
Censor-Hillel K(2015)Distributed Algorithms as Combinatorial StructuresACM SIGACT News10.1145/2744447.274446146:1(63-76)Online publication date: 9-Mar-2015
https://dl.acm.org/doi/10.1145/2744447.2744461
(2014)The worst case behavior of randomized gossip protocolsTheoretical Computer Science10.5555/2945717.2945734560:P2(108-120)Online publication date: 4-Dec-2014
https://dl.acm.org/doi/10.5555/2945717.2945734
Doerr BFriedrich TSauerwald T(2014)Quasirandom Rumor SpreadingACM Transactions on Algorithms10.1145/265018511:2(1-35)Online publication date: 30-Oct-2014
https://dl.acm.org/doi/10.1145/2650185
Haeupler BKhanna S(2013)Simple, fast and deterministic gossip and rumor spreadingProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627868(705-716)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627868
Censor-Hillel KHaeupler BKelner JMaymounkov PKarloff HPitassi T(2012)Global computation in a poorly connected worldProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214064(961-970)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214064

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents