de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

How Helpers Hasten h-Relations

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.

Item is

### Basic

show hide
Bookmark this item:
Genre: Conference Paper

show Files

show

### Creators

show
hide
Creators:
Sanders, Peter1, Author
Solis-Oba, Roberto1, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, escidoc:24019

### Content

show
hide
Free keywords: -
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.

### Details

show
hide
Language(s): eng - English
Dates: 2010-03-022000
Pages: -
Publishing info: -
Rev. Method: -
Identifiers: eDoc: 518107
Other: Local-ID: C1256428004B93B8-E294CF768CBC2EE0C12569DD00693B1E-Sanders2000a
Degree: -

### Event

show
hide
Title: Untitled Event
Place of Event: Saarbrücken, Germany
Start-/End Date: 2000 -

show

### Source 1

show
hide
Title: Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
Source Genre: Proceedings
Creator(s):
Paterson, Mike, Editor
Affiliations:
-
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 392 - 402 Identifier: ISBN: 3-540-41004-X

### Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
Creator(s):
-
Affiliations:
-
Publ. Info: -
Pages: - Volume / Issue: 1879 Sequence Number: - Start / End Page: - Identifier: -