---
abstract: 'This paper deals with the impact of fault prediction techniques on checkpointing strategies. We extend the classical analysis of Young and Daly in the presence of a fault prediction system, which is characterized by its recall and its precision, and which provides either exact or window-based time predictions. We succeed in deriving the optimal value of the checkpointing period (thereby minimizing the waste of resource usage due to checkpoint overhead) in all scenarios. These results allow to analytically assess the key parameters that impact the performance of fault predictors at very large scale. In addition, the results of this analytical evaluation are nicely corroborated by a comprehensive set of simulations, thereby demonstrating the validity of the model and the accuracy of the results.'
author:
- |
    Guillaume Aupy$^{1}$,Yves Robert$^{1,2}$, Frédéric Vivien$^{1}$ and Dounia Zaidouni$^{1}$\
    $1.$ Ecole Normale Supérieure de Lyon & INRIA, France\
    [{Guillaume.Aupy | Yves.Robert | Frederic.Vivien | Dounia.Zaidouni}@ens-lyon.fr]({Guillaume.Aupy | Yves.Robert | Frederic.Vivien | Dounia.Zaidouni}@ens-lyon.fr)\
    $2.$ University of Tennessee Knoxville, USA
bibliography:
- 'biblio.bib'
title: Impact of fault prediction on checkpointing strategies
---

Introduction {#sec.intro}
============

In this paper, we assess the impact of fault prediction techniques on checkpointing strategies. We assume to have jobs executing on a platform subject to faults, and we let $\mu$ be the mean time between faults (MTBF) of the platform. In the absence of fault prediction, the standard approach is to take periodic checkpoints, each of length [C]{}, every period of duration [$T$]{}. In steady-state utilization of the platform, the value [$T_{\text{opt}}$]{}of [$T$]{}that minimizes the (expectation of the) waste of resource usage due to checkpointing is easily approximated as ${\ensuremath{T_{\text{opt}}}\xspace}= \sqrt{2 \mu{C\xspace}}$, or ${\ensuremath{T_{\text{opt}}}\xspace}= \sqrt{2 (\mu +{R\xspace}){C\xspace}}$ (where [R]{}is the duration of the recovery). The former expression is the well-known Young’s formula [@young74], while the latter is due to Daly [@daly04].

Now, when some fault prediction mechanism is available, can we compute a better checkpointing period to decrease the expected waste? and to what extent? Critical parameters that characterize a fault prediction system are its recall [$r$]{}, which is the fraction of faults that are indeed predicted, and its precision [$p$]{}, which is the fraction of predictions that are correct (i.e., correspond to actual faults). The major objective of this paper is to refine the expression of the expected waste as a function of these new parameters, and to design efficient checkpointing policies that take predictions into account. We deal with two problem instances, one where the predictor system provides exact dates for predicted events, and another where it only provides time windows during which events take place. The key contributions of this paper are the following: (i) The design of several checkpointing policies, their analysis, and a new formula for the checkpointing period that extends Young’s and Daly’s to take predictions into account; (ii) The analytical characterization of the best policy for each set of parameters; (iii) The validation of the theoretical results via extensive simulations, for both Exponential and Weibull failure distributions; (iv) The demonstration that even a poor predictor can lead to a significant reduction of application execution time; and (v) The demonstration that recall is far more important than precision, hence giving insight into the design of future predictors.

The rest of the paper is organized as follows. We first detail the framework in Section \[sec.framework\]. We deal with exact date predictions in Section \[sec.no.intervals\], and with time-window based predictions in Section \[sec.intervals\]. Section \[sec.simulations\] is devoted to simulations. Finally, we provide concluding remarks in Section \[sec.conclusion\].

Framework {#sec.framework}
=========

Checkpointing strategy
----------------------

We consider a *platform* subject to faults. Our work is agnostic of the granularity of the platform, which may consist either of a single processor, or of several processors that work concurrently and use coordinated checkpointing. The key parameter is $\mu$, the mean time between faults (MTBF) of the platform. If the platform is made of $N$ components whose individual MTBF is $\mu_{ind}$, then $\mu = \frac{\mu_{ind}}{N}$. Checkpoints are taken at regular intervals, or periods, of length [$T$]{}. We use [C]{}, [D]{}, and [R]{}for the duration of the checkpoint, downtime and recovery (respectively). We must enforce that ${C\xspace}\leq {\ensuremath{T}\xspace}$, and useful work is done only during ${\ensuremath{T}\xspace}-{C\xspace}$ units of time for every period of length [$T$]{}, if no fault occurs. The *waste* due to checkpointing in a fault-free execution is ${\ensuremath{\textsc{Waste}}\xspace}= \frac{{C\xspace}}{{\ensuremath{T}\xspace}}$. In the following, the *waste* always denote the fraction of time that the platform is not doing useful work.

Fault predictor
---------------

A fault predictor is a mechanism that is able to predict that some faults will take place, either at a certain point in time, or within some time-interval window. The accuracy of the fault predictor is characterized by two quantities, the *recall* and the *precision*. The recall [$r$]{}is the fraction of faults that are predicted while the precision [$p$]{}is the fraction of fault predictions that are correct. Traditionally, one defines three types of *events*: (i) *True positive* events are faults that the predictor has been able to predict (let $\textit{True}_P$ be their number); (ii) *False positive* events are fault predictions that did not materialize as actual faults (let $\textit{False}_P$ be their number); and (iii) *False negative* events are faults that were not predicted (let $\textit{False}_N$ be their number). With these definitions, we have ${\ensuremath{r}\xspace}= \frac{\textit{True}_P}{\textit{True}_P+\textit{False}_N}$ and ${p\xspace}= \frac{\textit{True}_P}{\textit{True}_P+ \textit{False}_P}$.

Fault rates
-----------

In addition to $\mu$, the platform MTBF, let ${\ensuremath{\mu_{P}}\xspace}$ be the mean time between predicted events (both true positive and false positive), and let ${\ensuremath{\mu_{NP}}\xspace}$ be the mean time between unpredicted faults (false negative). Finally, we define the mean time between events as ${\ensuremath{\mu_e}\xspace}$ (including all three event types). The relationships between $\mu$, ${\ensuremath{\mu_{P}}\xspace}$, ${\ensuremath{\mu_{NP}}\xspace}$, and ${\ensuremath{\mu_e}\xspace}$ are the following:

-   $\frac{{1-{\ensuremath{r}\xspace}}}{\mu} =  \frac{1}{{\ensuremath{\mu_{NP}}\xspace}}$ (here, $1-{\ensuremath{r}\xspace}$ is the fraction of faults that are unpredicted);

-   $ \frac{{\ensuremath{r}\xspace}}{\mu} =  \frac{{\ensuremath{p}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}$ (here, ${\ensuremath{r}\xspace}$ is the fraction of faults that are predicted, and ${\ensuremath{p}\xspace}$ is the fraction of fault predictions that are correct);

-   $\frac{1}{{\ensuremath{\mu_e}\xspace}}=\frac{1}{{\ensuremath{\mu_{P}}\xspace}}+\frac{1}{{\ensuremath{\mu_{NP}}\xspace}}$ (here, events are either predicted (true or false), or not).

Predictor with exact event dates {#sec.no.intervals}
================================

In this section, we present an analytical model to assess the impact of prediction on periodic checkpointing strategies. We consider the case where the predictor is able to provide exact prediction dates, and to generate such predictions at least ${C\xspace}$ seconds in advance, so that a checkpoint can indeed be taken before the event (otherwise the prediction cannot be used, because there is not enough time to take proactive actions). We consider the following algorithm:\
(1) While no fault prediction is available, checkpoints are taken periodically with period ${\ensuremath{T}\xspace}$;\
(2) When a fault is predicted, we decide whether to take the prediction into account or not. This decision is randomly taken: with probability [$q$]{}, we trust the predictor and take the prediction into account, and, with probability $1-{\ensuremath{q}\xspace}$, we ignore the prediction. If we take the prediction into account, there are two cases. If we have enough time before the prediction date, we take a checkpoint as late as possible, i.e., so that it completes right at the time where the fault is predicted to happen. After the checkpoint, we then complete the execution of the period (see Figure \[fig.enoughtime\](a)). Otherwise, if we do not have enough time to take an extra checkpoint (because we are already checkpointing), then we do some extra work during $\varepsilon$ seconds (see Figure \[fig.no\_enoughtime\](b)). We account for this work as idle time in the expression of the waste, to ease the analysis. Our expression of the waste is thus an upper bound.

The rationale for not always trusting the predictor is to avoid taking useless checkpoints too frequently. Intuitively, the precision ${\ensuremath{p}\xspace}$ of the predictor must be above a given threshold for its usage to be worthwhile. In other words, if we decide to checkpoint just before a predicted event, either we will save time by avoiding a costly re-execution if the event does correspond to an actual fault, or we will lose time by unduly performing an extra checkpoint. We need a larger proportion of the former cases, i.e., a good precision, for the predictor to be really useful. The following analysis will determine the optimal value of ${\ensuremath{q}\xspace}$ as a function of the parameters ${C\xspace}$, $\mu$, ${\ensuremath{r}\xspace}$, and ${\ensuremath{p}\xspace}$.

\[fig.no\_enoughtime\]

Computing the waste {#sec.nointalg}
-------------------

Our goal in this section is to compute a formula for the expected waste. Recall that the waste is the fraction of time that the processors do not perform useful computations, either because they are checkpointing, or because a failure has struck. There are four different sources of waste (see Figure \[fig.waste-exact\]):\
(1) **Checkpoints:** During a fault-free execution, the fraction of resources used in checkpointing is $
\frac{{C\xspace}}{{T}}$.\
(2) **Unpredicted faults:** This overhead occurs each time a unpredicted fault strikes, that is, on average, once every ${\ensuremath{\mu_{NP}}\xspace}$ seconds. The time wasted because of the unpredicted fault is then the time elapsed between the last checkpoint and the fault, plus the downtime and the time needed for the recovery. The expectation of the time elapsed between the last checkpoint and the fault is equal to half the period of checkpoints, because the time where the fault hits the system is independent of the checkpointing algorithm. Finally, the waste due to unpredicted faults is: $ \frac{1}{{\ensuremath{\mu_{NP}}\xspace}} \left[ \frac{{T}}{2} + {D\xspace}+  {R\xspace}\right]$.\
(3) **Predictions taken into account:** Now we have to compute the execution overhead due to a prediction which we trust (hence we checkpoint just before its date). This overhead occurs each time a prediction is made by the predictor, that is, on average, once every ${\ensuremath{\mu_{P}}\xspace}$ seconds, and that we decide to trust it, with probability ${\ensuremath{q}\xspace}$. If the predicted event is an actual fault, we waste ${C\xspace}+{D\xspace}+{R\xspace}$ seconds: we waste ${D\xspace}+ {R\xspace}$ seconds because the predicted event corresponds to an actual fault, and if we have enough time before the prediction date, we waste ${C\xspace}$ seconds because we take an extra checkpoint as late as possible before the prediction date (see Figure \[fig.enoughtime\](a)). Note that if we do not have enough time to take an extra checkpoint (see Figure \[fig.no\_enoughtime\](b)), we overestimate the waste as ${C\xspace}$ seconds. If the predicted event is not an actual fault, we waste ${C\xspace}$ seconds. An actual fault occurs with probability ${\ensuremath{p}\xspace}$, and a false prediction is made with probability $(1-{\ensuremath{p}\xspace})$. Averaging with these probabilities, we waste an expected amount of $\left [ {p\xspace}({C\xspace}+ {D\xspace}+ {R\xspace}) + (1-{p\xspace}) {C\xspace}\right] $ seconds. Finally, the corresponding overhead is $\frac{1}{{\ensuremath{\mu_{P}}\xspace}} {\ensuremath{q}\xspace}\left [ {p\xspace}({C\xspace}+ {D\xspace}+ {R\xspace}) + (1-p) {C\xspace}\right]$.\
(4) **Ignored predictions:** The final source of waste is for predictions that we do not trust. This overhead occurs each time a prediction is made by the predictor, that is, on average, once every ${\ensuremath{\mu_{P}}\xspace}$ seconds, and that we decide to trust it, with probability $1-{\ensuremath{q}\xspace}$. If the predicted event corresponds to an actual fault, we waste $(\frac{{T}}{2} +{D\xspace}+ {R\xspace})$ seconds (as for an unpredicted fault). Otherwise there is no fault and we took no extra checkpoint, and thus we lose nothing. An actual fault occurs with a probability [$p$]{}. The corresponding overhead is $\frac{1}{{\ensuremath{\mu_{P}}\xspace}} (1-{\ensuremath{q}\xspace}) \left [  {p\xspace}(\frac{{T}}{2} + {D\xspace}+ {R\xspace}) + (1-{p\xspace}) 0  \right] $.\
Summing up the overhead over the four different sources, and after simplification, we obtain the following equation for the waste: $${\ensuremath{\textsc{Waste}}\xspace}= \frac{{C\xspace}}{{T}} + \frac{1}{\mu} \left[ (1- {\ensuremath{r}\xspace}{\ensuremath{q}\xspace}) \frac{{T}}{2} + {D\xspace}+ {R\xspace}+ \frac{{\ensuremath{q}\xspace}{\ensuremath{r}\xspace}}{{p\xspace}} {C\xspace}\right]
\label{eq.waste}$$

Validity of the analysis {#sec.validity}
------------------------

Equation (\[eq.waste\]) is accurate only when two events (an event being a prediction (true or false) or an unpredicted fault) do not take place within the same period. To ensure that this condition is met with a high probability, we bound the length of the period: without predictions, or when predictions are not taken into account, we enforce the condition ${T}< \alpha \mu$; otherwise, with predictions, we enforce the condition ${T}< \alpha {\ensuremath{\mu_e}\xspace}$. Here, $\alpha$ is some tuning parameter chosen as follows. The number of events during a period of length ${T}$ can be modeled as a Poisson process of parameter $\beta = \frac{{T}}{\mu}$ (without prediction) or $\beta = \frac{{T}}{{\ensuremath{\mu_e}\xspace}}$ (with prediction). The probability of having $k \geq 0$ faults is $P(X=k) = \frac{\beta^{k}}{k!}  e^{-\beta}$, where $X$ is the number of faults. Hence the probability of having two or more faults is $\pi = P(X\geq2) = 1 -( P(X=0) + P(X=1)) = 1 - (1+\beta) e^{-\beta}$. If we assume $\alpha=0.27$ then $\pi \leq 0.03$, hence a valid approximation when bounding the period range accordingly. Indeed, with such a conservative value for $\alpha$, we have overlapping faults for only $3\%$ of the checkpointing segments in average, so that the model is quite reliable.

In addition to the previous constraint, we must always enforce the condition ${C\xspace}\leq {T}$, by construction of the periodic checkpointing policy. Finally, the optimal waste may never exceed $1$; when the waste is equal to $1$, the application no longer makes any progress.

Waste minimization {#sec.minwaste}
------------------

We differentiate twice Equation  with respect to [T]{}: $${\ensuremath{\textsc{Waste}}\xspace}'({T}) = \frac{-{C\xspace}}{{T}^{2}} + \frac{1}{\mu} \left[ (1- {\ensuremath{r}\xspace}{\ensuremath{q}\xspace}) \frac{1}{2}\right]$$ $${\ensuremath{\textsc{Waste}}\xspace}''({T}) = \frac{2 {C\xspace}}{{T}^{3} } > 0$$ We obtain that ${\ensuremath{\textsc{Waste}}\xspace}''({T}) $ is strictly positive, hence ${\ensuremath{\textsc{Waste}}\xspace}({T}) $ is a convex function of ${T}$ and admits a unique minimum on its domain. We also compute ${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{q\}}}\xspace}$, the extremum value of ${T}$ that is the unique zero of the function ${\ensuremath{\textsc{Waste}}\xspace}'({T})$, as ${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{q\}}}\xspace}=\sqrt{ \frac{2 \mu {C\xspace}}{1-{\ensuremath{r}\xspace}{\ensuremath{q}\xspace}}}$. Note that this Equation makes sense even when $1-{\ensuremath{r}\xspace}{\ensuremath{q}\xspace}=0$. Indeed this would mean that both ${\ensuremath{r}\xspace}=1$ and ${\ensuremath{q}\xspace}=1$: the predictor predicts every fault, and we take proactive action for each one of them, there should never be any periodic checkpointing! Finally, note that ${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{q\}}}\xspace}$ may well not belong to the admissible domain $[{C\xspace}, \alpha {\ensuremath{\mu_e}\xspace}]$.

The optimal waste ${\ensuremath{\textsc{Waste}_{\text{opt}}}\xspace}$ is determined via the following case analysis. We rewrite the waste as an affine function of ${\ensuremath{q}\xspace}$: $${\ensuremath{\textsc{Waste}}\xspace}({\ensuremath{q}\xspace}) = \frac{{\ensuremath{r}\xspace}{\ensuremath{q}\xspace}}{\mu}\left (\frac{{C\xspace}}{{p\xspace}}-\frac{{T}}{2}\right )+\left ( \frac{{C\xspace}}{{T}}+\frac{{T}}{2 \mu}+\frac{{D\xspace}+ {R\xspace}}{\mu} \right )$$ For any value of [T]{}, we deduce that ${\ensuremath{\textsc{Waste}}\xspace}({\ensuremath{q}\xspace})$ is minimized either for ${\ensuremath{q}\xspace}=0$ or for ${\ensuremath{q}\xspace}=1$. This (somewhat unexpected) conclusion is that the predictor should sometimes be always trusted, and sometimes never, but no in-between value for ${\ensuremath{q}\xspace}$ will do a better job. Thus we need to minimize the two functions ${\ensuremath{\textsc{Waste}}\xspace}^{\{0\}}$ and ${\ensuremath{\textsc{Waste}}\xspace}^{\{1\}}$ over the domain of admissible values for [T]{}, and to retain the best result.

We have ${\ensuremath{\textsc{Waste}}\xspace}^{\{0\}}(T)= \frac{{C\xspace}}{{T}} + \frac{1}{\mu} \left[ \frac{{T}}{2} + {D\xspace}+ {R\xspace}\right]$. We recognize here the waste function of Young [@young74] and write ${\ensuremath{\textsc{Waste}_Y}\xspace}= \frac{{C\xspace}}{{T}} + \frac{1}{\mu} \left[ \frac{{T}}{2} + {D\xspace}+ {R\xspace}\right]$. The function ${\ensuremath{\textsc{Waste}_Y}\xspace}(T)$ is a convex function and reaches its minimum for ${\ensuremath{T_{\text{Y}}}\xspace}$ in the interval $[{C\xspace},\alpha \mu]$:

-   If (${C\xspace}<{\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{0\}}}\xspace}<\alpha \mu$): ${\ensuremath{T_{\text{Y}}}\xspace}={\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{0\}}}\xspace}=\sqrt{2 \mu {C\xspace}}$

