# Partial Detectors Versus Replication To Cope With Silent Errors

Anne Benoit, Thomas Herault, Yves Robert, Alix Tremodeux

► To cite this version:

Anne Benoit, Thomas Herault, Yves Robert, Alix Tremodeux. Partial Detectors Versus Replication To Cope With Silent Errors. Euro-Par 2025 - 31 st International European Conference on Parallel and Distributed Computing, Aug 2025, Dresden, Germany. hal-05231852

HAL Id: hal-05231852

https://inria.hal.science/hal-05231852v1

Submitted on 31 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à 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.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Partial Detectors Versus Replication
## To Cope With Silent Errors

Anne Benoit¹,², Thomas Herault³, Yves Robert¹, Alix Tremodeux¹

¹ Laboratoire LIP, ENS Lyon & Inria, Lyon, France

² Institut Universitaire de France and IDEaS, Georgia Tech, USA

³ Inria, Bordeaux, France

`{anne.benoit, thomas.herault, yves.robert, alix.tremodeux}@inria.fr`

**Abstract** This work studies an iterative algorithm running on an error-prone platform, where silent errors strike each iteration with some probability. A detector verifies correctness before taking a checkpoint but may fail to detect errors. Specifically, an error at iteration *I* is detected only after iteration (*I* − 1) + *X*, where *X* follows a bounded probability distribution like a truncated geometric distribution. Intuitively, the error silently amplifies during some iterations before it can be detected at distance *X* or higher, and there is the risk of missing an error that has struck recently but cannot be detected yet. *X* is bounded by *D*, the maximum detection latency. To mitigate undetected errors during verification, a simple strategy keeps two checkpoints and divides the execution into *D* − 1 iteration segments, each followed by verification and checkpoint. In steady state: (i) if verification succeeds, the oldest checkpoint is erased and replaced; (ii) if it fails, rollback occurs to the oldest verified checkpoint. This work explores whether this scheme outperforms replication and determines the optimal number of checkpoints and segment lengths, both theoretically and via Monte Carlo simulations.

# 1 Introduction

Let us consider an iterative algorithm whose execution is struck by silent errors.
The only application-independent approach to mitigate the impact of such errors
is *replication*, which works as follows:

- The execution is partitioned into *segments* of *M* iterations, each followed by a checkpoint. Assume that the initial data can also be recovered if necessary;

- The execution of a new segment (after a checkpoint *C*) consists of at least two attempts, and possibly more:

• First attempt: execute the segment and checkpoint the result $res_1$;

* While the results after $t \ge 1$ attempts are all different, execute new attempt $t+1$, i.e., recover from the checkpoint *C*, redo the *M* iterations and checkpoint the result *res*$_{t+1}$;

* Keep the outcome of the two identical checkpoints and proceed to the next segment.

Here, the classical hypothesis is that two errors will never lead to the same
(incorrect) result; more precisely, one neglects this event whose probability is
extremely low. Hence, the rationale is to make attempts until the same result
is obtained twice, because that result will necessarily be correct. Interestingly,
the optimal value of *M* (the segment length) can be obtained numerically as a
function of the resilience parameters, namely the fault-rate and checkpoint cost.
The optimal value is defined as minimizing the expected time per iteration. We
provide such a derivation in Section 4. Note that, to the best of our knowledge,
this derivation is new, despite the many related studies on replication.

While replication is the only general-purpose approach to cope with silent
errors, several application-specific methods have been introduced. We survey sev-
eral examples of such detectors in Section 2, which is devoted to related work.
In a nutshell, one uses a detector (typically an application-specific routine) to
verify that the current state of the computation is correct. The main problem
with silent errors is their detection latency: when a silent error strikes, it does not
manifest immediately to the application, but only after some non-deterministic
number of iterations. A detector is required to verify the application's correct-
ness. Without one (and without replication), any detected error forces a full
re-execution, as the exact moment of failure is unknown, making intermediate
checkpoints unreliable. With a detector, errors can be identified before taking
a checkpoint, ensuring a safe restart point. Crucially, the detector must be per-
fect, meaning it can detect all silent errors as soon as it strikes. With a perfect
detector, The optimal strategy to place checkpoints is well-known [3], as well as
a first-order approximation that is the counterpart for silent errors of the Young
& Daly formula for fail-stop errors [19,10].

Unfortunately, it is very difficult, if at all possible, to design perfect detectors. More likely, one can design *partial* detectors that will detect many errors, but not all. One can envision several trade-offs where the recall<fnref n="4" /> of the detector can be adjusted as a function of the cost of the verification mechanism. The more comprehensive the verification, the higher the recall of the detector, but also the higher its cost [1,11].

