MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Sanders, Peter
Egner, Sebastian
Korst, Jan		dblp
dblp
dblp
Editor(s):
BibTeX cite key*:
SanEgnKor2000
Title, Booktitle
Title*:
Fast Concurrent Access to Parallel Disks
Booktitle*:
Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-00)
Event, URLs
Conference URL::
http://www.siam.org/meetings/da00/
Downloading URL:
Event Address*:
San Francisco, USA
Language:
English
Event Date*
(no longer used):
January 9-11
Organization:
Association of Computing Machinery (ACM)
Event Start Date:
4 October 2023
Event End Date:
4 October 2023
Publisher
Name*:
ACM Press
URL:
http://www.acm.org/
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
849-858
Year*:
2000
VG Wort Pages:
45
ISBN/ISSN:
0-89871-453-2
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
High performance applications involving large data sets require the
efficient and flexible use of multiple disks. In an external memory
machine with $D$ parallel, independent disks, only one block can be
accessed on each disk in one I/O step. This restriction leads to a
load balancing problem that is perhaps the main inhibitor for adapting
single-disk external memory algorithms to multiple disks. This paper
shows that this problem can be solved efficiently using a combination
of randomized placement, redundancy and an optimal scheduling
algorithm. A buffer of $\Ohh{D}$ blocks suffices to support efficient
writing of arbitrary blocks if blocks are distributed uniformly at
random to the disks (e.g., by hashing). If two randomly allocated
copies of each block exist, $N$ arbitrary blocks can be read within
$\ceil{N/D}+1$ I/O steps with high probability. In addition, the
redundancy can be reduced from $2$ to $1+1/r$ for any integer $r$.
%Using appropriate codes even multiple disk %failures can be tolerated
with low redundancy. These results can be used to emulate the simple
and powerful ``single-disk multi-head'' model of external computing
\cite{AggVit88} on the physically more realistic independent disk
model \cite{VitShr94} with small constant overhead. This is faster
than a lower bound for deterministic emulation \cite{Arm96}.
Keywords:
parallel disks, scheduling, storage systems, maximum flow, randomized algorithm
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{SanEgnKor2000,
AUTHOR = {Sanders, Peter and Egner, Sebastian and Korst, Jan},
 TITLE = {Fast Concurrent Access to Parallel Disks},
 BOOKTITLE = {Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-00)},
 PUBLISHER = {ACM Press},
 YEAR = {2000},
 ORGANIZATION = {Association of Computing Machinery (ACM)},
 PAGES = {849--858},
 ADDRESS = {San Francisco, USA},
 ISBN = {0-89871-453-2},
}

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:46:46
Revisions
5.
4.
3.
2.
1.		Editor(s)
Uwe Brahm
Anja Becker
Anja Becker
Anja Becker
Anja Becker		Edit Dates
05/02/2001 11:19:13 AM
20.03.2001 17:21:55
14.03.2001 12:49:21
14.03.2001 12:48:25
14.03.2001 12:46:24