Sorting and searching in the presence of memory faults (without redundancy)

Abstract

We investigate the design of algorithms resilient to memory faults, i. e., algorithms that, despite the corruption of some memory values during their execution, are able to produce a correct output on the set of uncorrupted values. In this framework, we consider two fundamental problems: sorting and searching. In particular, we prove that any O(nlog n) comparison-based sorting algorithm can tolerate at most O((nlog n)1/2) memory faults. Furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to O((nlog n)1/3) faults. We also prove polylogarithmic lower and upper bounds on fault-tolerant searching.