×

The worst case behavior of randomized gossip protocols. (English) Zbl 1303.68030

Summary: This paper considers the quasi-random rumor spreading model introduced by B. Doerr et al. [in: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2008, San Francisco, CA, January 20–22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 773–781 (2008; Zbl 1192.90024)], hereafter referred to as the list-based model. Each node is provided with a cyclic list of all its neighbors, and, upon reception of a message, it chooses a random position in its list, and from then on calls its neighbors in the order of the list. This model is known to perform asymptotically at least as well as the random phone-call model, for many network classes. Motivated by potential applications of the list-based model to live streaming, we are interested in its worst case behavior. Our first main result is the design of an \(O(m + n \log n)\)-time algorithm that, given any n-node m-edge network G, and any source-target pair \(s, t \in V(G)\), computes the maximum number of rounds it may take for a rumor to be broadcast from s to t in G, in the list-based model. Hence, the list-based model is computationally easy to tackle in its basic version. The situation is radically different when one is considering variants of the model in which nodes are aware of the status of their neighbors, i.e., are aware of whether or not they have already received the rumor, at any point in time. Indeed, our second main result states that, unless \(\operatorname{P} = \operatorname{NP}\), the worst case behavior of the list-based model with the additional feature that every node is perpetually aware of which of its neighbors have already received the rumor cannot be approximated in polynomial time within a \((\frac{1}{n})^{\frac{1}{2} - \epsilon}\) multiplicative factor, for any \(\epsilon > 0\). As a byproduct of this latter result, we can show that, unless \(\operatorname{P} = \operatorname{NP}\), there are no PTAS enabling to approximate the worst case behavior of the list-based model, whenever every node perpetually keeps track of the subset of its neighbors which have sent the rumor to it so far.

MSC:

68M12 Network protocols
68Q25 Analysis of algorithms and problem complexity
90B18 Communication networks in operations research

Citations:

