Anne Benoit
email: anne.benoit@inria.fr

Yishu Du
email: yishu.du@inria.fr

Thomas Herault
email: herault@icl.utk.eduuniv.tenn.

Loris Marchal
email: loris.marchal@inria.fr

Guillaume Pallez
email: guillaume.pallez@inria.fr

Lucas Perotin
email: lucas.perotin@inria.fr

Yves Robert
email: yves.robert@inria.fr

Frédéric Hongyang Sun
email: hongyang.sun@ku.edu

Frédéric Vivien
email: frederic.vivien@inria.fr

Checkpointing à la Young/Daly: An Overview

Keywords: Checkpoint, Optimal period, Young/Daly formula

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Checkpointing is the standard technique to protect applications running on HPC (High-Performance Computing) platforms. Every day, the platform experiences a few fail-stop errors (or failures, we use both terms indifferently). After each failure, the application executing on the faulty processor (and likely on many other processors for a large parallel application) is interrupted and must be restarted. Without checkpointing, all the work executed for the application is lost. With checkpointing, the execution can resume from the last checkpoint, after some downtime (enroll a spare to replace the faulty processor) and a recovery (read the checkpoint).

Consider a parallel application executing on an HPC platform whose nodes are subject to fail-stop errors. How frequently should it be checkpointed so that its expected execution time is minimized? There is a well-known trade-off (see Figure 1): taking too many checkpoints leads to high overhead, especially when there are few failures while taking too few checkpoints leads to a large re-execution time after each failure. The optimal checkpointing period is (approximately) given by the Young/Daly formula as 𝑊 YD = √ 2𝜇𝐶 [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF][START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF], where 𝜇 is the application MTBF (Mean Time Between Failures) and 𝐶 is the checkpoint duration. This paper provides an overview of the applicability and robustness of the Young/Daly formula for different application scenarios. There are two main frameworks. The first part of the survey deals with preemptible applications, which may be checkpointed at any time step. In this context, checkpointing is a coordinated process and involves all the processors enrolled in the execution of the application. The second part of the survey focuses on task systems, where applications are composed of a set of atomic tasks, possibly with inter-dependences. In this context, checkpoints are task-based and can be taken only at the end of a task. Only the processors that execute a task are involved in its checkpoint. The problem is then to decide which tasks to checkpoint.

The paper is organized as follows. We first survey preemptible applications in Section 2. Then we deal with task systems in Section 3. We address some questions related to uncertainty in Section 4. Finally, we conclude with some open questions in Section 6.

IC3 2022, August 4-6, 2022, Noida, India Anne Benoit, Yishu Du, Thomas Herault, Loris Marchal, Guillaume Pallez, Lucas Perotin, Yves Robert, Hongyang Sun, and Frédéric Vivien

PREEMPTIBLE APPLICATIONS

In this section, we deal with parallel applications that can be checkpointed at any time. In scheduling terminology, the applications are preemptible.

Background

Platform and applications. Consider a large parallel platform with 𝑚 identical processors, or nodes. These nodes are subject to fail-stop errors, or failures. A failure interrupts the execution of the node and provokes the loss of its whole memory.

Consider a parallel application running on several nodes: when one of these nodes is struck by a failure, the state of the application is lost, and execution must restart from scratch unless a faulttolerance mechanism has been deployed. The classical technique to deal with failures makes use of a checkpoint-restart mechanism: the state of the application is periodically checkpointed, i.e., all participating nodes take a checkpoint simultaneously. This is the standard coordinated checkpointing protocol, which is routinely used on large-scale platforms [START_REF] Chandy | Distributed Snapshots: Determining Global States of Distributed Systems[END_REF], where each node writes its share of application data to stable storage (checkpoint of duration 𝐶). When a failure occurs, the platform is unavailable during a downtime 𝐷, which is the time to enroll a spare processor that will replace the faulty processor [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF][START_REF]Fault-Tolerance Techniques for High-Performance Computing[END_REF]. Then, all application nodes (including the spare) recover from the last valid checkpoint in a coordinated manner, reading the checkpoint file from stable storage (recovery of duration 𝑅). Finally, the execution is resumed from that point on, rather than starting again from scratch. Note that failures can strike during checkpoint and recovery, but not during downtime (otherwise there are no differences between downtime and recovery and we can simply include the downtime in the recovery time). When a failure hits a processor, that processor is replaced by a spare. This amounts to starting anew with a fresh processor. In the terminology of stochastic processes, the faulty processor is rejuvenated. However, all the other processors are not rejuvenated: this would be infeasible due to the multitudinous spares needed! Failures. We assume that each node experiences failures whose inter-arrival times follow Independent and Identically Distributed (IID) random variables obeying an arbitrary probability distribution D. We only assume that D is continuous and of finite expectation and variance, a condition satisfied by all standard distributions. We let 𝜇 ind denote the expectation of D, also known as the individual processor MTBF. Even if each node has an MTBF of several years, large-scale parallel platforms are composed of so many nodes that they will experience several failures per day [START_REF] Cappello | Toward Exascale Resilience: 2014 update[END_REF][START_REF] Ferreira | Evaluating the Viability of Process Replication Reliability for Exascale Systems[END_REF]. Hence, a parallel application using a significant fraction of the platform will typically experience a failure every few hours. More precisely, an application executing with 𝑝 processors has an MTBF 𝜇 = 𝜇 ind 𝑝 : intuitively, the application is struck by failures at a rate which is 𝑝 times higher than that of each enrolled processor. We come back to this statement in Section 2.3.

Checkpointing strategies. Given a parallel application of length 𝑇 base (base time without checkpoints nor failures), the optimization problem is to decide when and how often to take a checkpoint, to minimize the expected execution time of the application. The application is divided into 𝑁 c segments of length 𝑊 𝑖 , 1 ≤ 𝑖 ≤ 𝑁 c , each followed by a checkpoint of length 𝐶. Of course 𝑁 c 𝑖=1 𝑊 𝑖 = 𝑇 base . We add a final checkpoint at the end of the last segment, e.g., to write final outputs to stable storage. Symmetrically, we add an initial recovery when re-executing the first segment of an application (e.g., to read inputs from stable storage) if it has been struck by a failure before completing the checkpoint. Adding a final checkpoint and an initial recovery brings symmetry and simplifies formulas, but it is not at all mandatory: see [START_REF] Benoit | Checkpointing strategies to protect parallel jobs from non-memoryless fail-stop errors[END_REF] for an extension relaxing either or both assumptions. The question is then to determine the number 𝑁 c of segments and their lengths 𝑊 𝑖 .

