We study efficient simulation algorithms for estimating $\mathbb{P}(X>x)$, where $X$ is the total time of a job with ideal time $T$ that needs to be restarted after a failure. The main tool is importance sampling where one tries to identify a good importance distribution via an asymptotic description of the conditional distribution of $T$ given $X>x$.

If $T\equiv t$ is constant, the problem reduces to the efficient simulation of geometric sums, and a standard algorithm involving a Cramér type root $\gamma(t)$ is available. However, we also discuss an algorithm avoiding the rootfinding. If $T$ is random, particular attention is given to $T$ having either a gamma-like tail or a regularly varying tail, and to failures at Poisson times. Different type of conditional limits occur, in particular exponentially tilted Gumbel distributions and Pareto distributions. The algorithms based upon importance distributions for $T$ using these asymptotical descriptions have bounded relative error as $x\to\infty$ when combined with the ideas used for a fixed $t$.

Nevertheless, the paper gives examples that algorithms carefully designed to enjoy bounded relative error may provide little or no asymptotic improvement of crude Monte Carlo simulation when the computational effort is taken into account. To resolve this problem, an alternative algorithm using two-sided Lundberg bounds is suggested.