We investigate the problem of computing in a reliable fashion in the presence of faults that may arbitrarily corrupt memory locations. In this framework, we focus on the design of resilient data structures, i.e., data structures that, despite the corruption of some memory values during their lifetime, are nevertheless able to operate correctly (at least) on the set of uncorrupted values. In particular, we present resilient search trees which achieve optimal time and space bounds while tolerating up to O(√log n) memory faults, where n is the current number of items in the search tree. In more detail, our resilient search trees are able to insert, delete and search for a key in O(log n + δ2) amortized time, where δ is an upper bound on the total number of faults. The space required is O(n + δ). Copyright © 2007 by the Association for Computing Machinery, Inc. and the Society for Industrial and Applied Mathematics.

Resilient Search Trees / Finocchi, Irene; Grandoni, Fabrizio; G. F., Italiano. - STAMPA. - 07-09-January-2007:(2007), pp. 547-555. (Intervento presentato al convegno 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 tenutosi a New Orleans; United States nel January 7-9, 2007) [10.1145/1283383.1283442].

Resilient Search Trees

FINOCCHI, Irene;GRANDONI, FABRIZIO;
2007

Abstract

We investigate the problem of computing in a reliable fashion in the presence of faults that may arbitrarily corrupt memory locations. In this framework, we focus on the design of resilient data structures, i.e., data structures that, despite the corruption of some memory values during their lifetime, are nevertheless able to operate correctly (at least) on the set of uncorrupted values. In particular, we present resilient search trees which achieve optimal time and space bounds while tolerating up to O(√log n) memory faults, where n is the current number of items in the search tree. In more detail, our resilient search trees are able to insert, delete and search for a key in O(log n + δ2) amortized time, where δ is an upper bound on the total number of faults. The space required is O(n + δ). Copyright © 2007 by the Association for Computing Machinery, Inc. and the Society for Industrial and Applied Mathematics.
2007
18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Amortized time; Memory faults; Memory locations
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Resilient Search Trees / Finocchi, Irene; Grandoni, Fabrizio; G. F., Italiano. - STAMPA. - 07-09-January-2007:(2007), pp. 547-555. (Intervento presentato al convegno 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 tenutosi a New Orleans; United States nel January 7-9, 2007) [10.1145/1283383.1283442].
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/357946
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 27
  • ???jsp.display-item.citation.isi??? 18
social impact