×

Lower bounds on systolic gossip. (English) Zbl 1105.68006

Summary: Gossiping is an extensively investigated information dissemination process in which each processor has a distinct item of information and has to collect all the items possessed by the other processors. In this paper we provide an innovative and general lower bound technique relying on the novel notion of delay digraph of a gossiping protocol and on the use of matrix norm methods. Such a technique is very powerful and allows the determination of new and significantly improved lower bounds in many cases. In fact, we derive the first general lower bound on the gossiping time of systolic protocols, i.e., constituted by a periodic repetition of simple communication steps. In particular, given any network of \(n\) processors and any systolic period \(s\), in the directed and the undirected half-duplex cases every \(s\)-systolic gossip protocol takes at least \(\log (n)/\log (1/\lambda) - O (\log \log(n))\) time steps, where \(\lambda\) is the unique solution between 0 and 1 of \(\lambda \cdot \sqrt{p_{\lfloor s/2 \rfloor}(\lambda)} \cdot \sqrt{p_{\lceil s/2 \rceil}(\lambda)}=1\), with \(p_i (\lambda) = 1 + \lambda^2 + \cdots + \lambda^{2i - 2}\) for any integer \(i > 0\). We then provide improved lower bounds in the directed and half-duplex cases for many well-known network topologies, such as Butterfly, de Bruijn, and Kautz graphs.
All the results are extended also to the full-duplex case. Our technique is very general, as for \(s \to \infty\) it allows the determination of improved results even for non-systolic protocols. In fact, for general networks, as a simple corollary it yields a lower bound only an \(O (\log \log(n))\) additive factor far from the general one independently proved in [S. Even and B. Monien, Proc. 1st ACM Symposium on Parallel Algorithms and Architectures (SPAA), 318–327 (1989); D. W. Krumme, G. Cybenko and K. N. Venkataraman, SIAM J. Comput. 21, 111–139 (1992; Zbl 0743.68039); V. S. Sunderam and P. Winkler, Discrete Appl. Math. 42, 75–86 (1993; Zbl 0797.68005)] for all graphs and any (non-systolic) gossip protocol. Moreover, for specific networks, it significantly improves with respect to the previously known results, even in the full-duplex case. Correspondingly, better lower bounds on the gossiping time of non-systolic protocols are determined in the directed, half-duplex and full-duplex cases for Butterfly, de Bruijn, and Kautz graphs. Even if in this paper we give only a limited number of examples, our technique has wide applicability and gives a general framework that often allows to get improved lower bounds on the gossiping time of systolic and non-systolic protocols in the directed, half-duplex and full-duplex cases.

MSC:

