Optimal Resilient Dynamic Dictionaries

Abstract

We investigate the problem of computing in the presence of faults that may arbitrarily (i.e., adversarily) corrupt memory locations. In the faulty memory model, any memory cell can get corrupted at any time, and corrupted cells cannot be distinguished from uncorrupted ones. An upper bound delta on the number of corruptions and O(1) reliable memory cells are provided. In this model, we focus on the design of resilient dictionaries, i.e., dictionaries which are able to operate correctly (at least) on the set of uncorrupted keys. We first present a simple resilient dynamic search tree, based on random sampling, with O(log n + delta) expected amortized cost per operation, and O(n) space complexity. We then propose an optimal deterministic static dictionary supporting searches in Theta(log n + delta) time in the worst case, and we show how to use it in a dynamic setting in order to support updates in O(log n + delta) amortized time. Our dynamic dictionary also supports range queries in O(log n + delta + t) worst case time, where t is the size of the output. Finally, we show that every resilient search tree (with some reasonable properties) must take  Omega(log n + delta) worst-case time per search.

Full text: http://dx.doi.org/10.1007/978-3-540-75520-3_32