-   If (${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{0\}}}\xspace}<{C\xspace}$): ${\ensuremath{T_{\text{Y}}}\xspace}={C\xspace}$

-   If (${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{0\}}}\xspace} \geq \alpha \mu$): ${\ensuremath{T_{\text{Y}}}\xspace}=\alpha \mu$

Thus, [$\textsc{Waste}_Y$]{}($ = {\ensuremath{\textsc{Waste}}\xspace}^{\{0\}}$) is minimized for: $${\ensuremath{T_{\text{Y}}}\xspace}=\min \left ( \alpha \mu,\max(\sqrt{2 \mu {C\xspace}}, {C\xspace})   \right )$$

Similarly, we have: ${\ensuremath{\textsc{Waste}}\xspace}^{\{1\}}({T})=\frac{{C\xspace}}{{T}} + \frac{1}{\mu} \left[ (1- {\ensuremath{r}\xspace}) \frac{{T}}{2} + {D\xspace}+ {R\xspace}+ \frac{{\ensuremath{r}\xspace}}{{p\xspace}} {C\xspace}\right] $. The function ${\ensuremath{\textsc{Waste}}\xspace}^{\{1\}}(T)$ is a convex function and reaches its minimum for [$T_{1} $]{} in the interval $[{C\xspace},\alpha {\ensuremath{\mu_e}\xspace}]$.

-   If (${C\xspace}<{\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{1\}}}\xspace}<\alpha {\ensuremath{\mu_e}\xspace}$): ${\ensuremath{T_{1} }\xspace}={\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{1\}}}\xspace}=\sqrt{ \frac{2 \mu {C\xspace}}{1-{\ensuremath{r}\xspace}}}$

-   If (${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{1\}}}\xspace}<{C\xspace}$): ${\ensuremath{T_{1} }\xspace}={C\xspace}$

