長時間ジョブの管理：チェックポイント・再開の冪等性・最適な保存間隔

0. この記事の要点

3 日かかる計算が 2 日目の終わりに止まってしまったとき、最初からやり直さずに済ませるには、途中経過を保存しておくのが基本です。この記事では、保存したところから再開しても結果が変わらないのはどんなときか、どのくらいの間隔で保存すれば時間の無駄が最も少ないか、時間切れで終わらなかった計算を集計でどう扱うか、の 3 つを順に考えます。読み終えると、長い計算を安心して中断・再開できる書き方と、保存間隔の目安が分かります。

• ジョブを「状態と 1 ステップの遷移」の状態機械とみると、遷移が決定的で、チェックポイントが状態を完全に保存し、書き込みが原子的（途中までしか書かれた状態が見えず、全部書けたか、まったく書けていないかのどちらか）なら、何回中断して再開しても最終結果は中断のない実行と一致します。3 つの条件のどれを落としても破れます（乱数生成器の状態の保存漏れ、書きかけのファイル、追記の重複）。
• 各ステップの結果を「キーがあれば読む、なければ計算して保存する」形にすると、同じステップが 2 回走っても結果は変わりません（冪等。同じ操作を何回行っても 1 回行ったのと同じ結果になること）。
• 故障が強度 $\lambda = 1/\mu$ の Poisson 過程で起こるとき、仕事 $\tau$ とチェックポイント $C$ の 1 区間を終えるまでの期待時間は $(\mu + R)(e^{\lambda(\tau + C)} - 1)$ です。仕事あたりの時間を最小にする間隔 $\tau^{*}$ は $\sqrt{2C\mu} - 2C \le \tau^{*} \le \sqrt{2C\mu}$ を満たします（Young の近似）。最適の近くは平らで、間隔が倍や半分でも損は小さいままです。
• 「制限時間内に終わった試行だけ」を集計すると、所要時間と結果が相関するときに推定が偏ります。打ち切った試行は消さずに、件数と理由を残します。
• 1 次収束する反復の残り回数は $\log(\mathrm{tol}/e_k)/\log\rho$ で見積もれます。2 次収束ではこの外挿は過大評価になります。

この記事で使う事前知識

• 擬似乱数生成器: 内部の状態から次々に乱数を作り出す仕組みで、状態を保存すれば続きの乱数を再現できます。→ 擬似乱数生成器
• 数値実験の再現性: 同じ種と設定からは同じ結果が出る、という約束です。→ 数値実験
• 指数分布と Poisson 過程: 故障が起こるまでの時間が、それまでの経過によらず同じ確率で決まる、という故障のモデルです（対象読者の前提とする確率論の初歩です）。
• ベイズの定理と全確率の公式: 条件付き確率を、場合分けして足し合わせたり、条件の向きを入れ替えたりする計算です。第 5 節で使います。
• 1 次収束・2 次収束: 反復のたびに誤差が一定の比で小さくなるものを 1 次収束、誤差が 2 乗になるものを 2 次収束といいます。第 6 節で使います。

1. 動機

1 時間で終わる計算は、失敗したらやり直せば済みます。3 日かかる計算はそうはいきません。共用の計算機には時間制限があり、ノードは落ち、停電があり、自分のノート PC はスリープします。3 日のうち 2 日と 23 時間まで進んだところで止まり、最初からやり直す、というのは誰もが一度は経験する失敗です。

対策は途中の状態を保存しておくこと（チェックポイント）ですが、これには 3 つの問いが付いてきます。第一に、再開した計算は、中断しなかった場合と同じ結果を出すのか。同じでなければ、結果は「どこで止まったか」という記録に残らない偶然に依存することになり、再現できる数値実験の章で立てた「結果は種と設定の関数である」という約束が壊れます。第二に、どのくらいの間隔で保存すればよいか。頻繁に保存すれば保存の時間が無駄になり、まれにしか保存しなければ故障のたびに失う仕事が増えます。第三に、打ち切られた計算をどう数えるか。時間切れの試行を黙って捨てると、集計が偏ります。

この章では、3 つの問いにそれぞれ命題で答えます。第一の問いには状態機械としての定式化と帰納法、第二の問いには指数分布の計算と微分、第三の問いには条件付き確率の計算を使います。

2. ジョブを状態機械とみる

定義 2.1（ジョブ）↗

ジョブとは、集合 $S$（状態の集合）、初期状態 $s_0 \in S$、写像 $T : S \to S$（1 ステップの遷移）、部分集合 $D \subset S$（終了状態の集合）の組である。$s_{k+1} = T(s_k)$ で定まる列 $s_0, s_1, s_2, \ldots$ を軌道という。$s_k \in D$ となる最小の $k$ が存在するとき、それを $N$ と書き、$s_N$ をジョブの結果という。

状態には、計算を続けるのに必要なものをすべて含めます。反復番号、それまでの計算結果の配列、そして乱数生成器の状態です。擬似乱数生成器はそれ自体が状態機械（定義 5.1［再現できる数値実験］）なので、その状態をジョブの状態の成分に含めれば、乱数を消費する遷移も「状態だけで決まる写像 $T$」の形に書けます。終了条件（反復回数に達した、収束判定を満たした、打ち切りの条件に達した）は $D$ で表します。

次の定義は、計算を「メモリ上の作業中の状態」と「ディスクに残した保存」の 2 つの置き場に分けて整理します。メモリの中身は中断で消えますが、保存したものは残ります。再開したとき、どちらから何を読み戻すかを正確に言うための準備です。

定義 2.2（チェックポイントと中断のある実行）↗

保存域は、各時点で $S \cup \{\bot\}$ の元 $c$ を 1 つ保持する（$\bot$ は「まだ何も保存されていない」ことを表す）。実行中のプロセスはメモリ上に状態 $m \in S$ をもち、次の操作を行う。

• 開始・再開: $c \ne \bot$ なら $m \leftarrow c$、$c = \bot$ なら $m \leftarrow s_0$ とする。
• ステップ: $m \notin D$ のとき $m \leftarrow T(m)$ とする。
• 保存（チェックポイント）: $c \leftarrow m$ とする。いつ保存するかは任意である。
• 中断: メモリ上の $m$ が失われる。その後、再開から続ける。中断はどの時点でも（ステップや保存の途中でも）起こりうる。

$m \in D$ になったら、$m$ を結果として返して終わる。次の 2 つの性質を考える。

• 完全性: 保存されるのは状態 $m$ の全体で、再開で読み戻される値は保存された $m$ そのものである。
• 原子性: 保存の途中で中断が起きても、その後の保存域の値は、保存の前の値か、保存しようとした $m$ のどちらかである。

原子性は、ファイルでは「一時ファイルに全部を書き、書き終えてから改名で置き換える」ことで実現します。同じファイルシステムの中の改名は、POSIX では 1 回の操作として行われ、途中の状態が外から見えません。Python では os.replace がこれに当たります。既存のファイルを直接上書きすると、書きかけの時点で中断したときに、古い内容と新しい内容が混ざったファイルが残ります。

3. 再開しても結果が変わらない条件

定理 3.1（再開の同値性）✓

結果 $s_N$ をもつジョブ（定義 2.1）を、定義 2.2 の操作で実行する。遷移 $T$ が状態だけで決まる写像であり（決定性）、保存が完全性と原子性を満たすならば、中断が何回、どの時点で起きても、実行が終わったときに返される結果は $s_N$ である。

証明の方針です。中断のない実行がたどる状態を「正しい状態」と呼ぶことにします。どんな操作の後でも、保存域にもメモリにも正しい状態しか入らないことを、操作の回数についての帰納法で示します。そうすれば、終了状態に着いたとき、それは正しい状態の中の終了状態、つまり $s_N$ しかありえません。

