Improving the Computation and Communication Time with Buffers.
Teofilo F. Gonzalez · 2005
We consider the multimessage multicasting over the n processor complete (or fully connected) static network when there are l incoming buffers to each processor. We present an efficient distributed algorithm to route the messages for every degree d problem instance with total communication time d/l + l − 1, where d is the maximum number of messages that each processor may send (or receive). Our algorithm takes linear time with respect to the input length. When l = d our algorithm generates communication schedules with smaller total communication time than previous algorithms, even when forwarding is allowed. Furthermore, such schedules can be constructed in linear time. For l = 1, d/2, and d we present lower bounds for the total communication time. The lower bounds match the upper bounds for the schedules generated by our algorithm when l = 1 and l = d, and are within 25% when l = d/2.