Aarhus University Seal

Optimal Resilient Dynamic Dictionaries

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Allan Grønlund Jørgensen
  • Gerth Stølting Brodal
  • Gabriel Moruz, Denmark
  • Thomas Mølhave, Denmark
  • Rolf Fagerberg, University of Southern Denmark, Denmark
  • Irene Finocchi, Dipartimento di Informatica, Universit'a di Roma, Italy
  • Fabrizio Grandoni, Dipartimento di Informatica, Universit`a di Roma, Italy
  • Giuseppe F. Italiano, Dipartimento di Informatica, Sistemi e Produzione, Universit`a di Roma, Italy
  • Department of Computer Science
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 $\delta$ 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 + \delta)$ expected amortized cost
per operation, and $O(n)$ space complexity. We then propose an
optimal deterministic static dictionary supporting searches in
$\Theta(\log n+\delta)$ 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+\delta)$ amortized time. Our dynamic dictionary also supports range
queries in $O(\log n+\delta+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~$\Omega(\log n +
\delta)$ worst-case time per search.
Original languageEnglish
Title of host publicationAlgorithms – ESA 2007 : 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007. Proceedings
EditorsLars Arge, Michael Hoffmann, Emo Welzl
Number of pages12
Publication year2007
ISBN (print)978-3-540-75519-7
Publication statusPublished - 2007
Event15th Annual European Symposium on Algorithms - Eilat, Israel
Duration: 8 Oct 200710 Oct 2007


Conference15th Annual European Symposium on Algorithms
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 7703190