-   If (${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{1\}}}\xspace} \geq \alpha {\ensuremath{\mu_e}\xspace}$): ${\ensuremath{T_{1} }\xspace}=\alpha {\ensuremath{\mu_e}\xspace}$

Thus, ${\ensuremath{\textsc{Waste}}\xspace}^{\{1\}}$ is minimized for: $${\ensuremath{T_{1} }\xspace}=\min \left ( \alpha {\ensuremath{\mu_e}\xspace},\max(\sqrt{ \frac{2 \mu {C\xspace}}{1-{\ensuremath{r}\xspace}} }, {C\xspace})   \right )$$ Finally, the optimal waste is: $${\ensuremath{\textsc{Waste}_{\text{opt}}}\xspace}= \min \left ({\ensuremath{\textsc{Waste}_Y}\xspace}({\ensuremath{T_{\text{Y}}}\xspace}),{\ensuremath{\textsc{Waste}}\xspace}^{\{1\}}({\ensuremath{T_{1} }\xspace}) \right )$$

Prediction and preventive migration {#sec.migration}
-----------------------------------

In this section, we make a short digression and briefly present an analytical model to assess the impact of prediction and preventive migration on periodic checkpointing strategies. As before, we consider a predictor that is able to predict exactly when faults happen, and to generate these predictions at least ${C\xspace}$ seconds before the event dates.

The idea of migration consists in moving a task for execution on another node, when a fault is predicted to happen on the current node in the near future. Note that the faulty node can later be replaced, in case of a hardware fault, or software rejuvenation can be used in case of a software fault. We consider the following algorithm, which is very similar to that used in Section \[sec.nointalg\]:

1.  When no fault prediction is available, checkpoints are taken periodically with period ${\ensuremath{T}\xspace}$.

2.  When a fault is predicted, we decide whether to execute the migration or not. The decision is a random one: with probability [$q$]{}we trust the predictor and do the migration and, with probability 1-[$q$]{}, we ignore the prediction. If we take the prediction into account, we execute the migration as late as possible, so that it completes right at the time when the fault is predicted to happen.

As before, we have four different sources of waste. Summing the overhead of the execution of these different sources, we obtain the following equation for the waste (where ${M}$ is the duration of a migration):

$$\begin{aligned}
 {\ensuremath{\textsc{Waste}}\xspace}&=  \frac{{C\xspace}}{{T}} \\&+  \frac{1}{{\ensuremath{\mu_{NP}}\xspace}} \left[ \frac{{T}}{2} + {D\xspace}+ {R\xspace}\right] \\&+  \frac{1}{{\ensuremath{\mu_{P}}\xspace}} {\ensuremath{q}\xspace}\left [ {p\xspace}({M}) + (1-p) {M}\right] \\&+  \frac{1}{{\ensuremath{\mu_{P}}\xspace}} (1-{\ensuremath{q}\xspace}) \left [  {p\xspace}(\frac{{T}}{2} + {D\xspace}+ {R\xspace}) + (1-{p\xspace}) 0  \right] $$

After simplification, we get:$${\ensuremath{\textsc{Waste}}\xspace}= \frac{{C\xspace}}{{T}} + \frac{1}{\mu} \left[ (1- {\ensuremath{r}\xspace}{\ensuremath{q}\xspace}) \left (\frac{{T}}{2}+{D\xspace}+ {R\xspace}\right )  + \frac{{\ensuremath{q}\xspace}{\ensuremath{r}\xspace}}{{p\xspace}} {M}\right]
\label{eq.wasteM}$$

Equation  is very similar to Equation , and the minimization of the waste proceeds exactly as in Section \[sec.minwaste\]. In a nutshell, ${\ensuremath{\textsc{Waste}}\xspace}(T) $ is again a convex function and admits a unique minimum over its domain $[{C\xspace}, \alpha {\ensuremath{\mu_e}\xspace}]$, the unique zero of the derivative has the same value ${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{q\}}}\xspace}=\sqrt{ \frac{2 \mu {C\xspace}}{1-{\ensuremath{r}\xspace}{\ensuremath{q}\xspace}}}$, and for any value of $T$, the waste is minimized for either ${\ensuremath{q}\xspace}=0$ or ${\ensuremath{q}\xspace}=1$. We conduct the very same case analysis as in Section \[sec.minwaste\].

