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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
