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. [13] and Brodal et al. [6] on the faulty RAM model, in which all but O(1) memory is unreliable. There, if an upper bound δ on the number of corruptions is known in advance, all dictionary operations can be implemented in Θ(log n + δ) amortized time, thus trading resiliency for speed as soon as δ = ω(log n). Our construction does not need to know the value of δ 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.

Resilient dictionaries for randomly unreliable memory

Leucci S.
;
2019-01-01

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. [13] and Brodal et al. [6] on the faulty RAM model, in which all but O(1) memory is unreliable. There, if an upper bound δ on the number of corruptions is known in advance, all dictionary operations can be implemented in Θ(log n + δ) amortized time, thus trading resiliency for speed as soon as δ = ω(log n). Our construction does not need to know the value of δ 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/147825
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact