Markov Renewal Methods in Restart Problems in Complex Systems

A task with ideal execution time L such as the execution of a computer program or the transmission of a file on a data link may fail, and the task then needs to be restarted. The task is handled by a complex system with features similar to the ones in classical reliability: failures may be mitigated by using server redundancy in parallel or k-out-of-n arrangements, standbys may be cold or warm, one or more repairmen may take care of failed components, etc. The total task time X (including restarts and pauses in failed states) is investigated with particular emphasis on the tail $${\mathbb P}(X>x)$$ P ( X > x ) . A general alternating Markov renewal model is proposed and an asymptotic exponential form $${\mathbb P}(X>x)\sim C{\mathrm {e}}^{-\gamma x}$$ P ( X > x ) ∼ C e - γ x identified for the case of a deterministic task time $$L\equiv \ell $$ L ≡ ℓ . The rate $$\gamma $$ γ is given by equating the spectral radius of a certain matrix to 1, and the asymptotic form of $$\gamma =\gamma (\ell )$$ γ = γ ( ℓ ) as $$\ell \rightarrow \infty $$ ℓ → ∞ is derived, leading to the asymptotics of $${\mathbb P}(X>x)$$ P ( X > x ) for random task times L. A main finding is that X is always heavy-tailed if L has unbounded support. The case where the Markov renewal model is derived by lumping in a continuous-time finite Markov process with exponential holding times is given special attention, and the study includes analysis of the effect of processing rates that differ with state or time.