証明（定理 3.1）

$O = \{s_0, s_1, \ldots, s_N\}$ を、中断のない実行がたどる状態の集合とします。$N$ の定義から $s_0, \ldots, s_{N-1} \notin D$、$s_N \in D$ なので $O \cap D = \{s_N\}$ です。

実行は操作（開始・再開、ステップ、保存、中断）の有限列です。操作の回数についての帰納法で、次の不変条件を示します。

不変条件: 各操作の後で、保存域の値は $c \in O \cup \{\bot\}$ を満たし、プロセスが動いていればメモリ上の状態は $m \in O$ を満たす。

最初の操作は開始で、$c = \bot$ なので $m = s_0 \in O$ です。以下、ある操作の前に不変条件が成り立つとして、操作の後を調べます。

• 再開. $c \ne \bot$ なら、完全性から $m$ は $c$ そのもので、帰納法の仮定から $c \in O$ です。$c = \bot$ なら $m = s_0 \in O$ です。$c$ は変わりません。
• ステップ. ステップが行われるのは $m \notin D$ のときです。$m \in O$ かつ $m \notin D$ なので、ある $k \lt N$ について $m = s_k$ です。$T$ は状態だけで決まるので、新しい状態は $T(s_k) = s_{k+1} \in O$ です。$c$ は変わりません。
• 保存. 最後まで行われれば $c = m \in O$ です。途中で中断されても、原子性から $c$ は前の値（$O \cup \{\bot\}$ の元）か $m$（$O$ の元）です。
• 中断. メモリ上の状態が失われるだけで、$c$ は（保存の途中だった場合を上で扱ったので）$O \cup \{\bot\}$ の元のままです。

実行が終わるのは $m \in D$ となったときで、不変条件から $m \in O \cap D = \{s_N\}$ です。この議論は中断の回数にも時点にもよりません。

∎

定理が言っているのは、再開のたびに「軌道の上のどこか」に戻り、そこから同じ軌道をたどり直す、ということだけです。証明が使った 3 つの仮定は、それぞれ実務でよく破れます。

例 3.2（仮定を 1 つずつ落とした 3 つの反例）

ステップ $k$ で値 $v_k$ を受け取って和 $a$ に足すジョブを考えます。状態は $(k, a, r)$ で、$r$ は $v_k$ を作る生成器の状態、遷移は $T(k, a, r) = (k + 1,\ a + g(r),\ \theta(r))$、$N = 4$ で終わるとします。生成器の出力列を $g(r_0), g(r_1), g(r_2), g(r_3) = 1, 2, 4, 8$ とすると、中断のない実行の結果は $a = 15$ です。

(i) 完全性の破れ：生成器の状態を保存しない。 $(k, a)$ だけを保存し、再開のときに生成器を種から作り直すとします。$k = 2$ の後で保存して中断すると、再開後の状態は $(2, 3, r_0)$ で、これは軌道の上の状態 $(2, 3, r_2)$ ではありません。残りの 2 ステップで足されるのは $g(r_0) + g(r_1) = 1 + 2$ で、結果は $a = 6$ です。保存したデータからは遷移が決まらないので、定理の証明の「ステップ」の段が成り立ちません。Monte Carlo 法では、同じ乱数を 2 回使うことになり、標本が独立でなくなります。

(ii) 原子性の破れ：書きかけのファイル。 $k$ と $a$ を 1 つのファイルに順に上書きするとします。保存域の値が $(2, 3, r_2)$ のとき、$(3, 7, r_3)$ を保存しようとして $k$ を書いた直後に中断すると、ファイルには $(3, 3, r_2)$ が残ります。これは軌道の上にありません。再開すると $3 + 4 = 7$ で終わり、結果は $15$ になりません。ファイルの末尾が欠けて読み込みに失敗するならまだ気づけますが、この例のように読めてしまう場合が危険です。

(iii) 状態の外への書き込み：追記の重複。 各ステップで $v_k$ を別のファイルに 1 行ずつ追記し、和は後でそのファイルから計算するとします。$k = 2$ で保存し、$k = 3$ のステップの後（追記の後）で中断すると、再開後に $k = 3$ のステップがもう一度行われ、ファイルには $1, 2, 4, 4, 8$ の 5 行が並びます。和は $19$ です。追記されたファイルは保存域と同期していないので、ジョブの状態の一部になっていません。定理は状態 $m$ についての主張で、状態の外に出た副作用については何も保証しません。

(iii) への対処は 2 つあります。出力を状態の中に含めてチェックポイントと一緒に保存するか、出力の各行にキー（ステップ番号）を付けて、同じキーを 2 回書いても結果が変わらないようにするかです。後者を一般的な形で述べます。

次の命題が言っているのは、身近な言い方をすると、「結果を保存するファイルの名前を、その計算の入力で決めておく。ファイルがあれば読み、なければ計算して書く。こうしておけば、同じ計算が 2 回頼まれても、途中で止まっても、最後にできるファイルの集まりは同じになる」ということです。以下の「キー」はそのファイル名、「表」はファイル名と中身の対応のことです。

命題 3.3（キーつきの保存による冪等性）✓

$K$ をキーの集合、$f : K \to V$ を写像とする。保存域は $K$ から $V$ への部分写像 $\sigma$（有限個のキーに値が対応している表）を保持し、1 件の書き込みは原子的（表に入るか、まったく入らないか）とする。キー $\kappa \in K$ に対する操作 $\mathrm{step}(\kappa)$ を、「$\kappa$ が $\sigma$ の定義域にあれば $\sigma(\kappa)$ を返す。なければ $v = f(\kappa)$ を計算し、$(\kappa, v)$ を表に書き込んで $v$ を返す」と定める。最初の表 $\sigma_0$ が、定義域の上で $f$ と一致するとする。このとき、$\mathrm{step}(\kappa_1), \ldots, \mathrm{step}(\kappa_n)$ をどんな順序で、同じキーを何回繰り返して、またどの操作が途中で中断されても、次が成り立つ。

1. 表はつねに定義域の上で $f$ と一致し、最後まで行われた $\mathrm{step}(\kappa)$ は $f(\kappa)$ を返す。
2. すべての操作が少なくとも 1 回ずつ最後まで行われた後の表は、定義域が $\mathrm{dom}\,\sigma_0 \cup \{\kappa_1, \ldots, \kappa_n\}$ で、その上で $f$ と一致する表であり、順序と繰り返しの回数によらない。とくに $\mathrm{step}(\kappa)$ を 2 回続けて行った後の表は、1 回行った後の表と同じである（冪等性）。

証明（命題 3.3）

1. 操作の回数についての帰納法で「表は定義域の上で $f$ と一致する」を示します。最初は仮定です。$\mathrm{step}(\kappa)$ の前に成り立つとします。$\kappa$ が定義域にあれば表は変わらず、返る値は $\sigma(\kappa) = f(\kappa)$ です。なければ、書き込まれるのは $(\kappa, f(\kappa))$ で、書き込みは原子的なので、表は変わらないか、$\kappa$ に $f(\kappa)$ を対応させる 1 件が加わるかのどちらかです。どちらでも表は $f$ と一致したままで、最後まで行われれば返る値は $f(\kappa)$ です。

2. 表から対応が消える操作はないので、定義域は増えるだけです。$\mathrm{step}(\kappa)$ が最後まで行われた後は $\kappa$ が定義域に入っているので、最終的な定義域は $\mathrm{dom}\,\sigma_0 \cup \{\kappa_1, \ldots, \kappa_n\}$ を含みます。定義域に加わるのは操作されたキーだけなので、等号が成り立ちます。1 から、その上で表は $f$ と一致します。定義域と値がともに順序と回数によらないので、表そのものがよりません。同じキーの 2 回目の操作は、$\kappa$ がすでに定義域にあるので表を変えません。