68M14 Distributed systems
68M12 Network protocols
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Berman, R. Plemmons, Nonnegative matrices in the mathematical science, Classics in Applied Mathematics, SIAM, 1994.; A. Berman, R. Plemmons, Nonnegative matrices in the mathematical science, Classics in Applied Mathematics, SIAM, 1994. · Zbl 0815.15016
[2] Bermond, J.; Hell, P.; Liestman, A.; Peters, J., Broadcasting in bounded degree graphs, SIAM Journal on Discrete Mathematics, 5, 1, 10-24 (1992) · Zbl 0753.68007
[3] de Rumeur, J., Communication dans les réseaux de processeurs (1994), Collection Etudes et Recherches en Informatique: Collection Etudes et Recherches en Informatique Masson, (English version to appear)
[4] S. Even, B. Monien, On the number of rounds necessary to disseminate information, in: Proc. 1st ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1989, pp. 318-327.; S. Even, B. Monien, On the number of rounds necessary to disseminate information, in: Proc. 1st ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1989, pp. 318-327.
[5] Flammini, M.; Pérennès, S., On the optimality of general lower bounds for broadcasting and gossiping, SIAM Journal on Discrete Mathematics, 14, 2, 267-282 (2001) · Zbl 0968.68003
[6] Fraigniaud, P.; Lazard, E., Methods and problems of communication in usual networks, Discrete Applied Mathematics, 53, 1-3, 79-133 (1994) · Zbl 0818.94029
[7] Hedetniemi, S.; Hedetniemi, S.; Liestman, A., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349 (1986) · Zbl 0649.90047
[8] Hromkovič, J.; Klasing, R.; Pardubská, D.; Unger, W.; Wagener, H., The complexity of systolic dissemination of information in interconnection networks, R.A.I.R.O. Theoretical Informatics and Applications, 28, 3-4, 303-342 (1994) · Zbl 0888.68014
[9] Hromkovič, J.; Klasing, R.; Monien, B.; Peine, R., Dissemination of information in interconnection networks (broadcasting and gossiping), (Du, Ding-Zhu; Frank Hsu, D., Combinatorial Network Theory (1995), Kluwer Academic Publishers), 125-212 · Zbl 0840.68088
[10] Hromkovič, J.; Klasing, R.; Stohr, E.; Wagener, H., Gossiping in vertex-disjoint paths mode in d-dimensional grids and planar graphs, Information and Computation, 123, 1, 17-28 (1995) · Zbl 1096.68514
[11] J. Hromkovič, R. Klasing, D. Pardubská, W. Unger, J. Waczulik, H. Wagener, Effective systolic algorithms for gossiping in cycles and two-dimensional grids, in: Proc. 10th Conference on Fundamentals of Computation Theory (FCT), Vol. 965 of Lecture Notes in Computer Science, Springer-Verlag, 1995, pp. 273-282; J. Hromkovič, R. Klasing, D. Pardubská, W. Unger, J. Waczulik, H. Wagener, Effective systolic algorithms for gossiping in cycles and two-dimensional grids, in: Proc. 10th Conference on Fundamentals of Computation Theory (FCT), Vol. 965 of Lecture Notes in Computer Science, Springer-Verlag, 1995, pp. 273-282
[12] Hromkovič, J.; Klasing, R.; Unger, W.; Wagener, H., Optimal algorithms for broadcast and gossip in the edge-disjoint path modes, Information and Computation, 133, 1, 1-33 (1997) · Zbl 0878.68070
[13] Klasing, R.; Monien, B.; Peine, R.; Stohr, E., Broadcasting in butterfly and de Bruijn networks, Discrete Applied Mathematics, 53, 1-3, 183-197 (1994) · Zbl 0807.94035
[14] Kortsarz, G.; Peleg, D., Traffic-light scheduling on the grid, Discrete Applied Mathematics, 53, 1-3, 211-234 (1994) · Zbl 0810.90036
[15] Krumme, D. W.; Cybenko, G.; Venkataraman, K. N., Gossiping in minimal time, SIAM Journal on Computing, 21, 1, 111-139 (1992) · Zbl 0743.68039
[16] Kung, H., Let’s design algorithms for VLSI systems, (Seifz, C. L.L., Proceedings of the Caltech Conference of VLSI (1979), Pasadena: Pasadena California), 65-90
[17] Labahn, R.; Warnke, I., Quick gossiping by multi-telegraphs, Topics in Combinatorics and Graph Theory, 451-458 (1990) · Zbl 0749.05061
[18] Labahn, R.; Hedetniemi, S.; Laskar, R., Periodic gossiping on trees, Discrete Applied Mathematics, 53, 1-3, 235-246 (1994) · Zbl 0836.68085
[19] Leighton, T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees (1992), Hypercubes: Hypercubes Morgan Kaufman · Zbl 0743.68007
[20] Liestman, A.; Richards, D., Network communication in edge-colored graphs: gossiping, IEEE Transactions on Parallel and Distributed Systems, 4, 438-445 (1993)
[21] Liestman, A.; Richards, D., Perpetual gossiping, Parallel Processing Letters, 3, 4, 347-355 (1993)
[22] Liestman, A.; Peters, J., Broadcast networks of bounded degree, SIAM Journal on Discrete Mathematics, 1, 4, 531-540 (1998) · Zbl 0662.94027
[23] S. Pérennès, Lower bounds on broadcasting time of de Bruijn networks, in: Proc. 2nd Int. Euro-Par Conference, Vol. 1123 of Lecture Notes in Computer Science, Springer-Verlag, 1996, pp. 325-332; S. Pérennès, Lower bounds on broadcasting time of de Bruijn networks, in: Proc. 2nd Int. Euro-Par Conference, Vol. 1123 of Lecture Notes in Computer Science, Springer-Verlag, 1996, pp. 325-332
[24] S. Pérennès, Communications dans les réseaux d’interconnexion, Ph.D. thesis, Université de Nice—Sophia Antipolis, Laboratoire d’Informatique, Signaux et Systèmes de Sophia Antipolis CNRS URA 1376, 1996; S. Pérennès, Communications dans les réseaux d’interconnexion, Ph.D. thesis, Université de Nice—Sophia Antipolis, Laboratoire d’Informatique, Signaux et Systèmes de Sophia Antipolis CNRS URA 1376, 1996
[25] Pérennès, S., Broadcasting and gossiping on de Bruijn, shuffle-exchange and similar networks, Discrete Applied Mathematics, 83, 247-262 (1998) · Zbl 0907.90137
[26] Sunderam, V.; Winkler, P., Fast information sharing in a complete network, Discrete Applied Mathematics, 42, 75-86 (1993) · Zbl 0797.68005
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.