Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Sanders, Peter
Solis-Oba, Roberto

dblp
dblp



Editor(s):

Paterson, Mike

dblp



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

URL of the conference:

http://www.mpi-sb.mpg.de/~conf2000/esa2000/

URL for downloading the paper:


Event Address*:

Saarbrücken, Germany

Language:

English

Event Date*
(no longer used):

September, 5-8

Organization:


Event Start Date:

8 December 2019

Event End Date:

8 December 2019

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 08:09:24 PM
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