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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Partial Detectors Versus Replication to Cope with Silent Errors

  • Anne Benoit,
  • Thomas Herault,
  • Yves Robert,
  • Alix Tremodeux

摘要

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.