MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Sanders, Peterdblp
Editor(s):
BibTeX cite key*:
San2001a
Title, Booktitle
Title*:
Reconciling Simplicity and Realism in Parallel Disk Models
Booktitle*:
Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01)
Event, URLs
Conference URL::
Downloading URL:
http://www.mpi-sb.mpg.de/~sanders/papers/
Event Address*:
Waschington DC, USA
Language:
English
Event Date*
(no longer used):
January 7- January 9
Organization:
ACM, SIAM
Event Start Date:
3 October 2023
Event End Date:
3 October 2023
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
January
Pages:
67-76
Year*:
2001
VG Wort Pages:
36
ISBN/ISSN:
0-89871-490-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
For the design and analysis of algorithms that process huge data sets,
a machine model is needed that handles parallel disks. There seems to
be a dilemma between simple and flexible use of such a model and
accurate modelling of details of the hardware. This paper explains
how many aspects of this problem can be resolved. The programming
model implements one large logical disk allowing concurrent access to
arbitrary sets of variable size blocks. This model can be implemented
efficienctly on multiple independent disks even if zones with
different speed, communication bottlenecks and failed disks are
allowed. These results not only provide useful algorithmic tools but
also imply a theoretical justification for studying external memory
algorithms using simple abstract models.

The algorithmic approach is random redundant placement of data and
optimal scheduling of accesses. The analysis generalizes a previous
analysis for simple abstract external memory models in several ways
(Higher efficiency, variable block sizes, more detailed disk model).
As a side effect, an apparently new Chernoff bound for sums of
weighted 0-1 random variables is derived.
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, VG Wort



BibTeX Entry:

@INPROCEEDINGS{San2001a,
AUTHOR = {Sanders, Peter},
 TITLE = {Reconciling Simplicity and Realism in Parallel Disk Models},
 BOOKTITLE = {Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01)},
 PUBLISHER = {ACM},
 YEAR = {2001},
 ORGANIZATION = {ACM, SIAM},
 PAGES = {67--76},
 ADDRESS = {Waschington DC, USA},
 MONTH = {January},
 ISBN = {0-89871-490-7},
}

Entry last modified by Anja Becker, 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/21/2002 16:11:32
Revisions
4.
3.
2.
1.
0.		Editor(s)
Anja Becker
Anja Becker
Peter Sanders
Peter Sanders
Peter Sanders		Edit Dates
22.03.2002 13:26:40
22.03.2002 13:17:35
21/01/2002 16:23:43
21/01/2002 16:23:04
21/01/2002 16:11:33