In this paper we investigate the design and analysis of algorithms resilient to memory faults. We focus on algorithms that, despite the corruption of some memory values during their execution, are nevertheless able to produce a correct output at least 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 the corruption of at most O((nlog∈n) 1/2) keys. Furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to O((nlog∈n) 1/3) memory faults. We also prove polylogarithmic lower and upper bounds on resilient searching. © 2007 Springer Science+Business Media, LLC.
Sorting and searching in faulty memories / Finocchi, Irene; Giuseppe F., Italiano. - In: ALGORITHMICA. - ISSN 0178-4617. - STAMPA. - 52:3(2008), pp. 309-332. [10.1007/s00453-007-9088-4]
Sorting and searching in faulty memories
FINOCCHI, Irene;
2008
Abstract
In this paper we investigate the design and analysis of algorithms resilient to memory faults. We focus on algorithms that, despite the corruption of some memory values during their execution, are nevertheless able to produce a correct output at least 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 the corruption of at most O((nlog∈n) 1/2) keys. Furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to O((nlog∈n) 1/3) memory faults. We also prove polylogarithmic lower and upper bounds on resilient searching. © 2007 Springer Science+Business Media, LLC.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
