Paper Info
Title
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 one 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 call 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(log(2) log(2) n) rounds slower than the optimal gossip algorithms on complete graphs are designed. Note that the results achieved have also practical applications, because the vertex-disjoint paths mode carl be implemented in several hardware realisations of computing networks.
Year
Venue
Keywords
1996
COMPUTERS AND ARTIFICIAL INTELLIGENCE
communication algorithms,parallel computations
Field
DocType
Volume
Broadcasting,Complete graph,Disjoint sets,Vertex (geometry),Computer science,Gossip,Theoretical computer science,Dissemination,Gossip protocol,Hypercube
Journal
15
Issue
ISSN
Citations 
4
0232-0274
9
PageRank 
References 
Authors
0.62
0
3
Name
Order
Citations
PageRank
Juraj Hromkovic160276.02
Ralf Klasing286654.83
Elena Stöhr3649.52