Zbl 1192.90024
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahlswede, R.; Haroutunian, H. S.; Khachatrian, L. H., Messy broadcasting in networks, (Communications and Cryptography (1994), Kluwer Academic Publishers), 13-24
[2] Bar-Noy, A.; Guha, S.; Naor, J.; Schieber, B., Multicasting in heterogeneous networks, (Proc. 30th ACM Symp. on the Theory of Computing (STOC) (1998)), 448-453 · Zbl 1028.68013
[3] Berenbrink, P.; Elsässer, R.; Friedetzky, T., Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems, (Proc. 27th ACM Symp. on Principles of Distributed Computing (PODC) (2008)), 155-164 · Zbl 1301.68198
[4] Boyd, S.; Ghosh, A.; Prabhakar, B.; Shah, D., Randomized gossip algorithms, IEEE Trans. Inform. Theory, 52, 6, 2508-2530 (2006) · Zbl 1283.94005
[5] Censor-Hillel, K.; Shachnai, H., Partial information spreading with application to distributed maximum coverage, (Proc. 29th ACM Symp. on Principles of Distributed Computing (PODC) (2010)), 161-170 · Zbl 1315.68007
[6] Chierichetti, F.; Lattanzi, S.; Panconesi, A., Rumour spreading and graph conductance, (Proc. 21st ACM-SIAM Symp. on Discrete Algorithms (SODA) (2010)), 1657-1663 · Zbl 1288.05266
[7] Chierichetti, F.; Lattanzi, S.; Panconesi, A., Almost tight bounds for rumour spreading with conductance, (Proc. 42nd ACM Symp. on Theory of Comp. (STOC) (2010)), 399-408 · Zbl 1293.05358
[8] Costa, P.; Migliavacca, M.; Picco, G. P.; Cugola, G., Epidemic algorithms for reliable content-based publish-subscribe: an evaluation, (Proc. 24th International Conference on Distributed Computing Systems (ICDCS) (2004)), 552-561
[9] Demers, A.; Greene, D.; Hauser, C.; Irish, W.; Larson, J.; Shenker, S.; Sturgis, H.; Swinehart, D.; Terry, D., Epidemic algorithms for replicated database maintenance, (Proc. 6th ACM Symposium on Principles of Distributed Computing (PODC) (1987)), 1-12
[10] Doerr, B.; Friedrich, T.; Sauerwald, T., Quasirandom rumor spreading, (Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA) (2008)), 773-781 · Zbl 1192.90024
[11] Doerr, B.; Friedrich, T.; Sauerwald, T., Quasirandom rumor spreading: expanders, push vs. pull, and robustness, (Proc. 36th Int. Colloq. on Automata, Languages and Programming (ICALP) (2009)), 366-377 · Zbl 1195.68021
[12] Elkin, M.; Kortsarz, G., A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem, SIAM J. Comput., 35, 3, 672-689 (2005) · Zbl 1095.68130
[13] Elkin, M.; Kortsarz, G., Sublogarithmic approximation for telephone multicast: path out of jungle, (Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (SODA) (2003)), 76-85 · Zbl 1094.68515
[14] Elsässer, R., On the communication complexity of randomized broadcasting in random-like graphs, (Proc. 18th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA) (2006)), 148-157
[15] Elsässer, R.; Lorenz, U.; Sauerwald, T., On randomized broadcasting in star graphs, Discrete Appl. Math., 157, 1, 126-139 (2009) · Zbl 1155.90007
[16] Elsässer, R.; Sauerwald, T., Broadcasting vs. mixing and information dissemination on Cayley graphs, (Proc. 24th Symp. on Theoretical Aspects of Computer Science (STACS) (2007)), 163-174 · Zbl 1186.68336
[17] Elsässer, R.; Sauerwald, T., The power of memory in randomized broadcasting, (Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA) (2008)), 218-227 · Zbl 1192.94019
[18] Elsässer, R.; Sauerwald, T., On the runtime and robustness of randomized broadcasting, Theoret. Comput. Sci., 410, 36, 3414-3427 (2009) · Zbl 1206.68362
[19] Feige, U.; Peleg, D.; Raghavan, P.; Upfal, E., Randomized broadcast in networks, (Proc. Int. Symp. on Algorithms (SIGAL). Proc. Int. Symp. on Algorithms (SIGAL), LNCS, vol. 450 (1990), Springer), 128-137
[20] Fountoulakis, N.; Panagiotou, K., Rumor spreading on random regular graphs and expanders, (Proc. 14th Intl. Workshop on Randomization and Comp. (RANDOM) (2010)), 560-573 · Zbl 1305.68136
[21] Fraigniaud, P.; Giakkoupis, G., On the bit communication complexity of randomized rumor spreading, (Proc. 22nd ACM Symp. on Parallel Algorithms and Architectures (SPAA) (2010)), 134-143
[22] Fraigniaud, P.; Lazard, E., Methods and problems of communication in usual networks, Discrete Appl. Math., 53, 79-133 (1994) · Zbl 0818.94029
[23] Frey, D.; Guerraoui, R.; Kermarrec, A.-M.; Monod, M., Boosting gossip for live streaming, (Proc. 10th Int. Conference on Peer-to-Peer Computing (P2P) (2010)), 1-10
[24] Frieze, A.; Grimmett, G., The shortest-path problem for graphs with random arc-lengths, Discrete Appl. Math., 10, 57-77 (1985) · Zbl 0608.05047
[25] Frieze, A.; Molloy, M., Broadcasting in random graphs, Discrete Appl. Math., 54, 77-79 (1994) · Zbl 0811.05061
[26] Giakkoupis, G., Tight bounds for rumor spreading in graphs of a given conductance, (Proc. 28th Int. Symp. on Theoretical Aspects of Computer Science (STACS) (2011)), 57-68 · Zbl 1230.68053
[27] Giakkoupis, G.; Woelfel, P., On the randomness requirements of rumor spreading, (Proc. 22nd ACM-SIAM Symp. on Discrete Algorithms (SODA) (2011)), 449-461 · Zbl 1376.68110
[28] Gupta, I.; Kermarrec, A.-M.; Ganesh, A., Efficient Epidemic-style protocols for reliable and scalable multicast, (Proc. 21st Symp. on Reliable Dist. Syst. (SRDS) (2002)), 180-189
[29] Hart, T.; Harutyunyan, H. A., Improved messy broadcasting in hypercubes and complete bipartite graphs, Congr. Numer., 156, 124-140 (2002) · Zbl 1025.68004
[30] Harutyunyan, H. A.; Hell, P.; Liestman, A. L., Messy broadcasting — decentralized broadcast schemes with limited knowledge, Discrete Appl. Math., 159, 5, 322-327 (2011) · Zbl 1209.05253
[31] Harutyunyan, H. A.; Liestman, A. L., Messy broadcasting, Parallel Process. Lett., 8, 2, 149-159 (1998)
[32] Hedetniemi, S.; Hedetniemi, S.; Liestman, A., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349 (1986) · Zbl 0649.90047
[33] Hromković, J.; Klasing, R.; Monien, B.; Peine, R., Dissemination of information in interconnection networks, (Combinatorial Network Theory (1995), Kluwer Academic), 125-212 · Zbl 0840.68088
[34] Karp, R.; Schindelhauer, C.; Shenker, S.; Vocking, B., Randomized rumor spreading, (Proc. 41st IEEE Symp. on Foundations of Computer Science (FOCS) (2000)), 565-574
[35] Olariu, S., An optimal greedy heuristic to color interval graphs, Inform. Process. Lett., 37, 1, 21-25 (1991) · Zbl 0711.68083
[36] Pittel, B., On spreading a rumour, SIAM J. Appl. Math., 47, 213-223 (1987) · Zbl 0619.60068
[37] Ravi, R., Rapid rumor ramification: approximating the minimum broadcast time, (Proc. 35th Symp. on Foundations of Computer Science (FOCS) (1994)), 202-213
[38] Sauerwald, T., On mixing and edge expansion properties in randomized broadcasting, (Proc. 18th Intl. Symp. on Algorithms and Computation (ISAAC) (2007)), 196-207 · Zbl 1193.68038
[39] Sauerwald, T.; Stauffer, A., Rumor spreading and vertex expansion on regular graphs, (Proc. 22nd ACM-SIAM Symp. on Discrete Algorithms (SODA) (2011)), 462-475 · Zbl 1376.68116
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.