Document Open Access Logo

Resilient Dictionaries for Randomly Unreliable Memory

Authors Stefano Leucci , Chih-Hung Liu , Simon Meierhans

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.70.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Stefano Leucci
  • Department of Algorithms and Complexity, Max Planck Institute for Informatics, Germany
Chih-Hung Liu
  • Department of Computer Science, ETH Zürich, Switzerland
Simon Meierhans
  • Department of Computer Science, ETH Zürich, Switzerland

Funding

Research supported by the SNSF (Swiss National Science Foundation) grant 200021_165524.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ESA.2019.70

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • resilient dictionary
  • unreliable memory
  • faulty RAM

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google Scholar
  2. Yonatan Aumann and Michael A. Bender. Fault Tolerant Data Structures. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 580-589, 1996. URL: https://doi.org/10.1109/SFCS.1996.548517.
  3. A. Bagchi. On Sorting in the Presence of Erroneous Information. Inf. Process. Lett., 43(4):213-215, 1992. URL: https://doi.org/10.1016/0020-0190(92)90203-8.
  4. Robert S. Boyer and J. Strother Moore. MJRTY: A fast majority vote algorithm. In Automated Reasoning: Essays in Honor of Woody Bledsoe, pages 105-118, 1991. Google Scholar
  5. Mark Braverman and Elchanan Mossel. Noisy Sorting Without Resampling. In Proceedings of the 19th Annual Symposium on Discrete Algorithms, pages 268-276, 2008. URL: http://arxiv.org/abs/0707.1051.
  6. Gerth Stølting Brodal, Rolf Fagerberg, Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano, Allan Grønlund Jørgensen, Gabriel Moruz, and Thomas Mølhave. Optimal Resilient Dynamic Dictionaries. In Lars Arge, Michael Hoffmann, and Emo Welzl, editors, Algorithms - ESA 2007, pages 347-358, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  7. Gerth Stølting Brodal, Rolf Fagerberg, and Riko Jacob. Cache oblivious search trees via binary trees of small height. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA., pages 39-48, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545386.
  8. Paul Christiano, Erik D. Demaine, and Shaunak Kishore. Lossless Fault-Tolerant Data Structures with Additive Overhead. In Algorithms and Data Structures - 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings, pages 243-254, 2011. URL: https://doi.org/10.1007/978-3-642-22300-6_21.
  9. Ferdinando Cicalese. Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2013. Google Scholar
  10. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  11. Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with Noisy Information. SIAM J. Comput., 23(5):1001-1018, 1994. URL: https://doi.org/10.1137/S0097539791195877.
  12. Irene Finocchi, Fabrizio Grandoni, and Giuseppe F. Italiano. Optimal resilient sorting and searching in the presence of memory faults. Theor. Comput. Sci., 410(44):4457-4470, 2009. URL: https://doi.org/10.1016/j.tcs.2009.07.026.
  13. Irene Finocchi, Fabrizio Grandoni, and Giuseppe F. Italiano. Resilient dictionaries. ACM Trans. Algorithms, 6(1):1:1-1:19, 2009. URL: https://doi.org/10.1145/1644015.1644016.
  14. Irene Finocchi and Giuseppe F. Italiano. Sorting and Searching in Faulty Memories. Algorithmica, 52(3):309-332, 2008. URL: https://doi.org/10.1007/s00453-007-9088-4.
  15. Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Sorting with Recurrent Comparison Errors. In Yoshio Okamoto and Takeshi Tokuyama, editors, 28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:12, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2017.38.
  16. Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Optimal Dislocation with Persistent Errors in Subquadratic Time. In Proc. of the 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), volume 96 of LIPIcs, pages 36:1-36:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.36.
  17. Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Optimal Sorting with Persistent Comparison Errors. In Proc. of the 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.46.
  18. Marius Hillenbrand. Physical Address Decoding in Intel Xeon v3/v4 CPUs: A Supplemental Datasheet, 2017. URL: https://os.itec.kit.edu/downloads/publ_2017_hillenbrand_xeon_decoding.pdf.
  19. Matthias Jung, Carl Christian Rheinländer, Christian Weis, and Norbert Wehn. Reverse Engineering of DRAMs: Row Hammer with Crosshair. In Proceedings of the Second International Symposium on Memory Systems, MEMSYS 2016, Alexandria, VA, USA, October 3-6, 2016, pages 471-476, 2016. URL: https://doi.org/10.1145/2989081.2989114.
  20. Rolf Klein, Rainer Penninger, Christian Sohler, and David P. Woodruff. Tolerant Algorithms. In Proc. of the 19th Annual European Symposium on Algorithm (ESA), pages 736 - -747, 2011. Google Scholar
  21. K. B. Lakshmanan, Bala Ravikumar, and K. Ganesan. Coping with Erroneous Information while Sorting. IEEE Trans. Computers, 40(9):1081-1084, 1991. URL: https://doi.org/10.1109/12.83656.
  22. Philip M. Long. Sorting and Searching with a Faulty Comparison Oracle. Technical report, University of California at Santa Cruz, Santa Cruz, CA, USA, 1992. Google Scholar
  23. Andrzej Pelc. Searching games with errors - fifty years of coping with liars. Theor. Comput. Sci., 270(1-2):71-109, 2002. Google Scholar
  24. Peter Pessl, Daniel Gruss, Clémentine Maurice, Michael Schwarz, and Stefan Mangard. DRAMA: exploiting DRAM addressing for cross-cpu attacks. In 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016., pages 565-581, 2016. URL: https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/pessl.
  25. Aviad Rubinstein and Shai Vardi. Sorting from Noisier Samples. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 960-972, 2017. URL: https://doi.org/10.1137/1.9781611974782.60.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact