Reliability decay and the optimal checkpoint

Parent: derivations

0. Claim and contribution

For a task of $n$ error-prone atomic steps:

1. Exponential reliability decay — with no intermediate check, P(correct) $=p^n$; half-life $=\Theta(1/(1-p))$ (Thm 1–2).
2. Restart cost without checkpoints — expected total work $=n/p^n$, super-exponential (Thm 3).
3. Checkpoints drop the exponent $n\to k$ — expected execution work $=n/p^k$ (Thm 4).
4. Optimal interval — exact per-interval expected work in a Poisson model, then the rigorous $\tau^\*=\sqrt{2\delta M}$ limit, with checkpoint cost $\delta$ in the accounting throughout (Thm 5). Cites only basic probability.

1. Discrete model

$n$ sequential steps. (A1) each step is correct (prob $p\in(0,1)$) or wrong (prob $q=1-p$), independently. (A2) a checkpoint perfectly detects whether the segment since the last one is all-correct. (A3) with no intermediate check, detection is only at the end (errors are silent within a pass, so each pass executes all $n$ steps).

2. Theorem 1 (exponential decay)

Theorem 1

$P(\bigcap_{k=1}^nA_k)=\prod_kP(A_k)=p^n$ by independence (A1). Since $p<1$, $p^n=e^{n\ln p}\to0$.

3. Theorem 2 (half-life, with bounds)

Theorem 2

$m_{1/2}$ solving $p^{m_{1/2}}=\tfrac12$ satisfies

$$m_{1/2}=\frac{\ln2}{-\ln(1-q)},\qquad \frac{\ln2}{q}(1-q)\le m_{1/2}\le\frac{\ln2}{q}.$$

Proof

$m_{1/2}\ln p=\ln\tfrac12$ gives the equality. From $-\ln(1-q)=\sum_{j\ge1}q^j/j$: $\ge q$ gives the upper bound; $\le\sum q^j=\frac{q}{1-q}$ gives the lower.

(e.g. $q=0.01\Rightarrow m_{1/2}\in[68.6,69.3]$.)

4. Theorem 3 (restart cost, no checkpoints)

Lemma

Geometric mean. Success prob $r$ per trial; first-success index $N$ has $E[N]=1/r$.

Proof. $P(N=j)=(1-r)^{j-1}r$; with $\sum_{j\ge1}jx^{j-1}=(1-x)^{-2}$, $E[N]=r(1-(1-r))^{-2}=1/r$.

Theorem 3

Redo the whole task on failure $\Rightarrow$ expected execution work $=n/p^n$.

Proof. Passes are i.i.d. with success $p^n$ (Thm 1); $E[\#\text{passes}]=1/p^n$; each pass executes $n$ steps (A3). Super-exponential in $n$.

5. Theorem 4 (checkpoints: exponent $n\to k$)

Theorem 4

Partition into $n/k$ segments of length $k$, each with a detecting checkpoint (redo only the failed segment to pass). Expected execution work $=\frac{n}{k}\cdot\frac{k}{p^k}=n/p^k$. Ratio to Thm 3: $p^{k-n}=(1/p)^{n-k}$, exponentially small for $n\gg k$.

(Accounting) This counts execution only, not checkpoint cost $\delta$; if $\delta$ were free, $k=1$ is optimal. The optimal granularity once $\delta>0$ is priced is §6 — fixing the inconsistency of counting work but not gates.

6. Theorem 5 (optimal interval, exact then asymptotic)

Theorem 5

Model. Progress in useful work; failures a Poisson process of rate $\lambda$ (so $M=1/\lambda$ mean work between failures); checkpoint every $\tau$, cost $\delta$; a failure rolls back to the last checkpoint (redo the whole current interval).

Exact per-interval work. Per-attempt no-failure prob $a=e^{-\lambda\tau}$. Truncated mean: $E[T_f\mathbf 1_{T_f<\tau}]=\int_0^\tau t\lambda e^{-\lambda t}dt=-\tau e^{-\lambda\tau}+\frac{1-e^{-\lambda\tau}}{\lambda}$, so $E[T_f\mid T_f<\tau]=\frac1\lambda-\frac{\tau a}{1-a}$; expected failed attempts $\frac{1-a}{a}$. Hence

$$\mathbb E[\text{interval work}]=\tau+\delta+\frac{1-a}{a}\Big(\frac1\lambda-\frac{\tau a}{1-a}\Big)\quad\text{(exact).}$$

Rare-failure limit $\lambda\tau\to0$. With $x=\lambda\tau$: $\frac{1-a}{a}(\frac1\lambda-\frac{\tau a}{1-a})=\frac1\lambda(e^x-1)-\tau=\frac{\lambda\tau^2}{2}+O(\lambda^2\tau^3)$ (the linear term cancels via $\frac1\lambda x=\tau$). So extra overhead per interval $=\delta+\frac{\lambda\tau^2}{2}+O(\lambda^2\tau^3)$, and over total useful work $T$:

$$C(\tau)=\frac{\delta T}{\tau}+\frac{\lambda T\tau}{2}+O(\lambda^2\tau^2T).$$

Convex; $C'(\tau)=-\delta T/\tau^2+\lambda T/2=0\Rightarrow$

$$\boxed{\tau^\*=\sqrt{2\delta M}}\quad(\text{valid in }\lambda\tau^\*\ll1),\qquad C(\tau^\*)=T\sqrt{2\delta/M}\,(1+o(1)),$$

with checkpoint and rework costs equal at the optimum.

Remark

Second order gives Daly (2006)'s correction $\tau^\*=\sqrt{2\delta M}(1-\tfrac13\sqrt{\delta/2M}+\cdots)$ — cited; leading order is the result.

7. Scope

Independent steps (correlated/common-cause failures change $p^n$); perfect detection (a miss rate makes the gate only partly truncate the exponent — the "semantic error passing the type gate" case); rollback-to-checkpoint (finer recovery shrinks the $\tau/2$ waste and shifts $\tau^\*$); §2–5 discrete vs §6 continuous — consistent (both: the gate truncates the long-horizon multiplicative cost).

8. Cited vs proved

Proved: $p^n$ via independence; log-series bounds; geometric mean; restart & segmented work; exact per-interval cost and its limit. Cited: exponential inter-arrival of the Poisson process; Daly's second-order correction.