Pierre Fraigniaud
George Giakkoupis
ABSTRACT
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 messages during a round only with the player that u called, and with all the players that $u$ received calls from, in that round. In every round, a (possibly empty) set of rumors to be distributed among all players is generated, and each of the rumors is initially placed in a subset of the players. Karp et. al \cite{Karp2000} showed that no rumor-spreading algorithm that spreads a rumor to all players with constant probability can be both time-optimal, taking O(lg n) rounds, and message-optimal, using O(n) messages per rumor. For address-oblivious algorithms, in particular, they showed that Ω(n lg lg n) messages per rumor are required, and they described an algorithm that matches this bound and takes O(lg n) rounds.
We investigate the number of communication bits required for rumor spreading. On the lower-bound side, we establish that any address-oblivious algorithm taking O(lg n) rounds requires Ω(n (b+ lg lg n)) communication bits to distribute a rumor of size b bits. On the upper-bound side, we propose an address-oblivious algorithm that takes O(lg n) rounds and uses O(n(b+ lg lg n lg b)) bits. These results show that, unlike the case for the message complexity, optimality in terms of both the running time and the bit communication complexity is attainable, except for very small rumor sizes b << lg lg n lg lg lg n.
- P. Berenbrink, R. Elsässer, and T. Friedetzky. Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. In Proc. 27th ACM Symp. on Principles of Distributed Computing (PODC), pages 155--164, 2008. Google Scholar
Digital Library
- B. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422--426, 1970. Google ScholarDigital Library
- A. Broder and M. Mitzenmacher. Network applications of Bloom filters: A survey. Internet Mathematics, 1(4):485--509, 2005.Google ScholarCross Ref
- 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 Proc. 6th ACM Symp. on Principles of Distributed Computing (PODC), pages 1--12, 1987. Google ScholarDigital Library
- B. Doerr, T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading. In Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 773--781, 2008. Google ScholarDigital Library
- B. Doerr, T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading: Expanders, push vs. pull, and robustness. In Proc. 36th Int. Colloq. on Automata, Languages and Programming (ICALP), pages 366--377, 2009. Google ScholarDigital Library
- D. Dubhashi and D. Ranjan. Balls and bins: A study in negative dependence. Random Struct. Algorithms, 13(2):99--124, 1998. Google ScholarDigital Library
- R. Elsässer. On randomized broadcasting in power law networks. In Proc. 20th Int. Symp. on Distributed Computing (DISC), pages 370--384, 2006. Google ScholarDigital Library
- R. Elsässer. On the communication complexity of randomized broadcasting in random-like graphs. In Proc. 18th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 148--157, 2006. Google ScholarDigital Library
- R. Elsässer and T. Sauerwald. The power of memory in randomized broadcasting. In Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 218--227, 2008. Google ScholarDigital Library
- U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Random Structures and Algorithms, 1(4):447--460, 1990.Google ScholarCross Ref
- P. Fraigniaud and E. Lazard. Methods and problems of communication in usual networks. Discrete Appl. Math., 53(1-3):79--133, 1994. Google ScholarDigital Library
- A. Frieze and G. Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math., 10:57--77, 1985.Google ScholarCross Ref
- S. Hedetniemi, T. Hedetniemi, and A. Liestman. A survey of gossiping and broadcasting in communication networks. NETWORKS, 18:319--349, 1988.Google ScholarCross Ref
- J. Hromkovic, R. Klasing, B. Monien, and R. Piene. Dissemination of information in interconnection networks (broadcasting & gossiping). In Combinatorial Network Theory, pages 125--212. Springer, 1995.Google Scholar
- R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumor spreading. In Proc. 41st IEEE Symp. on Foundations of Computer Science (FOCS), pages 565--574, 2000. Google ScholarDigital Library
- B. Pittel. On spreading a rumor. SIAM J. Appl. Math., 47(1):213--223, 1987. Google ScholarDigital Library
- J. H. van Lint. Introduction to Coding Theory. Springer Verlag, 3rd edition, 1998. Google ScholarDigital Library
Index Terms
- On the bit communication complexity of randomized rumor spreading
Recommendations
Simple, Fast and Deterministic Gossip and Rumor Spreading
We study gossip algorithms for the rumor spreading problem, which asks each node to deliver a rumor to all nodes in an unknown network. Gossip algorithms allow nodes only to call one neighbor per round and have recently attracted attention as message ...
Breaking the $$\log n$$logn barrier on rumor spreading
$$O(\log n)$$O(logn) rounds has been a well known upper bound for rumor spreading using push&pull in the random phone call model (i.e., uniform gossip in the complete graph). A matching lower bound of $$\varOmega (\log n)$$Ω(logn) is also known for this ...
Simple and optimal randomized fault-tolerant rumor spreading
We revisit the classic problem of spreading a piece of information in a group of $$n$$n fully connected processors. By suitably adding a small dose of randomness to the protocol of Gasieniec and Pelc (Parallel Comput 22:903---912, 1996), we derive for ...
Comments