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-call it P0-communicating with all other processors. In scattering, P0 sends (possibly) distinct message s to all other processors; in gathering, the other processors send (po ssibly) distinct messages to P0. We consider networks that are trees o f processors. We present algorithms for scattering messages from and g athering messages to the processor that resides at the root of the tre e. The algorithms are: 1) quite general, in that the messages transmit ted can differ arbitrarily in length; 2) quite strong, in that they se nd messages along noncolliding paths, hence do not require any bufferi ng or queuing mechanisms in the processors; and 3) quite efficient: Th e algorithms for scattering in general trees are optimal, the algorith m for gathering in a path is optimal, and the algorithms for gathering in general trees are nearly optimal. Our algorithms can easily be con verted, via the use of spanning trees, to efficient algorithms for sca ttering and gathering in networks of arbitrary topologies.