{'fraction_non_alphanumeric': 0.03264068088188691, 'fraction_numerical': 0.010095522658336728, 'mean_word_length': 4.412103393360284, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Checkpointing strategies with prediction windows

This paper deals with the impact of fault prediction techniques on checkpointing strategies. We suppose that the fault-prediction system provides prediction windows instead of exact predictions, which dramatically complicates the analysis of the checkpointing strategies. We propose a new approach based upon two periodic modes, a regular mode outside prediction windows, and a proactive mode inside prediction windows, whenever the size of these windows is large enough. We are able to compute the best period for any size of the prediction windows, thereby deriving the scheduling strategy that minimizes platform waste. In addition, the results of this analytical evaluation are nicely corroborated by a comprehensive set of simulations, which demonstrate the validity of the model and the accuracy of the approach.


Introduction
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 µ 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 opt of T that minimizes the expected waste of resource usage due to checkpointing is easily approximated as T opt = √ 2µC +C, or T opt = 2(µ + R)C +C (where R is the duration of the recovery). The former expression is the well-known Young's formula [18], while the latter is due to Daly [6].
Assume now that some fault prediction system is available. Such a system is characterized by two critical parameters, 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). In the simple case where predictions are exact-date predictions, several recent papers [10,1] have independently shown that the optimal checkpointing period becomes T opt = 2µC 1 − r . This latter expression is valid only when µ is large enough and can be seen as an extension of Young's formula where µ is replaced by µ 1−r : faults are replaced by non-predicted faults, and the overhead due to false predictions is negligible. A more accurate expression for the optimal checkpointing period is available in [1]. This paper deals with the realistic case (see [19,16] and Section 5) where the predictor system does not provide exact dates for predicted events, but instead provides prediction windows. A prediction window is a time interval of length I during which the predicted event is likely to happen. Intuitively, one is more at risk during such an interval than in the absence of any prediction, hence the need to checkpoint more frequently. But with which period? And what is the size of the prediction window above which it proves worthwhile to use a different (smaller) checkpointing period?
The main objective of this paper is to provide a quantitative answer to these questions. Our key contributions are the following: (i) The design of several checkpointing policies that account for the different sizes of prediction windows; (ii) The analytical characterization of the best policy for each set of parameters; and (iii) The validation of the theoretical results via extensive simulations, for both Exponential and Weibull failure distributions. It turns out that the analysis of the waste is dramatically more complicated than when using exact-date predictions [10,1].
The rest of the paper is organized as follows. First we detail the framework in Section 2. In Section 3 we describe the new checkpointing policies with prediction windows, and show how to compute the optimal checkpointing periods that minimize the platform waste. Section 4 is devoted to simulations. Section 5 provides a brief overview of related work. Finally, we present concluding remarks in Section 6.

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. Checkpoints are taken at regular intervals, or periods, of length T . We denote by C the duration of a checkpoint; by construction, we must enforce that C ≤ T . Useful work is done only during T − C units of time for every period of length T , if no fault occurs. Hence the waste due to checkpointing in a fault-free execution is Waste = C T . In the following, the waste always denote the fraction of time that the platform is not doing useful work.
When a fault strikes the platform, the application is lacking some resource for a certain period of time of length D, the downtime. The downtime accounts for software rejuvenation (i.e., rebooting [14,5]) or for the replacement of the failed hardware component by a spare one. Then, the application recovers from the last checkpoint. R denotes the duration of this recovery time.

