Fault Tolerant External Memory Algorithms

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

In Proc. 11th International Workshop on Algorithms and Data Structures, volume 5664 of Lecture Notes in Computer Science, pages 411-422. Springer Verlag, Berlin, 2009.

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 dictionary that is resilient to memory faults. We design a static and a dynamic deterministic dictionary with optimal query performance as well as an optimal sorting algorithm and an optimal priority queue. Finally, we consider scenarios where only cells in memory or only cells on disk are corruptible and separate randomized and deterministic dictionaries in the latter.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2009. All rights reserved.

Online version

wads09.pdf (159 Kb)

DOI

10.1007/978-3-642-03367-4_36

Links

BIBTEX entry

@incollection{wads09,
  author = "Gerth St{\o}lting Brodal and Allan Gr{\o}nlund J{\o}rgensen and Thomas M{\o}lhave",
  booktitle = "Proc. 11th International Workshop on Algorithms and Data Structures",
  doi = "10.1007/978-3-642-03367-4_36",
  isbn = "978-3-642-03366-7",
  pages = "411-422",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Fault Tolerant External Memory Algorithms",
  volume = "5664",
  year = "2009"
}