Resilient search trees

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 + δ).