Communication in the two-way listen-in vertex-disjoint paths mode

AbstractA new communication mode for the dissemination of information among processors of interconnection networks via vertex-disjoint paths is introduced and investigated. In this communication mode, in one communication step two processors communicating via a path P send their pieces of information to all other processors on this path, too. The complexity of a communication algorithm is measured by the number of communication steps (rounds). In this paper we will design optimal broadcast, accumulation, and gossip algorithms for various classes of networks including paths, cycles, and hypercube-like networks. The main results are optimal accumulation and gossip algorithms for the two-dimensional grid. The technique used for the design of these algorithms is based on finding Hamiltonian paths in the grid with certain endpoints or center points