Chapter 10
Recovery Algorithms: An Analysis
Abstract Discovered algorithm of modified linear recovery seems to be effective
in terms of power of detection of fault and correct state of the system. At the same
time, classic algorithms well presented in literature binary search and linear search
can also be applied for the same purpose. Thus, we have to consider the recovery
process itself and analyze which classic algorithms are applicable and fit the purpose of efficient recovery. We introduce and analyze three recovery algorithms that
are able to ensure successful recovery by iteratively go through all stored recovery
points.
10.1 Comparison of MLR and Two Other Recovery
Algorithms of the Same Family
Two other algorithms, namely, the linear recovery algorithm and the dichotomous
recovery algorithm [1–4], are part of the same family of the recovery algorithms as
the MLR algorithm.
We quickly introduce these algorithms and then compare their efficiency to the
MLR (based on [3–5] and adapted for our needs). We do this by assuming a
Poisson error rate and compare the three algorithms with increasing recovery depth.
For all three algorithms, we partition the program execution in segments and
create a recovery point after each segment. The difference between the three
algorithms lies in fact in the way the recovery is performed. We give more details
during the analysis.
10.2 Computational Model
The execution model for the three algorithms is basically the same we used in the
analysis of the MLR algorithm.
© Springer Nature Switzerland AG 2020
I. Schagaev et al., Software Design for Resilient Computer Systems,
https://doi.org/10.1007/978-3-030-21244-5_10
153
Recovery Algorithms: An Analysis
Abstract Discovered algorithm of modified linear recovery seems to be effective
in terms of power of detection of fault and correct state of the system. At the same
time, classic algorithms well presented in literature binary search and linear search
can also be applied for the same purpose. Thus, we have to consider the recovery
process itself and analyze which classic algorithms are applicable and fit the purpose of efficient recovery. We introduce and analyze three recovery algorithms that
are able to ensure successful recovery by iteratively go through all stored recovery
points.
10.1 Comparison of MLR and Two Other Recovery
Algorithms of the Same Family
Two other algorithms, namely, the linear recovery algorithm and the dichotomous
recovery algorithm [1–4], are part of the same family of the recovery algorithms as
the MLR algorithm.
We quickly introduce these algorithms and then compare their efficiency to the
MLR (based on [3–5] and adapted for our needs). We do this by assuming a
Poisson error rate and compare the three algorithms with increasing recovery depth.
For all three algorithms, we partition the program execution in segments and
create a recovery point after each segment. The difference between the three
algorithms lies in fact in the way the recovery is performed. We give more details
during the analysis.
10.2 Computational Model
The execution model for the three algorithms is basically the same we used in the
analysis of the MLR algorithm.
© Springer Nature Switzerland AG 2020
I. Schagaev et al., Software Design for Resilient Computer Systems,
https://doi.org/10.1007/978-3-030-21244-5_10
153