Predictor with a prediction window {#sec.intervals}
==================================

In the previous section, we supposed that the predictor was able to predict exactly when faults will strike. Here, we suppose (maybe more realistically) that the predictor gives a *prediction window*, that is an interval of time of length [$I$]{}during which the predicted fault is likely to happen. As before in Section \[sec.no.intervals\]: (i) We suppose that we have enough time to checkpoint before the beginning of the prediction window; and (ii) When a prediction is made, we enforce that the scheduling algorithm has the choice either to take or not to take this prediction into account, with probability [$q$]{}.

We start with a description of the strategies that can be used, depending upon the (relative) length [$I$]{}of the prediction window. Let us define two *modes* for the scheduling algorithm:\
**Regular**: This is the mode used when no fault prediction is available, or when a prediction is available but we decide to ignore it (with probability $1-{\ensuremath{q}\xspace}$). In regular mode, we use periodic checkpointing with period [$T_{\text{R}}$]{}. Intuitively, [$T_{\text{R}}$]{}corresponds to the checkpointing period $T$ of Section \[sec.no.intervals\].\
**Proactive**: This is the mode used when a fault prediction is available and we decide to trust it, a decision taken with probability [$q$]{}. Consider such a trusted prediction made with the prediction window $[t_0,t_0+{\ensuremath{I}\xspace}]$. Several strategies can be envisioned:\
(1) [<span style="font-variant:small-caps;">Instant</span>]{}, for *Instantaneous–* The first strategy is to ignore the time-window and to execute the same algorithm as if the predictor had given an exact date prediction at time $t_{0}$. Just as described in Section \[sec.no.intervals\], the algorithm interrupts the current period (of scheduled length [$T_{\text{R}}$]{}), checkpoints during the interval $[t_{0}-C,t_{0}]$, and then returns to regular mode: at time $t_{0}$, it resumes the work needed to complete the interrupted period of the regular mode.\
(2) [<span style="font-variant:small-caps;">NoCkptI</span>]{}, for *No checkpoint during prediction window–* The second strategy is intended for a short prediction window: instead of ignoring it, we acknowledge it, but make the decision not to checkpoint during it. As in the first strategy, the algorithm interrupts the current period (of scheduled length [$T_{\text{R}}$]{}), and checkpoints during the interval $[t_{0}-C,t_{0}]$. But here, we return to regular mode only at time $t_0+{\ensuremath{I}\xspace}$, where we resume the work needed to complete the interrupted period of the regular mode. During the whole length of the time-window, we execute work without checkpointing, at the risk of losing work if a fault indeed strikes. But for a small value of [$I$]{}, it may not be worthwhile to checkpoint during the prediction window (if at all possible, since there is no choice if ${\ensuremath{I}\xspace}< C$).\
(3) [<span style="font-variant:small-caps;">WithCkptI</span>]{}, for *With checkpoints during prediction window–* The third strategy is intended for a longer prediction window and assumes that ${C\xspace}\leq {\ensuremath{I}\xspace}$: the algorithm interrupts the current period (of scheduled length [$T_{\text{R}}$]{}), and checkpoints during the interval $[t_{0}-C,t_{0}]$, but now decides to take several checkpoints during the prediction window. The period [$T_{\text{P}}$]{}of these checkpoints in proactive mode will presumably be shorter than [$T_{\text{R}}$]{}, to take into account the higher fault probability. To simplify the presentation, we use an integer number of periods of length [$T_{\text{P}}$]{} within the prediction window. In the following, we analytically compute the optimal number of such periods. But we take at least one period here, hence one checkpoint, which implies $C \leq I$. We return to regular mode either right after the fault strikes within the time window $[t_0,t_0+{\ensuremath{I}\xspace}]$, or at time $t_0+{\ensuremath{I}\xspace}$ if no actual fault happens within this window. Then, we resume the work needed to complete the interrupted period of the regular mode. The third strategy is the most complex to describe, and the complete behavior of the scheduling algorithm is shown in Algorithm \[algo.proactive\].

Note that for all strategies, exactly as in Section \[sec.no.intervals\], we insert some additional work for the particular case where there is not enough time to take a checkpoint before entering proactive mode (because a checkpoint for the regular mode is currently on-going, see Figure \[fig.no\_enoughtime\](b)). We account for this work as idle time in the expression of the waste, to ease the analysis. Our expression of the waste is thus an upper bound.

Waste for strategy [<span style="font-variant:small-caps;">WithCkptI</span>]{} {#sec-waste-int}
------------------------------------------------------------------------------

In this section we focus on computing the waste of [<span style="font-variant:small-caps;">WithCkptI</span>]{}, the most complex strategy. We first compute the fraction of time spent in the *regular* mode (checkpointing with period [$T_{\text{R}}$]{}) and the fraction of time spent in the *proactive* mode (checkpointing with period [$T_{\text{P}}$]{}). Let [$I'$]{}be the average time spent in the *proactive* mode. When a prediction is made, we may choose to ignore it, which happens with probability $1-{\ensuremath{q}\xspace}$. In this case, the algorithm stays in regular mode and does not spend any time in the proactive mode. With probability [$q$]{}, we may decide to take the prediction into account. In this case, if the prediction is a false positive event (no actual fault strikes), which happens with probability $1-{\ensuremath{p}\xspace}$, then the algorithm spends [$I$]{}units of time in the proactive mode. Otherwise, if the prediction is a true positive event (an actual fault hits the system), which happens with probability ${\ensuremath{p}\xspace}$, then the algorithm spends an average of ${\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}$ in the proactive mode. Here ${\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}$ is the expectation of the time elapsed between the beginning of the prediction window and the time when a fault happens, knowing that a fault happens in the prediction window. Note that if faults are uniformly distributed across the prediction window, then ${\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}= \frac{{\ensuremath{I}\xspace}}{2}$. Altogether, we obtain $
  {\ensuremath{I'}\xspace}= {\ensuremath{q}\xspace}\left((1-{\ensuremath{p}\xspace}){\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}\right)$. Each time there is a prediction, that is, on the average, every ${\ensuremath{\mu_{P}}\xspace}$ seconds, the algorithm spends a time ${\ensuremath{I'}\xspace}$ in the proactive mode. Therefore, Algorithm \[algo.proactive\] spends a fraction of time $\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}$ in the proactive mode, and a fraction of time $1-\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}$ in the regular mode.

As in Section \[sec.no.intervals\], we assume that there is a single event of any type (either a prediction (true or false), or an unpredicted failure) within each interval under study. The condition $T \leq \alpha {\ensuremath{\mu_e}\xspace}$ then becomes ${\ensuremath{T_{\text{R}}}\xspace}+ {\ensuremath{I}\xspace}\leq \alpha {\ensuremath{\mu_e}\xspace}$, since ${\ensuremath{T_{\text{R}}}\xspace}+{\ensuremath{I}\xspace}$ is the longest time interval considered in the analysis of Algorithm \[algo.proactive\]. We now identify the four different sources of waste, and we analyze their respective costs:\
(1) **Waste due to periodic checkpointing.** There are two cases, depending upon the mode of Algorithm \[algo.proactive\]:\
(a) **Regular mode.** In this mode, we take periodic checkpoints. We take a checkpoint of size [C]{}each time the algorithm has processed work for a time ${\ensuremath{T_{\text{R}}}\xspace}-{C\xspace}$ in the regular mode. This remains true if, after spending some time in the regular mode, the algorithm switches to the proactive mode, and later switches back to the regular mode. This behavior is enforced by recording the amount of work performed under the regular mode (variable [$W_{\mathit{reg}}$]{}, at line \[algo.proactive.wreg\] of Algorithm \[algo.proactive\]), and by taking this value into account at line \[algo.proactive.completion\]. Given the fraction of time that Algorithm \[algo.proactive\] spends in the regular mode, this source of waste has a total cost of $\left(1 -\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}\right)\frac{{C\xspace}}{{\ensuremath{T_{\text{R}}}\xspace}}$.\
(b) **Proactive mode.** In this mode, we take a checkpoint of size [C]{}each time the algorithm has processed work for a time ${\ensuremath{T_{\text{P}}}\xspace}-{C\xspace}$. If no fault happens while the algorithm is in the proactive mode, then the algorithm stays exactly a time [$I$]{}in this mode (thanks to the condition at line \[algo.proactive.Ilimit\]). The waste due to the periodic checkpointing is then exactly $\frac{{C\xspace}}{{\ensuremath{T_{\text{P}}}\xspace}}$ (because [$T_{\text{P}}$]{}divides [$I$]{}). If a fault happens while the algorithm is in proactive mode, then, the expectation of the waste due to the periodic checkpointing is upper-bounded by the same quantity $ \frac{{C\xspace}}{{\ensuremath{T_{\text{P}}}\xspace}}$ (this is an over-approximation of the waste in that case). Overall, taking into account the fraction of time Algorithm \[algo.proactive\] is in the proactive mode, the cost of this source of waste is $\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}\frac{{C\xspace}}{{\ensuremath{T_{\text{P}}}\xspace}}$.\
(2) **Waste incurred when switching to the proactive mode.** Each time we take into account a prediction (which happens with probability [$q$]{}on average every [$\mu_{P}$]{}units of time), we start by doing one preliminary checkpoint if we have the time to do so (line \[algo.proactive.addC\]). If we do not have the time to take an additional checkpoint, the algorithm do not do any processing for a duration of at most [C]{} (line \[algo.proactive.wait\]). In both cases, the wasted time is at most [C]{}and this happens once every $\frac{{\ensuremath{\mu_{P}}\xspace}}{{\ensuremath{q}\xspace}}$. Hence, switching from the regular mode to the proactive one induces a waste of at most $\frac{{\ensuremath{q}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}C$.\
(3) **Waste due to predicted faults.** Predicted faults happen with frequency $\frac{{\ensuremath{p}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}$. As we may choose to ignore a prediction, there are still two cases depending on the mode of the algorithm at the time of the fault:\
(a) **Regular mode.** If the algorithm is in regular mode when a predicted fault hits, this means that we have chosen to ignore the prediction, a decision taken with probability $(1-{\ensuremath{q}\xspace})$. The time wasted because of the predicted fault is then the time elapsed between the last checkpoint and the fault, plus the downtime and the time needed for the recovery. The expectation of the time elapsed between the last checkpoint and the fault is equal to half the period of checkpoints, because the time where the fault hits the system is independent of the checkpointing algorithm. Therefore, the waste due to predicted faults hitting the system in regular mode is $\frac{{\ensuremath{p}\xspace}(1-{\ensuremath{q}\xspace})}{{\ensuremath{\mu_{P}}\xspace}}\left(\frac{{\ensuremath{T_{\text{R}}}\xspace}}{2}+{D\xspace}+{R\xspace}\right)$.\
(b) **Proactive mode.** If the algorithm is in proactive mode when a fault hits, then we have chosen to take the prediction into account, a decision that is taken with probability ${\ensuremath{q}\xspace}$. The time wasted because of the predicted fault is then, in addition to the downtime and the time needed for the recovery, the time elapsed between the last checkpoint and the fault or, if no checkpoint had already been taken in the proactive mode, the time elapsed between the start of the proactive mode and the fault. Here, we can no longer assume that the time the fault hits the system is independent of the checkpointing date. This is because the proactive mode starts exactly at the beginning of the prediction window. Let [$T_{\text{lost}}$]{}denote the computation time elapsed between the latest of the beginning of the proactive mode and the last checkpoint, and the fault date. Then the expectation of [$T_{\text{lost}}$]{}depends on the distribution of the fault date in the prediction window. However, we know that whatever the distribution, ${\ensuremath{T_{\text{lost}}}\xspace}\leq {\ensuremath{T_{\text{P}}}\xspace}$. Therefore we over approximate the waste in that case by $\frac{{\ensuremath{q}\xspace}{\ensuremath{p}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}\left({\ensuremath{T_{\text{P}}}\xspace}+{D\xspace}+{R\xspace}\right)$.\
(4) **Waste due to unpredicted faults.** There are again two cases, depending upon the mode of the algorithm at the time the fault hits the system:\
(a) **Regular mode.** In this mode the work done is periodically checkpointed with period [$T_{\text{R}}$]{}. The time wasted because of an unpredicted fault is then the time elapsed between the last checkpoint and the fault, plus the downtime and the time needed for the recovery. As before, the expectation of this value is ${\ensuremath{T_{\text{lost}}}\xspace}= \frac{{\ensuremath{T_{\text{R}}}\xspace}}{2}$. An unexpected fault hits the system once every ${\ensuremath{\mu_{NP}}\xspace}$ seconds on the average. Taking into account the fraction of the time the algorithm is in regular mode, the waste due to unpredicted faults hitting the system in regular mode is $\left(1-\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}\right)\frac{1}{{\ensuremath{\mu_{NP}}\xspace}}\left(\frac{{\ensuremath{T_{\text{R}}}\xspace}}{2}+{D\xspace}+{R\xspace}\right)$.\
(b) **Proactive mode.** Because of the assumption that a single event takes place within a time-interval, we do not consider the very unlikely case where a unpredicted fault strikes during a prediction window. This amounts to assume that $\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}\frac{1}{{\ensuremath{\mu_{NP}}\xspace}}({\ensuremath{T_{\text{P}}}\xspace}+{D\xspace}+{R\xspace})$ is negligible.

We gather the expressions of the six different types of waste and simplify to obtain the formula of the overall waste: $$\begin{aligned}
   {\ensuremath{\textsc{Waste}}\xspace}_{{\textsc{WithCkptI}\xspace}}&= 
  \quad \left(\left (1 -\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}} \right )\frac{1}{{\ensuremath{T_{\text{R}}}\xspace}} +
  \frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}\frac{1}{{\ensuremath{T_{\text{P}}}\xspace}}
  + \frac{{\ensuremath{q}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}\right){C\xspace}+ \frac{{\ensuremath{p}\xspace}(1-{\ensuremath{q}\xspace})}{{\ensuremath{\mu_{P}}\xspace}}\frac{{\ensuremath{T_{\text{R}}}\xspace}}{2}  \nonumber \\
 & + \frac{{\ensuremath{p}\xspace}{\ensuremath{q}\xspace}}{{\ensuremath{\mu_{P}}\xspace}} {\ensuremath{T_{\text{P}}}\xspace}+\left (1 -\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}} \right ) \frac{1}{{\ensuremath{\mu_{NP}}\xspace}} \frac{{\ensuremath{T_{\text{R}}}\xspace}}{2}  \nonumber \\
 & + \left(\frac{{\ensuremath{p}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}+\left(1-\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}\right)\frac{1}{{\ensuremath{\mu_{NP}}\xspace}}\right)\left({D\xspace}+{R\xspace}\right)
  \label{eq.proa.waste}\end{aligned}$$