The Young/Daly Formula

Here is an intuitive (but simplified) derivation of the Young/Daly formula for the optimal checkpoint period. Owing to the addition of the final checkpoint and the initial recovery, all segments of the application have the same shape. It is thus natural (by symmetry) to assume that they have the same length 𝑊 in the optimal solution. Thus we assume that checkpoints are taken periodically, after every 𝑊 unit of work. Now, after every 𝑊 unit of work, we spend 𝐶 seconds to checkpoint, which corresponds to a first source of waste 𝑆 1 = 𝐶 𝑊 +𝐶 . Here the waste is defined as the fraction of time during which the application is not performing useful computations; checkpoint, recovery, downtime, and re-execution do not count as useful computations. 𝑆 1 is the failure-free waste. The second source of waste 𝑆 2 is due to failures: each time a failure strikes, which happens every 𝜇 seconds on average, we lose 𝐷 + 𝑅 for downtime and recovery, and then we have to re-execute some work, namely the work performed since the last checkpoint (or from the beginning of the execution if none has been taken yet). On average again, the failure strikes in the middle of the segment: sometimes before, sometimes after, hence, on average after 𝑊 +𝐶 2 seconds. We obtain 𝑆 2 = 1 𝜇 (𝐷 + 𝑅 + 𝑊 +𝐶 2 ). 𝑆 1 is the failure-induced waste. Altogether, both sources of waste approximately add up, so we have to find 𝑊 that minimizes 𝑆 1 + 𝑆 2 . We further simplify the solution by assuming that 𝑊 must be an order of magnitude higher than the fault-tolerance parameters 𝐷, 𝐶, 𝑅. This is a necessary condition for the waste to remain reasonably low. This leads to 𝑆 1 ≈ 𝐶 𝑊 and 𝑆 2 ≈ 𝑊 2𝜇 . The total waste 𝑆 1 + 𝑆 2 ≈ 𝐶 𝑊 + 𝑊 2𝜇 is minimum for

𝑊 YD = √ 2𝜇𝐶 (1)
This is nothing else than the famous Young/Daly formula! Finally, note that 𝑆 1 = 𝑆 2 for 𝑊 YD , which corroborates the intuition given in Figure 1 that both sources of waste, failure-free and failure-induced, should be balanced in the optimal solution. See [START_REF]Fault-Tolerance Techniques for High-Performance Computing[END_REF] for a more detailed derivation using the waste argument.

Accuracy

Recall that each node experiences failures whose inter-arrival times follow IID random variables obeying a probability distribution D.

When D is Exp(𝜆), i.e., an Exponential distribution of rate 𝜆, the framework is well-understood. This is because the inter-arrival times of the failures that strike an application with 𝑝 processors are IID random variables obeying an Exponential distribution Exp(𝑝𝜆). This is due to the memoryless property of the Exponential distribution: when a failure strikes one processor, that processor is rejuvenated, while the remaining 𝑝 -1 processors are not. With an arbitrary distribution D, the time to the next failure would depend upon the history of these 𝑝 -1 processors: for each of them, the time to their next failure depends upon when their last failure struck. This is not the case for an Exponential distribution, owing to its memoryless property: after a failure on any of the 𝑝 processors, the time to the next failure remains the same random variable Exp(𝜆) for each of them, rejuvenated or not. Therefore, the time to the next failure for the application obeys an Exp(𝑝𝜆) distribution, as the minimum of 𝑝 Exp(𝜆) distributions. From the resilience point of view, the application executes on a single processor of fault rate 𝑝𝜆! Owing to this observation, one can formally derive that the optimal checkpoint strategy is periodic, and compute the optimal checkpoint period. The derivation is a bit technical and the optimal segment length 𝑊 opt is obtained using the Lambert W function. But comfortingly, a first-order approximation of 𝑊 opt is 𝑊 YD , the value given by the Young/Daly formula. See [START_REF] Benoit | Checkpointing strategies to protect parallel jobs from non-memoryless fail-stop errors[END_REF][START_REF] Bougeret | Checkpointing strategies for parallel jobs[END_REF] for details on the derivation. Now, any continuous distribution D other than Exponential is not memoryless, and the optimal checkpoint strategy is unknown in that case. The bad news is that the most accurate probability distributions modeling processor failures are LogNormal [START_REF] Heien | Modeling and tolerating heterogeneous failures in large parallel systems[END_REF] and Weibull [START_REF] Schroeder | A large-scale study of failures in highperformance computing systems[END_REF][START_REF] Schroeder | Understanding failures in petascale computers[END_REF][START_REF] Subasi | Toward a General Theory of Optimal Checkpoint Placement[END_REF][START_REF] Subasi | Unified fault-tolerance framework for hybrid task-parallel message-passing applications[END_REF] instead of Exponential. For instance, LANL failure traces are best fit by Weibull distributions of different shapes [START_REF] El | To checkpoint or not to checkpoint: Understanding energy-performance-I/O tradeoffs in HPC checkpointing[END_REF]. Weibull distributions with a shape parameter smaller than 1 experience infant mortality; for those distributions, it is known that periodic checkpointing is not optimal. Intuitively, the length of a segment between two consecutive checkpoints should increase with time, as the instantaneous failure rate decreases. However, the good news is that the MTBF can still be defined as the limit:

lim 𝑇 →∞ 𝑛(𝑇 ) 𝑇 = 𝜇 ind 𝑝
where 𝑛(𝑇 ) is the expected number of failures striking an application with 𝑝 processors in the time interval [0,𝑇 ]. This limit exists for any regular distribution D. A natural heuristic is to use a periodic checkpoint strategy, with a segment length given by the Young/Daly formula and using that latter value for the MTBF. It is unknown how this approach is close to the optimal but it seems good enough in many scenarios. See [START_REF] Benoit | Checkpointing strategies to protect parallel jobs from non-memoryless fail-stop errors[END_REF][START_REF] Bougeret | Checkpointing strategies for parallel jobs[END_REF] for an assessment of this heuristic, and for a comparison with other checkpoint strategies which aim at maximizing work or efficiency until the next failure.

