R. Feldmann et al., OPTIMAL-ALGORITHMS FOR DISSEMINATION OF INFORMATION IN GENERALIZED COMMUNICATION MODES, Discrete applied mathematics, 53(1-3), 1994, pp. 55-78
Some generalized communication modes enabling the dissemination of inf
ormation among processors of interconnection networks via vertex-disjo
int or edge-disjoint paths in one communication step will be investiga
ted. A thorough study of these communication modes will be presented b
y giving optimal algorithms for broadcasting, accumulation and gossipi
ng in most of the well-known parallel architectures. For those network
s in which a Hamiltonian path exists (hypercubes, cube connected cycle
s, butterflies, shuffle exchange, etc.) optimal algorithms can be obta
ined quite easily, but for complete binary trees, complete k-ary trees
(k greater-than-or-equal-to 3) and arbitrary degree bounded graphs, t
he optimal algorithms as well as the matching lower bound proofs are m
ore involved. An interesting consequence of the presented algorithms i
s the fact that in almost all these interconnection networks the gossi
p problem cannot be solved in less time than the sum of time complexit
ies of the accumulation problem and the broadcast problem (i.e. for mo
st networks the optimal algorithm for the gossip problem is simply the
concatenation of optimal algorithms for accumulation and broadcasting
).