Young-Daly Checkpoint Interval

The Young–Daly checkpoint interval is the rule of thumb for how often a long-running job should save its state when failures arrive at random. Saving too often wastes time on writes, and saving too rarely loses a lot of work at each failure. Young (1974) gave a first-order approximation for the interval that minimizes the total waste, and Daly (2006) analyzed it with higher-order terms and stated when it holds.

The formula

Let \( \delta \) be the time the job is blocked while writing one checkpoint, and \( M \) the mean time between failures (MTBF) of the job as a whole. Young’s approximation for the compute time between checkpoints is

\[ T_{\text{opt}} \approx \sqrt{2\,\delta\,M} \]

The reasoning is a balance of two terms. Checkpointing costs \( \delta / T \) per unit of useful work. Each failure, which happens about once per \( M \), loses on average half an interval of work, so failures cost \( T/(2M) \). The total \( \delta/T + T/(2M) \) falls and then rises as \( T \) grows, and setting its derivative \( -\delta/T^2 + 1/(2M) \) to zero gives the square root. Because the minimum is shallow, an interval within a factor of about two of the optimum costs only a little more, which is why an estimate is good enough in practice. The optimum grows only with the square root of each parameter: a checkpoint four times as expensive, or a cluster four times as reliable, calls for an interval twice as long.

Restart time \( R \) adds \( R/M \) to the waste, but it does not depend on \( T \), so it does not move the optimum in this first-order model.

Assumptions

• Failures arrive at random at a constant rate, so the expected position of a failure in an interval is its midpoint.
• The checkpoint time \( \delta \) is small compared with \( M \), and the job is restored from the most recent checkpoint only.
• \( \delta \) is the time the job is blocked. If the job copies its state to memory and writes it in the background, use the blocking part.
• \( M \) belongs to the whole job: the failure rate of one GPU multiplied across all the GPUs and hosts the job needs.

A numerical check

The script below uses an MTBF of 3.1 hours and a restart time of 10 minutes, values chosen to be a plausible magnitude. For each checkpoint cost it finds the interval that minimizes the expected overhead under an exponential failure model in which failures can also strike during a checkpoint write and during a restart, then compares it with Young’s formula and with Daly’s refinement, \( \sqrt{2\delta M} – \delta \), which Daly’s paper recommends when \( \delta < M/2 \) (and \( M \) otherwise). Overhead is extra wall-clock time per unit of useful work. It also checks the model against a Monte Carlo simulation of 300 runs per row.

import math, random
M, R = 3.1*3600, 600.0                      # MTBF and restart (seconds)

def waste_fo(T, d):  return d/T + (T/2 + R)/M          # first-order model
def young(d, M=M):   return math.sqrt(2*d*M)
def daly(d, M=M):    return math.sqrt(2*d*M) - d if d < M/2 else M

def overhead_exact(T, d):                    # exponential failures, failures can hit save/restart
    seg = T + d
    return M*math.exp(R/M)*(math.exp(seg/M)-1)/T - 1   # extra wall time per unit of useful work

def sim(T, d, work=2e5, runs=300, seed=1):
    rnd = random.Random(seed); tot = 0.0
    for _ in range(runs):
        done = 0.0; t = 0.0
        while done < work:
            chunk = min(T, work-done); seg = chunk + d
            while True:                      # attempt one segment
                x = rnd.expovariate(1/M)
                if x >= seg: t += seg; done += chunk; break
                t += x
                while True:                  # restart, which can also fail
                    y = rnd.expovariate(1/M)
                    if y >= R: t += R; break
                    t += y
        tot += t/work - 1
    return tot/runs

for d in (20, 120, 600):
    Ty, Td = young(d), daly(d)
    grid = [Ty*k/400 for k in range(40, 1600)]
    best = min(grid, key=lambda T: overhead_exact(T, d))
    print(f"d={d:4d}s  Young {Ty/60:5.1f} min  Daly {Td/60:5.1f} min  numeric optimum {best/60:5.1f} min | "
          f"overhead at Young {overhead_exact(Ty,d):.3f}, at optimum {overhead_exact(best,d):.3f}")
