Resilient Dictionaries for Randomly Unreliable Memory
Stefano Leucci, Chih-Hung Liu, Simon Meierhans · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2019
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