×

Optimal algorithms for dissemination of information in generalized communication modes. (English) Zbl 0823.68041

Summary: Some generalized communication modes enabling the dissemination of information among processors of interconnection networks via vertex- disjoint or edge-disjoint paths in one communication step will be investigated. A thorough study of these communication modes will be presented by giving optimal algorithms for broadcasting, accumulation and gossiping in most of the well-known parallel architectures. For those networks in which a Hamiltonian path exists (hypercubes, cube connected cycles, butterflies, shuffle exchange, etc.) optimal algorithms can be obtained quite easily, but for complete binary trees, complete \(k\)-ary trees \((k\geq 3)\) and arbitrary degree bounded graphs, the optimal algorithms as well as the matching lower bound proofs are more involved. An interesting consequence of the presented algorithms is the fact that in almost all these interconnection networks the gossip problem cannot be solved in less time than the sum of time complexities of the accumulation problem and the broadcast problem (i.e. for most networks the optimal algorithm for the gossip problem is simply the concatenation of optimal algorithms for accumulation and broadcasting).

MSC:

68Q25 Analysis of algorithms and problem complexity
05C90 Applications of graph theory
68R10 Graph theory (including graph drawing) in computer science
94C15 Applications of graph theory to circuits and networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, B.; Shostak, R., Gossips and telephones, Dissertationes Math., 2, 191-193 (1972) · Zbl 0245.05002
[2] Hajnal, A.; Milner, E. C.; Szemeredi, E., A cure for the telephone disease, Canad. Math. Bull., 15, 447-450 (1972) · Zbl 0251.05132
[3] 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
[4] Even, S.; Monien, B., On the number of rounds necessary to disseminate information, Proceedings of first ACM Symposium on Parallel Algorithms and Architectures, 318-327 (1989)
[5] Hromkovic, J.; Jeschke, C. D.; Monien, B., Optimal algorithms for dissemination of information in some interconnection networks, (Proceedings of fifteenth MFCS’90. Proceedings of fifteenth MFCS’90, Lecture Notes in Computer Science, 452 (1990), Springer: Springer Berlin), 337-346
[6] Bagchi, A.; Hakimi, S. L.; Mitchem, J.; Schmeichel, E., Parallel algorithms for gossiping by mail, Inform. Process Lett., 34, 197-202 (1990) · Zbl 0696.68048
[7] Ben-Asher, Y.; Peleg, D.; Ramaswami, R.; Schuster, A., The power of reconfiguration (1990), The Hebrew University: The Hebrew University Jerusalem, Tech. Rept. · Zbl 0769.68023
[8] Farley, A. M., Minimum-time line broadcast networks, Networks, 10, 59-70 (1980) · Zbl 0432.90030
[9] Dally, W.; Seitz, C., Deadlock free message routing in multiprocessor interconnection networks, IEEE Trans. Comput., C-36, 5, 547-553 (1987) · Zbl 0617.68037
[10] Kermani, P.; Kleinrock, L., Virtual cut-through: A new computer communications switching technique, Comput. Networks, 3, 4, 267-286 (1979) · Zbl 0408.68090
[11] Aiello, B.; Leighton, T.; Maggs, B.; Newman, M., Fast algorithms for bit-serial routing on a hypercube, Proceedings of the second ACM Symposium on Parallel Algorithms and Architectures, 55-64 (1990)
[12] Feldmann, R.; Mysliwietz, P., The shuffle exchange network has a hamiltonian path, (Proceedings of the seventeenth MFCS’92. Proceedings of the seventeenth MFCS’92, Lecture Notes in Computer Science, 629 (1992), Springer: Springer Berlin), 246-254 · Zbl 0861.68006
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.