publication . Part of book or chapter of book . Contribution for newspaper or weekly magazine . 2009

Fault Tolerant External Memory Algorithms

Jørgensen, Allan Grønlund; Brodal, Gerth Stølting; Mølhave, Thomas;
Open Access
  • Published: 01 Jan 2009
  • Publisher: Springer Berlin Heidelberg
Abstract
Algorithms dealing with massive data sets are usually designed for I/O-efficiency, often captured by the I/O model by Aggarwal and Vitter. Another aspect of dealing with massive data is how to deal with memory faults, e.g. captured by the adversary based faulty memory RAM by Finocchi and Italiano. However, current fault tolerant algorithms do not scale beyond the internal memory. In this paper we investigate for the first time the connection between I/O-efficiency in the I/O model and fault tolerance in the faulty memory RAM, and we assume that both memory and disk are unreliable. We show a lower bound on the number of I/Os required for any deterministic diction...
Subjects
ACM Computing Classification System: Hardware_MEMORYSTRUCTURES
free text keywords: Sorting algorithm, Page fault, Algorithm, Flat memory model, Upper and lower bounds, Parallel computing, Priority queue, Segmentation fault, Fault tolerance, Computer science, Out-of-core algorithm
Related Organizations
Download fromView all 2 versions
http://www.cs.au.dk/~gerth/pap...
Part of book or chapter of book
Provider: UnpayWall
PURE Aarhus University
Contribution for newspaper or weekly magazine . 2009
http://link.springer.com/conte...
Part of book or chapter of book
Provider: Crossref
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Part of book or chapter of book . Contribution for newspaper or weekly magazine . 2009

Fault Tolerant External Memory Algorithms

Jørgensen, Allan Grønlund; Brodal, Gerth Stølting; Mølhave, Thomas;