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
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

URL of the conference:

http://www.siam.org/meetings/da00/

URL for downloading the paper:


Event Address*:

San Francisco, USA

Language:

English

Event Date*
(no longer used):

January 9-11

Organization:

Association of Computing Machinery (ACM)

Event Start Date:

16 October 2019

Event End Date:

16 October 2019

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
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:46:46 PM
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