Dissemination of Information in Vertex-Disjoint Paths Mode

Abstract

The communication modes (one-way and two-way mode) used for disseminating information among processors of interconnection networks via vertex-disjoint paths in the communication step are investigated. The complexity of communication algorithms is measured by the number of communication steps (rounds). Since optimal broadcast and accumulation algorithms for these modes can be achieved in a straightforward way for almost all interconnection networks used, the paper concentrates on the gossip problem. The main results are listed below:
1.    Optimal gossip algorithms for paths, complete graphs and flakes in both modes.
2.    For hypercubes, cube-connected cycles, butterfly networks, etc., gossip algorithms which are only about O (log2log2n) rounds slower than the optimal gossip algorithms on complete graphic are designed.
Note that the results achieved have also practical applications, because the vertex/disjoint paths mode can be implemented in several hardware realisations of computing networks.