Extensions

In Section 2.2, we have shown how to derive the optimal checkpoint period when the objective is to minimize the expected completion time of the application. We used a simplified model where no computation could take place while checkpointing. Modern processors could run several threads in parallel and compute while executing I/O transfers. A first extension to the framework of Section 2.2 is to extend the model with a linear slowdown factor 𝛼 ∈ [0, 1], where, say, 𝛼 = 0.5 means that computations progress at half the main speed when checkpointing. The two extreme values are 𝛼 = 0 when checkpoints are blocking (no overlap), and 𝛼 = 1 when execution can progress with no penalty while a checkpoint is taken (full overlap). The Young/Daly formula becomes 𝑊 YD = √ 2𝜇 (1 -𝛼)𝐶. Note that 𝛼 = 0 leads to the original Young/Daly formula, while 𝛼 = 1 leads to 𝑊 YD = 0, which means that one should checkpoint all the time if checkpointing is free! Of course in practical scenarios we expect 𝛼 < 1. See [START_REF]Fault-Tolerance Techniques for High-Performance Computing[END_REF] for more details.

Another extension to the framework of Section 2.2 is to target a different optimization objective: instead of minimizing the (expected) total execution time, one would aim at minimizing the (expected) total energy consumed to execute the application. This objective is important both for economic and environmental reasons. The optimal period 𝑊 energy to minimize energy consumption is different from the Young/Daly formula mainly because the power spent when computing is not the same as power spent when checkpointing. More precisely, the power consumption at each time step of the application relies on three components: • P Static : base power consumed when platform is switched on, • P Cal : when the platform is computing, we have to consider the CPU overhead in addition to the static power P Static .

• P I/O : similarly, this is the power overhead due to file I/O. This supplementary power consumption is induced by checkpointing, or when recovering from a failure. A key parameter to compare𝑊 energy and𝑊 YD is the ratio

P Static +P I/O P Static +P Cal .
See [START_REF] Aupy | Optimal checkpointing period: time vs. energy[END_REF][START_REF] El | To checkpoint or not to checkpoint: Understanding energy-performance-I/O tradeoffs in HPC checkpointing[END_REF][START_REF] Gelenbe | Optimum Checkpoints for Time and Energy[END_REF] and the references therein for further details.

Finally, another optimization objective is to minimize the expected volume of I/O operations due to checkpointing and recovery. This objective is important because I/O resources are scarce in HPC platforms. Typical HPC applications execute on dedicated computing nodes but share the I/O bandwidth of the platform with other applications. Hence, decreasing the volume of I/O operations by each application is likely to improve the global throughput of the platform. A natural question is then: given a single application that executes on the platform, can we increase the checkpoint period significantly beyond the Young/Daly formula without sacrificing too much in performance? Note that we have a bi-criteria optimization problem here because we need to trade off performance with I/O pressure. Note also that a single application running on the platform may be a capability workload that spans the entire platform. The answer to the question is yes: Arunagiri et al. [START_REF] Arunagiri | Modeling and Analysis of Checkpoint I/O Operations[END_REF] studied longer, sub-optimal periods for a single application, with the intent of reducing I/O pressure. They showed, both analytically and empirically using four real platforms, that a decrease in the I/O requirement can be achieved with only a small increase in waste.

However, space-sharing HPC platforms for the concurrent execution of multiple parallel applications is the prevalent usage strategy in today's HPC centers, and capability workloads that span the entire platform are much less common [START_REF] Weidner | Rethinking High Performance Computing Platforms: Challenges, Opportunities and Recommendations[END_REF]. The question becomes how to avoid contention when several applications try to checkpoint at the same time: the I/O bandwidth will be shared among these applications, their checkpoint time will increase, and the Young/Daly formula that was computed for each application in isolation is no longer optimal due to these interferences. We will come back to this question in Section 4.2.

Loosely-Coupled Applications

The Young/Daly formula applies to a parallel application where all processors progress and cooperate continuously, e.g., by exchanging messages: the application cannot continue its execution when one processor is struck by a failure; it has to wait until a spare is up and running. In other words, the application is assumed to be tightly coupled and behaves as if it were executed on a single (very powerful) processor. Recall that we already made such an analogy for failures: in fact, the parallel application can be viewed as a sequential one, executing on a single processor, very fast but very unreliable too.

What if the application is not tightly-coupled? If the application includes several tasks that can execute concurrently and independently on different subsets of resources, how frequently should each task be checkpointed? We use the word task here, but not in the traditional meaning where tasks are atomic and can only be checkpointed at the end of their execution (see Section 3 for such a framework). On the contrary, we assume that each task is preemptible and can be checkpointed at any time step. It is then natural to checkpoint each task using the Young/Daly period. But is this a good strategy, given that many tasks execute in parallel, and that the failure of one task will slow down the whole application?

Consider the simple example of a fork-join application that consists of 302 tasks: an entry task, 300 identical parallel tasks, and an exit task. Each parallel task runs on 𝑝 = 30 processors for 𝑇 base = 10 hours, and is checkpointed in 𝐶 = 6 minutes. The platform has at least 9, 000 processors so that the 300 parallel tasks can indeed execute concurrently. Such applications are typical of HPC applications that explore a wide range of parameters or launch subproblems in parallel. Assume a short downtime 𝐷 = 1 minute, and recovery time 𝑅 = 𝐶. Finally, assume that each task has 0.5% chances to fail during execution; this setting corresponds to an individual MTBF 𝜇 ind such that 1 -𝑒 -𝑝𝑇 base 𝜇 ind = 0.005, i.e., 𝜇 ind = 59, 850 hours (or 6.8 years). This is in accordance with MTBFs typically observed on large-scale platforms, which range from a few years to a few dozens of years [START_REF] Cappello | Toward Exascale Resilience: 2014 update[END_REF].

In the following paragraphs, we refer to [START_REF] Benoit | Checkpointing Workflows à la Young/Daly Is Not Good Enough[END_REF] for the details of computing the expectations of execution times. For each task, the Young/Daly period is

