Linear Algebraic Methods in RESTART Problems in Markovian Systems

A task with ideal execution time $$\ell $$ ℓ is handled by a Markovian system with features similar to the ones in classical reliability. The Markov states are of two types, UP and DOWN, such that the task only can be processed in an UP state. Upon entrance to a DOWN state, processing is stopped and must be restarted from the beginning upon the next entrance to an UP state. The total task time $$X=X_\mathrm {r}(\ell )$$ X = X r ( ℓ ) (including restarts and pauses in failed states) is investigated with particular emphasis on the expected value $${\pmb {\mathbb {E}}}[X_\mathrm {r}(\ell )]$$ E [ X r ( ℓ ) ] , for which an explicit formula is derived that applies for all relevant systems. In general, transitions between UP and DOWN states are interdependent, but simplifications are pointed out when the UP to DOWN rate matrix (or the DOWN to UP) has rank one. A number of examples are studied in detail and an asymptotic exponential form $$\exp (\beta _\mathrm {m} \ell )$$ exp ( β m ℓ ) is found for the expected total task time $${\pmb {\mathbb {E}}}[X(\ell )]$$ E [ X ( ℓ ) ] as $$\ell \rightarrow \infty $$ ℓ → ∞ . Also, the asymptotic behavior of the total distribution, $$H_\mathrm {r}(x|\ell )\rightarrow \exp (-x\gamma (\ell ))$$ H r ( x | ℓ ) → exp ( - x γ ( ℓ ) ) , as $$x\rightarrow \infty $$ x → ∞ is discussed.