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
|
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.
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Uncontrolled Keywords: | Combinatorial algorithms; Sorting; Searching; Memory faults; Memory models; Computing with unreliable information |
| Subjects: | Computer sciences |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 14 Mar 2014 09:01 |
| Last Modified: | 23 May 2016 14:48 |
| URI: | http://repository.supsi.ch/id/eprint/4500 |
Actions (login required)
 |
View Item |