https://scholars.lib.ntu.edu.tw/handle/123456789/624635
標題: | Resilient dictionaries for randomly unreliable memory | 作者: | Leucci S Liu C.-H Meierhans S. CHIH-HUNG LIU |
關鍵字: | Faulty RAM; Resilient dictionary; Unreliable memory | 公開日期: | 2019 | 卷: | 144 | 來源出版物: | Leibniz International Proceedings in Informatics, LIPIcs | 摘要: | 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. © Stefano Leucci, Chih-Hung Liu, and Simon Meierhans. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85074823007&doi=10.4230%2fLIPIcs.ESA.2019.70&partnerID=40&md5=6870822f9ab00fcbee20276fc030a327 https://scholars.lib.ntu.edu.tw/handle/123456789/624635 |
ISSN: | 18688969 | DOI: | 10.4230/LIPIcs.ESA.2019.70 | SDG/關鍵字: | Amortized time; Building blockes; Dictionary operations; Insertions and deletions; Memory corruption; Priority queues; Probability p; Search operations; Random access storage |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。