∎

分散処理では、仕事が「少なくとも 1 回」実行されること（at-least-once）までは保証しやすい一方、「ちょうど 1 回」は保証しにくいことが知られています。応答が返る前に通信が切れると、呼び出した側は仕事が済んだのかどうかを区別できず、もう一度頼むしかないからです。命題は、操作を冪等にしておけば「少なくとも 1 回」で足りることを言っています。Kubernetes の調整ループが、通知を取りこぼしても重複して受け取っても同じ状態に収束する（命題 6.2［Docker と Kubernetes］）のも同じ考え方です。

命題の仮定で大事なのは、$f$ がキーだけで決まる写像であることです。パラメータの掃引なら、キーは「掃引の番号」ではなく「その点の計算結果を決めるものすべて」、すなわち設定・入力・コードの版・乱数種でなければなりません。実務では、これらをまとめたもののハッシュ値をキー（ファイル名）にします。内容アドレス格納庫（定義 2.1［バージョン管理システム Git］）と同じ発想で、異なる入力が同じキーになる確率は 再現性の章の衝突確率の評価（命題 4.1［再現できる数値実験］）で抑えられます。キーに入れ忘れた要素（たとえばコードの版）があると、古い結果が黙って再利用されます。命題の仮定「最初の表が $f$ と一致する」が破れた状態です。

例 3.4（再開できる反復の雛形と、中断・再開の実験）

標準正規乱数を 1 ステップに 1000 個ずつ引き、和と 2 乗和を累積する計算を 1000 ステップ行います。100 ステップごとにチェックポイントを取り、250 ステップ目と 777 ステップ目の直前で中断を模擬します（どちらもチェックポイントの間です）。

# Python 3.12.14 / NumPy 2.5.2
import hashlib, json, os
import numpy as np

def config_hash(cfg):
    return hashlib.sha256(json.dumps(cfg, sort_keys=True).encode()).hexdigest()

def save(path, k, acc, rng, cfg):
    tmp = path + ".tmp"
    with open(tmp, "wb") as f:                       # 一時ファイルに全部書いてから
        np.savez(f, k=k, acc=acc, cfg=config_hash(cfg),
                 rng=json.dumps(rng.bit_generator.state))
        f.flush()
        os.fsync(f.fileno())
    os.replace(tmp, path)                            # 改名で置き換える（原子的）

def load(path, cfg, restore_rng):
    rng = np.random.default_rng(cfg["seed"])
    if not os.path.exists(path):
        return 0, np.zeros(2), rng                   # 初期状態
    with np.load(path) as z:
        if str(z["cfg"]) != config_hash(cfg):
            raise RuntimeError("チェックポイントの設定が現在の設定と一致しない")
        k, acc = int(z["k"]), z["acc"].copy()
        if restore_rng:
            rng.bit_generator.state = json.loads(str(z["rng"]))
    return k, acc, rng

def run(path, cfg, stop_at=None, restore_rng=True, log=None):
    k, acc, rng = load(path, cfg, restore_rng)
    while k < cfg["steps"]:
        if k == stop_at:
            raise KeyboardInterrupt                  # 中断の模擬
        x = rng.standard_normal(cfg["batch"])        # 1 ステップ: 乱数を消費して累積
        acc += (x.sum(), (x * x).sum())
        k += 1
        if log:
            with open(log, "a") as f:                # 状態の外への追記（わざと残した欠陥）
                f.write(f"{k}\n")
        if k % cfg["every"] == 0:
            save(path, k, acc, rng, cfg)
    return acc

def interrupted(path, cfg, stops, **kw):
    for s in stops:                                  # stops の各時点で 1 回ずつ中断する
        try:
            run(path, cfg, stop_at=s, **kw)
        except KeyboardInterrupt:
            pass
    return run(path, cfg, **kw)

if __name__ == "__main__":
    cfg = {"seed": 20261008, "steps": 1000, "batch": 1000, "every": 100}
    for name in ("a.npz", "b.npz", "c.npz", "b.log"):
        if os.path.exists(name):
            os.remove(name)
    ref = run("a.npz", cfg)
    good = interrupted("b.npz", cfg, stops=[250, 777], log="b.log")
    bad = interrupted("c.npz", cfg, stops=[250, 777], restore_rng=False)
    print("中断なし            :", ref[0].hex(), ref[1].hex())
    print("中断 2 回・状態を復元:", good[0].hex(), good[1].hex(), " 一致:", ref.tobytes() == good.tobytes())
    print("中断 2 回・種から再開:", bad[0].hex(), bad[1].hex(), " 一致:", ref.tobytes() == bad.tobytes())
    ks = [int(s) for s in open("b.log")]
    print(f"ログの行数 = {len(ks)},  相異なる番号 = {len(set(ks))},  重複 = {len(ks) - len(set(ks))}")
    try:
        run("b.npz", dict(cfg, batch=2000))
    except RuntimeError as e:
        print("設定を変えて再開:", e)

中断なし            : 0x1.a0ca4517110dap+9 0x1.e7adea6c1c0c3p+19
中断 2 回・状態を復元: 0x1.a0ca4517110dap+9 0x1.e7adea6c1c0c3p+19  一致: True
中断 2 回・種から再開: -0x1.8fad4560692c2p+10 0x1.e8692cbb60c92p+19  一致: False
ログの行数 = 1127,  相異なる番号 = 1000,  重複 = 127
設定を変えて再開: チェックポイントの設定が現在の設定と一致しない

検算. (a) 生成器の状態（bit_generator.state）を保存して復元した実行は、2 回の中断をはさんでも、中断なしの実行とビット単位で一致します（定理 3.1）。(b) 生成器を種から作り直した実行は一致しません（例 3.2 の (i)）。2 乗和は $10^6$ 個の標準正規乱数について期待値 $10^6 = 2^{19.93}$ の近くにあり、どちらの値ももっともらしく見えるので、結果を眺めても誤りには気づけません。(c) 状態の外に追記したログは 1127 行で、重複は $127 = 50 + 77$ 行です。これは中断で失われて再実行されたステップの数（$250 - 200$ と $777 - 700$）に一致します（同じ例の (iii)）。番号をキーにして重複を除けば 1000 件です。(d) 設定のハッシュが違うチェックポイントからの再開は、例外で止まります。これがないと、設定を変えた計算が古いチェックポイントの続きとして走ります。

雛形の要点は 4 つです。状態（反復番号・累積した配列・生成器の状態）を 1 つのファイルにまとめること、一時ファイルに書いて os.replace で置き換えること、設定のハッシュを一緒に保存して再開のときに照合すること、開始と再開を同じ関数 load にして「チェックポイントがなければ初期状態」とすることです。最後の点は見落とされがちです。開始と再開が別の経路だと、再開の経路は故障したときにしか実行されず、テストされないまま残ります。

4. 故障のモデルとチェックポイントの間隔

4.1. 1 区間を終えるまでの期待時間

チェックポイントの間隔を決めるには、故障の起こり方のモデルが要ります。最も単純で、解析できるモデルは次のものです。

定義 4.1（故障の Poisson モデル）↗

$\lambda \gt 0$ とし、$\mu = 1/\lambda$ とおく。ジョブが計算またはチェックポイントの書き込みをしている時間（稼働時間）の軸の上で、故障は強度 $\lambda$ の Poisson 過程（定義 4.1［Markov 連鎖と Poisson 過程］）の到着時刻に起こるとする。すなわち、$i$ 回目に動き始めてから故障するまでの稼働時間 $X_i$（$i = 1, 2, \ldots$）は独立で、どれも指数分布 $\mathrm{Exp}(\lambda)$（密度 $\lambda e^{-\lambda x}$、$x \gt 0$）に従う。故障が起こると、最後に完了したチェックポイントより後の仕事は失われ、再起動に時間 $R \ge 0$ がかかる。再起動の間は故障しないとする。

