کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437844 | 690194 | 2015 | 12 صفحه PDF | دانلود رایگان |
• We study tradeoffs between algorithmic resiliency and hardware resiliency.
• We extend the Faulty RAM (FRAM) model by adding a safe memory S which is immune to corruptions.
• We propose a resilient sorting algorithm requiring O(nlogn+α(δ/S+logS))O(nlogn+α(δ/S+logS)) time.
• We propose a resilient priority queue data structure requiring O(logn+δ/S)O(logn+δ/S) amortized time per operation.
We extend the Faulty RAM model by Finocchi and Italiano (2008) by adding a safe memory of arbitrary size S, and we then derive tradeoffs between the performance of resilient algorithmic techniques and the size of the safe memory. Let δ and α denote, respectively, the maximum amount of faults which can happen during the execution of an algorithm and the actual number of occurred faults, with α≤δα≤δ. We propose a resilient algorithm for sorting n entries which requires O(nlogn+α(δ/S+logS))O(nlogn+α(δ/S+logS)) time and uses Θ(S)Θ(S) safe memory words. Our algorithm outperforms previous resilient sorting algorithms which do not exploit the available safe memory and require O(nlogn+αδ)O(nlogn+αδ) time. Finally, we exploit our sorting algorithm for deriving a resilient priority queue. Our implementation uses Θ(S)Θ(S) safe memory words and Θ(n)Θ(n) faulty memory words for storing n keys, and requires O(logn+δ/S)O(logn+δ/S) amortized time for each insert and deletemin operation. Our resilient priority queue improves the O(logn+δ)O(logn+δ) amortized time required by the state of the art.
Journal: Theoretical Computer Science - Volume 583, 7 June 2015, Pages 86–97