Waste of the other strategies {#sec-waste-other}
-----------------------------

The waste of the first strategy (*Instantaneous*) is very close to the one given in Equation . The difference lies in [$T_{\text{lost}}$]{}, the expectation of the work lost when a fault is predicted and the prediction is taken into account. When a prediction is taken into account and the predicted event is an actual fault, the waste in Equation  was $\frac{{\ensuremath{q}\xspace}{p\xspace}}{{\ensuremath{\mu_{P}}\xspace}}({C\xspace}+ {D\xspace}+ {R\xspace})$. Because the prediction was exact, [$T_{\text{lost}}$]{}was equal to 0. However in our new Equation, the waste for this part is now $\frac{{\ensuremath{q}\xspace}{p\xspace}}{{\ensuremath{\mu_{P}}\xspace}}({C\xspace}+ {\ensuremath{T_{\text{lost}}}\xspace}+ {D\xspace}+ {R\xspace})$. On average, the fault occurs after a time [$\mathbb{E}_{I}^{(f)}$]{}. However, because we do not know the relation between [$\mathbb{E}_{I}^{(f)}$]{}and [$T_{\text{R}}$]{}, then [$T_{\text{lost}}$]{}has expectation $\frac{{\ensuremath{T_{\text{R}}}\xspace}}{2}$ if $\frac{{\ensuremath{T_{\text{R}}}\xspace}}{2} \leq {\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}$. The new waste is then: $$\begin{aligned}
 {\ensuremath{\textsc{Waste}}\xspace}_{{\textsc{Instant}\xspace}} = \frac{{C\xspace}}{{\ensuremath{T_{\text{R}}}\xspace}} + \frac{1}{\mu} \left[ (1- {\ensuremath{r}\xspace}{\ensuremath{q}\xspace}) \frac{{\ensuremath{T_{\text{R}}}\xspace}}{2} + {D\xspace}+ {R\xspace}\right.  
 \left. + \frac{{\ensuremath{q}\xspace}{\ensuremath{r}\xspace}}{{p\xspace}} {C\xspace}+{\ensuremath{q}\xspace}{\ensuremath{r}\xspace}\min \left ( {\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}, \frac{{\ensuremath{T_{\text{R}}}\xspace}}{2} \right) \right] 
 \label{eq.waste-instant}\end{aligned}$$

As for the second strategy (*No checkpoint during prediction window*), we do no longer incur the waste due to checkpointing in proactive mode as we no longer checkpoint in proactive mode. Furthermore, the value of [$T_{\text{lost}}$]{}in proactive mode becomes [$\mathbb{E}_{I}^{(f)}$]{}instead of [$T_{\text{P}}$]{}. Consequently, the total waste when there is no checkpoint during the proactive mode is:

$$\begin{aligned}
        {\ensuremath{\textsc{Waste}}\xspace}_{\text{noCkpt}} &=\left (1 -\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}} \right )\frac{{C\xspace}}{{\ensuremath{T_{\text{R}}}\xspace}}
    + \frac{{\ensuremath{q}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}{C\xspace}+ \frac{{\ensuremath{p}\xspace}(1-{\ensuremath{q}\xspace})}{{\ensuremath{\mu_{P}}\xspace}}\left (\frac{{\ensuremath{T_{\text{R}}}\xspace}}{2} + {D\xspace}+{R\xspace}\right) \\
  & + \frac{{\ensuremath{p}\xspace}{\ensuremath{q}\xspace}}{{\ensuremath{\mu_{P}}\xspace}} \left ({\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}+ {D\xspace}+{R\xspace}\right) 
  +\left (1 -\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}} \right ) \frac{1}{{\ensuremath{\mu_{NP}}\xspace}} \left( \frac{{\ensuremath{T_{\text{R}}}\xspace}}{2} + {D\xspace}+{R\xspace}\right) \nonumber \\\end{aligned}$$

which we rewrite as $$\begin{aligned}
 {\ensuremath{\textsc{Waste}}\xspace}_{{\textsc{NoCkptI}\xspace}} &=\left(\left (1 -\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}} \right )\frac{1}{{\ensuremath{T_{\text{R}}}\xspace}} +  \frac{{\ensuremath{q}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}\right){C\xspace}+ \frac{{\ensuremath{p}\xspace}(1-{\ensuremath{q}\xspace})}{{\ensuremath{\mu_{P}}\xspace}}\frac{{\ensuremath{T_{\text{R}}}\xspace}}{2}  \nonumber \\
  & + \frac{{\ensuremath{p}\xspace}{\ensuremath{q}\xspace}}{{\ensuremath{\mu_{P}}\xspace}} {\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}+\left (1 -\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}} \right ) \frac{1}{{\ensuremath{\mu_{NP}}\xspace}} \frac{{\ensuremath{T_{\text{R}}}\xspace}}{2} \nonumber \\
 & + \left(\frac{{\ensuremath{p}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}+\left(1-\frac{{\ensuremath{I'}\xspace}}{{\ensuremath{\mu_{P}}\xspace}}\right)\frac{1}{{\ensuremath{\mu_{NP}}\xspace}}\right)\left({D\xspace}+{R\xspace}\right)
\label{eq.proa.noCkpt.waste}\end{aligned}$$

Note that when ${\ensuremath{I}\xspace}=0$, [<span style="font-variant:small-caps;">Instant</span>]{}and [<span style="font-variant:small-caps;">NoCkptI</span>]{}are identical. Indeed, we have ${\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}=0$ if ${\ensuremath{I}\xspace}=0$, and we check that Equations  and  are identical in that case.

Waste minimization {#sec-opt-int}
------------------

In this section we aim at minimizing the waste of the three strategies, and then we find conditions to characterize which one is better. Recall that : $${\ensuremath{I'}\xspace}= {\ensuremath{q}\xspace}\left ( (1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}\right )$$ **[<span style="font-variant:small-caps;">WithCkptI</span>]{}.** In order to compute the optimal value for [$T_{\text{P}}$]{}, let us find the portion of the waste that depends on [$T_{\text{P}}$]{}: $${\ensuremath{\textsc{Waste}}\xspace}_{{\ensuremath{T_{\text{P}}}\xspace}} =  \frac{{\ensuremath{r}\xspace}{\ensuremath{q}\xspace}}{ \mu}\left ( \frac{ (1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}}{{\ensuremath{p}\xspace}} \frac{ {C\xspace}}{{\ensuremath{T_{\text{P}}}\xspace}}  + {\ensuremath{T_{\text{P}}}\xspace}\right )$$ As we can see, the optimal value for [$T_{\text{P}}$]{}is independent from [$q$]{}, but also from $\mu$. The optimal value for [$T_{\text{P}}$]{}is thus: $$\label{tp.opt.int}
{\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{extr}}}}=\sqrt{ \dfrac{(1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}}{p} {C\xspace}}$$ However, for our algorithm to be correct, we want $\frac{{\ensuremath{I}\xspace}}{{\ensuremath{T_{\text{P}}}\xspace}} \in \mathbb{N}$ (the interval [$I$]{} is partitioned in $k$ intervals of length [$T_{\text{P}}$]{}, for some integer $k$). We choose ${\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{opt}}}}$ equal to either $\frac{{\ensuremath{I}\xspace}}{\left \lfloor \frac{{\ensuremath{I}\xspace}}{{\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{extr}}}}}\right \rfloor}$ or $\frac{{\ensuremath{I}\xspace}}{\left \lfloor \frac{{\ensuremath{I}\xspace}}{{\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{extr}}}}}\right \rfloor +1}$, depending on the value that minimizes ${\ensuremath{\textsc{Waste}}\xspace}_{{\ensuremath{T_{\text{P}}}\xspace}}$. Note that we also have the constraint ${\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{opt}}}} \geq {C\xspace}$, hence if both values are lower than [C]{}, then ${\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{opt}}}}={C\xspace}$.

Now that we know that ${\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{opt}}}}$ is independent from both [$q$]{}and [$T_{\text{R}}$]{}, we can see the waste in Equation  as a function of two variables. One can see from Equation  that the waste is an affine function of [$q$]{}. This means that the minimum is always reached for either ${\ensuremath{q}\xspace}=0$ or ${\ensuremath{q}\xspace}=1$. We now consider the two functions ${\ensuremath{\textsc{Waste}}\xspace}_{\text{withCkpt}\{{\ensuremath{q}\xspace}=0\}}$ and ${\ensuremath{\textsc{Waste}}\xspace}_{\text{withCkpt}\{{\ensuremath{q}\xspace}=1\}}$ in order to minimize them with respect to [$T_{\text{R}}$]{}. First we have:

$$\label{waste.int.q0}
    {\ensuremath{\textsc{Waste}}\xspace}_{\text{withCkpt}\{{\ensuremath{q}\xspace}=0\}} =\frac{{C\xspace}}{{\ensuremath{T_{\text{R}}}\xspace}} 
        + \frac{1}{\mu}\left ( \frac{{\ensuremath{T_{\text{R}}}\xspace}}{2} + {D\xspace}+{R\xspace}\right )$$

As expected, this is exactly the equation without prediction, the study of the optimal solution has been done in Section \[sec.no.intervals\], it is minimized when ${\ensuremath{T_{\text{R}}}\xspace}^{{\ensuremath{\text{opt}}}_0} =\min \left( \alpha {\ensuremath{\mu_e}\xspace}- {\ensuremath{I}\xspace}, \max \left ( \sqrt{2  {C\xspace}\mu}, {C\xspace}\right )\right )$.

Next we have: $$\begin{aligned}
    \label{waste.int.q1}
    {\ensuremath{\textsc{Waste}}\xspace}_{\text{withCkpt}\{{\ensuremath{q}\xspace}=1\}} &= \left (1 -\frac{{\ensuremath{r}\xspace}\left ( (1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}\right )}{{\ensuremath{p}\xspace}\mu} \right ) \left ( \frac{{C\xspace}}{{\ensuremath{T_{\text{R}}}\xspace}} +  \frac{1-{\ensuremath{r}\xspace}}{\mu}\frac{{\ensuremath{T_{\text{R}}}\xspace}}{2} \right )\nonumber \\
        & +\frac{{\ensuremath{r}\xspace}}{ \mu}\left ( \frac{\left ( (1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}\right )}{{\ensuremath{p}\xspace}} \frac{{C\xspace}}{{\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{opt}}}}}  + {\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{opt}}}} \right )  + \frac{{\ensuremath{r}\xspace}}{{\ensuremath{p}\xspace}\mu}{C\xspace}\nonumber \\ 
              & + \left(\frac{{\ensuremath{r}\xspace}}{\mu}+\left (1 -\frac{{\ensuremath{r}\xspace}\left ( (1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}\right )}{{\ensuremath{p}\xspace}\mu} \right )\frac{1-{\ensuremath{r}\xspace}}{\mu}\right)\left({D\xspace}+{R\xspace}\right)\end{aligned}$$ This equation is minimized when $${\ensuremath{T_{\text{R}}}\xspace}^{{\ensuremath{\text{opt}}}_1} = \sqrt{ \dfrac{2 \mu{C\xspace}}{(1-{\ensuremath{r}\xspace})}}$$ One can remark that this value is equal to the result without intervals (Section \[sec.no.intervals\]). Actually, the only impact of the prediction interval [$I$]{}is the moment when we should take a pre-emptive action. Note that when ${\ensuremath{r}\xspace}=0$ (this means that there is no prediction), we have ${\ensuremath{T_{\text{R}}}\xspace}^{{\ensuremath{\text{opt}}}_1} = {\ensuremath{T_{\text{R}}}\xspace}^{{\ensuremath{\text{opt}}}_0} $, and we retrieve Young’s formula [@young74].