仕事 $\tau \gt 0$ とチェックポイントの書き込み $C \ge 0$ をひと続きにしたものを 1 区間といい、$a = \tau + C$ とおく。1 区間は、稼働時間 $a$ を故障なしで続けたときに完了する。$K = \min\{k \ge 1 : X_k \ge a\}$（初めて成功する試みの番号）とおくと、1 区間を完了するまでの時間は

$$T_{\mathrm{seg}} = \sum_{k=1}^{K-1}(X_k + R) + a$$

である。

$\mu$ は故障間隔の平均です。指数分布を仮定するのは、故障が「それまで何時間動いていたか」によらずに起こる（無記憶性）という状況を表すためです。部品の初期不良や経年劣化のように故障率が時間とともに変わる場合は、このモデルの外です。

チェックポイントと故障。3 つ目の区間の途中で故障が起こると、直前のチェックポイント以降の仕事（破線）が失われ、再起動 R の後で同じ区間をやり直す。

定理 4.2（故障があるときの 1 区間の期待時間）✓

定義 4.1 のモデルで、1 区間を完了するまでの時間の期待値は

$$E[T_{\mathrm{seg}}] = \Bigl(\frac1\lambda + R\Bigr)\bigl(e^{\lambda(\tau + C)} - 1\bigr)$$

である。

証明の方針です。故障して失敗する試みの回数 $K - 1$ は、成功確率 $e^{-\lambda a}$ の試行を成功するまで繰り返す回数と同じ型なので、失敗した試みごとの損（故障までの時間と再起動 $R$）の期待値を計算し、失敗の回数についての等比級数として足し合わせます。途中の独立性の確認の段落は、「$k$ 回目より前にすべて失敗した」ことと「$k$ 回目の試みの結果」が無関係であることを丁寧に確かめているだけで、読み飛ばしても式の流れは追えます。

証明（定理 4.2）

$X$ を $\mathrm{Exp}(\lambda)$ に従う確率変数、$q = e^{-\lambda a}$ とします。まず 2 つの量を計算します。連続型の計算公式（系 4.6［確率変数と期待値］ の 2）から

$$P(X \lt a) = \int_0^a\lambda e^{-\lambda x}\,dx = \bigl[-e^{-\lambda x}\bigr]_0^a = 1 - q$$

で、部分積分（定理 6.2［積分の基本定理と定積分］。$u(x) = x$、$v(x) = -e^{-\lambda x}$）から

$$E\bigl[X\mathbf{1}_{\{X \lt a\}}\bigr] = \int_0^a x\lambda e^{-\lambda x}\,dx = \bigl[-xe^{-\lambda x}\bigr]_0^a + \int_0^a e^{-\lambda x}\,dx = -aq + \frac{1 - q}{\lambda}$$

です。したがって $m_a := E\bigl[(X + R)\mathbf{1}_{\{X \lt a\}}\bigr] = -aq + \bigl(\frac1\lambda + R\bigr)(1 - q)$ です。

次に $T_{\mathrm{seg}}$ を書き直します。$K \gt k$ は「最初の $k$ 回の試みがすべて失敗した」こと、つまり事象 $A_k = \{X_1 \lt a, \ldots, X_k \lt a\}$ と同じなので

$$T_{\mathrm{seg}} = a + \sum_{k=1}^{\infty}Z_k, \qquad Z_k = (X_k + R)\mathbf{1}_{A_k} \ge 0$$

です。右辺の部分和は非負の項の和で単調に増えるので、単調収束定理（定理 2.1［確率変数と期待値］）と期待値の線形性から $E[T_{\mathrm{seg}}] = a + \sum_{k=1}^\infty E[Z_k]$ です。

$E[Z_k]$ を求めます。$U = \mathbf{1}_{A_{k-1}}$（$k = 1$ のときは $U = 1$）、$V = (X_k + R)\mathbf{1}_{\{X_k \lt a\}}$ とおくと $Z_k = UV$ です。$U$ と $V$ は独立です。実際、$V$ は $X_k$ のボレル可測な関数なので、ボレル集合 $B'$ について $\{V \in B'\} = \{X_k \in B''\}$ となるボレル集合 $B''$ があり、$X_1, \ldots, X_k$ の独立性（定義 2.3［確率変数と期待値］）から

$$P\bigl(A_{k-1} \cap \{X_k \in B''\}\bigr) = \prod_{i=1}^{k-1}P(X_i \lt a)\cdot P(X_k \in B'') = P(A_{k-1})\,P(X_k \in B'')$$

です。$U$ は $A_{k-1}$ の上で $1$、補集合の上で $0$ なので、$\{U \in B\}$ は $\emptyset$、$\Omega$、$A_{k-1}$、$A_{k-1}^{c}$ のどれかで、$A_{k-1}^{c}$ についても $P(A_{k-1}^{c} \cap E) = P(E) - P(A_{k-1} \cap E) = P(A_{k-1}^{c})P(E)$（$E = \{X_k \in B''\}$）から積の形になります。同じ式で $B'' = \mathbb{R}$ とすると $E[U] = P(A_{k-1}) = (1 - q)^{k-1}$ です。$U$ は有界、$V$ は $0 \le V \le a + R$ で有界なので可積分で、独立な確率変数の積の期待値（命題 7.5［確率変数と期待値］）から

$$E[Z_k] = E[U]\,E[V] = (1 - q)^{k-1}m_a$$

です。$0 \le 1 - q \lt 1$ なので等比級数（命題 3.6［級数と収束判定］）から $\sum_{k=1}^\infty(1 - q)^{k-1} = 1/q$ で、

$$E[T_{\mathrm{seg}}] = a + \frac{m_a}{q} = a - a + \Bigl(\frac1\lambda + R\Bigr)\frac{1 - q}{q} = \Bigl(\frac1\lambda + R\Bigr)\bigl(e^{\lambda a} - 1\bigr)$$

です。$a = \tau + C$ を戻して主張を得ます。

∎

式の形から読み取れることを 2 つ挙げます。第一に、期待時間は区間の長さ $a$ について指数関数的に増えます。$a = \mu$ では $e^{\lambda a} - 1 = e - 1 \approx 1.7$ で、期待時間は $\mu$（$= a$）の $1.7$ 倍（に $R$ の分を加えた時間）です。$a = 3\mu$ では $e^{3} - 1 \approx 19$ で、$\mu$ の $19$ 倍、区間の長さ $a$ の約 $6.4$ 倍になります。チェックポイントなしで平均故障間隔より長い計算を走らせるのは、ほぼ終わらない賭けです。第二に、$\lambda a$ が小さいとき、$e^{\lambda a} - 1 \approx \lambda a + (\lambda a)^2/2$ から $E[T_{\mathrm{seg}}] \approx a + a^2/(2\mu) + Ra/\mu$ です。$a/\mu$ は区間の中で故障が起こる確率のおよその値、$a/2$ はそのとき失う仕事の平均、$R$ は再起動の時間、と読めます。

4.2. 最適な間隔

仕事の総量 $W_{\mathrm{tot}}$ を長さ $\tau$ の $n = W_{\mathrm{tot}}/\tau$ 個の区間に分けると、期待値の線形性から、完了までの期待時間は $nE[T_{\mathrm{seg}}] = W_{\mathrm{tot}}\,h(\tau)$ です。ここで

$$h(\tau) = \frac{E[T_{\mathrm{seg}}]}{\tau} = \Bigl(\frac1\lambda + R\Bigr)\frac{e^{\lambda(\tau + C)} - 1}{\tau}$$

