Optimal resilient sorting and searching in the presence of memory faults

Finocchi, Irene and Grandoni, Fabrizio and Italiano, Giuseppe F. (2009) Optimal resilient sorting and searching in the presence of memory faults. Theoretical Computer Science, 410 (44). pp. 4457-4470. ISSN 0304-3975

[img]
Preview
Text
1-s2.0-S0304397509005003-main.pdf - Accepted Version

Download (1MB) | Preview

Abstract

We investigate the problem of reliable computation in the presence of faults that may arbitrarily corrupt memory locations. In this framework, we consider the problems of sorting and searching in optimal time while tolerating the largest possible number of memory faults. In particular, we design an O(nlogn)O(nlogn) time sorting algorithm that can optimally tolerate up to View the MathML sourceO(nlogn) memory faults. In the special case of integer sorting, we present an algorithm with linear expected running time that can tolerate View the MathML sourceO(n) faults. We also present a randomized searching algorithm that can optimally tolerate up to O(logn)O(logn) memory faults in O(logn)O(logn) expected time, and an almost optimal deterministic searching algorithm that can tolerate O((logn)1−ϵ)O((logn)1−ϵ) faults, for any small positive constant ϵϵ, in O(logn)O(logn) worst-case time. All these results improve over previous bounds.

Actions (login required)

View Item View Item