Finally, we know that the waste is defined for ${C\xspace}\leq {\ensuremath{T_{\text{R}}}\xspace}\leq \alpha {\ensuremath{\mu_e}\xspace}- {\ensuremath{I}\xspace}$. Hence, if ${\ensuremath{T_{\text{R}}}\xspace}^{{\ensuremath{\text{opt}}}_1} \notin [{C\xspace},\alpha {\ensuremath{\mu_e}\xspace}- {\ensuremath{I}\xspace}]$, this solution is not satisfiable. However Equation  is convex, so the optimal solution is [C]{}if ${\ensuremath{T_{\text{R}}}\xspace}^{{\ensuremath{\text{opt}}}_1} < {C\xspace}$, and $\alpha {\ensuremath{\mu_e}\xspace}- {\ensuremath{I}\xspace}$ if ${\ensuremath{T_{\text{R}}}\xspace}^{{\ensuremath{\text{opt}}}_1} > \alpha {\ensuremath{\mu_e}\xspace}$. Hence, when ${\ensuremath{q}\xspace}=1$, the optimal solution should be $$\label{tnp.opt.int}
\min \left (\alpha {\ensuremath{\mu_e}\xspace}- {\ensuremath{I}\xspace},\max \left (\sqrt{ \dfrac{2 \mu{C\xspace}}{(1-{\ensuremath{r}\xspace})}},{C\xspace}\right )\right).$$

**[<span style="font-variant:small-caps;">Instant</span>]{}**. The derivation is similar . The optimal value for [$q$]{}is either $0$ or $1$, thus we consider ${\ensuremath{\textsc{Waste}}\xspace}_{{\textsc{Instant}\xspace}}^{\{0\}}  = {\ensuremath{\textsc{Waste}_Y}\xspace}$ and ${\ensuremath{\textsc{Waste}}\xspace}_{{\textsc{Instant}\xspace}}^{\{1\}}$. If ${\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}>\frac{{\ensuremath{T_{\text{R}}}\xspace}}{2}$, then ${\ensuremath{\textsc{Waste}}\xspace}_{{\textsc{Instant}\xspace}}^{\{0\}} < {\ensuremath{\textsc{Waste}}\xspace}_{{\textsc{Instant}\xspace}}^{\{1\}}$, so we can assume $\min({\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}, \frac{{\ensuremath{T_{\text{R}}}\xspace}}{2}) = {\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}$. Then we derive that ${\ensuremath{\textsc{Waste}}\xspace}_{{\textsc{Instant}\xspace}}^{\{1\}}$ is minimized for ${\ensuremath{T_{\text{R}}}\xspace}^{{\ensuremath{\text{opt}}}_1}$ as before.\
**[<span style="font-variant:small-caps;">NoCkptI</span>]{}**. One can see that Equation  and Equation  only differ by the quantity : $$\frac{{\ensuremath{q}\xspace}{\ensuremath{r}\xspace}}{\mu}\left ( \frac{(1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}}{{\ensuremath{p}\xspace}} \frac{{C\xspace}}{{\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{opt}}}}}  + {\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{opt}}}} - {\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}\right )$$ This value is linear in [$q$]{}and a constant with regards to [$T_{\text{R}}$]{}. Hence the minimization is almost the same.

Once again we can see that the optimal value for [$q$]{}is either 0 or 1. We can consider the two functions ${\ensuremath{\textsc{Waste}}\xspace}_{\text{noCkpt}\{{\ensuremath{q}\xspace}=0\}}$ and ${\ensuremath{\textsc{Waste}}\xspace}_{\text{noCkpt}\{{\ensuremath{q}\xspace}=1\}}$. We remark that ${\ensuremath{\textsc{Waste}}\xspace}_{\text{noCkpt}\{{\ensuremath{q}\xspace}=0\}} = {\ensuremath{\textsc{Waste}}\xspace}_{\text{withCkpt}\{{\ensuremath{q}\xspace}=0\}}$, and hence that the study has already been done. As for ${\ensuremath{\textsc{Waste}}\xspace}_{\text{noCkpt}\{{\ensuremath{q}\xspace}=1\}}$, it is also minimized when ${\ensuremath{T_{\text{R}}}\xspace}^{{\ensuremath{\text{opt}}}} = \sqrt{ \dfrac{2 \mu{C\xspace}}{(1-{\ensuremath{r}\xspace})}}$.

Finally, the last step of this study is identical to the previous minimization, and the optimal solution when ${\ensuremath{q}\xspace}=1$ is defined by : $${\ensuremath{T_{\text{R}}}\xspace}^{{\ensuremath{\text{opt}}}_1}=\min \left (\alpha {\ensuremath{\mu_e}\xspace}- {\ensuremath{I}\xspace},\max \left (\sqrt{ \dfrac{2 \mu{C\xspace}}{(1-{\ensuremath{r}\xspace})}},{C\xspace}\right )\right)$$

**Summary**. Finally in this section, we consider the waste for the two algorithms that take the prediction window into account (the one that does not checkpoint during the prediction window, and the one that checkpoints during the prediction window), and try to find conditions of dominance of one strategy over the other. Since the equation of the waste is identical when ${\ensuremath{q}\xspace}=0$, let us consider the case when ${\ensuremath{q}\xspace}=1$. We have seen that:

$$\begin{aligned}
    \label{diff.waste.algo}
 ({\ensuremath{\textsc{Waste}}\xspace}_{\text{withCkpt}\{{\ensuremath{q}\xspace}=1\}} - {\ensuremath{\textsc{Waste}}\xspace}_{\text{noCkpt}\{{\ensuremath{q}\xspace}=1\}}) & = 
 \frac{{\ensuremath{r}\xspace}\left ( (1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}\right )}{{\ensuremath{p}\xspace}\mu}\frac{{C\xspace}}{{\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{opt}}}}} \nonumber \\
 & + \frac{{\ensuremath{r}\xspace}}{\mu} \left ( {\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{opt}}}} - {\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}\right )
 \end{aligned}$$

We want to know when Equation  is nonnegative (meaning that it is beneficial not to take any checkpoints during proactive mode). We know that this value is minimized when ${\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{extr}}}}=\sqrt{ \dfrac{ (1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}}{p}{C\xspace}}$ (Equation ), then a sufficient condition would be to study the equation : $${\ensuremath{\textsc{Waste}}\xspace}_{\text{withCkpt}\{{\ensuremath{q}\xspace}=1\}} - {\ensuremath{\textsc{Waste}}\xspace}_{\text{noCkpt}\{{\ensuremath{q}\xspace}=1\}} \geq 0$$ with ${\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{extr}}}}$ instead of ${\ensuremath{T_{\text{P}}}\xspace}^{{\ensuremath{\text{opt}}}}$. That is: $$\begin{aligned}
&\frac{{\ensuremath{r}\xspace}(1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}}{{\ensuremath{p}\xspace}\mu}\frac{{C\xspace}}{\sqrt{ \dfrac{ (1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}}{p} {C\xspace}}} + \frac{{\ensuremath{r}\xspace}}{\mu} \left ( \sqrt{ \dfrac{ (1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}}{p} {C\xspace}} - {\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}\right ) &\geq 0 \nonumber\\
& \Leftrightarrow 2\sqrt{ \dfrac{ (1 - {\ensuremath{p}\xspace}) {\ensuremath{I}\xspace}+ {\ensuremath{p}\xspace}{\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}}{p} {C\xspace}} \geq {\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}\!^2
\label{cond.noCkpt}\end{aligned}$$

Consequently, we can say that if Equation  is matched, then ${\ensuremath{\textsc{Waste}}\xspace}_{\text{noCkpt}}$ $\leq {\ensuremath{\textsc{Waste}}\xspace}$, the algorithm where we do not checkpoint during the proactive mode has a better solution than Algorithm \[algo.proactive\]. For example, if we assume that faults strike uniformly during the prediction window $[t_{0}, t_{0}+{\ensuremath{I}\xspace}]$, in other words, if $0 \leq x \leq {\ensuremath{I}\xspace}$, the probability that the fault occurs in the interval $[t_{0}, t_{0}+x]$ is $\frac{x}{{\ensuremath{I}\xspace}}$, then ${\ensuremath{\mathbb{E}_{I}^{(f)}}\xspace}=\frac{I}{2}$, and our condition becomes $${\ensuremath{I}\xspace}\leq 16 \frac{1 - \sfrac{{\ensuremath{p}\xspace}}{2}}{{\ensuremath{p}\xspace}}{C\xspace}.$$

We can now finish our study by saying that in order to find the optimal solution, one should compute both optimal solutions for ${\ensuremath{q}\xspace}=0$ and ${\ensuremath{q}\xspace}= 1$, for both algorithms, and choose the one that minimizes the waste, as was done in Section \[sec.no.intervals\], except when Equation  is valid, then we can focus on the computation of the waste of the algorithms that does not checkpoint during proactive mode.

Simulation results {#sec.simulations}
==================

In order to validate our model, we have instantiated it with several scenarios. The experiments use parameters that are representative of current and forthcoming large-scale platforms [@j116; @Ferreira2011]. We have $C=R=10mn$, and $D=1mn$. The individual (processor) MTBF $\mu_{ind} = 125$ years, and the total number of processors $N$ varies from $N=16,384$ to $N=524,288$, so that the platform MTBF $\mu$ varies from $\mu=4,000mn$ (about $1.5$ day) down to $\mu=125mn$ (about $2$ hours). For instance the Jaguar platform, with $N=45,208$ processors, is reported to experience about one failure per day [@6264677], which leads to $\mu_{ind} = \frac{45,208}{365}\approx 125$ years.

We have analytically computed the optimal value of the waste for each strategy (using the formulas of Section \[sec-opt-int\]) using a computer algebra software. In order to check the accuracy of our model, we have compared the results with those from simulations using a fault generator. Our simulation engine generates a random trace of failures, parameterized either by an Exponential failure distribution or by a Weibull distribution law with shape parameter $0.5$ and $0.7$; Exponential failures are widely used for theoretical studies, while Weibull failures are representative of the behavior of real-world platforms [@Weibull1; @Weibull2; @Heien:2011:MTH:2063384.2063444]. With probability [$r$]{}, we decide if a failure is predicted or not. In both cases, the distribution is scaled so that its expectation corresponds to the platform MTBF $\mu$. Then the simulation engine generates another random trace of false predictions (whose distribution is identical to the first trace or a uniform distributions). This second distribution is scaled so that its expectation is $\frac{{\ensuremath{p}\xspace}\mu}{{\ensuremath{r}\xspace}(1-{\ensuremath{p}\xspace})}$, the inter-arrival time of false predictions. Finally, both traces are merged to derive the final trace with all events. Each value reported for the simulations is the average of $100$ randomly generated experiments.

In the simulations, we compare up to ten checkpointing strategies. Here is the list:\
$\bullet$ [<span style="font-variant:small-caps;">Young</span>]{}is the periodic checkpointing strategy of period ${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{0\}}}\xspace} = \sqrt{2 \mu {C\xspace}}$ given in [@young74]. Note that Daly’s formula [@daly04] leads to the same results.\
$\bullet$ [<span style="font-variant:small-caps;">ExactPrediction</span>]{}is derived from the strategy Section \[sec.no.intervals\] (with exact prediction dates). However, in the simulations, we always take prediction into account and use an uncapped period ${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{1\}}}\xspace} = \sqrt{ \dfrac{2 \mu{C\xspace}}{1-{\ensuremath{r}\xspace}}}$ instead of ${\ensuremath{T_{1} }\xspace} = \min(\alpha {\ensuremath{\mu_e}\xspace}- {\ensuremath{I}\xspace}, \max({C\xspace}, {\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{1\}}}\xspace}))$.\
$\bullet$ Similarly, [<span style="font-variant:small-caps;">Instant</span>]{}, [<span style="font-variant:small-caps;">NoCkptI</span>]{}and [<span style="font-variant:small-caps;">WithCkptI</span>]{}are the three strategies described in Section \[sec.intervals\], with the same modification: we always take prediction into account and use an uncapped period ${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{1\}}}\xspace} $ instead of ${\ensuremath{T_{1} }\xspace}$ in regular mode.\
$\bullet$ To assess the quality of each strategy, we compare it with its [<span style="font-variant:small-caps;">BestPeriod</span>]{}counterpart, defined as the same strategy but using the best possible period ${\ensuremath{T_{\text{R}}}\xspace}$. This latter period is computed via a brute-force numerical search for the optimal period.