は仕事 1 単位あたりの期待時間で、$h(\tau) - 1$ が無駄の割合です。上の近似を使うと $h(\tau) - 1 \approx C/\tau + \tau/(2\mu)$（に $\tau$ によらない項を加えたもの）で、第 1 項はチェックポイントの書き込みの無駄、第 2 項は故障で失う仕事の無駄です。2 つの和は $\tau = \sqrt{2C\mu}$ で最小になります。これが Young の近似です。近似を使わない形で述べます。

C = 1 分、μ = 1440 分の場合の無駄の割合（%）。保存の無駄 C/τ（下がる曲線）と、故障で失う仕事の無駄 τ/(2μ)（上がる直線）の和は、τ = √(2Cμ) ≈ 54 分で最小になる。

定理 4.3（最適なチェックポイント間隔（Young の近似））✓

$\lambda \gt 0$、$\mu = 1/\lambda$、$C \gt 0$、$R \ge 0$ とする。$h(\tau)$（$\tau \gt 0$）について次が成り立つ。

1. $h$ はただ 1 点 $\tau^{*}$ で最小値をとる。$\tau^{*}$ は $0 \lt \tau \lt \mu$ の範囲での方程式 $(1 - \lambda\tau)e^{\lambda(\tau + C)} = 1$ のただ 1 つの解で、$R$ によらない。$h$ は $(0, \tau^{*}]$ で狭義単調減少、$[\tau^{*}, \infty)$ で狭義単調増加である。
2. $\tau^{*} \le \sqrt{2C\mu}$。さらに $2C \le \mu$ ならば $$\sqrt{2C\mu} - 2C \le \tau^{*} \le \sqrt{2C\mu}.$$

証明の方針です。$h$ の導関数の符号を調べると、$1 - (1 - \lambda\tau)e^{\lambda(\tau+C)}$ の符号に帰着します。この式を扱いやすくするために、$x = \lambda\tau$ とおいて対数をとったときに現れる $g(x) = -\ln(1 - x) - x$ を最初に用意します。$g$ が増加関数であることから、符号が変わる点がただ 1 つであることが分かります。2 の不等式は、$g$ を $x^2/2$ で上下から挟んで得ます。

証明（定理 4.3）

$c = \lambda C \gt 0$ とおき、$0 \le x \lt 1$ で $g(x) = -\ln(1 - x) - x$ を考えます。$g(0) = 0$ で、$g'(x) = \frac{1}{1-x} - 1 = \frac{x}{1-x}$ は $0 \lt x \lt 1$ で正なので、$g$ は $[0, 1)$ で狭義単調増加です（系 3.4［平均値の定理とテイラーの定理］ の 3）。$x_1 = 1 - e^{-(c+1)}$ とすると $g(x_1) = (c + 1) - x_1 \gt c$ で、$g(0) = 0 \lt c$ なので、中間値の定理（定理 5.7［極限と連続性］）から $g(x^{*}) = c$ となる $x^{*} \in (0, x_1)$ があり、狭義単調性からただ 1 つです。$0 \lt x \lt x^{*}$ で $g(x) \lt c$、$x^{*} \lt x \lt 1$ で $g(x) \gt c$ です。

1. $A = \frac1\lambda + R \gt 0$ とおくと $h(\tau) = A(e^{\lambda(\tau + C)} - 1)/\tau$ で、商の微分から

   $$h'(\tau) = A\,\frac{\lambda\tau e^{\lambda(\tau + C)} - e^{\lambda(\tau + C)} + 1}{\tau^2} = \frac{A}{\tau^2}\bigl(1 - \varphi(\tau)\bigr), \qquad \varphi(\tau) = (1 - \lambda\tau)e^{\lambda(\tau + C)}$$

   です。$\tau \ge \mu$ では $1 - \lambda\tau \le 0$ なので $\varphi(\tau) \le 0 \lt 1$ で $h'(\tau) \gt 0$ です。$0 \lt \tau \lt \mu$ では $x = \lambda\tau \in (0, 1)$ とおくと $\varphi(\tau) \gt 0$ で、対数をとると

   $$\varphi(\tau) \gt 1 \iff \ln(1 - x) + x + c \gt 0 \iff g(x) \lt c \iff x \lt x^{*}$$

   です。同様に $\varphi(\tau) = 1 \iff x = x^{*}$、$\varphi(\tau) \lt 1 \iff x \gt x^{*}$ です。$\tau^{*} = x^{*}/\lambda$ とおくと、$h'$ は $(0, \tau^{*})$ で負、$(\tau^{*}, \infty)$ で正なので、系 3.4［平均値の定理とテイラーの定理］ の 3（と、それを $-h$ に使ったもの）から単調性の主張を得て、$\tau^{*}$ がただ 1 つの最小点です。$\tau^{*}$ を決める方程式 $\varphi(\tau) = 1$ に $R$ は現れません。

2. $0 \le x \lt 1$ で次の 2 つの不等式を示します。

   $$\frac{x^2}{2} \le g(x) \le \frac{x^2}{2(1 - x)}.$$

   左: $d(x) = g(x) - x^2/2$ は $d(0) = 0$、$d'(x) = \frac{x}{1-x} - x = \frac{x^2}{1-x} \ge 0$ なので、系 3.4［平均値の定理とテイラーの定理］ の 2 から広義単調増加で $d(x) \ge 0$ です。右: $D(x) = \frac{x^2}{2(1-x)} - g(x)$ は $D(0) = 0$ で、

   $$D'(x) = \frac{2x(1 - x) + x^2}{2(1 - x)^2} - \frac{x}{1 - x} = \frac{2x - x^2 - 2x(1 - x)}{2(1 - x)^2} = \frac{x^2}{2(1 - x)^2} \ge 0$$

   なので同じく $D(x) \ge 0$ です。

   $x = x^{*}$ とします。左の不等式から $(x^{*})^2/2 \le g(x^{*}) = c$ で、$x^{*} \le \sqrt{2c}$ です。$\tau^{*} = x^{*}/\lambda = \mu x^{*}$、$\mu\sqrt{2c} = \mu\sqrt{2C/\mu} = \sqrt{2C\mu}$ なので $\tau^{*} \le \sqrt{2C\mu}$ です。

   $2C \le \mu$、すなわち $\sqrt{2c} \le 1$ とします。右の不等式から $c \le (x^{*})^2/\bigl(2(1 - x^{*})\bigr)$ で、$x^{*} \le \sqrt{2c}$ を使うと

   $$(x^{*})^2 \ge 2c(1 - x^{*}) \ge 2c\bigl(1 - \sqrt{2c}\bigr) \ge 0$$

   です。$0 \le t \le 1$ で $\sqrt{1 - t} \ge 1 - t$（$0 \le 1 - t \le 1$ の数は平方すると小さくなるので）だから、$x^{*} \ge \sqrt{2c}\sqrt{1 - \sqrt{2c}} \ge \sqrt{2c}\bigl(1 - \sqrt{2c}\bigr) = \sqrt{2c} - 2c$ です。$\mu$ を掛けて $\tau^{*} \ge \sqrt{2C\mu} - 2C$ です。

∎

定理の 2 は「$\tau^{*} = \sqrt{2C\mu} + O(C)$」という Young の近似の、誤差項に具体的な定数を付けた形です。$C$ が $\mu$ に比べて小さいとき、$2C$ は $\sqrt{2C\mu}$ に比べて小さく（比は $\sqrt{2C/\mu}$）、$\sqrt{2C\mu}$ をそのまま使って差し支えありません。最適な間隔が再起動の時間 $R$ によらないことも実用上は便利です。Daly は、同種のモデルで高次の補正項を含む近似式を与えています（参考文献）。

例 4.4（C = 1 分、μ = 1 日の場合と、故障の模擬実験）