𝑊 YD = √ 2 𝜇 ind
𝑝 𝐶 ≈ 20 hours, and the expected execution time of a single task E(𝑇 1-task ) is minimized when only a single checkpoint is taken at the end of the execution. Recall that we always take a checkpoint at the end of the execution for simplification, thus the optimal solution for each task is to take no additional checkpoint. Then, one can derive that E(𝑇 1-task ) ≈ 10.4.

However, with 300 tasks executing concurrently, one can compute that the expectation of the total time required to complete all tasks is E(𝑇 all-tasks ) > 14. The key point here is that the expectation E(𝑇 all-tasks ) of the total time required to complete all tasks is far larger than the maximum of the expectations (which in the example all have the same value E(𝑇 1-task )).

Because the exit task cannot start before the last parallel task is completed, the expectation of the total execution time of the forkjoin application is E(𝑇 total ) = E(𝑇 entry ) + E(𝑇 all-tasks ) + E(𝑇 exit ), where E(𝑇 entry ) and E(𝑇 exit ) are the expected duration of the entry and exit tasks. Now, when adding four intermediate checkpoints to each task, we obtain E(𝑇 all-tasks ) < 12.75. The tasks are then slightly longer (10.5 hours without failure), but the impact of a failure is dramatically reduced if a checkpoint is taken every 2 hours. By diminishing E(𝑇 all-tasks ), we save 75 minutes (and in fact much more than that, because the lower and upper bounds for E(𝑇 all-tasks ) are loosely computed).

This little example shows that for loosely-coupled applications with a high degree of parallelism, checkpointing each task à la Young/Daly is not good enough! See [START_REF] Benoit | Checkpointing Workflows à la Young/Daly Is Not Good Enough[END_REF] for a comprehensive analysis and evaluation.

TASK GRAPHS

In this section, we deal with non-preemptible, task-based applications. The application is structured as a task graph, or workflow. Each task is atomic and checkpointing is only possible right after the completion of a task. The task graph summarizes the dependencies between the tasks. The problem is then to determine which tasks should be checkpointed. It turns out that optimal, or even efficient, checkpoint strategies are much more difficult to derive than for preemptible applications.

Baseline

In task-based systems, checkpoint and rollback-recovery have been considered, but the granularity of the task system has motivated a different approach. Since each task represents an atomic application in itself, the inputs of tasks (that are usually the outputs of other tasks) are checkpointed to enable the re-execution of failed tasks.

The de-facto standard approach for task systems is the checkpoint every task approach. This approach is inspired by the work done in cloud workflow systems, as is typically done in [START_REF] Xu | Dynamic resource provisioning with fault tolerance for data-intensive meteorological workflows in cloud[END_REF] for a recent example. See [START_REF] Bala | Fault tolerance-challenges, techniques and implementation in cloud computing[END_REF][START_REF] Ding | Fault-tolerant elastic scheduling algorithm for workflow in Cloud systems[END_REF][START_REF] Kandaswamy | Fault tolerance and recovery of scientific workflows on computational grids[END_REF][START_REF] Kumari | A survey of fault tolerance in cloud computing[END_REF][START_REF] Prathiba | Survey of failures and fault tolerance in cloud[END_REF] for a comprehensive survey of techniques. The outputs of all tasks, which will serve as inputs to other tasks later in the execution, are saved on stable storage as soon as each task completes. The stable storage is typically located in a data center whose disks are accessed by the virtual machines (VMs) that support the execution of the tasks. This approach guarantees that recovering from a failure only requires the re-execution of the task(s) that were executing when the failure stroke; no rollback to previous tasks is needed since their outputs have been checkpointed previously and can be retrieved from the disks.

Of course, checkpointing (the output of) every task may induce a huge overhead, in particular when there are many small tasks and limited I/O bandwidth to stable storage. We outline below a few cases where the optimal solution is known, before coming back to the general case of a workflow whose task graph is arbitrary.

Linear Chains

The simplest case is when the task graph of the workflow is a linear chain of (parallel) tasks 𝑇 1 ,𝑇 2 , . . . ,𝑇 𝑛 . There is a dependence from 𝑇 𝑖 to 𝑇 𝑖+1 for 1 ≤ 𝑖 ≤ 𝑛 -1. The optimal solution consists in determining which tasks should be checkpointed.

The execution time of 𝑇 𝑖 is 𝑤 𝑖 , its size is 𝑞 𝑖 processors, its checkpoint time 𝐶 𝑖 , and its recovery time is 𝑅 𝑖 . Assuming that failures obey an Exponential distribution Exp( 1 𝜇 ind ), where 𝜇 ind is the MTBF of each individual processor, the expected execution time E(𝑇 𝑖 ) to execute 𝑇 𝑖 and to checkpoint it at the end of the execution is wellknown; we have:

E(𝑇 𝑖 ) = 𝑞 𝑖 𝜇 ind + 𝐷 𝑒 𝑞 𝑖 𝜇 ind 𝑅 𝑖 𝑒 - 𝑞 𝑖 𝜇 ind (𝑤 𝑖 +𝐶 𝑖 ) -1
where 𝐷 is the downtime (see [START_REF] Benoit | Checkpointing strategies to protect parallel jobs from non-memoryless fail-stop errors[END_REF][START_REF]Fault-Tolerance Techniques for High-Performance Computing[END_REF]). The expression for E(𝑇 𝑖 ) can be extended for a block of consecutive tasks followed by a checkpoint (simply replace 𝑤 𝑖 by the execution time of the block). This gives the baseline for a dynamic programming algorithm where one tries to place the first checkpoint at the end of task 𝑇 𝑘 for 1 ≤ 𝑘 ≤ 𝑛 and computes recursively the optimal solution for the remaining sub-chain 𝑇 𝑘+1 ,𝑇 𝑘+2 , . . . ,𝑇 𝑛 . This is the approach followed by Toueg and Babaoglu [START_REF] Toueg | On the Optimum Checkpoint Selection Problem[END_REF].

Iterative Applications

The next problem after a linear chain is that of a pipelined linear workflow: we consider now a workflow made of a large number of iterations, each iteration being the same linear chain of parallel tasks. A typical example is an application consisting of an outer loop "While convergence is not met, do", and where the loop body includes a sequence of large parallel operations. As in Section 3.2, the objective is to find which task outputs should be saved on stable storage to minimize the expected duration of the whole computation. However, if the workflow consists of, say, ten thousand iterations, each with twenty tasks, one does not want to apply the dynamic programming algorithm of Toueg and Babaoglu [START_REF] Toueg | On the Optimum Checkpoint Selection Problem[END_REF] to a chain of two hundred thousand tasks!

