Scattering and gathering messages in networks of processors

The operations of scattering and gathering in a network of processors involve one processor of the network (P0) communicating with all other processors. In scattering, P0 sends distinct messages to P0. The authors consider networks that are trees of processors. Algorithms for scattering messages from and gathering messages to the processor that resides at the root of the tree are presented. The algorithms are quite general, in that the messages transmitted can differ arbitrarily in length; quite strong, in that they send messages along noncolliding paths, and hence do not require any buffering or queueing mechanisms in the processors; and quite efficient in that algorithms for scattering in general trees are optimal, the algorithm for gathering in a path is optimal and the algorithms for gathering in general trees are nearly optimal. The algorithms can easily be converted using spanning trees to efficient algorithms for scattering and gathering in networks of arbitrary topologies