Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse




Conference Paper

How Helpers Hasten h-Relations


Sanders,  Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Solis-Oba,  Roberto
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

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

Cite as:
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.