A natural heuristic is to use the Young/Daly formula and checkpoint at the end of the current task as soon as the total work executed since the last checkpoint exceeds the quantity √ 2𝜇𝐶. Unfortunately, even if all tasks may well enroll the same number of processors 𝑞 and, hence, have the same MTBF 𝜇 = 𝜇 ind 𝑞 , they are not likely to have the same checkpoint duration 𝐶. One can approximate 𝐶 by the minimum, maximum, or average values of the checkpoint duration of all tasks. This is the heuristic proposed in [START_REF] Du | Optimal checkpointing strategies for iterative applications[END_REF], and its performance is shown satisfactory for a wide range of application scenarios.

As a side note, when the number of iterations is infinite (or very large in practice), it is shown in [START_REF] Du | Optimal checkpointing strategies for iterative applications[END_REF] that there exists an optimal checkpointing strategy that is periodic. It consists of a pattern of task outputs to checkpoint, where this pattern spans over a set of iterations of bounded size. This pattern is repeated over and over throughout the execution. [START_REF] Du | Optimal checkpointing strategies for iterative applications[END_REF] also provides a dynamic programming algorithm, which is polynomial in the number of operations included in the outer loop to compute the optimal periodic checkpoint pattern. The complexity of the algorithm does not depend on the number of iterations of the outer loop. This pattern may well checkpoint many different tasks, across many different iterations. For a workflow with a fixed number of iterations, this periodic strategy is appealing. However, the cost of computing the optimal pattern may be high, and the Young/Daly extension described above may be preferred in some frameworks.

General Workflows

Another special case is that of a workflow whose dependence graph is arbitrary but whose tasks are parallel tasks that each executes on the whole platform. In other words, the tasks have to be serialized. The problem of ordering the tasks and placing checkpoints is proven NP-complete for simple join graphs in [START_REF] Aupy | Scheduling computational workflows on failure-prone platforms[END_REF], which also introduces several heuristics.

For general workflows, the news is not good either. Consider the problem of scheduling an arbitrary workflow. As mentioned in Section 3.1, the common strategy used in practice is checkpoint everything, or CkptAll: all output data of each task is saved onto stable storage. While this strategy leads to fast restarts in case of failures, its downside is that it maximizes checkpointing overhead. At the other end of the spectrum would be a checkpoint nothing strategy, or CkptNone, by which all output data is kept in memory (up to memory capacity constraints) and no task is checkpointed. This corresponds to "in-situ" workflow executions, which have been proposed to reduce I/O overhead [START_REF] Zhang | Enabling In-situ Execution of Coupled Scientific Workflow on Multi-core Platform[END_REF]. The downside is that, in case of a failure, a large number of tasks may have to be reexecuted, leading to slow restarts. The objective of an efficient checkpoint strategy is to achieve a desirable trade-off between these two extremes. But the complexity of this problem is steep.

The fundamental difficulty lies in the evaluation of a solution. A solution consists of an ordered list of tasks to execute for each processor, and for each task whether or not to save its output data to stable storage after its execution. In a failure-free execution, the total execution time, or makespan, of a solution is simply the longest path in the DAG, accounting for serialized task executions at each processor. With failures, the makespan becomes a random variable because task execution times are probabilistic, due to failures causing task re-executions. Consider a first simple case with the CkptAll strategy and a solution in which each task is assigned to a different processor. Computing the expected makespan amounts to computing the expected longest path in the schedule. Unfortunately, computing the expected length of the longest path in a DAG with probabilistic task durations is a known difficult problem [START_REF] Hagstrom | Computational complexity of PERT problems[END_REF][START_REF] Michael | Scheduling: Theory, Algorithms, and Systems[END_REF]. Even in the simplified case when task durations are random variables that can take only two discrete values, the problem is #P-complete [START_REF] Hagstrom | Computational complexity of PERT problems[END_REF]. 1Now, at the other extreme, consider a second simple example with the CkptNone strategy and a solution in which each task is assigned to a different processor. Even if each task has the unitary cost and can fail only once, computing the expected makespan is a #P-complete problem again [START_REF] Han | Checkpointing workflows for fail-stop errors[END_REF]. These two examples show all the difficulty of the problem, even when an ordered list of tasks to execute is already assigned to each processor. Several heuristics to tackle the general problem are proposed in [START_REF] Han | A Generic Approach to Scheduling and Checkpointing Workflows[END_REF].

DEALING WITH UNCERTAINTY

This section briefly addresses two scenarios where it is impossible to apply the Young/Daly formula directly, even though the target application is preemptible and tightly coupled as in Section 2. Basically, in the 𝑊 YD = √ 2𝜇𝐶 formula, this is when either 𝜇 or 𝐶 is unknown!

Unknown MTBF

When the MBTF 𝜇 ind of an individual processor is unknown, the MTBF 𝜇 = 𝜇 ind 𝑝 of the application is unknown too. There is no other solution than to learn the value of 𝜇 by trial and error. The initial guess for 𝜇 is arbitrary, say from a few hours to several weeks depending upon the size of the application. Compute 𝑊 YD accordingly and schedule the first checkpoint. If a failure strikes before this checkpoint, decrease the current estimate of 𝜇. If no failure strikes before this checkpoint, keep the current value for 𝜇 and proceed for a few periods of the same length. if there is still no failure at this point, it should be safe to increase the estimate of 𝜇. The rates for decreasing/increasing the current estimate could follow some geometric progression, e.g., the next estimate is either half or twice the current one.

An interesting heuristic is proposed in [START_REF] Sigdel | Realizing Best Checkpointing Control in Computing Systems[END_REF]. The checkpoint period is dynamically adjusted so that the aggregate checkpointing cost always equals the expected rework cost after failure recovery. The intuition follows the discussion in Section 2.2: in the optimal solution, both sources of waste (checkpoint and re-execution) should be balanced.

Unknown Checkpoint Time (Due to Contention)

