Optimal Resilient Dynamic Dictionaries

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

Technical Report, DAIMI PB-585, Department of Computer Science, Aarhus University, 14 pages, November 2007.

Abstract

In the resilient memory model any memory cell can get corrupted 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 introduce 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.

Online version

daimi-pb-585.pdf (182 Kb)

BIBTEX entry

@techreport{daimi-pb-585,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Allan Gr{\o}nlund J{\o}rgensen and Gabriel Moruz and Thomas M{\o}lhave",
  institution = "Department of Computer Science, Aarhus University",
  month = "November",
  number = "DAIMI PB-585",
  pages = "14",
  title = "Optimal Resilient Dynamic Dictionaries",
  year = "2007"
}