# zbMATH — the first resource for mathematics

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