チェックポイントの書き込みに $C = 1$ 分、平均故障間隔 $\mu = 1440$ 分（1 日）、再起動に $R = 5$ 分かかるとします。$\sqrt{2C\mu} = \sqrt{2880} \approx 53.7$ 分で、定理 4.3 から $51.7 \le \tau^{*} \le 53.7$ です。およそ 54 分に 1 回の保存が最適、ということになります。

故障を指数分布の乱数で模擬し、仕事の総量 $10080$ 分（7 日分）を間隔 $\tau$ で区切って完了するまでの時間を $10^4$ 回ずつ測って、定理 4.2 の式と比べます。

# Python 3.12.14 / NumPy 2.5.2
import math
import numpy as np

C, R, MU = 1.0, 5.0, 1440.0          # チェックポイント 1 分、再起動 5 分、故障間隔の平均 1 日
LAM = 1.0 / MU
WORK = 10080.0                       # 仕事の総量 = 7 日分
TRIALS = 10_000

def expected_segment(tau):           # 1 区間の期待時間 (1/λ + R)(e^{λ(τ+C)} - 1)
    return (MU + R) * math.expm1(LAM * (tau + C))

def simulate(tau, rng):
    """仕事 WORK を区間 tau に分けて完了するまでの時間（TRIALS 本）"""
    a = tau + C
    total = np.zeros(TRIALS)
    for _ in range(round(WORK / tau)):
        todo = np.arange(TRIALS)                 # この区間をまだ終えていない試行
        while todo.size:
            x = rng.exponential(MU, size=todo.size)   # 次の故障までの時間
            ok = x >= a
            total[todo[ok]] += a
            total[todo[~ok]] += x[~ok] + R
            todo = todo[~ok]
    return total

rng = np.random.default_rng(20261008)
print("   τ   区間数  理論 E/τ    模擬の平均   標準誤差   (模擬-理論)/標準誤差")
for tau in (12, 24, 36, 48, 56, 72, 96, 144, 240):
    t = simulate(tau, rng) / WORK
    theory = expected_segment(tau) / tau
    se = t.std(ddof=1) / math.sqrt(TRIALS)
    print(f"{tau:4d}  {round(WORK / tau):5d}   {theory:.5f}    {t.mean():.5f}    {se:.5f}   {(t.mean() - theory) / se:+.2f}")

# 最適な間隔: (1 - λτ) e^{λ(τ+C)} = 1 の解を二分法で求める
lo, hi = 0.0, MU
for _ in range(200):
    mid = (lo + hi) / 2
    if (1 - LAM * mid) * math.exp(LAM * (mid + C)) > 1:
        lo = mid
    else:
        hi = mid
tau_star, young = lo, math.sqrt(2 * C * MU)
print(f"τ* = {tau_star:.3f},  √(2Cμ) = {young:.3f},  √(2Cμ) - 2C = {young - 2 * C:.3f}")
h = lambda tau: expected_segment(tau) / tau
for name, tau in (("τ*/2", tau_star / 2), ("τ*", tau_star), ("2τ*", 2 * tau_star), ("√(2Cμ)", young)):
    print(f"  τ = {name:7s} = {tau:7.2f}:  E/τ - 1 = {100 * (h(tau) - 1):.3f} %")

   τ   区間数  理論 E/τ    模擬の平均   標準誤差   (模擬-理論)/標準誤差
  12    840   1.09202    1.09207    0.00003   +1.75
  24    420   1.05441    1.05442    0.00005   +0.27
  36    280   1.04471    1.04468    0.00007   -0.44
  48    210   1.04201    1.04203    0.00009   +0.28
  56    180   1.04188    1.04185    0.00010   -0.24
  72    140   1.04364    1.04351    0.00013   -1.04
  96    105   1.04885    1.04889    0.00017   +0.21
 144     70   1.06307    1.06258    0.00024   -1.98
 240     42   1.09688    1.09714    0.00041   +0.63
τ* = 53.001,  √(2Cμ) = 53.666,  √(2Cμ) - 2C = 51.666
  τ = τ*/2    =   26.50:  E/τ - 1 = 5.135 %
  τ = τ*      =   53.00:  E/τ - 1 = 4.182 %
  τ = 2τ*     =  106.00:  E/τ - 1 = 5.152 %
  τ = √(2Cμ)  =   53.67:  E/τ - 1 = 4.182 %

検算. (a) 模擬の平均は、9 通りの $\tau$ のすべてで理論値と標準誤差の 2 倍以内で一致しています（9 個のうち 1 個が $-1.98$ で、独立な 9 回の比較としては不自然ではありません）。(b) 理論値も模擬の平均も、表の中では $\tau = 56$ で最小です。二分法で求めた $\tau^{*} = 53.001$ は、定理の区間 $[51.666, 53.666]$ に入っています。(c) $\tau = 12$ の理論値は手計算で確かめられます。$e^{13/1440} - 1 \approx 0.0090686$、これに $1445/12$ を掛けて $1.0920$ です。(d) 最適な間隔での無駄は $4.2\%$ で、間隔を半分にしても倍にしても $5.1\%$ 台です。$\sqrt{2C\mu}$ をそのまま使った場合は、最適との差が表示の桁に現れません。最適の近くは平らなので、$C$ や $\mu$ を正確に知らなくても、桁が合っていれば十分です。逆に、$\tau = 12$ 分（細かすぎる）や $240$ 分（粗すぎる）では無駄が $9\%$ を超えます。

5. 打ち切りと偏り

時間制限のある環境では、終わらなかった試行が必ず出ます。それを集計から黙って外すと、残った試行は元の母集団の無作為な標本ではなくなります。

命題 5.1（打ち切りによる選択の偏り）✓

試行の結果を $Y \in \{0, 1\}$、$P(Y = 1) = q$ とし、試行が制限時間内に終わるという事象を $F$ とする。$a_1 = P(F \mid Y = 1)$、$a_0 = P(F \mid Y = 0)$ とおき、$0 \lt q \lt 1$、$P(F) \gt 0$ とする。このとき、終わった試行だけで見た $Y = 1$ の割合の期待値 $P(Y = 1 \mid F)$ は

$$P(Y = 1 \mid F) - q = \frac{q(1 - q)(a_1 - a_0)}{qa_1 + (1 - q)a_0}$$

を満たす。したがって偏りが $0$ であることは $a_1 = a_0$（終わるかどうかが結果と無関係）と同値で、$a_1 \gt a_0$ なら過大評価、$a_1 \lt a_0$ なら過小評価になる。

証明（命題 5.1）

全確率の公式（定理 5.3［確率空間とコルモゴロフの公理］ の 2）から $P(F) = qa_1 + (1 - q)a_0$ で、ベイズの定理（同じ定理の 3）から $P(Y = 1 \mid F) = qa_1/P(F)$ です。よって

$$P(Y = 1 \mid F) - q = \frac{qa_1 - q\bigl(qa_1 + (1 - q)a_0\bigr)}{P(F)} = \frac{q(1 - q)a_1 - q(1 - q)a_0}{P(F)} = \frac{q(1 - q)(a_1 - a_0)}{qa_1 + (1 - q)a_0}$$

です。$q(1 - q) \gt 0$、分母は正なので、右辺の符号は $a_1 - a_0$ の符号と一致します。

∎

たとえば、ある最適化の手法が「大域的な最小値に到達した」（$Y = 1$）割合を調べるとします。真の割合が $q = 0.5$ で、到達する試行は速く終わるので必ず時間内に終わり（$a_1 = 1$）、到達しない試行は迷走して $4$ 割が時間切れになる（$a_0 = 0.6$）とすると、終わった試行での割合は $0.5/(0.5 + 0.3) = 0.625$ です。手法の成功率を $12.5$ ポイント過大に報告することになります。難しい問題ほど時間がかかる、という相関はたいていの数値実験にあるので、この偏りは例外ではなく通例です。