Fault predictor
A fault predictor is a mechanism that is able to predict that some faults will take place, within some time-interval window. In this paper, we assume that the predictor is able to generate its predictions early enough so that a proactive checkpoint can indeed be taken before or during the event. A first proactive checkpoint will typically be taken just before the beginning of the prediction window, and possibly several other ones will be taken inside the prediction window, if its size I is large enough.
Proactive checkpoints may have a different length C p than regular checkpoints of length C. In fact there are many scenarios. On the one hand, we may well have C p > C in scenarios where regular checkpoints are taken at time-steps where the application memory footprint is minimal [13]; on the contrary, proactive checkpoints are taken according to predictions that can take place at arbitrary instants. On the other hand, we may have C p < C in other scenarios [21], e.g., when the prediction is localized to a particular resource subset, hence allowing for a smaller volume of checkpointed data. To keep full generality, we deal with two checkpoint sizes in this paper: C for periodic checkpoints, and C p for proactive checkpoints (those taken upon predictions).
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 True P be their number); (ii) False positive events are fault predictions that did not materialize as actual faults (let False P be their number); and (iii) False negative events are faults that were not predicted (let False N be their number). With these definitions, we have r = True P True P +False N and p = True P True P +False P . In the literature, the lead time is the interval between the date at which the prediction is made available, and the predicted date of failure (or, more precisely, the beginning of the prediction window). However, because we do not consider pro-active actions with different durations (they all have length C p ), we point out that the distribution of these lead times is irrelevant to our problem. Indeed, either we have the time to take a proactive action before the failure strikes or not. Therefore, if a failure strikes less than C p seconds after the prediction is made available, the prediction was useless. In other words, predicted failures that come too early to enable any proactive action should be classified as unpredicted faults, leading to a smaller value of the predictor recall and to a shorten prediction window. Therefore, in the following, we consider, without loss of generality, that all predictions are made available C p seconds before the beginning of the prediction window.

Fault rates
The key parameter is µ, the mean time between faults (MTBF) of the platform. If the platform is made of N components whose individual MTBF is µ ind , then µ = µ ind N . This result is true regardless of the fault distribution law [1]. In addition to µ, the platform MTBF, let µ P be the mean time between predicted events (both true positive and false positive), and let µ N P be the mean time between unpredicted faults (false negative). Finally, we define the mean time between events as µ e (including all three event types). The relationships between µ, µ P , µ N P , and µ e are the following: • Rate of unpredicted faults: 1 µ N P = 1−r µ , since 1 − r is the fraction of faults that are unpredicted; • Rate of predicted faults: r µ = p µ P , since r is the fraction of faults that are predicted, and p is the fraction of fault predictions that are correct; • Rate of events: 1 µe = 1 µ P + 1 µ N P , since events are either predictions (true or false), or unpredicted faults.

Checkpointing strategies
In this section, we introduce the new checkpointing strategies, and we determine the waste that they induce. We then proceed to computing the optimal period for each strategy.

Description of the different strategies
We consider the following general scheme: 1. While no fault prediction is available, checkpoints are taken periodically with period T ; 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 − q, we ignore the prediction; 3. If we decide to trust the predictor, we use various strategies, depending upon the length I of the prediction window. Before describing the different strategies in the situation (3), we point out that the rationale for not always trusting the predictor is to avoid taking useless checkpoints too frequently. Intuitively, the precision p 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. Now, to describe the strategies used when we trust a prediction (situation (3)), we 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 − q). In regular mode, we use periodic checkpointing with period T R . Intuitively, T R corresponds to the checkpointing period T of Section 2.1. 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 + I]. Several strategies can be envisioned: (1) Instant, 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 . The algorithm interrupts the current period (of scheduled length T R ), checkpoints during the interval [t 0 − C p , 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) NoCkptI, 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 R ), and checkpoints during the interval [t 0 − C p , t 0 ]. But here, we return to regular mode only at time t 0 + I, 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 (3) WithCkptI, for With checkpoints during prediction window-The third strategy is intended for a longer prediction window and assumes that C p ≤ I: the algorithm interrupts the current period (of scheduled length T R ), and checkpoints during the interval [t 0 − C p , t 0 ], but now also decides to take several checkpoints during the prediction window. The period T P of these checkpoints in proactive mode will presumably be shorter than T R , to take into account the higher fault probability. 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 p ≤ I. We return to regular mode either right after the fault strikes within the time window [t 0 , t 0 + I], or at time t 0 + I 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 corresponding scheduling algorithm is shown in Algorithm 1. Note that, for all strategies, 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). 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. Enter regular mode; 4 if in proactive mode for a time greater than or equal to I then 5 Switch to regular mode 6 if Prediction made with interval [t, t + I] and prediction taken into account then 7 Let t C be the date of the last checkpoint under regular mode to start no later than t − C p ;