Using partial detectors instead of replication seems a promising cost-effective
alternative to replication. To ensure correctness, one must assume that detection
latency is bounded. If a silent error occurs during an iteration and remains
undetected for all subsequent iterations, the final result will be invalid – and there
will be no way to determine whether this has happened. Henceforth, we study
partial detectors whose detection latency is bounded. More precisely, we envision
the following scenario: when a silent error strikes during iteration *I*, one will be
able to detect it by applying the partial detector at iteration (*I* − 1)+*X* or after,
where *X* is a random variable obeying a probability distribution with bounded
support [1, *D*]. For instance say a silent error strikes at iteration *I* = 10, and
draw *X* = 3. Applying the detector at the end of iterations *I* = 10 or *I* = 11 will
not detect this error, but it will be detected for any iteration *I* ≥ 12. Regardless
of the value of *X*, the partial detector will systematically detect the error *D*
iterations later, where *D* is the maximum detection latency, The rationale for

<footnote n="4">⁴ The recall of a detector is defined as the fraction of errors that it can detect. If it is lower than 1, some errors, the *false negatives*, are missed by the detector.</footnote>
this model if that we expect the impact of the silent error on the application data to grow and become more and more *detectable*. For computation errors, this corresponds to a numerical amplification of the error as the execution progresses.

The main focus of this work is to provide a comprehensive assessment of the above scenario. Given a partial detector of bounded latency, what is the best (less costly) execution scheme to ensure correctness? How does it compare to replication? The simplest scheme is to have segments of $M = D - 1$ iterations and to keep two checkpoints in memory, as illustrated below:

<figure><img src="image_2.png" /></figure>

When executing segment $S_0$, checkpoints $C_1$ and $C_2$ are stored in memory. By induction, the oldest checkpoint $C_2$ is certified to be verified, but this is not yet the case for checkpoint $C_1$. When we complete the execution of the current segment $S_0$, we apply the detector through verification $V_0$. There are two cases:

- No error is detected. Then checkpoint $C_1$ is verified, because all errors that might have struck during segment $S_1$ did so at least $D$ iterations before and would have been detected by $V_0$. For instance, if an error struck during the last iteration of $S_1$, then its distance to the last iteration of segment $S_0$ is the maximum detection latency $D$ (remember that we include the original struck iteration in the distance count). We can safely take checkpoint $C_0$ and overwrite the older checkpoint $C_2$.

- An error is detected. We must roll back. But there is no way of knowing whether the error struck during segment $S_0$ or earlier on during $S_1$; in the latter case, the error went through undetected when verification $V_1$ was applied. Hence, we need to roll back to checkpoint $C_2$, which is known to be verified, and to re-execute $S_1$ followed by $S_0$. But now, if an error is detected by $V_1$, we can roll back to $C_2$ again, because $C_2$ is verified.

Despite simple to understand, this scheme is not easy to evaluate and compare with replication. Our main contribution is to assess the efficiency of this scheme and more complicated ones, involving many segments. In fact, we solve the main optimization problem: how many segments, or equivalently how many checkpoints to keep in memory? And how many iterations to execute within each segment? These results lay the theoretical foundations for the problem of comparing partial detectors and replication.

The rest of the paper is organized as follows. Section 2 surveys related work. In Section 3, we detail the framework. Section 4 is devoted to analyzing replication and its optimization. Section 5 is the heart of the paper, where we assess partial detectors: we compute the expected time per iteration for a general scheme, and we provide the optimal values of its parameters. This theoretical analysis is complemented by Monte Carlo simulations in Section 6. Finally, we give concluding remarks and hints for future work in Section 7.
## 2 Related work

Due to lack of space, an extensive discussion of related work can be found in the companion research report [5], with some background on silent errors, a review of partial detectors, and a discussion on recall and precision.

In a nutshell, considerable efforts have been directed at designing detectors to reveal silent errors, because the only general-purpose method, replication, is very costly. Application-specific information can be very useful to enable ad-hoc solutions, which dramatically decreases the cost of detection. Many techniques have been advocated [14,13,17,15,7,16,9,12,2,8]. None of them is perfect, but these techniques cover a substantial number of silent errors, and more importantly, they incur very low overheads. These properties make them attractive candidates for designing efficient protocols based upon partial detection.

Perfect detectors would be very appealing because they can be applied before taking a checkpoint, which by definition will be verified since all potential errors would have been detected. With a perfect detector, the approach is to use a single segment of execution, and a single checkpoint is kept in memory. Partial detectors can be added in the middle of that segment to speed-up detection. However, perfect detectors are more a perspective than an actual proposal. Without a perfect detector, replication was the only known approach before this work. Introducing a partial detector with bounded detection latency, and assessing its performance, is the key contribution of this work.

## 3 Framework

This section details the framework and the objective function. We focus on a generic iterative application, because it is easier to express every quantity in terms of numbers of iterations. In particular, we account for the cost of every resilience mechanism (detector, checkpoint, recovery) as a number of iterations. This makes the approach agnostic of the granularity of the application, which can range from sequential to massively parallel, and of the nature of errors, either silent or transient.