対処は、打ち切りを結果の 1 つとして記録することです。開始した試行の件数、終わった件数、打ち切った件数と理由（時間、反復回数の上限、発散の検出）を残し、打ち切った試行を「失敗」として数えた割合と、除外した割合の両方を報告します。少なくとも、除外した件数が分かれば、読者は偏りの大きさを上の式で見積もれます。

6. 進み具合の見積もり

反復法を走らせている途中で「あとどれだけかかるか」を見積もれると、時間制限に間に合うかどうかを判断できます。誤差の列 $e_k \gt 0$ が分かっている（あるいは推定できる）場合を考えます。

命題 6.1（残りの反復回数の見積もり）✓

$\mathrm{tol} \gt 0$ を目標の誤差とする。

1. （1 次収束）$0 \lt \rho \lt 1$ で、すべての $j \ge k$ について $e_{j+1} = \rho e_j$ とし、$e_k \gt \mathrm{tol}$ とする。$e_{k+m} \le \mathrm{tol}$ となる最小の整数 $m \ge 0$ は $$m = \Bigl\lceil\frac{\ln(\mathrm{tol}/e_k)}{\ln\rho}\Bigr\rceil$$ で、$\rho$ は直近の比 $e_{k+1}/e_k$ に等しい。
2. （2 次収束）$c \gt 0$ で、すべての $j \ge k$ について $e_{j+1} = ce_j^2$ とし、$ce_k \lt 1$、$e_{k+1} \gt \mathrm{tol}$ とする。直近の比 $\rho_k = e_{k+1}/e_k = ce_k$ を 1 の式に入れた見積もり $m_{\mathrm{lin}} = \lceil\ln(\mathrm{tol}/e_{k+1})/\ln\rho_k\rceil$ と、$e_{k+1+m} \le \mathrm{tol}$ となる最小の整数 $m_{\mathrm{true}} \ge 0$ について $$m_{\mathrm{true}} = \Bigl\lceil\log_2\frac{\ln(c\,\mathrm{tol})}{\ln(ce_{k+1})}\Bigr\rceil \le m_{\mathrm{lin}}$$ が成り立つ。

この命題の 2 つの式は、あとの数値例（$c = 1$ の例）を見るのが早道です。1 は「誤差が毎回同じ比 $\rho$ で縮む」なら、$\rho$ を何回かけると $\mathrm{tol}$ 以下になるかを対数で解いただけです。2 は、誤差が 2 乗になっていく場合に同じ見積もりを使うと、実際より多い回数を答えてしまうことを式で確かめます。

証明（命題 6.1）

1. $e_{k+m} = \rho^m e_k$ なので、$e_{k+m} \le \mathrm{tol}$ は $m\ln\rho \le \ln(\mathrm{tol}/e_k)$ と同値です。$\ln\rho \lt 0$ で割ると不等号の向きが変わり、$m \ge \ln(\mathrm{tol}/e_k)/\ln\rho$ です。右辺は正（分子・分母とも負）なので、これを満たす最小の整数は右辺の切り上げです。$e_{k+1}/e_k = \rho$ は仮定そのものです。

2. $b_j = ce_j$ とおくと、$b_{j+1} = c \cdot ce_j^2 = b_j^2$ です。$0 \lt b_k \lt 1$ なので、帰納法で $0 \lt b_{j+1} = b_j^2 \lt b_j \lt 1$ がすべての $j \ge k$ で成り立ち、$b_j$ は単調に減少します。また $b_{k+1+m} = b_{k+1}^{2^m}$ です。

   $e_{k+1+m} \le \mathrm{tol}$ は $b_{k+1}^{2^m} \le c\,\mathrm{tol}$、すなわち $2^m\ln b_{k+1} \le \ln(c\,\mathrm{tol})$ と同値です。$\ln b_{k+1} \lt 0$ で割ると $2^m \ge \ln(c\,\mathrm{tol})/\ln b_{k+1}$ です。$e_{k+1} \gt \mathrm{tol}$ から $c\,\mathrm{tol} \lt b_{k+1} \lt 1$ で、右辺は $1$ より大きいので、$m \ge \log_2\bigl(\ln(c\,\mathrm{tol})/\ln(ce_{k+1})\bigr)$ を満たす最小の整数 $m \ge 0$ は右辺の切り上げです。

   $m_{\mathrm{lin}}$ との比較です。$j \ge k + 1$ では $e_{j+1}/e_j = b_j \le b_{k+1} \lt b_k = \rho_k$ なので、$e_{k+1+m} \le \rho_k^m e_{k+1}$ です。$m = m_{\mathrm{lin}}$ のとき、1 の計算と同じく $\rho_k^m e_{k+1} \le \mathrm{tol}$ なので $e_{k+1+m_{\mathrm{lin}}} \le \mathrm{tol}$ で、最小性から $m_{\mathrm{true}} \le m_{\mathrm{lin}}$ です。

∎

1 次収束（定義 2.1［非線形方程式の反復解法］）する反復、たとえば縮小写像の不動点反復では、誤差そのものは分からなくても、隣り合う反復の差 $|x_{k+1} - x_k|$ の比から $\rho$ を推定でき、同じ差から誤差の上界も得られます（定理 4.1［非線形方程式の反復解法］ の事後評価）。進捗ログに残差や差を 1 行ずつ出しておけば、途中で残り時間を見積もれます。

2 は、2 次収束する反復にこの外挿を使うと悲観的すぎることを言っています。$c = 1$、$e_k = 10^{-1}$、$e_{k+1} = 10^{-2}$、$\mathrm{tol} = 10^{-12}$ なら、1 次収束とみなした見積もりは $m_{\mathrm{lin}} = \lceil\ln 10^{-10}/\ln 10^{-1}\rceil = 10$ 回ですが、実際は $10^{-4}, 10^{-8}, 10^{-16}$ と進んで $m_{\mathrm{true}} = \lceil\log_2(12/2)\rceil = 3$ 回です。逆に、誤差の比が $1$ に近づいていく（収束が遅くなっていく）計算では、直近の比による外挿は楽観的すぎます。見積もりは、収束の型の仮定とともに記録します。

7. 整合検査と実務の作法

再開のときに確かめること。 定理 3.1 の仮定は、実装の誤りで簡単に破れます。破れを結果が出る前に見つけるために、再開のたびに次を検査します。

• 設定のハッシュがチェックポイントのものと一致するか（例 3.4 の (d)）。一致しなければ止まります。
• 件数と単調性。反復番号は 1 ずつ増えているか。出力の行数は反復番号と合っているか。
• キーの一意性。部分結果を集計するとき、同じキーが 2 回現れていないか（重複）、あるはずのキーが抜けていないか（欠落）。命題 3.3 の表の定義域が、予定したキーの集合と一致することの確認です。
• 保存量と不変量。計算が保つはずの量（確率の和が 1、エネルギー、対称性）が保たれているか。検算と検証の章で扱います。
• チェックサム。チェックポイントのファイルの内容ハッシュを併せて記録し、読み込んだときに照合します。

何を保存するか。 保存するのは、再計算が高くつくものだけです。状態から短時間で作り直せる量（導出した統計量、図）は保存しません。保存するものが増えると $C$ が増え、定理 4.3 から最適な間隔も無駄も増えます。

世代を 2 つ残す。 原子的な置き換えは書きかけのファイルを防ぎますが、「正しく書かれた、内容の壊れた状態」（計算の途中で NaN が入った、など）は防げません。1 つ前の世代を残しておけば、そこまで戻れます。

ログを 2 種類に分ける。 人が読む行（いつ、何をしているか）と、機械が読む行（1 行に 1 件の JSON で、反復番号・残差・経過時間など）を分けます。後者は進み具合の見積もり（命題 6.1）と事後の検査の入力になります。ログは追記なので、再開で同じ番号の行が重複しうることを前提に、番号をキーにして読みます（例 3.2 の (iii)）。