d = 120; Ty = young(d)
print("check by simulation, d=120s:")
for k in (0.25, 0.5, 1, 2, 4):
    T = Ty*k
    print(f"  T={T/60:6.1f} min  first-order {waste_fo(T,d):.3f}  exact-model {overhead_exact(T,d):.3f}  simulated {sim(T,d):.3f}")
# when d is not small relative to M
for d in (0.3*M, 0.5*M):
    Ty = young(d); grid=[M*k/200 for k in range(1,600)]
    best=min(grid,key=lambda T: overhead_exact(T,d))
    print(f"d={d/3600:.2f}h  Young {Ty/3600:.2f}h numeric {best/3600:.2f}h overhead@Young {overhead_exact(Ty,d):.2f} @opt {overhead_exact(best,d):.2f}")

Output from Python 3.12.14 on macOS 26.7.1:

d=  20s  Young  11.1 min  Daly  10.8 min  numeric optimum  10.9 min | overhead at Young 0.121, at optimum 0.121
d= 120s  Young  27.3 min  Daly  25.3 min  numeric optimum  26.0 min | overhead at Young 0.227, at optimum 0.226
d= 600s  Young  61.0 min  Daly  51.0 min  numeric optimum  54.6 min | overhead at Young 0.496, at optimum 0.493
check by simulation, d=120s:
  T=   6.8 min  first-order 0.365  exact-model 0.398  simulated 0.396
  T=  13.6 min  first-order 0.237  exact-model 0.262  simulated 0.262
  T=  27.3 min  first-order 0.200  exact-model 0.227  simulated 0.225
  T=  54.6 min  first-order 0.237  exact-model 0.278  simulated 0.278
  T= 109.1 min  first-order 0.365  exact-model 0.470  simulated 0.478
d=0.93h  Young 2.40h numeric 1.83h overhead@Young 1.63 @opt 1.57
d=1.55h  Young 3.10h numeric 2.17h overhead@Young 2.67 @opt 2.50

For checkpoint costs of 20 seconds and 2 minutes, Young’s interval (11.1 and 27.3 minutes) is within about 5 percent of the numerical optimum (10.9 and 26.0 minutes), and the overhead at Young’s interval is within a thousandth of the best achievable. Daly’s subtraction of \( \delta \) lands closer in all three rows (10.8, 25.3, and 51.0 minutes against 10.9, 26.0, and 54.6). At a 10-minute checkpoint, Young’s 61.0 minutes is 12 percent above the optimum, yet the overhead differs by only 0.003 (0.496 against 0.493), another sign of how flat the minimum is. The simulation agrees with the exponential model within about two percent. Both are higher than the first-order waste formula, which ignores failures during writes and restarts (0.227 against 0.200 at 27.3 minutes). The last two rows set the checkpoint cost to 0.3 and 0.5 times \( M \), where Young’s interval is clearly too long (2.40 against 1.83 hours, and 3.10 against 2.17) and the overhead is already above 100 percent, which says the checkpoints, not the interval, are the problem.

Using it

• Reducing \( \delta \) usually matters more than tuning \( T \), because overhead scales with \( \sqrt{\delta/M} \). Asynchronous and sharded checkpoints lower the blocking time.
• Recompute the interval from observed failure counts. \( M \) changes with job size, hardware generation, and time.
• \( \delta \) is not constant when many jobs write to shared storage at once, so concurrent checkpointing can push the real cost above the measured one.
• Failures that are not independent and identically distributed, such as correlated rack failures or infant mortality, break the constant-rate assumption. The formula then gives a starting point, not an optimum.
• The same rule applies to any restartable computation with a cost to save state, not only to training.

References

• J. T. Daly, A higher order estimate of the optimum checkpoint interval for restart dumps (2006): model and approximation derivations
• The Morning Paper, summary of Daly, A higher order estimate of the optimum checkpoint interval for restart dumps