This section deals with the scenario where checkpoint cost 𝐶 is unknown. In fact, this corresponds to a scenario where several applications are executing concurrently on the platform (recall space-sharing from Section 2.4). Each application has precise knowledge of the volume of data to be saved but the I/O bandwidth to stable storage that is granted is subject to variations over time. The main reason is contention: consider the simple case where two applications of the same size (number of processors) checkpoint simultaneously a file of the same size (volume). Each application will be assigned half the I/O bandwidth to checkpoint, therefore the commits will take twice as expected. In other words, the checkpoint time of each application is doubled, and the Young/Daly period √ 2𝜇𝐶 should have been increased by a factor √ 2; the checkpoint strategy is no longer optimal, and efficiency will decrease.

Several heuristics are described in [START_REF] Herault | Checkpointing Strategies for Shared High-Performance Computing Platforms[END_REF] for this contention problem. Each application attempts to use its Young/Daly period. The I/O token is given to only one application at every time step, and I/O operations cannot be interrupted once started. If several applications post concurrent requests to checkpoint, one will be selected and the other ones will continue their execution. The selection is based upon several criteria, including the time already spent waiting for I/O and the risk incurred by all the applications (increased waste) that have not been selected. See [START_REF] Herault | Checkpointing Strategies for Shared High-Performance Computing Platforms[END_REF] for details.

SILENT ERRORS

In this section, we consider another type of error: while all previous sections addressed fail-stop errors, we now deal with silent errors, first in isolation and then in combination with fail-stop errors. It turns out that the Young/Daly formula can be extended to deal with both types of errors.

Background

We start with some background on silent errors, a.k.a. silent data corruptions (SDCs). While fail-stop errors lead to fatal interruptions (such as a crash) and cause the loss of the entire memory of the processor, silent errors only impact a given process and lead to incorrect results. But a silent error strikes undetected and the processor can continue its execution; sometimes the silent error can be detected and corrected, and some other times it degenerates into a fatal fail-stop error.

Silent errors may be caused, for instance, by soft errors in the L1 cache, arithmetic errors in the ALU (Arithmetic and Logic Unit), or bit flips due to cosmic radiation [START_REF] Moody | Design, Modeling, and Evaluation of a Scalable Multi-level Checkpointing System[END_REF][START_REF] O'gorman | The effect of cosmic rays on the soft error rate of a DRAM at ground level[END_REF][START_REF] Ziegler | Cosmic ray soft error rates of 16-Mb DRAM memory chips[END_REF][START_REF] Ziegler | IBM Experiments in Soft Fails in Computer Electronics[END_REF]. Many silent errors caused by one or multiple bits that spontaneously flip to the opposite state are caught by hardware mechanisms such as error correcting codes (ECCs) that have been implemented to protect memory. But in reality, some bit flips still manage to pass undetected [START_REF] Vilas Sridharan | Memory Errors in Modern Systems: The Good, The Bad, and The Ugly[END_REF]. Moreover, processor caches are not protected by ECC in general, but by weaker mechanisms, like simple parity, exposing a higher risk of undetectable error in case of multiple simultaneous bit flips. Buses also often are a weak link in the protecting chain, making all data transfers at higher risk. In addition, the constant need to reduce component size and voltage increases the likelihood of silent errors. In a nutshell, silent errors have become a major threat due to the increase in problem size [START_REF] Snir | Addressing Failures in Exascale Computing[END_REF]: the larger the problem, the more memory to be used to store the data, the more frequent the errors, and the higher the probability of overriding ECC protection, generating multiple errors.

A major problem with silent errors is detection latency: contrarily to a fail-stop error whose detection is immediate, a silent error is identified only when the corrupted data is activated and/or leads to an unusual application behavior. On the contrary, checkpoint and rollback recovery assumes instantaneous error detection, and this raises a new difficulty: if the error stroke before the last checkpoint, and is detected after that checkpoint, then the checkpoint is corrupted and cannot be used to restore the application. To solve this problem, one may envision keeping several checkpoints in memory and restoring the application from the last valid checkpoint, thereby rolling back to the last correct state of the application [START_REF] Lu | When is Multi-version Checkpointing Needed?[END_REF]. But even if it was at all possible to store many checkpoints (which is very demanding in memory), one would not know how to identify the last valid one. Some verification mechanism, or detector, must be enforced.

Considerable efforts have been directed at designing such verification mechanisms to reveal silent errors, because error detection is usually very costly. Hardware mechanisms, such as ECC memory, can detect and even correct a fraction of errors, but in practice, they are complemented with software techniques. The only general-purpose method is to replicate the execution of the target computational kernel on two sets of processors and to compare the results of both executions. If they do not coincide, an error has been detected, and the application must be executed a third time. To avoid a-posteriori re-execution, triplication can be enforced, which allows for error correction in addition to error detection, using a simple majority vote. However, triplication (originally known as triple modular redundancy and voting [START_REF] Lyons | The use of triple-modular redundancy to improve computer reliability[END_REF]) is even more costly than replication, which already requires half the resources to execute redundant operations.

Application-specific information can be very useful to enable ad-hoc solutions, which dramatically decreases the cost of detection. Many techniques have been advocated. They include memory scrubbing [START_REF] Hwang | Cosmic rays don't strike twice: understanding the nature of DRAM errors and the implications for system design[END_REF] and ABFT techniques [START_REF] Bosilca | Algorithmbased fault tolerance applied to high performance computing[END_REF][START_REF] Huang | Algorithm-Based Fault Tolerance for Matrix Operations[END_REF][START_REF] Shantharam | Fault Tolerant Preconditioned Conjugate Gradient for Sparse Linear System Solution[END_REF], such as coding for the sparse-matrix vector multiplication kernel [START_REF] Shantharam | Fault Tolerant Preconditioned Conjugate Gradient for Sparse Linear System Solution[END_REF], and coupling a higher-order with a lower-order scheme for PDEs [START_REF] Benson | Silent error detection in numerical time-stepping schemes[END_REF]. These methods can only detect an error but do not correct it. Self-stabilizing corrections after error detection in the conjugate gradient method are investigated in [START_REF] Sao | Self-stabilizing Iterative Solvers[END_REF]. Fault-tolerant iterative solvers for sparse linear algebra are introduced in [START_REF] Bronevetsky | Soft error vulnerability of iterative linear algebra methods[END_REF][START_REF] Chen | Online-ABFT: An online algorithm fault tolerance scheme for soft error detection in iterative methods[END_REF][START_REF] Heroux | Fault-tolerant iterative methods via selective reliability[END_REF], using extra checks such as re-computing inner products of vectors that should be orthogonal, or even re-computing the residual.

