de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

#### How Helpers Hasten h-Relations

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45344

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45136

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

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Sanders, P., & Solis-Oba, R. (2001). How Helpers Hasten h-Relations. Journal of Algorithms, 41, 86-98. Retrieved from http://www.idealibrary.com/servlet/doi/10.1006/jagm.2001.1169.

We study the problem of exchanging a set of messages among a group of processors, where messages may consist of different numbers of packets. We consider the model of half-duplex communication. 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.