MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Sanders, Peter
Solis-Oba, Roberto		dblp
dblp
Editor(s):
Paterson, Mikedblp
BibTeX cite key*:
Sanders2000a
Title, Booktitle
Title*:
How Helpers Hasten h-Relations
Booktitle*:
Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
Event, URLs
Conference URL::
http://www.mpi-sb.mpg.de/~conf2000/esa2000/
Downloading URL:
Event Address*:
Saarbrücken, Germany
Language:
English
Event Date*
(no longer used):
September, 5-8
Organization:
Event Start Date:
2 April 2023
Event End Date:
2 April 2023
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1879
Number:
Month:
Pages:
392-402
Year*:
2000
VG Wort Pages:
21
ISBN/ISSN:
3-540-41004-X
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Keywords:
communication, parallel processing, matching
HyperLinks / References / URLs:
http://www.mpi-sb.mpg.de/~sanders/papers/index.html
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Sanders2000a,
AUTHOR = {Sanders, Peter and Solis-Oba, Roberto},
 EDITOR = {Paterson, Mike},
 TITLE = {How Helpers Hasten h-Relations},
 BOOKTITLE = {Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)},
 PUBLISHER = {Springer},
 YEAR = {2000},
 VOLUME = {1879},
 PAGES = {392--402},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Saarbr{\"u}cken, Germany},
 ISBN = {3-540-41004-X},
}

Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Peter Sanders		Created
01/23/2001 20:09:24
Revisions
5.
4.
3.
2.
1.		Editor(s)
Uwe Brahm
Anja Becker
Anja Becker
Anja Becker
Anja Becker		Edit Dates
04/10/2001 06:08:30 PM
20.03.2001 16:59:16
14.03.2001 12:58:10
14.03.2001 12:56:42
23/01/2001 20:36:30