How helpers hasten h-relations

We study the problem of exchanging a set of messages among a group of proce ssors, where messages may consist of different numbers of packets. We consi der the model of half-duplex communication. Let It denote the maximum numbe r of packets that a processor must send and receive. If all the packets nee d to be delivered directly, at least 3/2 h communication steps are needed t o solve the problem in the worst case. We show that by allowing forwarding, only 6/5 h + O(1) time steps are needed to exchange all the messages, and this is optimal. Our work was motivated by the importance of irregular mess age exchanges in distributed-memory parallel computers, but it can also be viewed as an answer to an open problem on scheduling file transfers posed b y Coffmann et al. in 1985 Saim J. Comput. 14, No. 3 (1985), 744-780). (C) 2 001 Academic Press.