The application is subject to the occurrence of errors, which can be mitigated either by replication or by applying a partial detector. We consider two main probability distribution laws to model error rates and latency detections:

- Occurrence: A silent error may strike each iteration independently and with a fixed probability $f$. In other words, error inter-arrival times obey a Geometric distribution law of parameter $f$.

- Detection: When an error strikes during iteration $I$, it can be detected (by applying the partial detector) only at iteration $(I - 1) + X$ or after, where $X$ is the detection distance, or latency. $X$ obeys a truncated Geometric distribution law: we have $X = \min(Y, D)$, where $Y$ is a random Geometric variable of parameter $\theta$, and $D$ is the maximum detection latency. This leads to $P(X = d) = P(Y = d) = (1 - \theta)^{d-1}\theta$ if $1 \le d < D$, and $P(X = D) = P(Y \ge D) = (1 - \theta)^{D-1}$. The support of $X$ is the interval $[1, D]$, and $X = 0$ elsewhere.
Again, once an error manifests, it never autocorrects and keeps manifesting during the following iterations until it can be detected. This is like tossing a biased coin (with probability $\theta$ for heads and $1 - \theta$ for tails) every iteration during which or after the error struck, until the first head is drawn, but we bound the maximum number of tosses to ensure correctness in the worst case. Table 1 helps get an insight on typical values for the maximum detection distance $D$. For an efficient partial detector ($\theta = 0.9$), distance detection never exceeds 10 in practice. For a poor partial detector ($\theta = 0.2$, capturing only 20% of errors), distance detection never exceeds 100 in practice.

<table><caption>Table 1: Bound for $D$ as a function of $\theta$.</caption><thead><tr><th>θ</th><th>min{d|P(X ≥ d) ≤ 10<sup>-6</sup>}</th><th>min{d|P(X ≥ d) ≤ 10<sup>-9</sup>}</th></tr></thead><tbody><tr><td>0.2</td><td>62</td><td>93</td></tr><tr><td>0.4</td><td>28</td><td>41</td></tr><tr><td>0.9</td><td>6</td><td>9</td></tr></tbody></table>

All the random variables for occurrence and detection are assumed to be independent. For error detection, one needs to restrict to a Poisson process (memoryless probability distribution for error inter-arrival times). Because time is discretized into iterations, we need to use a Geometric law instead of an Exponential law. While independence and memorylessness are restrictive assumptions, they represent the state-of-the art of all studies in resilience for HPC, as explained in [11,6]. However, this study can be directly extended to any bounded-support probability distribution law for error detection.

We further assume that the partial detector has precision 1 (no false alarm). This is only a simplification rather than an intrinsic limitation of partial detectors. Indeed, we can extend the complicated derivation provided in Section 5 to account for the extra rollbacks, recoveries and re-executions that would be caused by false alarms. Such an extended derivation is set for future work.

The execution scheme partitions the application into segments of $M$ iterations followed by a checkpoint. We always apply the partial detector, whose cost is $V$ iterations, before taking a checkpoint, whose cost is $C$ iterations. Note that: (i) we take that checkpoint only if no error is detected; and (ii) the checkpoint may still not be verified because some error has struck and remained undetected. However, some checkpoints are guaranteed to include no error; we call such checkpoint a *verified checkpoint*. If an error is detected by the verification, the application rolls back to the last verified checkpoint and pays a recovery, whose cost is $R$ iterations, before resuming the execution from that point on. The existence of a verified checkpoint is an invariant of the execution scheme and is proven by induction (see details in Section 5). There are no errors during verifications, checkpoints and recoveries.

Finally, the objective function is to minimize the expected slowdown $S$ per iteration, which characterizes the diminution of the application progress due to error mitigation. If the cost to execute a segment of $M$ iterations is $cost(M)$, then the slowdown is $S = \frac{cost(M)}{M}$.
## 4 Replication

As discussed in Section 1, replication uses segments of $M$ iterations followed by a checkpoint. Each segment is executed several times, until the results of two execution attempts are identical. The cost of the first attempt is $M + C$, while the cost of the following attempts is $R + M + C$ because each of them starts with a recovery. While we need to perform further attempts, we have to keep the checkpoints of all previous attempts in memory so that we can check whether the results of two attempts are identical. The number of attempts (which corresponds to the number of checkpoints that have to be stored) until one is successful obeys a geometric distribution law of parameter $p_S$, the probability of executing a segment of $M$ iterations without any error. We have $p_S = (1 - f)^M$, and the expected number of attempts until one is successful is $\frac{1}{p_S}$. The expected number of attempts until two are successful is $\frac{2}{p_S}$. Since the first attempt has cost $M + C$ and the following ones have cost $R + M + C$, the expected cost to execute a segment is

$$cost(M) = (M + C) + \left(\frac{2}{p_S} - 1\right) (R + M + C) = \frac{2(R + M + C)}{p_S} - R,$$

