Harutyunyan, Hovhannes A.; Hell, Pavol; Liestman, Arthur L. Messy broadcasting - decentralized broadcast schemes with limited knowledge. (English) Zbl 1209.05253 Discrete Appl. Math. 159, No. 5, 322-327 (2011). Summary: We consider versions of broadcasting that proceed in the absence of information about the network. In particular, the vertices of the network do not know the structure of the network or the starting time, originator, or state of the broadcast. Furthermore, the protocols are not coordinated. This synchronous anonymous communication model has been called messy broadcasting. We perform a worst case analysis of three variants of messy broadcasting. These results also provide upper bounds on broadcasting where every vertex simply calls each of its neighbors once in random order. We prove exact bounds on the time required for broadcasting under two variants and give a conjectured value for the third. Cited in 1 Document MSC: 05C90 Applications of graph theory 05C05 Trees Keywords:broadcasting; messy model; upper bound; trees PDFBibTeX XMLCite \textit{H. A. Harutyunyan} et al., Discrete Appl. Math. 159, No. 5, 322--327 (2011; Zbl 1209.05253) Full Text: DOI References: [1] Ahlswede, R.; Harutounian, H.; Khachatrian, L. H., Messy broadcasting in networks, (Blahut, R. E.; Costello, D. J.; Maurer, U.; Mittelholzer, T., Communications and Cryptography (1994), Kluwer Academic: Kluwer Academic Boston, Dordrecht, London), 13-24 [2] Awerbuch, B.; Goldreich, O.; Peleg, D.; Vainish, R., A trade-off between information and communication in broadcast protocols, Journal of the ACM, 37, 238-256 (1990) · Zbl 0696.68020 [3] Bermond, J.-C.; Ferreira, A.; Pérennès, S.; Peters, J. G., Neighborhood broadcasting in hypercubes, SIAM Journal on Discrete Mathematics, 21, 823-843 (2008) · Zbl 1178.94008 [4] Comellas, F.; Harutyunyan, H. A.; Liestman, A. L., Messy broadcasting in mesh and torus networks, Journal of Interconnection Networks, 4, 37-51 (2003) [5] De Marco, G.; Pelc, A., Deterministic broadcasting time with partial knowledge of the network, Theoretical Computer Science, 290, 2009-2020 (2003) · Zbl 1044.68019 [6] B. Doerr, T. Friedrich, T. Sauerwald, Quasirandom rumor spreading, in: Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 773-781.; B. Doerr, T. Friedrich, T. Sauerwald, Quasirandom rumor spreading, in: Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 773-781. · Zbl 1192.90024 [7] Elkin, M.; Kortsarz, G., A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem, SIAM Journal on Computing, 35, 672-689 (2006) · Zbl 1095.68130 [8] Elsässer, R.; Lorenz, U.; Sauerwald, T., On randomized broadcasting in star graphs, Discrete Applied Mathematics, 157, 126-139 (2009) · Zbl 1155.90007 [9] Feige, U.; Peleg, D.; Raghavan, P.; Upfal, E., Randomized broadcast in networks, Random Structures and Algorithms, 1, 447-460 (1990) · Zbl 0712.68011 [10] Flammini, M.; Pérennès, S., On the optimality of general lower bounds for broadcasting and gossiping, Discrete Applied Mathematics, C-53, 267-282 (2001) · Zbl 0968.68003 [11] P. Fraigniaud, D. Ilcinkas, A. Pelc, Oracle size: a new measure of difficulty for communication tasks, in: Proc. 25th Annual ACM Symposium on Principles of Distributed Computing, PODC’06, 2006, pp. 179-187.; P. Fraigniaud, D. Ilcinkas, A. Pelc, Oracle size: a new measure of difficulty for communication tasks, in: Proc. 25th Annual ACM Symposium on Principles of Distributed Computing, PODC’06, 2006, pp. 179-187. · Zbl 1314.68023 [12] Fraigniaud, P.; Lazard, E., Methods and problems of communication in usual networks, SIAM Journal on Discrete Mathematics, 14, 79-133 (1994) · Zbl 0818.94029 [13] Frieze, A. M.; Grimmett, G. R., The shortest-path problem for graphs with random-arc-lengths, Discrete Applied Mathematics, 10, 57-77 (1985) · Zbl 0608.05047 [14] Gargano, L.; Pelc, A.; Pérennès, S.; Vaccaro, U., Efficient communication in unknown networks, Networks, 38, 39-49 (2001) · Zbl 1014.90014 [15] Hart, T.; Harutyunyan, H. A., Improved messy broadcasting in hypercubes and complete bipartite graphs, Congressus Numerantium, 156, 124-140 (2002) · Zbl 1025.68004 [16] Harutyunyan, H. A.; Liestman, A. L., Messy broadcasting, Parallel Processing Letters, 8, 149-159 (1998) [17] Hedetniemi, S. M.; Hedetniemi, S. T.; Liestman, A. L., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349 (1988) · Zbl 0649.90047 [18] Hromkovič, J.; Klasing, R.; Monien, B.; Peine, R., Dissemination of information in interconnection networks (broadcasting and gossiping), (Du, D.-Z.; Hsu, D. F., Combinatorial Network Theory (1995), Kluwer: Kluwer Dordrecht, Netherlands), 125-212 · Zbl 0840.68088 [19] Hromkovič, J.; Klasing, R.; Pelc, A.; Ružička, P.; Unger, W., Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance (2005), Springer: Springer Berlin · Zbl 1067.68016 [20] R.M. Karp, C. Schindelhauer, S. Shenker, B. Vocking, Randomized rumor spreading, in: Proc. 41st Ann. Symp. on Foundations of Comp. Sci. 2000, pp. 565-574.; R.M. Karp, C. Schindelhauer, S. Shenker, B. Vocking, Randomized rumor spreading, in: Proc. 41st Ann. Symp. on Foundations of Comp. Sci. 2000, pp. 565-574. [21] Li, C.; Hart, T.; Henry, K.; Neufeld, I., Average-case messy broadcasting, Journal of Interconnection Networks, 9, 487-505 (2008) [22] Pittel, B., On spreading a rumor, SIAM Journal on Applied Mathematics, 47, 1, 213-223 (1987) · Zbl 0619.60068 [23] Raghavendra, C. S.; Sridhar, M. A., Exact solutions to diameter and routing problems in PEC networks, Journal of Parallel and Distributed Computing, 34, 202-210 (1996) [24] D. Richards, Z. Jia, The structure of PEC networks, in: Proc. Combinatorial and Algorithmic Aspects of Networking, 2005.; D. Richards, Z. Jia, The structure of PEC networks, in: Proc. Combinatorial and Algorithmic Aspects of Networking, 2005. · Zbl 1205.68053 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.