Resilient Dictionaries for Randomly Unreliable Memory
- Leucci, Stefano
- Liu, Chih-Hung
- Meierhans, Simon
DOIAbstract
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 leas...
Add to ORKG