Optimal Resilient Dynamic Dictionaries⋆

  • Gerth Stølting Brodal
  • Rolf Fagerberg
  • Allan Grønlund Jørgensen
  • Gabriel Moruz
  • Thomas Mølhave

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.
Published
2007-01-01
How to Cite
Brodal, G., Fagerberg, R., Jørgensen, A., Moruz, G., & Mølhave, T. (2007). Optimal Resilient Dynamic Dictionaries⋆. DAIMI Report Series, 36(585). https://doi.org/10.7146/dpb.v36i585.7222