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

dblp



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

URL of the conference:


URL for downloading the paper:

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:

17 September 2019

Event End Date:

17 September 2019

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
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/21/2002 04:11:32 PM
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