The rationale for modifying the strategies described in the previous sections is of course to better assess the impact of prediction. For the computer algebra plots, in addition to the waste with the *capped periods* given in Section \[sec-opt-int\], i.e., with ${\ensuremath{T_{0} }\xspace}= {\ensuremath{T_{\text{Y}}}\xspace}= \min(\alpha \mu, \max({C\xspace}, {\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{0\}}}\xspace}))$, and ${\ensuremath{T_{1} }\xspace} = \min(\alpha {\ensuremath{\mu_e}\xspace}- {\ensuremath{I}\xspace}, \max({C\xspace}, {\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{1\}}}\xspace}))$, we also report the waste obtained for the *uncapped periods*, i.e., using ${\ensuremath{T_{0} }\xspace} = {\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{0\}}}\xspace}$ without prediction and ${\ensuremath{T_{1} }\xspace} = {\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{1\}}}\xspace} = \sqrt{ \dfrac{2 \mu{C\xspace}}{1-{\ensuremath{r}\xspace}}}$ with prediction. The objective is twofold: (i) Assess whether the validity of the model can be extended; and (ii) Provide an exact match with the simulations, which mimic a real-life execution and do allow for an arbitrary number of faults per period.

Predictors from the literature
------------------------------

We first experiment with two predictors from the literature: one accurate predictor with high recall and precision [@5958823], namely with ${\ensuremath{p}\xspace}=0.82$ and ${\ensuremath{r}\xspace}=0.85$, and another predictor with more limited recall and precision [@5542627], namely with ${\ensuremath{p}\xspace}=0.4$ and ${\ensuremath{r}\xspace}=0.7$. In both cases, we use two different time-windows, ${\ensuremath{I}\xspace}=300s$ and ${\ensuremath{I}\xspace}=3,000s$. The former value does not allow for checkpointing within the prediction window, while the latter values allow for several checkpoints. Note that we always compare the results with [<span style="font-variant:small-caps;">ExactPrediction</span>]{}, the strategy that assumes exact prediction dates. Figures \[fig.082.085\] and \[fig.04.07\] show the average waste degradation of the ten heuristics for both predictors, as a function of the number of processors $N$. We draw the plots as a function of the number of processors $N$ rather than of the platform MTBF $\mu = \mu_{ind}/N$ , because it is more natural to see the waste increase with larger platforms; however, this work is agnostic of the granularity of the processors and intrinsically focuses on the impact of the MTBF on the waste.

The first observation is that the prediction is always useful for the whole set of parameters under study! The second observation is the good correspondence between analytical results and simulations in Figures \[fig.082.085\] and \[fig.04.07\] (compare subfigures (a) and (b) with (c), (d) and (e), and subfigures (f) and (g) with (h), (i) and (j)). This shows the validity of the model for the whole range of distributions (Exponential and both Weibull shapes). More precisely: (i) The capped model overestimates the waste for large platforms (or small MTBFs), in particular for large values of ${\ensuremath{I}\xspace}$ (see Figures \[fig.082.085\](f) and \[fig.04.07\](f)), but this was the price to pay for mathematical rigor; (ii) The uncapped model is accurate for the whole range of the study. Another striking result is that all strategies taking prediction into account have the same waste as their [<span style="font-variant:small-caps;">BestPeriod</span>]{}counterpart, which demonstrates that our formula ${\ensuremath{T_{{\ensuremath{\text{extr}}}}^{\{1\}}}\xspace} = \sqrt{\frac{2 \mu {C\xspace}}{1-{\ensuremath{r}\xspace}}}$ is indeed the best possible checkpointing period in regular mode.

Unsurprisingly, [<span style="font-variant:small-caps;">ExactPrediction</span>]{}is better than the heuristics that use a time window instead of exact prediction dates, especially with a high number of processors. However, interval based heuristics achieve close results when ${\ensuremath{I}\xspace}=300s$, or when ${\ensuremath{I}\xspace}=3,000s$ and a small number of processors ($N<2^{16}$).

\
\

\

\

\

In order to compare the heuristics without prediction to those with prediction, we report job execution times in Table \[makespan.300.tab\]. For the strategies with prediction, we compute the gain (expressed in percentage) over [<span style="font-variant:small-caps;">Young</span>]{}, the reference strategy without prediction. For ${\ensuremath{I}\xspace}=300s$, the three strategies are identical. But for ${\ensuremath{I}\xspace}=3,000s$, [<span style="font-variant:small-caps;">WithCkptI</span>]{}has often better results. First, with ${\ensuremath{p}\xspace}=0.85$ and ${\ensuremath{r}\xspace}=0.82$ and ${\ensuremath{I}\xspace}=3,000s$, we save $25\% $ of the total time with $N=2^{19}$, and $14\%$ with $N=2^{16}$ using strategy [<span style="font-variant:small-caps;">WithCkptI</span>]{}. With ${\ensuremath{I}\xspace}=300s$, we save up to $44\%$ with $N=2^{19}$, and $18\%$ with $N=2^{16}$ using any strategy (though [<span style="font-variant:small-caps;">NoCkptI</span>]{}is slightly better than [<span style="font-variant:small-caps;">Instant</span>]{}). Then, with ${\ensuremath{p}\xspace}=0.4$ and ${\ensuremath{r}\xspace}= 0.7$, we still save $32\%$ of the execution time when ${\ensuremath{I}\xspace}=300s$ and $N=2^{19}$, and $13\%$ with $N=2^{16}$. The gain gets smaller with ${\ensuremath{I}\xspace}=3,000s$, but remains non negligible since we can save up to $9.7\%$ with $N=2^{19}$, and $7.6\%$ with $N=2^{16}$. Unexpectedly in this last case, the strategy that is the most efficient is [<span style="font-variant:small-caps;">Instant</span>]{}and not [<span style="font-variant:small-caps;">WithCkptI</span>]{}.

We observe that the size of the prediction-window [$I$]{}plays an important role too: we have better results for ${\ensuremath{I}\xspace}=300$ and $({\ensuremath{p}\xspace},{\ensuremath{r}\xspace})=(0.4,0.7)$, than for ${\ensuremath{I}\xspace}=3000$ and $({\ensuremath{p}\xspace},{\ensuremath{r}\xspace})=(0.82,0.85)$.

In Table \[makespan.300.tab\], we report the job execution times for Weibull distributions with $k=0.5$.

For ${\ensuremath{I}\xspace}=300s$, the three strategies are identical. But for ${\ensuremath{I}\xspace}=3,000s$, [<span style="font-variant:small-caps;">WithCkptI</span>]{}has often better results. First, with ${\ensuremath{p}\xspace}=0.85$ and ${\ensuremath{r}\xspace}=0.82$ and ${\ensuremath{I}\xspace}=3,000s$, we save $61\% $ of the total time with $N=2^{19}$, and $30\%$ with $N=2^{16}$ using strategy [<span style="font-variant:small-caps;">WithCkptI</span>]{}.

With ${\ensuremath{I}\xspace}=300s$, we save up to $74\%$ with $N=2^{19}$, and $38\%$ with $N=2^{16}$ using any strategy (though [<span style="font-variant:small-caps;">NoCkptI</span>]{}is slightly better than [<span style="font-variant:small-caps;">Instant</span>]{}).

Then, with ${\ensuremath{p}\xspace}=0.4$ and ${\ensuremath{r}\xspace}= 0.7$, we still save $66\%$ of the execution time when ${\ensuremath{I}\xspace}=300s$ and $N=2^{19}$, and $33\%$ with $N=2^{16}$. The gain gets smaller with ${\ensuremath{I}\xspace}=3,000s$, but we can save up to $52\%$ with $N=2^{19}$, and $22\%$ with $N=2^{16}$.

Using a Weibull failure distribution with shape parameter 0.5, we observe that the gain due to prediction is twice larger than the gain computed with a Weibull failure distribution with shape parameter 0.7. We can conclude the same remark from Figures \[fig.082.085\](e), \[fig.082.085\](j), \[fig.04.07\](e) and \[fig.04.07\](j).

