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.
2008
combinatorial algorithms; computing with unreliable information; memory faults; memory models; searching; sorting
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

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: https://hdl.handle.net/11573/132711
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 17
social impact