In summary, application-specific detectors are very appealing due to their low cost as compared to replication, but they suffer from some limitations. Most application-specific detectors can only detect errors, not correct them. Next, they are used to detect errors of a certain type, while many types can strike. For instance, with iterative methods, orthogonality tests will detect arithmetic errors but cannot do anything if we start with corrupted data in memory. Worse, even for a given type of error, the detector will not detect all the errors of that type, but only a fraction of them (one says that the detector recall is strictly smaller than one). Finally, ABFT is one of the few methods that enables error correction in addition to detection, but it is currently limited to correcting a single error due to the numerical instability of state-of-the-art methods.

Optimal Period for Silent Errors

We study a generic solution that is agnostic of the nature of the verification mechanism (replication, checksum, error correcting code, coherence tests, etc.). We assume that we can rely on a fully general-purpose detector, of cost 𝑉 . The idea is to perform a verification just before taking each checkpoint. If the verification succeeds, then one can safely store the checkpoint. If the verification fails, it means that a silent error has struck since the last checkpoint, which was duly verified, and one can safely recover from that checkpoint to resume the execution of the application.

See Figure 2 for an illustration and comparison with fail-stop errors. If a silent error strikes, it is always detected only at the end of the period, when the verification reveals the error; on the contrary, a fail-stop error strikes in the middle of the period on average and is detected immediately. Note that there is no downtime for silent errors because the processor can continue its execution after a silent error and need not be replaced. For simplification, we have used 𝐷 = 0 in the second row of Figure 2 (with fail-stop error), but recall there is a downtime after a fail-stop error in the general case.

Just as for fail-stop errors, we introduce the MTBE of individual nodes as 𝜇 silent ind . Here the MTBE is the Mean Time Between Errors, the counterpart for silent errors of the MBTF for fail-stop errors.

The MTBE of an application with 𝑝 processors will be 𝜇 silent = 𝜇 silent ind 𝑝 : because the frequency of silent errors is proportional to the number of arithmetic operations executed, and/or to the volume of the memory footprint of the application; the MTBE scales linearly with the size of the application, just as the MTBF does. Now consider a parallel application of MTBE 𝜇 silent . At first sight, one could think that the optimal Young/Daly period for silent errors will be 𝑊 YD =

√

2𝜇 silent (𝑉 + 𝐶), because we have replaced each checkpoint of cost 𝐶 by a verified checkpoint of cost 𝑉 +𝐶. However, because a silent error is always detected only at the end of the period, when the verification reveals the error, the formula will be different. With the notations of Section 2.2, the two sources of waste become 𝑆 1 = 𝑉 +𝐶 𝑊 +𝑉 +𝐶 and 𝑆 2 = 1 𝜇 silent (𝑅 +𝑊 +𝑉 ). Altogether, both sources of waste approximately add up, so we have to find 𝑊 that minimizes 𝑆 1 + 𝑆 2 . Simplifying as before, we obtain 𝑆 1 + 𝑆 2 ≈ 𝑉 +𝐶 𝑊 + 𝑊 𝜇 silent , which is minimized for

𝑊 YD = √ 𝜇 silent (𝑉 + 𝐶) (2)
Equation ( 2) is the Young/Daly formula for silent errors!

Extensions

A first natural extension is to deal with both fail-stop and silent errors. Indeed, both sources of errors are likely to strike simultaneously when executing a parallel application. In that case, the failure-free waste 𝑆 1 = 𝑉 +𝐶 𝑊 +𝑉 +𝐶 remains unchanged but the failureinduced waste should be updated to account for both error types:

𝑆 2 = 1 𝜇 fail 𝐷 + 𝑅 + 1 2 (𝑊 + 𝑉 + 𝐶) + 1 𝜇 silent (𝑅 + 𝑊 + 𝑉 )
Here for clarity, we have used 𝜇 fail instead of simply 𝜇 for the MTBF of the application. Simplifying again, we obtain that the total waste is minimized for

𝑊 YD = 1 1 2𝜇 fail + 1 𝜇 silent (𝑉 + 𝐶) (3)
Equation ( 3) is the Young/Daly formula for fail-stop and silent errors combined! We check that Equation (3) reduces to Equation (1) when 𝜇 silent = ∞ and 𝑉 = 0 (only fail-stop errors) and to Equation (2) when 𝜇 fail = ∞ (only silent errors). The general case uses the harmonic mean of 𝜇 fail and 𝜇 silent weighted by the average proportion of re-execution time in a period when struck by an error.

The second extension applies when application-specific information enables to decrease the cost of a verification well below the cost of a checkpoint, i.e., when 𝑉 ≪ 𝐶. In that case, it is useful to insert some intermediate verifications within the period to detect silent errors early on. Assume that we deal with silent errors only and see Figure 3 for an example of a period with 2 intermediate verifications (and a third one at the end of the period to verify the checkpoint). The failure-free waste 𝑆 1 is increased to 𝑆 1 = 3𝑉 +𝐶 𝑊 +3𝑉 +𝐶 ≈ 3𝑉 +𝐶 𝑊 . However, the failure-induced waste is reduced to

𝑆 2 = 1 𝜇 silent 1 3 (𝑅 + 𝑊 3 + 𝑉 ) + 1 3 (𝑅 + 2𝑊 3 + 2𝑉 ) + 1 3 (𝑅 + 𝑊 + 3𝑉 ) ≈ 1 𝜇 silent (1+2+3)𝑊 9 = 2𝑊 3𝜇 silent
To see this, with equal probability 1 3 , the silent error will strike either third of the pattern, and re-execution will cost either 𝑊 3 (first third), or 2𝑊 3 (second third), or 𝑊 (last third). This leads to 𝑆 . This is very likely to be the case with an application-specific detector.

