Optimal Resilient Dynamic Dictionaries⋆

Abstract

Abstract. In the resilient memory model any memory cell can get cor- rupted at any time, and corrupted cells cannot be distinguished from uncorrupted cells. An upper bound, , on the number of corruptions and O(1) reliable memory cells are provided. In this model, a data structure is denoted resilient if it gives the correct output on the set of uncor- rupted elements. We propose two optimal resilient static dictionaries, a randomized one and a deterministic one. The randomized dictionary supports searches in O(log n + ) expected time using O(log ) random bits in the worst case, under the assumption that corruptions are not performed by an adaptive adversary. The deterministic static dictionary supports searches in O(log n + ) time in the worst case. We also in- troduce a deterministic dynamic resilient dictionary supporting searches in O(log n + ) time in the worst case, which is optimal, and updates in O(log n + ) amortized time. Our dynamic dictionary supports range queries in O(log n + + k) worst case time, where k is the size of the output.