TY - JOUR AU - Brodal, Gerth Stølting AU - Fagerberg, Rolf AU - Jørgensen, Allan Grønlund AU - Moruz, Gabriel AU - Mølhave, Thomas PY - 2007/01/01 Y2 - 2024/03/28 TI - Optimal Resilient Dynamic Dictionaries⋆ JF - DAIMI Report Series JA - DPB VL - 36 IS - 585 SE - Articles DO - 10.7146/dpb.v36i585.7222 UR - https://tidsskrift.dk/daimipb/article/view/7222 SP - AB - 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. ER -