1 Search Results for "Meierhans, Simon"

Document

DOI: 10.4230/LIPIcs.ESA.2019.70

Resilient Dictionaries for Randomly Unreliable Memory

Authors: Stefano Leucci, Chih-Hung Liu, and Simon Meierhans

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract

We study the problem of designing a dictionary data structure that is resilient to memory corruptions. Our error model is a variation of the faulty RAM model in which, except for constant amount of definitely reliable memory, each memory word is randomly unreliable with a probability p < 1/2, and the locations of the unreliable words are unknown to the algorithm. An adversary observes the whole memory and can, at any time, arbitrarily corrupt (i.e., modify) the contents of one or more unreliable words. Our dictionary has capacity n, stores N<n keys in the optimal O(N) amount of space, supports insertions and deletions in O(log n) amortized time, and allows to search for a key in O(log n) worst-case time. With a global probability of at least 1-1/n, all possible search operations are guaranteed to return the correct answer w.r.t. the set of uncorrupted keys. The closest related results are the ones of Finocchi et al. [Irene Finocchi et al., 2009] and Brodal et al. [Brodal et al., 2007] on the faulty RAM model, in which all but O(1) memory is unreliable. There, if an upper bound delta on the number of corruptions is known in advance, all dictionary operations can be implemented in Theta(log n + delta) amortized time, thus trading resiliency for speed as soon as delta = omega(log n). Our construction does not need to know the value of delta in advance and remains fast and effective even when up to a constant fraction of the available memory is corrupted. Our techniques can be immediately extended to implement other data types (e.g., associative containers and priority queues), which can then be used as a building block in the design of other resilient algorithms. For example, we are able to solve the resilient sorting problem in our model using O(n log n) time.

Cite as

Stefano Leucci, Chih-Hung Liu, and Simon Meierhans. Resilient Dictionaries for Randomly Unreliable Memory. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 70:1-70:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{leucci_et_al:LIPIcs.ESA.2019.70,
  author =	{Leucci, Stefano and Liu, Chih-Hung and Meierhans, Simon},
  title =	{{Resilient Dictionaries for Randomly Unreliable Memory}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{70:1--70:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.70},
  URN =		{urn:nbn:de:0030-drops-111911},
  doi =		{10.4230/LIPIcs.ESA.2019.70},
  annote =	{Keywords: resilient dictionary, unreliable memory, faulty RAM}
}

Refine by Author
1 Leucci, Stefano
1 Liu, Chih-Hung
1 Meierhans, Simon

Refine by Classification
1 Theory of computation → Data structures design and analysis

Refine by Keyword
1 faulty RAM
1 resilient dictionary
1 unreliable memory

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "Meierhans, Simon"

Resilient Dictionaries for Randomly Unreliable Memory

Abstract

Cite as

Thanks for your feedback!

Could not send message