Exploiting non-constant safe memory in resilient algorithms and data structures

Lorenzo De Stefani, Francesco Silvestri

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

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 $\delta$ and $\alpha$ denote, respectively, the maximum amount of faults which can happen during the execution of an algorithm and the actual number of occurred faults, with $\alpha \leq \delta$. We propose a resilient algorithm for sorting $n$ entries which requires $O\left(n\log n+\alpha (\delta/S + \log S)\right)$ time and uses $\Theta(S)$ safe memory words. Our algorithm outperforms previous resilient sorting algorithms which do not exploit the available safe memory and require $O\left(n\log n+ \alpha\delta\right)$ time. Finally, we exploit our sorting algorithm for deriving a resilient priority queue. Our implementation uses $\Theta(S)$ safe memory words and $\Theta(n)$ faulty memory words for storing $n$ keys, and requires $O\left(\log n + \delta/S\right)$ amortized time for each insert and deletemin operation. Our resilient priority queue improves the $O\left(\log n + \delta\right)$ amortized time required by the state of the art.
OriginalsprogEngelsk
TidsskriftTheoretical Computer Science
Vol/bind583
Sider (fra-til)86-97
ISSN0304-3975
DOI
StatusUdgivet - 7 jun. 2015
Udgivet eksterntJa

Fingeraftryk

Dyk ned i forskningsemnerne om 'Exploiting non-constant safe memory in resilient algorithms and data structures'. Sammen danner de et unikt fingeraftryk.

Citationsformater