Home News About Us Contact Contributors Disclaimer Help FAQ

 Display Documents

ID: 518107.0, MPI für Informatik / Algorithms and Complexity Group
How Helpers Hasten h-Relations
Authors:
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2000
Title of Proceedings:Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
Start Page:392
End Page:402
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Saarbrücken, Germany
(Start) Date of Conference/Meeting
(YYYY-MM-DD):
2000
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:
Identifiers:LOCALID:C1256428004B93B8-E294CF768CBC2EE0C12569DD00693B1E-...
ISBN:3-540-41004-X
 The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.