Optimal Resilient Dynamic Dictionaries

Gerth Stølting Brodal, Rolf Fagerberg, Irene Finocchi, Fabrizio Grandoni, Giuseppe Italiano, Allan Grønlund Jørgensen, Gabriel Moruz, and Thomas Mølhave

In Proc. 15th Annual European Symposium on Algorithms, volume 4708 of Lecture Notes in Computer Science, pages 347-358. Springer Verlag, Berlin, 2007.

Abstract

We investigate the problem of computing in the presence of faults that may arbitrarily (i.e., adversarially) 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 δ 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 + δ) expected amortized cost per operation, and O(n) space complexity. We then propose an optimal deterministic static dictionary supporting searches in Θ(log n+δ) 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+δ) amortized time. Our dynamic dictionary also supports range queries in O(log n+δ+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 Ω(log n + δ) worst-case time per search.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2007. All rights reserved.

Online version

esa07.pdf (145 Kb)

DOI

10.1007/978-3-540-75520-3_32

BIBTEX entry

@incollection{esa07,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Irene Finocchi and Fabrizio Grandoni and Giuseppe Italiano and Allan Gr{\o}nlund J{\o}rgensen and Gabriel Moruz and Thomas M{\o}lhave",
  booktitle = "Proc. 15th Annual European Symposium on Algorithms",
  doi = "10.1007/978-3-540-75520-3_32",
  isbn = "978-3-540-75519-7",
  pages = "347-358",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Optimal Resilient Dynamic Dictionaries",
  volume = "4708",
  year = "2007"
}

Other versions