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.

Sorting and searching in faulty memories / Finocchi, I.; Italiano, G. - In: ALGORITHMICA. - ISSN 0178-4617. - 52:3(2008), pp. 309-332. [10.1007/s00453-007-9088-4]

Sorting and searching in faulty memories

I. FINOCCHI;ITALIANO G
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.
Sorting and searching in faulty memories / Finocchi, I.; Italiano, G. - In: ALGORITHMICA. - ISSN 0178-4617. - 52:3(2008), pp. 309-332. [10.1007/s00453-007-9088-4]
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/193024
Citazioni
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 17
social impact