2013/05/16 by Lorenzo De Stefani, De Stefani, Lorenzo, Francesco Silvestri +1
Computer Science · Engineering · #68M15 #68P05 #68W40 #Advanced Data Storage Technologies #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #E.1 #F.2.2 #F.2.3 #FOS: Computer and information sciences #I.1.2 #Radiation Effects in Electronics #acm:68M15 #acm:68P05 #acm:68W40 #cs.DS #msc:68M15 #msc:68P05 #msc:68W40
paper · pdf · doi:10.48550/arxiv.1305.3828
To appear in Theoretical Computer Science, 2015
openalex publication_date 2013/05/16 · arxiv created 2015/04/02 · arxiv updated 2015/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(nlog n+α(δ/S + log S)) time and uses Θ(S) safe memory words. Our algorithm outperforms previous resilient sorting algorithms which do not exploit the available safe memory and require O(nlog n+ αδ) time. Finally, we exploit our sorting algorithm for deriving a resilient priority queue. Our implementation uses Θ(S) safe memory words and Θ(n) faulty memory words for storing n keys, and requires O(log n + δ/S) amortized time for each insert and deletemin operation. Our resilient priority queue improves the O(log n + δ) amortized time required by the state of the art.