and the expected slowdown is $S = \frac{cost(M)}{M} = \frac{2(R+C)}{M p_S} + \frac{2}{p_S} - \frac{R}{M}$. With $p_S = (1 - f)^M$, we let $g(M) = \frac{2(R+C)}{M(1-f)^M} + \frac{2}{(1-f)^M} - \frac{R}{M}$ and aim at minimizing $g(M)$. We get $g'(M) = \frac{(1-f)^{-M}}{M^2} (R((1-f)^M - 2) - 2M \ln(1-f)(C + R + M) - 2C)$. The optimal value $M_{opt}^{rep}$ of $M$ is such that $g'(M_{opt}^{rep}) = 0$. Unfortunately, this equation does not have a closed-form solution when $f$, $C$ and $R$ are unknown parameters, even when $R = C$. We need to resort to numerical methods to find the optimal value $M_{opt}^{rep}$ when the values of the parameters are given.

Note that the replication strategy has significant advantages: it is application-independent, and its performance depends only on the statistical properties of the risk of errors. However, as we will see in Section 6, it comes with a high cost, which may be prohibitive in practice.

## 5 Partial Detectors

In this section, we assess the use of the partial detector. We consider an execution scheme with $k$ segments and $k$ checkpoints stored in memory. Each segment consists of $M$ iterations, followed by a verification and a checkpoint. Segment $S_i$, $0 \le i \le k - 1$, is followed by verification $V_i$ and checkpoint $C_i$. Figure 1 provides an illustration with $k = 3$ and $M = 5$.

First, there is some relation to enforce between $M$, $k$ and the maximum detection latency $D$ for the execution scheme to be valid. We are currently executing segment $S_0$ and aiming to ensure that checkpoint $C_{k-1}$ ($C_2$ in the example) is verified, so that we can overwrite $C_3$ by $C_0$ if verification $V_0$ is successful. This requires that any error that may have struck within segment $S_{k-1}$ ($S_2$ in the example) is detected by $V_0$ eventually, if it has not been detected by previous
<figure><img src="image_3.png" /><figcaption>Figure 1: Example with $k = 3$ and $M = 5$.</figcaption></figure>

verifications $V_{k-1}, V_{k-2}, \dots, V_1$ earlier on. This requirement is fulfilled if we enforce that $(k-1)M \ge D - 1$, because an error that struck at the last iteration of segment $S_{k-1}$ is at distance $(k-1)M + 1 \ge D$ from the last iteration of segment $S_0$, and it will be detected by $V_0$ if it has not been detected before. Given a value for $M$, we will use

$$k = \left\lceil \frac{D-1}{M} \right\rceil + 1 \qquad (1)$$

as the minimum number of checkpoints that must be kept in memory; this is also the minimum number of segments for the execution scheme. Note that $k \ge 2$ unless $D = 1$, which corresponds to a perfect detector. In the example, $M = 5$ and $k = 3$, hence we must have $D \le 11$.

When executing the current segment $S_0$, checkpoints $C_1$ to $C_k$ are in memory, and checkpoint $C_k$ is known to be verified, since all errors previous to $C_k$ would have been detected by $V_1$ at the latest. However, errors having struck segments $S_{k-1}$ to $S_1$ may have remained undetected up to verification $V_1$ included.

Our objective is to determine the expected time needed to complete the $M$ iterations of segment $S_0$ and to replace the oldest checkpoint $C_k$ by a new one at the end of $S_0$. Once $V_0$ is successful, we know for sure that $C_{k-1}$ is a verified checkpoint; but if $V_0$ detects an error, we have to roll back to $C_k$, the last verified checkpoint, and to re-execute all the $k$ segments.

We start by computing the probability that an error is detected during a given verification. Let $P_{i,j}$ be the probability that an error that struck at the $i$-th iteration of the $\ell$-th segment (for $1 \le i \le M$ and $0 \le \ell \le k-1$) is detected at $V_{\ell-j}$ (for $0 \le j \le \ell$). Hence, for $j = 0$, this is the probability that the error is detected immediately at the end of the segment where it struck; otherwise, it is the probability of detection after $j$ other segments have been executed. We have

$$P_{i,j} = P(X \le jM + (M - i + 1)) - P(X \le (j-1)M + (M - i + 1)). \quad (2)$$

The probability to detect an error striking at iteration $i$ in segment $\ell$ to be detected after $V_{\ell-j}$ is denoted as $P_{i,>j} = P(X > jM + (M - i + 1))$.

Let $E_0$ be the expected time required to process segment $S_0$ entirely, and then to take a new checkpoint $C_0$ after a successful verification, hence deleting $C_k$ from memory and moving on to the next segment. By induction, $C_k$ is a verified
checkpoint when we start executing $S_0$, but the more recent $k-1$ checkpoints are not yet verified. The objective is to compute $E_0$.

