P c þ
X M
m¼1
P m þ P pf þ
X M
m¼1
P m ðLÞ þ P pl ðLÞ ¼ 1
We define now P km , P kpf, P km (L), and P kpf (L) as the conditional probabilities of
the above events when a malfunction occurs in segment k.
We do not cover all scenarios with k
3, since for k = 1, 2, 3, the recovery
times are in a similar range for all three algorithms.
By analog to the above equation, we derive
P c þ
X M
m¼1
P k m þ P k pf þ
X M
m¼1
P k m ðLÞ þ P k pf ðLÞ ¼ 1
The probability of successful program execution in the first run (event H c ) is
P c ¼ e
ÀkT
ð10:1Þ
We individually calculate the probabilities for successful recovery execution for
latent and non-latent malfunctions, first without latency, and failure detection at the
end of the segment where the fault appeared (k = J).
The probability of successful recovery of the ongoing task in the case of
non-latent malfunctions and recovery depth m (event H km ) is
P k m ¼ a k P 00 k 1 ; l; T; t beg m
À
Á
P 0 k 2 ; t beg m
À
Á
Â
À
X mÀ1
i¼1
P k i P 00 k 1 ; l; Dt
m
i
P 0 k 2 ; Dt
m
i
!
P 0 k; t rb m
ð
Þ
ð10:2Þ
In case of recovery depth m, the task is repeated m times, assuming the last time
starting from RP(k-m). Here a k is the probability of detecting the malfunction at the
end of segment k, m = 1, 2, …, k.
The required time for recovery is found as follows: the time when recovery step
m starts,
t beg m ¼ T P
mÀ1 þ d i À d
the time required by recovery step m,
t rb m ¼ mðT þ dÞ
the time difference between start and stop of step i
Dt
m
i
¼ t beg m À T P
i À d i þ d
156
10 Recovery Algorithms: An Analysis