シグナルを受けて止まる。 ジョブスケジューラは、時間制限に達する少し前に終了のシグナルを送るのが普通です。シグナルを受けたら「いまのステップを終えてからチェックポイントを取って終わる」ようにしておくと、失う仕事が $0$ になります。時間制限が分かっているなら、経過時間を自分で測って、制限の手前で止まるのも同じ効果があります。予定された停止は故障ではないので、§4 のモデルの $\lambda$ には数えません。

長い掃引は 1 点 1 ファイルにする。 パラメータの掃引の結果を 1 つの大きなファイルに書き足していくと、ファイル全体が 1 つのチェックポイントになり、書き込みの失敗がすべての点を巻き込みます。1 点の結果を 1 つのファイル（名前はその点のキー）に原子的に書けば、命題 3.3 の形になり、中断しても終わった点はそのまま残り、並列に走らせても互いに干渉しません。集計は、ファイルを集めて読むだけの別の段階にします。

8. 演習

演習 8.1易

チェックポイントの書き込みに $5$ 分、平均故障間隔が $12$ 時間の計算機で、Young の近似による間隔 $\sqrt{2C\mu}$ を求め、定理 4.3 が保証する $\tau^{*}$ の範囲を答えてください。

解答

$C = 5$ 分、$\mu = 720$ 分で、$\sqrt{2C\mu} = \sqrt{7200} \approx 84.9$ 分です。$2C = 10 \le 720 = \mu$ なので定理の 2 が使えて、$74.9 \le \tau^{*} \le 84.9$（分）です。1 時間 15 分から 1 時間 25 分に 1 回、ということになります。

演習 8.2標準

状態が $(k, a)$、遷移が $T(k, a) = (k + 1,\ a + k + 1)$、初期状態が $(0, 0)$、$k = 10$ で終わるジョブを考えます。毎ステップの後で、$k$ をファイル A に、$a$ をファイル B に、この順に別々に上書きして保存します（各ファイルの上書きは原子的とします）。(i) 中断のない実行の結果を求めてください。(ii) $k = 5$ になった直後の保存で、ファイル A を書いた後、ファイル B を書く前に中断したとします。再開後の結果を求め、定理 3.1 のどの仮定が破れているかを答えてください。

解答

(i) $a_k = 1 + 2 + \cdots + k = k(k+1)/2$ なので、結果は $(10, 55)$ です。

(ii) 中断の時点でファイル A は $5$、ファイル B は 1 つ前の $a_4 = 10$ です。再開後の状態は $(5, 10)$ で、軌道の上の状態 $(5, 15)$ ではありません。そこから $6 + 7 + 8 + 9 + 10 = 40$ が足されて、結果は $(10, 50)$ です。$5$ だけ小さくなります。

破れているのは原子性です。個々のファイルの上書きは原子的でも、2 つのファイルを合わせた保存域の値は、保存の前の値 $(4, 10)$ でも保存しようとした値 $(5, 15)$ でもない $(5, 10)$ になりえます。状態を 1 つのファイルにまとめて 1 回の改名で置き換えるか、世代ごとのディレクトリに書いてから「現在の世代」を指す 1 つのファイルを原子的に書き換えます。

演習 8.3標準

真の成功率が $q = 0.3$ の手法について、成功する試行の $90\%$、失敗する試行の $50\%$ が制限時間内に終わるとします。(i) 終わった試行だけで計算した成功率の期待値と偏りを求めてください。(ii) 打ち切った試行をすべて「失敗」として数えた成功率の期待値を求め、真の値と比べてください。

解答

(i) $P(F) = 0.3 \times 0.9 + 0.7 \times 0.5 = 0.62$、$P(Y = 1 \mid F) = 0.27/0.62 \approx 0.435$ です。偏りは 命題 5.1 から $0.3 \times 0.7 \times 0.4/0.62 \approx 0.135$ で、$0.435 - 0.3$ と一致します。

(ii) 「時間内に終わって成功した」割合は $P(Y = 1, F) = 0.27$ です。真の値 $0.3$ より小さく、こちらは過小評価です（時間をかければ成功したはずの試行を失敗に数えているため）。2 つの数え方は真の値を上下から挟みます。$P(Y = 1, F) \le q$ は常に成り立ち、$a_1 \ge a_0$ のとき $P(Y = 1 \mid F) \ge q$ だからです。両方を報告すれば、読者は真の値の範囲を知ることができます。

演習 8.4難

定義 4.1 を変えて、再起動の間にも同じ強度 $\lambda$ で故障が起こり、そのときは再起動を最初からやり直すとします。つまり、最初の試みは稼働時間 $a$、故障の後の試みは $R + a$ を故障なしで続ける必要があります。このとき 1 区間を完了するまでの期待時間が

$$\frac{1}{\lambda}\,e^{\lambda R}\bigl(e^{\lambda a} - 1\bigr)$$

であることを示し、最適な間隔 $\tau^{*}$ が 定理 4.3 と同じであることを確かめてください。

解答

長さ $b$ の稼働時間を故障なしで続けるまでの期待時間を $E(b)$ とすると、定理 4.2 で $R = 0$、$a = b$ とした場合なので $E(b) = \frac1\lambda(e^{\lambda b} - 1)$ です。

最初の試みが成功する確率は $q = e^{-\lambda a}$ で、そのときの時間は $a$ です。失敗したとき（$X_1 \lt a$）は、時間 $X_1$ を使った後、「$R + a$ を故障なしで続ける」ことを成功するまで繰り返します。2 回目以降の故障までの時間は $X_1$ と独立な $\mathrm{Exp}(\lambda)$ の列なので、その期待時間は $E(R + a)$ で、$X_1$ と独立です。したがって

$$E[T] = aq + E\bigl[X_1\mathbf{1}_{\{X_1 \lt a\}}\bigr] + (1 - q)E(R + a) = aq - aq + \frac{1 - q}{\lambda} + (1 - q)\frac{e^{\lambda(R + a)} - 1}{\lambda} = \frac{1 - q}{\lambda}e^{\lambda(R + a)}$$

です（$E[X_1\mathbf{1}_{\{X_1 \lt a\}}]$ は定理の証明で計算した値）。$(1 - q)e^{\lambda a} = e^{\lambda a} - 1$ なので $E[T] = \frac1\lambda e^{\lambda R}(e^{\lambda a} - 1)$ です。

仕事あたりの時間は $\frac1\lambda e^{\lambda R}(e^{\lambda(\tau + C)} - 1)/\tau$ で、$\tau$ によらない正の係数が $\frac1\lambda + R$ から $\frac1\lambda e^{\lambda R}$ に変わっただけです。定理 4.3 の証明は係数 $A \gt 0$ の値を使っていないので、同じ $\tau^{*}$ で最小になります。$\lambda R$ が小さければ $e^{\lambda R} \approx 1 + \lambda R$ で、2 つのモデルの期待時間もほとんど変わりません。

参考文献

• J. W. Young, “A first order approximation to the optimum checkpoint interval”, Communications of the ACM 17 (1974), 530–531. doi:10.1145/361147.361115
• J. T. Daly, “A higher order estimate of the optimum checkpoint interval for restart dumps”, Future Generation Computer Systems 22 (2006), 303–312. doi:10.1016/j.future.2004.11.016
• J. Gray, A. Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993 — 原子性と復旧の章。
• M. Kleppmann, Designing Data-Intensive Applications, O’Reilly, 2017 — 冪等性と「少なくとも 1 回」の配送を扱う章。
• NumPy のドキュメント「Bit generators」 https://numpy.org/doc/stable/reference/random/bit_generators/index.html
• Python のドキュメント「os — os.replace」 https://docs.python.org/3/library/os.html#os.replace