Because different rollbacks may be needed to complete the process of segment $S_0$, we introduce $E_j$ for $1 \le j \le k-1$ as the expected time required to go all the way up to taking $C_0$ starting at the first iteration of segment $S_j$, and knowing that no error has been detected by the previous verifications $V_{j'}$, where $j' \ge j + 1$: hence, no error has been detected in the first segments before $C_{j+1}$ and the start of segment $S_j$. The execution goes as follows: we execute $S_0$ and $V_0$. If $V_0$ is successful, we take checkpoint $C_0$, and we are done. Otherwise, we roll back to $C_k$ and re-execute all the last $k$ segments, recovering from $C_k$ which is the only verified checkpoint. Now, during this re-execution, some errors may strike, among which some may be detected. The execution progresses until an error is detected, in which case we roll back to $C_k$.

First segment $S_{k-1}$. We start by considering the first segment $S_{k-1}$, just after the verified checkpoint $C_k$. Let $Q_0$ be the probability that either there is no error during the $M$ iterations of $S_{k-1}$, or that none of the errors that struck during these iterations are detected by $V_{k-1}$. In other words, $Q_0$ is the probability to go through $V_{k-1}$ (so to speak), checkpoint and proceed to segment $S_{k-2}$:

$$ 
\begin{aligned}
E_{k-1} = & R + M + V \quad \text{recovery, computation and verification done in all cases} \\
& + Q_0(C + E_{k-2}) \quad \text{no error in } S_{k-1} \text{ that is detected by } V_{k-1} \\
& + (1 - Q_0)E_{k-1} \quad \text{roll back and start over: detected error}
\end{aligned}
$$

Since $C_k$ is correct by induction hypothesis, an error detected by $V_{k-1}$ can only have occurred in $S_{k-1}$, not before. Hence: $Q_0 = \prod_{i=1}^{M}(1 - fP_{i,0})$. Indeed, an error occurs at iteration $i$ of $S_{k-1}$ with probability $f$, it is detected at $V_{k-1}$ with probability $P_{i,0}$ (current segment), hence there is a probability $1 - fP_{i,0}$ that there were no error nor any detected error from iteration $i$. Note that $Q_0$ can actually be used for any segment, since it only considers errors occurring during the segment and detected at the end of that segment.

Next segments $S_j$, $1 \le j \le k-2$. We extend the formula to any $E_j$ as follows, for $j \ge 1$ (the case $E_0$ is slightly different):

$$ 
\begin{aligned}
E_j = & M + V \quad \text{computation and verification done in all cases} \\
& + \left( \prod_{\ell=0}^{k-1-j} Q_\ell \right) (C + E_{j-1}) \quad \text{no error that is detected by } V_j, \text{ move to } S_{j-1} \\
& + \left( 1 - \prod_{\ell=0}^{k-1-j} Q_\ell \right) E_{k-1} \quad \text{roll back and start over from } S_{k-1}: \text{ detected error}
\end{aligned}
$$

Here is how we compute the different probabilities. In order to be able to move to the next segment $S_{j-1}$, we now need to consider several cases:

- No error in $S_j$ has been detected by $V_j$ at the end of the segment: this happens with probability $Q_0$ as defined above.
- We must however also look for errors that may come from previous segments, and hence generalize the formula. $Q_\ell$ is the probability that there is no error coming from the $\ell$-th previous segment that is detected by $V_j$, for $0 \le \ell \le k-2$. Hence, for $\ell = 1$, we are looking at errors coming from the segment just before $S_j$ (hence in $S_{j+1}$). For each previous segment, there are three possibilities for any of the $M$ potential error locations:

* There is no error, with a probability $(1-f)$.

* There is an error that is not detected by $V_j$, but that will be detected later. By conditional definition of $E_j$, the error was not detected before either (with $V_{j'}$, where $j' > j$), and hence this is the probability $fP_{i,>\ell}$ (there is an error, it is detected later).

* Finally, there might have been an error that is detected by the current verification $V_j$, and this comes with a probability $fP_{i,\ell}$.

All probabilities must therefore be normalized by the sum of the probabilities of the three cases, which is $(1-f)+f(P_{i,>\ell}+P_{i,\ell})$. For $\ell = 0$, this sums to 1 since the error is either detected at the end of the current segment ($P_{i,0}$) or later ($P_{i,>0}$), and therefore we obtain the previous formula of $Q_0$ again. We finally obtain $Q_\ell = \prod_{i=1}^M \left(1 - \frac{fP_{i,\ell}}{(1-f)+f(P_{i,>\ell}+P_{i,\ell})}\right)$.

- By combining all possible locations of errors that remain undetected at $V_j$, coming from the current segment $S_j$ or previous ones (up to $k-1-j$ previous segments), we obtain the probability that no error is detected at $V_j$ and that we can move forward to $S_{j-1}$, expressed as $\prod_{\ell=0}^{k-1-j} Q_\ell$.

*Last segment $E_0$. Finally, for $E_0$, when we consider faults from segment $S_{k-1}$, they are necessarily detected by $V_0$, which slightly changes the computation of probabilities to complete. Indeed, the expression of $Q_{k-1}$ further considers that any error at $S_{k-1}$ will necessarily be detected at most at $V_0$, because the distance of detection $D$ is exceeded. Again, because of the conditional expression of $E_0$, we know that no error in $S_{k-1}$ has been detected before, and therefore, either there was no error (probability $(1-f)$), or the error is detected at $V_0$ (probability $P_{i,k-1}$). Hence, we write: $Q_{k-1} = \prod_{i=1}^M \left(1 - \frac{fP_{i,k-1}}{(1-f)+f(P_{i,k-1})}\right)$. We point out that this is the same formula as above because $P_{i,>k-1} = 0$ (remember that the distance detection is upper bounded by $D$).

We can finally write $E_0$, which is the quantity that we aim at minimizing, i.e., the time to progress to the next segment, add a new checkpoint and delete checkpoint $C_k$:

$$ 
\begin{aligned}
E_0 = & M + V && \text{computation and verification done in all cases} \\
& + \left( \prod_{\ell=0}^{k-1} Q_\ell \right) C && \text{no error that is detected at } V_0, \text{ take a checkpoint} \\
& + \left( 1 - \prod_{\ell=0}^{k-1} Q_\ell \right) E_{k-1} && \text{roll back and start over from } S_{k-1}: \text{ detected error}
\end{aligned}
$$
We check that this is indeed the same expression as for $E_j$ with $1 \le j \le k - 2$ if we let $E_{-1} = 0$, which is comforting.

In [5], we show by induction how these models can be used to derive the value for $E_0$, defining values $a_k$, $b_k$ and $c_k$. We then aim at minimizing the expected slowdown $S = \frac{E_0}{M}$, for all possible values of $M$. For each value of $M$, the value of $k$ is given by Equation (1) and is large enough to guarantee correctness. We do this with a simple exhaustive loop, where the upper bound $UB$ is chosen to be large experimentally:

$$M_{opt}^{par} = 0; k_{opt} = 0; S = \infty$$

for $M = 1$ to $UB$

$$k = \left\lceil \frac{D-1}{M} \right\rceil + 1; E^{iter} = \frac{E_0}{M} = a_k \frac{C}{M} + b_k \left(1 + \frac{V}{M}\right) + c_k \frac{R}{M}$$

if $E^{iter} < S$ then $M_{opt}^{par} = M; k_{opt} = k; S = E^{iter}$

# 6 Evaluation

In order to evaluate the different models, we have implemented a set of discrete events simulations that follow the protocols described above. The simulations are written in C, and are publicly available for reproducibility purposes in [4]. Each execution that we simulate is 100,000 iterations long, and as per our models above, C, V, R are all measured in terms of iterations. For each set of parameters, we simulate 10,000 executions and measure for each the total time of execution (wall time, in number of iterations), the number of errors, rollbacks, and the number of checkpoints taken. We then compute the mean and the variance of these values. Errors are injected following the model described in Section 3.

We have set the following parameters for the simulations: C and R are both equal and set to 3 iterations to account for the overheads in communications and I/O; V is set to 1 iteration, as verification is usually a fast operation (see [18] and the references therein). The other parameters of the simulations are varied to evaluate their respective impacts on the performance. The probability of occurrence of an error during an iteration, $f$, ranges between $10^{-4}$ (producing only a handful of errors during the 100,000 iterations of an execution) and $8.6 \cdot 10^{-3}$ (leading up to 4,500 errors during the execution); we consider all values for $\theta$ between 10% and 90%; as suggested by Table 1, we consider values of D ranging from 10 to 100. In order to validate the model, we evaluate the protocols for all values of $M$, and set $k$ using Equation (1). We compare the optimal value for $(k, M_{opt}^{par})$ predicted by the model with the experimental value.

**Validation.** Figure 2 shows, for a specific configuration ($D = 80, \theta = 0.4$), the optimal interval between checkpoints for the Partial Detector strategy (on the left axis), and the wall time of a run of 100,000 iterations (on the right axis), as calculated by the theoretical model and as measured by the simulations. The goal of this figure is to validate that both the mathematical model and the simulation reach the same measurement on the key metrics. The wall time predicted by the model is slightly smaller than the wall time measured during simulations for very high $f$ (when the frequency of errors is high), but the difference remains under 5%. Conjointly, $M_{opt}^{par}$ according to the theoretical model is different by one iteration from the value extracted from the simulations, on a small range of
<figure><img src="image_4.png" /><figcaption>Figure 2: Comparison between the model and the simulations.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 3: Simulated mean wall time function of risk of error ($f$) and number of iterations ($M$).</figcaption></figure>

low $f$ values. These small differences are due to rounding errors in the simulation framework.

*Parameter exploration.* Figure 3 shows the simulated mean wall time for $\theta = 0.4$ and $D = 70$, varying the risk of error ($f$) and the number of iterations between two checkpoints ($M$). For each value of $f$, we consider all possible values of $M$ between $C$ (number of iterations to take a single checkpoint) and $D$ (maximum latency to detect an error). For each $M$, we set $k$, the number of checkpoints to keep, according to Equation (1). First, we observe that simulations with a low $f$ ($f \le 0.00113906$), taking more checkpoints than the minimal two or using an interval between checkpoints lower than $D$ is detrimental to performance. Errors are so rare in this situation (low $f$), and the chance that they are detected right away is so high ($\theta = 0.4, D = 70$), that the most efficient strategy consists in waiting as long as possible before introducing a verification and a checkpoint.

When the risk of error increases, however, we see that the optimal strategy changes. The wall time figure then looks like a step-wise function, with steps happening every time $M$ divides $D$ into equal intervals. The low points of this step-wise function define a parabolic curve that accepts a minimal value of the wall time for various couples ($k, M_{opt}^{par}$) that are identified in the figure. For instance, when $f = 0.00864976$, the couple ($k = 6, M = 14$) defines a low point, where the wall time is at 266,027 (so 2.66 times slower than the execution without faults nor fault tolerance enabled).

Figure 4 shows the impact of the detection bound ($D$) on the wall time for $\theta = 0.4$, varying the risk of error ($f$). All curves show a parabolic behavior, with an optimal that depends on $D$. For experiments where the risk of error is low, a high $D$ value turns out more efficient than a lower $D$ value, which is to be expected as errors being rare, longer working periods allow us to reduce the overheads due to forced (and useless) checkpoints. Three of the curves shown
<figure><img src="image_6.png" /><figcaption>Figure 4: Impact of the detection bound ($D$) on the wall time for $\theta = 0.4$, varying the risk of error ($f$).</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 5: Wall time for replication, as a function of $M$ and the risk of error ($f$).</figcaption></figure>

in this figure are limited to values of $D$ that are suboptimal ($D = 100$), and even higher values of $D$ could be explored. These curves represent the runs in which errors are the most unlikely to occur. For more volatile experiments, when $f$ has a high value and many errors impact the system, a lower $D$ value is optimal. However, $D$ is not a parameter that the user can choose for performance reasons, but is strongly constrained by the properties of the partial detector. It is possible, depending on the detector properties, that $D$ becomes higher than the optimal value. If this is the case, this figure also shows that performance can be significantly impacted, for highly volatile systems.

*Comparison with replication.* Figure 5 shows the wall time for the replication strategy, as a function of the interval between two checkpoints ($M$) and the risk of error ($f$). As for the partial detector strategy, the wall time exhibits a parabolic behavior, with an optimal value $M_{opt}^{rep}$ that depends on $f$. The figure shows the location of this optimal value for each different value of $f$. As $f$ decreases, $M_{opt}^{rep}$ increases, and more importantly, the wall time decreases to asymptotically reach a factor two when $f$ is low enough and almost no errors hit the system. By construction, the replication strategy cannot be more efficient than this limit, as each segment must be executed at least twice to validate the result. This is the cost to pay to have a generic and perfect error mitigation mechanism.

Figure 6 shows the best interval between two checkpoints in the case of the replication strategy ($M_{opt}^{rep}$), compared between the simulation results and the theoretical model. Additionally, the second axis shows how many checkpoints need to be kept in the worst cases. The figure shows that the theoretical model is very close to the simulation results, for values of $f$ bigger than 0.00050625. For $f < 0.00050625$, the simulation artificially bounded the maximum value of $M_{opt}^{rep}$ to $D$ (as it was done in the case of the partial detector strategy), and the minimum value is observed in simulations for that bound, while the model predicts much higher values of $M_{opt}^{rep}$. The figure also shows that the maximum number of checkpoints required in the simulations is relatively small, with a maximum of 10 checkpoints required in the worst case that we have considered.

Figure 7 compares the performance of the replication strategy with the partial detector strategy for a few values of $D$ and $\theta$. As we have observed that $\theta$ does
<figure><img src="image_8.png" /><figcaption>Figure 6: Comparison between the simulation results and the theoretical model for replication.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 7: Comparison of the wall time of replication with partial detection for various values of $D$.</figcaption></figure>

not have a significant impact on the performance (see the companion research report [5] for details), we have chosen to show only the results for $\theta = 0.4$. The figure shows that the replication strategy is less efficient than the partial detector strategy in a large range of $D$ and $f$ values. Only when errors are very frequent (for $f = 0.008$, executions typically experience more than 4,000 errors to execute the 100,000 iterations), and the error detector is so unreliable that the bound for the maximum number of iterations to detect an error is 100, the replication strategy becomes more efficient.

# 7 Conclusion

This work is the first study devoted to comparing replication with the use of partial detectors with bounded latency. We have formalized the problem, and provided a detailed analysis of the optimal schemes for both approaches. Given the application and platform parameters, we derived the optimal number of iterations that should be executed between two checkpoints, as well as the number of checkpoints to keep in memory in the case of partial detectors.

Next, we have assessed and compared the performance of both strategies through a comprehensive set of Monte-Carlo simulations. Simulated results perfectly match the theoretical predictions, and illustrate the gain that results from using non-trivial patterns in terms of number of segments and number of iterations. More importantly, the simulations demonstrate that the use of partial detectors can massively outperform replication, allowing the application to complete within a significantly smaller time (typically, twice faster in the presence of few errors). Furthermore, the number of checkpoints that need to be stored to guarantee that we can always recover from a verified checkpoint is fixed with partial detectors, while it is unclear how many checkpoints will have to remain in memory when using replication.

We plan to extend this work by considering more complex patterns for rollbacks, trying to rollback to intermediate unverified checkpoints and combining replication with partial detectors to verify some of them. An experimental validation with some iterative numerical application (the Preconditioned Conjugate Gradient method would be an ideal candidate) would also further demonstrate the usefulness of partial detectors.
**Acknowledgements and Artifact Availability:** As part of the "France 2030" initiative, this work has benefited from a national grant managed by the French National Research Agency (Agence Nationale de la Recherche) attributed to the Exa-MA project of the NumPEx PEPR program, under the reference ANR-22-EXNU-0002. The software used to produce the results of this paper is available in [4].

## References

1. L. Bautista-Gomez, A. Benoit, A. Cavelan, S. Raina, Y. Robert, and H. Sun. Coping with recall and precision of soft error detectors. *JPDC*, 98:8-24, 2016.

2. L. Bautista Gomez and F. Cappello. Detecting silent data corruption through data dynamic monitoring for scientific applications. *SIGPLAN*, 49(8):381-382, 2014.

3. A. Benoit, A. Cavelan, Y. Robert, and H. Sun. Assessing general-purpose algorithms to cope with fail-stop and silent errors. *ACM TOPC*, 3(2), 2016.

4. A. Benoit, T. Herault, Y. Robert, and A. Tremodeux. Artifact of the paper: Partial detectors versus replication to cope with silent errors. https://doi.org/10.5281/zenodo.15591615, June 2025.

5. A. Benoit, T. Herault, Y. Robert, and A. Trémodeux. Partial detectors versus replication to cope with silent errors. Research report 9581, INRIA, 2025. https://inria.hal.science/hal-04996292v1.

6. A. Benoit, L. Perotin, Y. Robert, and F. Vivien. Checkpointing strategies to tolerate non-memoryless failures on HPC platforms. *ACM Trans. Parallel Computing*, 11(1), 2024.

7. A. R. Benson, S. Schmit, and R. Schreiber. Silent error detection in numerical time-stepping schemes. *Int. J. High Performance Computing Applications*, 2014.

8. E. Berrocal, L. Bautista-Gomez, S. Di, Z. Lan, and F. Cappello. Lightweight silent data corruption detection based on runtime data analysis for HPC applications. In *HPDC*. ACM, 2015.

9. Z. Chen. Online-ABFT: An online algorithm based fault tolerance scheme for soft error detection in iterative methods. In *Proc. PPoPP*, pages 167-176, 2013.

10. J. T. Daly. A higher order estimate of the optimum checkpoint interval for restart dumps. *FGCS*, 22(3):303-312, 2006.

11. T. Herault and Y. Robert, editors. *Fault-Tolerance Techniques for High-Performance Computing*. Springer Verlag, 2015.

12. M. Heroux and M. Hoemmen. Fault-tolerant iterative methods via selective reliability. Research report SAND2011-3915 C, Sandia Nat. Lab., 2011.

13. K.-H. Huang and J. A. Abraham. Algorithm-based fault tolerance for matrix operations. *IEEE Trans. Comput.*, 33(6):518-528, 1984.

14. A. A. Hwang, I. A. Stefanovici, and B. Schroeder. Cosmic rays don't strike twice: understanding the nature of DRAM errors and the implications for system design. *SIGARCH Comput. Archit. News*, 40(1):111-122, 2012.

15. S. Li, S. Di, K. Zhao, X. Liang, Z. Chen, and F. Cappello. Resilient error-bounded lossy compressor for data transfer. In *SC'94*, SC '21. ACM, 2021.

16. P. Sao and R. Vuduc. Self-stabilizing iterative solvers. In *ScalA '13*, 2013.

17. M. Shantharam, S. Srinivasmurthy, and P. Raghavan. Fault tolerant preconditioned conjugate gradient for sparse linear system solution. In *ICS*. ACM, 2012.

18. A. Tremodeux, E. Agullo, A. Benoit, L. Giraud, T. Herault, and Y. Robert. Fault-tolerant numerical iterative algorithms at scale. Technical Report RR-9567, Inria Lyon, 2025.

19. J. W. Young. A first order approximation to the optimum checkpoint interval. *Comm. of the ACM*, 17(9):530-531, 1974.