# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### How Helpers Hasten h-Relations

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Sanders, P., & Solis-Oba, R. (2000). How Helpers Hasten h-Relations. In M. Paterson
(*Algorithms - ESA 2000, Proceedings of the 8th Annual
European Symposium (ESA-00)* (pp. 392-402). Berlin, Germany: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-33BA-9

##### Abstract

We study the problem of exchanging a set of messages among a group of
processors, using the model of simplex communication.
Messages may consist of different numbers of packets. Let $\Lmax$
denote the maximum number of packets that a processor must send and
receive. If all the packets need to be delivered directly, at least
$\frac{3}{2}\Lmax$ communication steps are needed to solve the problem
in the worst case. We show that by allowing forwarding, only
$\frac{6}{5}\Lmax + \Oh{1}$ time steps are needed to exchange all the
messages, and this is optimal. Our work was motivated by the
importance of irregular message exchanges in distributed-memory
parallel computers, but it can also be viewed as an answer to an open
problem on scheduling file transfers posed by Coffmann, Garey,
Johnsson, and LaPaugh in 1985.