We also performed simulations with a trace of false predictions parametrized by a uniform distribution and we observe that the result (Figures  \[fig.082.085.UNIF\] and  \[fig.04.07.UNIF\]) are similar to the result (Figures  \[fig.082.085\] and  \[fig.04.07\]) with simulations with a trace of false predictions parametrized by a distribution identical to the distribution of the trace of failures.

  ------------------------------------------------------------------- ---------------- ---------------- ---------------- ----------------
                                                                                                                         
                     ${\ensuremath{I}\xspace}=300$                                                                       
                                                                       $2^{16}$ procs   $2^{19}$ procs   $2^{16}$ procs   $2^{19}$ procs
        [<span style="font-variant:small-caps;">Young</span>]{}             81.3             30.1             81.2             30.1
   [<span style="font-variant:small-caps;">ExactPrediction</span>]{}     65.9 (19%)       15.9 (47%)       69.7 (14%)       19.3 (36%)
       [<span style="font-variant:small-caps;">NoCkptI</span>]{}         66.5 (18%)       16.9 (44%)       70.3 (13%)       20.5 (32%)
       [<span style="font-variant:small-caps;">Instant</span>]{}         66.5 (18%)       17.0 (44%)       70.3 (13%)       20.7 (31%)
  ------------------------------------------------------------------- ---------------- ---------------- ---------------- ----------------

  : Comparing job execution times for a Weibull distribution ($k=0.7$), and reporting the gain when comparing to [<span style="font-variant:small-caps;">Young</span>]{}.[]{data-label="makespan.300.tab"}

\

  ------------------------------------------------------------------- ---------------- ---------------- ---------------- ----------------
                                                                                                                         
                    ${\ensuremath{I}\xspace}=3,000$                                                                      
                                                                       $2^{16}$ procs   $2^{19}$ procs   $2^{16}$ procs   $2^{19}$ procs
        [<span style="font-variant:small-caps;">Young</span>]{}             81.2             30.1             81.2             30.1
   [<span style="font-variant:small-caps;">ExactPrediction</span>]{}     66.0 (19%)       15.9 (47%)       69.8 (14%)       19.3 (36%)
       [<span style="font-variant:small-caps;">NoCkptI</span>]{}         71.1 (12%)       24.6 (18%)      75.2 (7.3%)      28.9 (4.0%)
      [<span style="font-variant:small-caps;">WithCkptI</span>]{}        70.0 (14%)       22.6 (25%)      75.4 (7.1%)      27.2 (9.7%)
       [<span style="font-variant:small-caps;">Instant</span>]{}         71.2 (12%)       24.2 (20%)      75.0 (7.6%)      28.3 (6.0%)
  ------------------------------------------------------------------- ---------------- ---------------- ---------------- ----------------

  : Comparing job execution times for a Weibull distribution ($k=0.7$), and reporting the gain when comparing to [<span style="font-variant:small-caps;">Young</span>]{}.[]{data-label="makespan.300.tab"}

  ------------------------------------------------------------------- ---------------- ---------------- ---------------- ----------------
                                                                                                                         
                     ${\ensuremath{I}\xspace}=300$                                                                       
                                                                       $2^{16}$ procs   $2^{19}$ procs   $2^{16}$ procs   $2^{19}$ procs
        [<span style="font-variant:small-caps;">Young</span>]{}            125.4            171.8            125.5            171.7
   [<span style="font-variant:small-caps;">ExactPrediction</span>]{}     75.8 (40%)       39.4 (77%)       82.9 (34%)       51.8(70%)
       [<span style="font-variant:small-caps;">NoCkptI</span>]{}         77.3 (38%)       44.8 (74%)       84.6 (33%)       58.2 (66%)
       [<span style="font-variant:small-caps;">Instant</span>]{}         77.4 (38%)       45.1 (74%)       84.7 (33%)       59.1 (66%)
  ------------------------------------------------------------------- ---------------- ---------------- ---------------- ----------------

  : Comparing job execution times for a Weibull distribution ($k=0.5$), and reporting the gain when comparing to [<span style="font-variant:small-caps;">Young</span>]{}.[]{data-label="makespan.300.tab"}

\

  ------------------------------------------------------------------- ---------------- ---------------- ---------------- ----------------
                                                                                                                         
                    ${\ensuremath{I}\xspace}=3,000$                                                                      
                                                                       $2^{16}$ procs   $2^{19}$ procs   $2^{16}$ procs   $2^{19}$ procs
        [<span style="font-variant:small-caps;">Young</span>]{}            125.4            171.9            125.4            172.0
   [<span style="font-variant:small-caps;">ExactPrediction</span>]{}     76.1 (39%)       39.4 (77%)       83.0 (34%)       51.7 (70%)
       [<span style="font-variant:small-caps;">NoCkptI</span>]{}         90.0 (28%)       71.8 (58%)       98.3 (22%)       84.5 (51%)
      [<span style="font-variant:small-caps;">WithCkptI</span>]{}        87.8 (30%)       66.6 (61%)       98.0 (22%)       82.2 (52%)
       [<span style="font-variant:small-caps;">Instant</span>]{}         89.8 (28%)       70.9 (59%)       98.2 (22%)       83.2 (52%)
  ------------------------------------------------------------------- ---------------- ---------------- ---------------- ----------------

  : Comparing job execution times for a Weibull distribution ($k=0.5$), and reporting the gain when comparing to [<span style="font-variant:small-caps;">Young</span>]{}.[]{data-label="makespan.300.tab"}

Recall vs. precision {#sec.impact}
--------------------

In this section, we assess the impact of the two key parameters of the predictor, its recall [$r$]{}and its precision ${\ensuremath{p}\xspace}$. To this purpose, we conduct simulations where one parameter is fixed, and we let the other vary. We choose two platforms, a smaller one with $N=2^{16}$ processors (or a MTBF $\mu=1,000mn$) and the other with $N=2^{19}$ processors (or a MTBF $\mu=125mn$). In both cases, we use a prediction-window of size ${\ensuremath{I}\xspace}=300s$, and a Weibull failure distribution with shape parameter $k=0.7$ (we have similar results (Figures  \[fig.recall.19.05\] and  \[fig.precision.19.05\]) for $k=0.5$).

In Figure \[fig.recall.19\], we fix the value of [$r$]{}(either ${\ensuremath{r}\xspace}=0.4$ or ${\ensuremath{r}\xspace}=0.8$) and we let ${\ensuremath{p}\xspace}$ vary from $0.3$ to $0.99$. In the four plots, we observe that the precision has a minor impact on the waste. In Figure \[fig.precision.19\], we conduct the opposite experiment and fix the value of [$p$]{}(either $ {\ensuremath{p}\xspace}=0.4$ or ${\ensuremath{p}\xspace}=0.8$), letting ${\ensuremath{r}\xspace}$ vary from $0.3$ to $0.99$. Here we observe that increasing the recall can significantly improve the performance.

Altogether we conclude that it is more important (for the design of future predictors) to focus on improving the recall [$r$]{}rather than the precision [$p$]{}, and our results can help quantify this statement. We provide an intuitive explanation as follows: unpredicted failures prove very harmful and heavily increase the waste, while unduly checkpointing due to false predictions turns out to induce a smaller overhead.

Related work {#sec.related}
============

Considerable research has been conducted on fault prediction using different models (system log analysis [@5958823], event-driven approach [@GainaruIPDPS12; @5958823; @5542627], support vector machines [@LiangZXS07; @Fulp:2008:PCS:1855886.1855891]), nearest neighbors [@LiangZXS07], …). In this section we give a brief overview of the results obtained by predictors. We focus on their results rather than on their methods of prediction.

The authors of [@5542627] introduce the *lead time*, that is the time between the prediction and the actual fault. This time should be sufficient to take proactive actions. They are also able to give the location of the fault. While this has a negative impact on the precision (see the low value of [$p$]{}in Table \[rel.work.tab\]), they state that it has a positive impact on the checkpointing time (from 1500 seconds to 120 seconds). The authors of [@5958823] also consider a lead time, and introduce a *prediction window* when the predicted fault should happen. The authors of [@LiangZXS07] study the impact of different prediction techniques with different prediction window sizes. They also consider a lead time, but do not state its value. These two latter studies motivate the work of Section \[sec.intervals\], even though [@5958823] does not provide the size of their prediction window.

Unfortunately, much of the work done on prediction does not provide information that could be really useful for the design of efficient algorithms. These informations are those stated above, namely the lead time and the size of the prediction window, but other information that could be useful would be: (i) the distribution of the faults in the prediction window; (ii) the precision as a function of the recall (see our analysis); and (iii) the precision and recall as functions of the prediction window (what happens with a larger prediction window).

While many studies on fault prediction focus on the conception of the predictor, most of them consider that the proactive action should simply be a checkpoint or a migration right in time before the fault. However, in their paper [@Fu:2007:EEC:1362622.1362678], Li et al. consider the mathematical problem to determine when and how to migrate. In order to be able to use migration, they stated that at every time, 2% of the resources are available. This allowed them to conceive a Knapsack-based heuristic. Thanks to their algorithm, they were able to save 30% of the execution time compared to an heuristic that does not take the reliability into account, with a precision and recall of 70%, and with a maximum load of 0.7.

Finally, to the best of our knowledge, this work is the first to focus on the mathematical aspect of fault prediction, and to provide a model and a detailed analysis of the waste due to all three types of events (true and false predictions and unpredicted failures).

Conclusion {#sec.conclusion}
==========

In this work, we have studied the impact of prediction, either with exact dates or window-based, on checkpointing strategies. We have designed several algorithms that decide when to trust these predictions, and when it is worth taking preventive checkpoints. We have introduced an analytical model to capture the waste incurred by each strategy, and provided the optimal solution to the corresponding optimization problems. We have been able to derive some striking conclusions:\
$\bullet$ The model is quite accurate and its validity goes beyond the conservative assumption that requires capping checkpointing periods to diminish the probability of having several faults within the same period;\
$\bullet$ A unified formula for the optimal checkpointing period is $\sqrt{ \dfrac{2 \mu{C\xspace}}{1-{\ensuremath{r}\xspace}{\ensuremath{q}\xspace}}}$, which unifies both cases with and without prediction, and nicely extends the work of Young and Daly to account for prediction;\
$\bullet$ The simulations fully validate the model, and show that: (i) A significant gain is induced by using predictions, even for mid-range values of recall and precision; and (ii) The best period (found by brute-force search) is always very close to the one predicted by the model and given by the previous unified formula; this holds true both for Exponential and Weibull failure distributions;\
$\bullet$ The recall has more impact on the waste than the precision: *better safe than sorry*, or better prepare for a false event than miss an actual failure!

Altogether, the analytical model and the comprehensive results provided in this work enable to fully assess the impact of fault prediction on optimal checkpointing strategies. Future work will be devoted to refine the assessment of the usefulness of prediction with trace-based failure and prediction logs from current large-scale supercomputers.

[*Acknowledgments.*]{} The authors are with Université de Lyon, France. Y. Robert is with the Institut Universitaire de France. This work was supported in part by the ANR [*RESCUE*]{} project.