We refer to [START_REF] Benoit | Assessing general-purpose algorithms to cope with fail-stop and silent errors[END_REF] for the analysis of more general patterns. Also, we have assumed a perfect verification mechanism, while all application detectors have a limited recall (ratio of missed errors, or false negatives) and a limited precision (ratio of detected errors that are in fact not errors, or false positives). One can have an arsenal of several detectors of different recall, precision, and cost that can be used; see [START_REF] Bautista-Gomez | Coping with recall and precision of soft error detectors[END_REF] for choosing the best approach.

CONCLUSION

This survey has dealt with checkpointing policies based upon the Young/Daly period and has assessed its usefulness and robustness together with its limitations. We discuss some extensions and open problems in this conclusion.

For preemptible applications (Section 2), we have focused on coordinated checkpointing onto stable storage, but most of the results hold for other methods that reduce checkpoint overhead, such as in-memory checkpointing [START_REF] Dongarra | Performance and reliability trade-offs for the double checkpointing algorithm[END_REF][START_REF] Ni | Hiding checkpoint overhead in HPC applications with a semi-blocking algorithm[END_REF][START_REF] Zheng | FTC-Charm++: an in-memory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF], two-level checkpointing [START_REF] Di | Toward an Optimal Online Checkpoint Solution under a Two-Level HPC Checkpoint Model[END_REF][START_REF] Silva | Using two-level stable storage for efficient checkpointing[END_REF] and multi-level checkpointing [START_REF] Bautista-Gomez | FTI: High Performance Fault Tolerance Interface for Hybrid Systems[END_REF][START_REF] Benoit | Towards optimal multi-level checkpointing[END_REF][START_REF] Di | Optimization of multi-level checkpoint model for large scale HPC applications[END_REF][START_REF] Moody | Design, Modeling, and Evaluation of a Scalable Multi-level Checkpointing System[END_REF].

For task-based applications, one could envision an extension of coordinated checkpointing designed for such systems. Using periodic coordinated checkpointing to decide which tasks to checkpoint in a distributed task system consists of finding a period between two checkpoint waves, and coordinating all the processes of the application to checkpoint their state. Applying this heuristic to a task-based system does not ensure optimal performance, because the amount of data to checkpoint depends on the number and input of the ready tasks and varies over time, which is outside the assumptions of the periodic checkpointing approach. However, by continuously adapting the period to the amount of work executed (either maximal or averaged across all processors), this strategy may provide an efficient solution in scenarios where tasks are small and where failures are rare.

For both application models (preemptible and task-based), we have assumed failure independence. Indeed, the standard model assumes IID failure inter-arrival times, or IATs, on each node, with a common distribution D. As for temporal dependence, it has been observed many times that when a failure occurs, it may trigger other failures that will strike different system components [START_REF] Bautista-Gomez | Reducing Waste in Extreme Scale Systems through Introspective Analysis[END_REF][START_REF] Heien | Modeling and tolerating heterogeneous failures in large parallel systems[END_REF][START_REF] Tiwari | Lazy Checkpointing: Exploiting Temporal Locality in Failures to Mitigate Checkpointing Overheads on Extreme-Scale Systems[END_REF]. As an example, a failing cooling system may cause a series of successive crashes of different nodes. Also, an outstanding error in the file system will likely be followed by several others [START_REF] Steven | Making Cloud Intermediate Data Fault-tolerant[END_REF][START_REF] Schroiff | Cascading failover of a data management application for shared disk file systems in loosely coupled node clusters[END_REF]. As for spatial dependence, it is clear that the overheating of some node in a cabinet is quite likely to be followed by the overheating of neighbor nodes (which comes atop of a temporal dependence as well!). Bautista-Gomez et al. [START_REF] Bautista-Gomez | Reducing Waste in Extreme Scale Systems through Introspective Analysis[END_REF] have studied nine systems, and they report periods of high failure density in all of them. They call these periods cascade failures. This observation has led them to revisit the temporal failure independence assumption, and to design bi-periodic checkpointing algorithms that use different periods in normal (failure-free) and degraded (with failure cascades) modes. [START_REF] Tiwari | Lazy Checkpointing: Exploiting Temporal Locality in Failures to Mitigate Checkpointing Overheads on Extreme-Scale Systems[END_REF] introduces a dynamic strategy called lazy checkpointing to adjust to changes in the failure rate. Another approach has been proposed in [START_REF] Aupy | Assuming failure independence: are we right to be wrong?[END_REF], using quantiles of consecutive IAT pairs. It is an open problem to derive an efficient checkpoint strategy that can account for temporal or spatial dependence between failures. For example, spatial dependence calls for a variant of in-memory checkpointing where the buddy of a processor (acting replica of a checkpoint) is chosen far away from that processor, while it is better to select a physical neighbor to optimize communication overhead if failures are truly independent. Complicated trade-offs must be achieved.

Finally, for silent errors, the first open problem remains which detector to use and when. Some parts of the application are critical (such as its execution code) and must be protected at all costs while some other parts (like non-critical data) may be loosely and infrequently verified by cheap mechanisms; we speak of selective reliability in such a framework. More generally, trustworthy computing is the problem of guaranteeing, at least with some high probability, that the final results of a parallel application are correct. The higher the flop count and the larger the data footprint, the more challenging to achieve this goal!

Figure 1 :

 1 Figure 1: Trade-off for the optimal checkpoint period.

Figure 2 :

 2 Figure 2: Fails-stop errors versus silent errors.

Figure 3 :

 3 Figure 3: Introducing two intermediate verifications in the period.

  𝜇 silent (3𝑉 + 𝐶) and we get (𝑆 1 + 𝑆 2 ) min = 3𝜇 silent for that value. In comparison, without intermediate verification, we had (𝑆 1 + 𝑆 2 ) min = 2 √ 𝑉 +𝐶 𝜇 silent . We check that adding two intermediate verifications is better than none as long as 𝑉 ≤

	1 + 𝑆 2
	√ 2 2 3 minimized for 𝑊 = √ 2(3𝑉 +𝐶 )
	𝐶
	3

Recall that #P is the class of counting problems that correspond to NP decision problems[START_REF] Hans | A Note on the Complexity of Network Reliability Problems[END_REF][START_REF] Provan | The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected[END_REF][START_REF] Valiant | The Complexity of Enumeration and Reliability Problems[END_REF], and that #P-complete problems are at least as hard as NPcomplete problems.