Strategy WithCkptI
In this section we evaluate the execution time under heuristic WithCkptI. To do so, we partition the whole execution into time intervals defined by the presence or absence of events. An interval starts and ends with either the completion of a checkpoint or of a recovery (after a failure). To ease the analysis, we make a simplifying hypothesis: we assume that at most one event, failure or prediction, occurs within any interval of length T R + I + C p . In particular, this implies that a prediction or an unpredicted fault always take place during the regular mode.
We list below the four types of intervals, and evaluate their respective average length, together with the average work completed during each of them (see Table 1 for a summary): 1. Two consecutive regular checkpoints with no intermediate events. The time elapsed between the completion of the two checkpoints is exactly T R , and the work done is exactly T R − C. 2. Unpredicted fault. Recall that, because of the simplifying hypothesis, the fault happens in regular mode. Because instants where the fault strikes and where the last checkpoint was taken are independent, on average the fault strikes at time T R /2. A downtime of length D and a recovery of length R occur before the interval completes. There is no work done. 3. False prediction. Recall that it happens in regular mode. There are two cases: (a) Taken into account. This happens with probability q. The interval lasts T R + C p + I, since we take a proactive checkpoint and spend the time I in proactive mode. The work done is (T R − C) + (I − I TP C p ). (b) Not taken into account. This happens with probability 1 − q. The interval lasts T R and the work done is T R − C. Considering both cases with their probabilities, the average time spent is equal to: q(T R +C p +I) I , we work and checkpoint in proactive mode, with period T P . In addition, we take a proactive checkpoint right before the start of the prediction window. Then we spend the time E So far, we have evaluated the length, and the work done, for each of the interval types. We now estimate the expectation of the number of intervals of each type. Consider the intervals defined by an event whose mean time between occurrences is λ. On average, during a time T , there will be T /λ such intervals. Due to the simplifying hypothesis, intervals of different types never overlap. Table 1 presents the estimation of the number of intervals of each type.
We want to estimate the total execution time. To estimate the time spent within intervals of a given type, we multiply the expectation of the number of intervals of that type by the expectation of the time spent in each of them. Of course, multiplying expectations is correct only if the corresponding random variables are independent. Nevertheless, we hope that this will lead us to a good approximation of the expected execution time. We will assess the quality of the approximation through simulations in Mode Number of intervals We use the same line of reasoning to compute the overall amount of work done, that must be equal, by definition, to Time base , the execution time of the application without any overhead: This equation gives the value of w 1 as a function of the other parameters. Looking at Equations (1) and (2), and at the values of w 2 , w 3 , and w 4 , we remark that Time Final can be rewritten as a function of q, as follows: where neither α, nor β, nor γ depend on q. With a simple differentiation of Time Final with respect to q, we obtain that Time Final is either increasing or decreasing with q, depending on the sign of γ. Consequently, in an optimal solution, either q = 0 or q = 1. This (somewhat unexpected) conclusion is that the predictor should sometimes be always trusted, and sometimes never, but no in-between value for q will do a better job. Thus we can now focus on the two functions Time Final , the one when q = 0 (Time  Table 1 and Equations (1) and (2), one can easily see that This is exactly the equation from [1] in the case of exact-date predictions that are never taken into account (a good sanity check!). When q = 1, we have: After a little rewriting we obtain: . Therefore, we have:

Waste minimization
When q = 0, the optimal period can readily be computed from Equation (3) and we derive that the optimal period is 2(µ − (D + R))C. This defines a periodic policy we call RFO, for Refined First-Order approximation. We now minimize the waste of the strategy where q = 1. In order to compute the optimal value for T P , we identify the fraction of the waste in Equation (4) that depends on T P . We can rewrite Equation (4) as: where α does not depend on T P . The waste is thus minimized when T P is equal to T extr Note that we always have to enforce that T extr P is larger than C p and does not exceed I, and we may have to round its values accordingly in some extreme cases.
In order to compute the optimal value for T R , we identify the fraction of the waste in Equation (4) that depends on T R . We can rewrite Equation (4) as: where β does not depend on T R because T opt P does not depend on T R . Therefore, Waste {1} is minimized when T R is equal to Recall that we must always enforce that T extr R is always greater than C. One can note that when r = 0, this means that none of the prediction predicts an actual fault, and we obtain the same period than without a predictor. Finally, if we assume that, on average, fault strikes at the middle of the prediction window, i.e., E we obtain simplified values:

Strategy NoCkptI
In this section we evaluate the execution time under heuristic NoCkptI. The analysis is rather similar to that of WithCkptI, the only differences being, obviously, in the presence of true and false predictions: 3. False prediction. There are two cases: (a) Taken into account. This happens with probability q. The interval lasts T R + C p + I, since we take a proactive checkpoint and spend the time I in proactive mode (here, working without checkpointing). The work done is (T R − C) + I. (b) Not taken into account. This happens with probability 1 − q. The interval lasts T R and the work done is T R − C. Considering both cases with their probabilities, the average time spent is equal to: True prediction. There are two cases: (a) Taken into account. Let E (f ) I be the average time at which a fault occurs within the prediction window. We take a proactive checkpoint right before the start of the prediction window. Then we spend the time E (f ) I in proactive mode working without checkpointing, and we have a downtime and a recovery. Hence, such an interval lasts So far, we have evaluated the length, and the work done, for each of the interval types. We now estimate the expectation of the number of intervals of each type as we did for WithCkptI. Table 2 presents the estimation of the number of intervals of each type.
We estimate the total execution time as for WithCkptI. The formula is the exact same function of w 1 , w 2 , w 3 , and w 4 (but the values of there four parameters will change as the average work done during some of the types of intervals changes): We use the same line of reasoning as previously to compute the overall amount of work done: This equation gives the value of w 1 as a function of the other parameters. As for WithCkptI, one can easily show that in an optimal solution, either q = 0 or q = 1. Thus we can now focus on the two functions Time Final , the one when q = 0 (Time  Table 2 and Equations (7) and (8), one can easily see that This is exactly the equation from [1] in the case of exact-date predictions that are never taken into account, what we had already retrieved with WithCkptI (same sanity check!). When q = 1, we have: After a little rewriting we obtain: . Therefore, we have:

Waste minimization
When q = 0, the optimal value for T R is obviously the same than the one we computed for WithCkptI in the case q = 0. We now minimize the waste of the strategy where q = 1. In order to compute the optimal value for T R , we identify the fraction of the waste in Equation (10) that depends on T R . We can rewrite Equation (10) as: where β does not depend on T R . This equation is identical to Equation (5) and therefore the value of T R that minimizes the waste is T extr R , the value given by Equation (6).

Strategy Instant
In this section we evaluate the execution time under heuristic Instant. The analysis is very similar to that of NoCkptI. Indeed, we only focus to the differences between the performance of Instant and WithCkptI. The differences happening, obviously, only in the presence of true and false predictions: 3. False prediction. There are two cases: (a) Taken into account. This happens with probability q. The interval lasts T R + C p , since we fallback to regular mode as soon as the proactive checkpoints completes. The work done is T R − C. (b) Not taken into account. This happens with probability 1 − q. The interval lasts T R and the work done is T R − C. Considering both cases with their probabilities, the average time spent is equal to: 4. True prediction. There are two cases: (a) Taken into account. Let E (f ) I be the average time at which a fault occurs within the prediction window. We take a proactive checkpoint right before the start of the prediction window. Then we fallback to the regular mode. After a time E (f ) I the fault strikes. Depending on the size I of the prediction window, and of when the prediction started after the completion of the last regular checkpoint three scenarios can happen. Either the fault strikes while the heuristic is still trying to complete the work of size T R − C, or it strikes while the heuristic is trying to take the regular checkpoint after that work, or it strikes after that regular checkpoint was completed. We overestimate the time lost by assuming that we are in one of the two former cases, because these are the cases that maximizes the amount of work destroyed by a strike. (In some way, this is equivalent to assuming that I is very small with respect to T R .) The predicted fault and the completion time of the last regular checkpoint are independent events. Therefore, on average the fault strikes at time T R /2. After the fault strikes, the downtime and the recovery we complete the period struck by the fault. Then, the interval lasts So far, we have evaluated the length, and the work done, for each of the interval types. We estimate the expectation of the number of intervals of each type as we did for WithCkptI and for NoCkptI. Table 3 presents the estimation of the number of intervals of each type.
We estimate the total execution time as for WithCkptI and NoCkptI: We use the same line of reasoning as previously to compute the overall amount of work done: This equation gives the value of w 1 as a function of the other parameters. As with WithCkptI and NoCkptI, one can easily show that in an optimal solution, either q = 0 or q = 1. Thus we can now focus on the two functions Time Final , the one when q = 0 (Time  Table 3 and Equations (11) and (12), one can easily see that This is exactly the equation from [1] in the case of exact-date predictions that are never taken into account, what we had already remarked with WithCkptI and NoCkptI (yet another good sanity check!). When q = 1, we have: After a little rewriting we obtain: . Therefore, we have: Waste minimization When q = 0, the optimal value for T R is obviously the same than the one we computed for WithCkptI and for NoCkptI in the case q = 0. We now minimize the waste of the strategy where q = 1. In order to compute the optimal value for T R , we identify the fraction of the waste in Equation (14) that depends on T R . We can rewrite Equation (14) as: where β does not depend on T R . Therefore, the value of T R that minimizes the waste is T extr R , where Again, recall that we must always enforce that T extr R is always greater than C. Finally, if we assume that, on average, fault strikes at the middle of the prediction window, i.e., E

Simulation results
We start by presenting the simulation framework (Section 4.1). Then we report results using the characteristics of two fault predictors from the literature (Section 4.2).

Simulation framework
In order to validate the model, we have instantiated it with several scenarios. The experiments use parameters that are representative of current and forthcoming large-scale platforms [4,7]. We take C = R = 600 seconds, and D = 60 seconds. We consider three scenarios where proactive checkpoints are (i) exactly as expensive as periodic checkpoints (C p = C); (ii) ten times cheaper (C p = 0.1C); and (iii) two times more expensive (C p = 2C). The individual (processor) MTBF is µ ind = 125 years, and the total number of processors N varies from N = 2 16 [20], which leads to µ ind = 45,208 365 ≈ 125 years. The application size is set to Time base = 10, 000 years/N.
We use Maple to analytically compute and plot the optimal value of the waste for the three predictionaware policies, Instant, NoCkptI, and WithCkptI, for the prediction-ignoring policy RFO (corresponding to the case q = 0), and for the reference heuristic Daly (Daly's [6] periodic policy). In order to check the accuracy of our model, we have compared the analytical results with results obtained with a discrete-event simulator. The simulation engine generates a random trace of faults, parameterized either by an Exponential fault distribution or by Weibull distribution laws with shape parameter 0.5 or 0.7. Note that Exponential faults are widely used for theoretical studies, while Weibull faults are representative of the behavior of real-world platforms [11,17,12]. In both cases, the distribution is scaled so that its expectation corresponds to the platform MTBF µ. With probability r, we decide if a fault is predicted or not. The simulation engine also generates a random trace of false predictions, whose distribution is identical to that of the first trace (in Figures 8 through 13, we also consider the case where false predictions are generated according to a uniform distribution; results are quite similar). This second distribution is scaled so that its expectation is equal to µ P 1−p = pµ r(1−p) , the inter-arrival time of false predictions. Finally, both traces are merged to produce the final trace including all events (true predictions, false predictions, and non predicted faults). Each reported value is the average over 100 randomly generated instances.
In the simulations, we compare the five checkpointing strategies listed above. To assess the quality of each strategy, we compare it with its BestPeriod counterpart, defined as the same strategy but using the best possible period T R . This latter period is computed via a brute-force numerical search for the optimal period. Altogether, there are four BestPeriod heuristics, one for each of the three variants with prediction, and one for the case where we ignore predictions, which corresponds to both Daly and RFO. Altogether we have a rich set of nine heuristics, which enables us to comprehensively assess the actual quality of the proposed strategies. Note that for computer algebra plots, obviously we do not need BestPeriod heuristics, since each period is already chosen optimally from the equations.
We experiment with two predictors from the literature: one accurate predictor with high recall and precision [19], namely with p = 0.82 and r = 0.85, and another predictor with more limited recall and precision [21], namely with p = 0.4 and r = 0.7. In both cases, we use five different prediction windows, of size I = 300, 600, 900, 1200, and 3000 seconds. Figures 2 through 7 show the average waste degradation of the nine 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 µ = µ 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.

Analysis of the results
We start with a preliminary remark: when the graphs for Instant and WithCkptI cannot be seen in the figures, this is because their performance is identical to that of NoCkptI, and their respective graphs are superposed.
We first compare the analytical results, plotted by the Maple curves, to the simulations results. There is a good correspondence between the analytical curves and the simulations, especially those using an Exponential distribution of failures. However, the larger the platform (or the smaller the MTBF), the less realistic our assumption that no two events happen during an interval of length T R + I + C p , and the analytical models become less accurate for prediction-aware heuristics. Therefore, the analytical results are overly pessimistic in the most failure-prone platforms. Also, recall that an exponential law is a Weibull law of shape parameter 1. Therefore, the further the distribution of failures is from an exponential law, the larger the difference between analytical results and simulated ones. However, in all cases, the analytical results are able to predict the general trends.
A second assessment of the quality of our analysis comes from the BestPeriod variants of our heuristics. When predictions are not taken into account, Daly, and to a lesser extent RFO, are not close to the optimal period given by BestPeriod (a similar observation was made in [2]). This gap increases when the distribution is further apart from an Exponential distribution. However, predictionaware heuristics are very close to BestPeriod in almost all configurations. The only exception is with heuristics Instant when C p = 2C, the total number of processors N is equal to either 2 18 and 2 19 , and I is large. However, when I = 3000 and N = 2 19 , the platform MTBF is approximately equal to 6C p which renders our hypothesis and analysis invalid. The difference in this case between Instant and its BestPeriod should therefore not come as a surprise.
To better understand why close-to-optimal periods are obtained by prediction-aware heuristics (while this is not the case without predictions), we plot the waste as a function of the period T R for RFO and the prediction-aware heuristics (Figures 14 through 17). On these figures one can see that, whatever the configuration, periodic checkpointing policies (ignoring predictions) have well-defined global optimum. (One should nevertheless remark that the performance is almost constant in the neighborhood of the optimal period which explains why policies using different periods can obtain in practice similar performance, as in [3].) For prediction-aware heuristics, however, the behavior is quite different and two scenarios are possible. In the first one, once the optimum is reached, the waste very slowly increases to reach an asymptotic value which is close to the optimum waste (e.g., when the platform MTBF is large and failures follow an exponential distribution). Therefore, any period chosen close to the optimal one, or greater than it, will deliver good quality performance. In the second scenario, the waste decreases until the period becomes larger than the application size, and the waste stays constant. In other words, in these configurations, periodic checkpointing is unnecessary, only proactive actions matter! This striking result can be explained as follows: a significant fraction of the failures are predicted, and thus taken care of, by proactive checkpoints. The impact of unpredicted failures is mitigated by the proactive measures taken for false predictions. To further mitigate the impact of unpredicted faults, the period T R should be significantly shorter than the mean-time between proactive checkpoints, which would induce a lot of waste due to unnecessary checkpoints if the mean-time between unpredicted faults is large with respect to the mean-time between predictions. This greatly restrict the scenarios for which the periodic checkpointing can lead to a significant decrease of the waste.
When the prediction window I is shorter than the duration C p of a proactive checkpoint, there is no difference between NoCkptI and WithCkptI. When I is small but greater than C p (say, when I is around 2C p ), WithCkptI spends most of the prediction window taking a proactive checkpoint and NoCkptI is more efficient. When I becomes "large" with respect to C p , WithCkptI can become more efficient than NoCkptI, but becomes significantly more efficient only if the proactive checkpoints are significantly shorter than regular ones. Instant can hardly be seen in the graphs as its performance is most of the time equivalent to that of NoCkptI. Figures 18 through 21 show the influence of the size of the prediction window I on the performance of the heuristics. As expected, the smaller the prediction window, the more efficient the prediction-aware heuristics. Also, the smaller the number of processors (or the larger the platform MTBF), the larger the impact of the size of the prediction window. A surprising result is that taking prediction into account is not always beneficial! The analytical results predict that prediction-aware heuristics would achieve worse performance than periodic policies in our settings, as soon as the platform includes 2 18 processors. In simulations, results are not so extreme. For the largest platforms considered, using predictions has almost no impact on performance. But when the prediction window is very large, taking predictions into account can indeed be detrimental. These observations can be explained as follows. When the platform includes 2 19 processors, the platform MTBF is equal to 7500 s. Therefore, any interval of duration 3000 has a 40% chance to include a failure: a prediction window of 3000 is not very informative, unless the precision and recall of the predictor are almost equal to 1 (which is never the case in practice). Since the predictor brings almost no knowledge, trusting it may be detrimental. When comparing the performance of, say, NoCkptI for the two predictors, one can see that when failures follow a Weibull distribution with shape parameter k = 0.7, I = 600, and N = 2 18 , NoCkptI achieves better performance than RFO when r = 0.85 and p = 0.82, but worse when p = 0.4 and r = 0.7. The latter predictor generates more false predictions -each one inducing an unnecessary proactive checkpoint-and misses more actual failures -each one destroying some work. The drawbacks of trusting the predictor outweigh the advantages. If failures are few and apart, almost any predictor will be beneficial. When the platform MTBF is small with respect to the cost of proactive checkpoints, only almost perfect predictors will be worth using. For each set of predictor characteristics, there is a threshold for the platform MTBF under which predictions will be useless or detrimental, but above which predictions will be beneficial.
In order to compare the impact of the heuristics ignoring predictions to those using them, we report job execution times in Table 4. For the strategies with prediction, we compute the gain (expressed in percentage) over Daly, the reference strategy without prediction. We first remark that RFO achieves lower makespans than Daly with gains ranging from 1% with 2 16 processors to 18% with 2 19 processors.   Overall, the gain due to the predictions decreases when the size of the prediction window increases, and increases with the platform size. This gain is obviously closely related to the characteristics of the predictor. When I = 300, the three strategies are identical. When I increases, NoCkptI achieves slightly better results than Instant. For low values of I, WithCkptI is the worst prediction-aware heuristics. But when I becomes large and if the predictor is efficient, then WithCkptI becomes the heuristics of choice (I = 3000, p = 0.82, and r = 0.85).
The reductions in the application executions times due to the predictor can be very significant. With p = 0.85 and r = 0.82 and I = 3000, we save 25% of the total time with N = 2 19 , and 13% with N = 2 16 using strategy WithCkptI. With I = 300, we save up to 45% with N = 2 19 , and 18% with N = 2 16 using any strategy (though NoCkptI is slightly better than Instant). Then, with p = 0.4 and r = 0.7, we still save 33% of the execution time when I = 300 and N = 2 19 , and 14% with N = 2 16 . The gain gets smaller with I = 3000 and N = 2 16 but remains non negligible since we can save 8%. When I = 3000 and N = 2 19 , however, the best solution is to ignore predictions and simply use RFO (we fall-back to the case q = 0). If we now consider a Weibull law with shape parameter 0.5 instead of 0.7, keeping all other parameters identical (I = 3000, N = 2 19 , p = 0.4 and r = 0.7), then the heuristics of choice is WithCkptI and the gain with respect to Daly is 57.9%.

Paper Lead Time Precision Recall Prediction Window
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 [21] 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 6), they state that it has a positive impact on the checkpointing time (from 1500 seconds to 120 seconds). The authors of [19] also consider a lead time, and introduce a prediction window when the predicted fault should happen. The authors of [16] 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 this work, even though [19] 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 [15], 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.
In the simpler case where predictions are exact-date predictions, Gainaru et al [10] have shown that the optimal checkpointing period becomes T opt = 2µC 1 − r , but their analysis is valid only if µ is very large in front of the other parameters. Our previous work [1] has refined the results of [10], focusing on a more accurate analysis of fault prediction with exact dates, and providing a detailed study on the impact of recall and precision on the waste. As shown in Section 3, the analysis of the waste is dramatically more complicated when using prediction windows than when using exact-date predictions. To the best of our knowledge, this work is the first to focus on the mathematical aspect of fault prediction with prediction windows, 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
In this work, we have studied the impact of prediction windows on checkpointing strategies. We have designed several heuristics that decide whether to trust these predictions, and when it is worth taking preventive checkpoints. We have been able to derive a comprehensive set of results and conclusions: • We have introduced an analytical model to capture the waste incurred by each strategy, and provided for each optimization problem a closed-form formula giving its optimal solution. Contrarily to the cases without prediction, or with exact-date predictions, the computation of the waste requires a sophisticated analysis of the various events, including the time spent irregular or proactive modes.
• The simulations fully validate the model, and the brute-force computation of the optimal period guarantees that our prediction-aware strategies are always very close to the optimal. This holds true both for Exponential and Weibull failure distributions.
• The model is quite accurate and its validity goes beyond the conservative assumption that requires a single event per time interval; even more surprising, the accuracy of the model for prediction-aware strategies is much better than for the case without predictions, where Daly can be far from the optimal period in the case of Weibull failure distributions.
• Both the analytical computations and the simulations enable to characterize when prediction is useful, and which strategy performs better, given the key parameters of the system: recall r, precision p, size of the prediction window I, size of proactive checkpoints C p versus regular checkpoints C, and platform MTBF µ.
Altogether, the analytical model and the comprehensive results provided in this work enable to fully assess the impact of fault prediction with time-windows 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.