数理解析研究所講究録 1457 巻 2005 年 200-207

200
Behavioral Analysis of a Fault-Tolerant Software System with
Rejuvenation
野坂 弘一郎, 土肥 正

Koichiro Rinsaka and Tadashi Dohi
Departm ent of Information Engineering, Graduate School of Engineering,
Hiroshima University, Japan
Abstract In recent years, considerable attention has been devoted to continuously running softwaresystems whose performance characteristics are smoothly degrading in time Software aging often affects
the performance of a software system and eventually causes it to fail. A novel approach to handle
transient software failures due to software aging is called software rejuvenation, which can be regarded asa preventive and proactive solution that is particularly useful for counteracting the aging phenomenon. In
this paper, we focus on a high assurance software system with fault-tolerance and preventive rejuvenation,
and analyze the stochastic behavior of such a highly critical software system. More precisely, we consider
a fault-tolerant software system with two version redundant structure and random rejuvenation schedule,
and evaluate quantitatively a dependability measure like the steady-state system availability based on thefamiliar Markovian analysis. In numerical examples, we examine the dependence of two system diversity
techniques; design and environment diversity techniques, on the system dependability measures.

1.

Introduction

Present day applications impose stringent requirements in terms of software dependability since inmany cases the consequences of software failure
can lead to huge economic losses or risk to human life. However, these requirements are very
difficult to design for and guarantee, particularly
in applications of nontrivial complexity. In general, the software dependability techniques can beclassified into two approaches: design and environment diversity techniques. The former corresponds to the redundant-software architecture suchas recovery block, version programming andself-check programming $[16,23]$ , the latter to diversify the software operating circumstance temporarily. The typical examples of environment diversity technique are progressive retry, rollback rolJforvvard recovery with checkpointing, restart, hardware reboot, etc. In recent years, considerable attention has been devoted to continuously runningsoftware systems whose performance characteristics are smoothly degrading in time. That is tosay, when software application executes continuously for long periods of time, some of the faults
cause software appear to age due to the error conditions that accrue with timeload. Thisphenomenon is called software aging and can be observed in many real software systems [1,5,7,21,28].
Huang et al. [12] report this phenomenon in thereal telecommunication billing application where
over time the application experiences a crash ora hang failure. Avritzer and Weyuker [3] discuss$\mathrm{N}$$\mathrm{N}$$\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}\mathrm{r}$aging in a telecommunication switching software
where the effect manifests as gradual performancedegradation. Software aging has also been
served in widely-used software like Netscape andxrn [5]. Perhaps the most vivid example of aging in safety critical systems is the Patriot’s software [17], where the accumulated errors led to a
failure that resulted in loss of human lives. Resource leaking and other problems causing software
to age are due to the software faults whose fixing
is not always possible because, for exam
, thesource code is not always available. Our common
experience suggests that most software failures aretransient in nature] Since transient failures
will likely not recur even if the operation is retried
later in slightly different context, it is difficult tocharacterize their root origin. The time to find anddeploy a fix to such faults can sometimes be intolerably long. Therefore, the residual faults are often
tolerated in the operational phase. Usual strategies
to deal with failures in operational phase are reactive in nature; they consist of action taken after
the occurrence of the failure.
$\mathrm{o}\mathrm{b}arrow$$\mathrm{p}\mathrm{l}\mathrm{e}$$\llcorner\lceil 11$-

A novel approach to handle transient software
failures is called so frware rejuvenation which canbe regarded as a preventive and proactive solution that is particularly useful for counteracting
the phenomenon of software aging. It involves
stopping the running software occasionally, cleaning its internal state and restarting it. Cleaning the internal state of a software might involve
garbage collection, flushing operating system kernel tables, reinitializing inter al data structures201
etc. An extreme, but well known example of rejuvenation which has been around as long as computers themselves is a hardware reboot. Apart frombeing used in an ad-hoc manner by almost all computer users, software rejuvenation has been used inhigh availability and mission critical systems. The
studies of aging-related fiqilures are based on two
approaches: measurement-based and model-based.
The measurement-based approach concentrates ontlle detection and validation of the existence ofsoftware aging and estimating its effects on system
resources [10, 13,24,29,30]. On the other hand, themodel-based approach aims at evaluating the effectiveness of software rejuvenation and determining
the optin al schedule to perform it,

Huang, et al. [12] consider a model-based approach where the degradation is described by a two
step process. Prom the clean state the software system makes a transition into a degraded state fromwhich two actions are possible: rejuvenation withreturn to the clean state or transition to the complete failure state. They model the four-state pro
cess as a continuous-time Markov chain (CTMC)
and derive the steady-state availability and the expected cost per unit time in the steady state. Garg
et $d$ . [8] introduce the idea of periodic rejuvenation
into the Huang et at. model [12], and represent
the system behavior through a Markov regenerative stochastic Petri net. Dohi et al. [6], Suzuki
et at. $[25, 26]$ extend the Huang et at. model [12]to semi-Markov models and further develop nonparal etric algorithms to estimate the optimal software rejuvenation schedule. Tai et al. [27] also discuss the concept of on-board preventive mainte
nance which is an analogous to software rejuvenation and maximize the mission reliability Garg
et al. [9] develop a preventive maintenance modelwith two kinds of environment diversity techniquesand examine the effects of checkpointing and rejuvenation for the expected completion time of asoftware program. Liu et al. [14] and Park and Kim[22] evaluate the cable modem termination system
cluster systems with rejuand thevenation, respectively. Aung [2] and Iiu et at. [15]treat the determination problem of software rejuvenation schedule from the view point of software
survivability. Bao et , [4] develop an adaptive
software rejuvenation scheme based on the statistical observation of system failure time.
$\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}/\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{b}\mathrm{y}$$al$

In this paper, we focus on a high assurance software system with fault-tolerance and preventive rejuvenation, and analyze the stochastic behavior ofsuch a highly critical software system. More precisely, we consider a fault-tolerant software systemwith two version redundant structure and random
rejuvenation schedule, and evaluate quantitatively
a dependability measure like the steady-state sys-

tem availability based on the familiar Markovian
analysis. Two version software system is perhaps
the most popular fault tolerant software systemwith redundancy In the hardware fault tolerance( $e.g$ . see Osaki [19]), two independent components
are assumed in the computer architecture. However, it is almost impossible to develop statistically independent software programs. Hence, when
two version software system is modeled mathem atically, the correlation on the failure property be
tween two software systems has to be represented
by bivariate probability distribution. In this paper we develop a CTMC model with redundancy
and rejuvenation, by taking account of the failure correlation of two software systems. Then,the bivariate exponential distribution in the senseof Marshall and Olkin [18] is introduced to represent the correlation between two software systems.
Also, in order to model the deterioration process
due to software aging, we aPPly the two step failure model similar to Huang et al. [12]. This pointshould be distinguished from the existing result in
the hardware fault tolerant literature ( $e.g$ . Osaki [20] , though this paper is a continuation ofearlier work [12].
The rest of this paper is organized as follows
In Section 2, we describe a Markov software rejuvenation model discussed by Huang et al. [12] andsummarize their results on the steady-state system
availability. In Section 3, we model a two version
software system with rejuvenation and derive analytically the steady-state system availability. Sectlon 4 is devoted to numerical examples, where we
examine the dependence of two system diversity
techniques; design and environment diversity techniques. on the system dependability measures. Finally, the paper is concluded with some remarks.
$)$

2.

Single Version Software
System with Rejuvenation

Suppose that a singte version software system isstarted for operation at time $t=0$ with the highlyrobust state (normal operation state). The sys
tem can smoothly degrade in time. As assumed
in the existing literature [6, 8, i2, 25, $26|$ , we fo
cus on the two step failure process to model thetelecommunication billing application in AT & ,, the highly robust state changes to the failure
probable state at random timing. Just after thestate becomes the failure probable state, a system
failure may occur with a positive probability. If
the system failure occurs before triggering a software rejuvenation, then the recovery operation isstarted immediately at that time and is completedwith a random recovery overhead. Otherwise, the$\mathrm{T}$$\mathrm{i}.e.$202

Figure 2: Configuration of two version softwaresystem.
Figure 1: Markovian transition diagram for a single version software system with rejuvenation.

(1)$\frac{dQ_{0,1}(t)}{dt}=-(\lambda_{1\underline{7}}+\mu_{1})Q_{0,1}(t)+\lambda_{11}Q_{0,0}(t)$software rejuvenation is triggered and the softwaresystem becomes as good as new with the rejuvenation overhead. Then, the software age is initialized
to zero at the beginning of the next highly robust
state. We define the time interval from the beginning of the system operation to the completion ofrecovery oPeration or software rejuvenation as one
cycle, and assume that the same cycle is repeatedagain and again.
Huang et al. [12] introduce the simple software
rejuvenation model based on the CTM C. Define
the following four states:$\frac{dQ_{0,2}(t)}{dt}=-r_{3}Q_{0,2}(t)+\lambda_{12}Q_{0_{\rangle}1}(t)$

(2)

,

(3)

,

(4)

$\frac{dQ_{0,3}(t)}{dt}=-r_{1}Q_{0,3}(t)+\mu_{1}Q_{0,1}(t)$with the initial conditions:$Q_{0,0}$(0) $=1$ ,$Q_{0,1}(0)=Q_{0,2}(0)=Q_{0,3}(0)=0$ .

(5)Suppose that the limiting transition probability$(j=0,1, 2, 3)$ exists,.
$\mathrm{i}.e$$p_{j}$

State 0: highly robust state (normal operation$pj= \lim_{tarrow\infty}Q\mathrm{o},i(t)$,$j=0,1,2,3$ .

(6)state)

By taking the limitation, since the Kolmogorov’s
differential equations in Eqs. (1) $-(4)$ are reduced
to the algebraic equations:

State 1: failure probable stateState 2: system failure stateState 3: software rejuvenation state.

$-\lambda_{11}p_{0}+r_{3}p_{2}+r_{1}p_{3}=0$

Figure 1 depicts the Markovian transition diagramof Huang et al. model [12], where $\lambda_{11}(>0)$ ,$\lambda_{12}(>0)$ , pi $(>0)$ , $r_{1}(>0)$ and $r_{3}(>0)$
denotethe transition rates from the highly robust state to
the failure probable state, the system failure ratefrom the failure probable state, the transition rate
to trigger the software rejuvenation from the failure probable state, the recovery rate from the system failure state and the recovery rate from thesoftware rejuvenation state, respectively. In thismodel setting, the opportunity to trigger the software rejuvenation arrives at the system according
to the homogeneous Poisson process with rate .
This assumption does not seem to be restrictive,
because the preventive rejuvenation is not always
possible at pre-scheduled time in continuously running software systems.
Let $\{X(t)=\mathrm{i},t \geq 0\}$ , $(\mathrm{i}=0,1, 2,3)$ be thesystem state at time with the transition prob
ability Qoj(t) $=\mathrm{P}\mathrm{r}\{X(t)=j|X(0)=0\}(t\geq$, $j=0$ , 1, 2, 3). From an elementary probabilistic
argument, the Kolmogorov’s differential equations
which the transition probabilities have to satisfy
are given by$-(\lambda_{12}+\mu_{1})p_{1}+\lambda_{11}p_{0}=0$$-r_{3}p\underline{\circ}+\lambda_{12}p_{1}=0$$-r_{1}p_{3}+\mu_{1}p_{1}=0$,,$p_{0}+p_{1}+p_{\underline{\mathrm{Q}}}+p_{3}=1$$0$$\frac{dQ\mathrm{o},\mathrm{o}(\mathrm{f})}{dt}=-\lambda_{11}Q_{0,0}(t)+r_{3}Q_{0,2}(t)+r_{1}Q_{0,3}(t)$

,

,

,

(7)
(8)
(9)
(10)
(11)

we obtain the steady-state system availability as
follow :$\mathrm{s}$

A

$=$

$=$

$Pc$ $+$$\mathrm{J}\mathrm{t}$$\frac{\frac{1}{\lambda_{11}}+\frac{1}{\lambda_{12}+\mu_{1}}}{\frac{1}{\lambda_{11}}+\frac{1}{\lambda_{12}+\mu_{1}}+\ovalbox{\tt\small REJECT}\lambda+\frac{\mu_{1}}{(\lambda_{12}+\mu_{1})r_{1}},(\lambda_{1}\underline{\circ}+\mu_{1})r_{3}}$

.

(12)

$\mu_{1}$

$t$

,

3.

Fault-Tolerant
Software
System with Rejuvenation

3.1

Availability Analysis

Next, we consider a fault-tolerant software sys
tem with redundancy and preventive rejuvenation.
Suppose that two software programs are runningin parallel. Figure 2 indicates the configurationof two version software system. In a fashion similar to Huang et al. model [12], it is assumed that

203
each software deteriorates and reaches to the system failure state if no software rejuvenation is triggered after entering to the failure probable state.
More specifically, consider a two-unit parallel redundant system with deterioration on a lattice. In
the two unit hot-standby parallel redundant, each unit has two stage deterioration levels,
say failure probable state and system failure state,
and the transition from the normal operation (deterioration) level to the deterioration (system failure) level is occurred following an exponential distribution. Let $X$ and $Y$ be the deterioration times
for Software System 1 and Software System 2, respectively, and denote the non-negative randomvariables having the following marginal distribution functions;$\mathrm{s}\mathrm{y}\mathrm{s}arrow$

State 1 (3): System 1 (2) deteriorates but System 2 (1) is operating
State 5 (7): System 1 (2) fails but System 2 (1)deteriorat$\mathrm{e}$State 6 (2): System 2 (1) fails but System 1 (2)is operating$\mathrm{t}\mathrm{e}\mathrm{m}$, $x>0$ , A $1>0$ , (13)$F_{Y}(y)=1-\exp\{-\lambda_{2}y\}$ ,. (14)$y>0$ ,

$F\mathrm{x}(x)=1-$ $\exp\{-\lambda_{1}x\}$$\lambda_{2}>0$State 9 (10): System 1 (2) is rejuvenated but
System 2 (1) is operating

State 11 (12): System 1 (2) is rejuvenated but
System 2 (1) deteriorates
State 13 (14): System 1 (2) is rejuvenated but
System 2 (1) fails.
Based on the definition above, the system failure
is corresponding to States 8, 13 and 14,
Figure 3 depicts the Markovian transition diagram for fault-tolerant software system with reju, A12, , andvenation in renewal case, where(A21, A22,and ) denote the transition
rates from the highly robust state to the failure
probable state, the system failure rate from thefailure probable state, the transition rate to trigger of software rejuvenation from the failure probable state, the recovery rate from the system failurestate and the recovery rate from the software rejuvenation state for Software System 1 (Softwaredenotes the
System 2), respectively. Further,transition rate that both software systems deteridenotes the tranorate simultaneously, A32
sition rate that Software System 1 (2) fails andSoftware System 2 (1) deteriorates simultaneously,
and A34 denotes the simultaneous system failure
rate ffom the failure probable state
Let $\{X(t)=\mathrm{i}, t\geq 0\}(\mathrm{i}=0,1, \cdots, 14)$ be the
CTMC to represent the stochastic behavior of thetwo version software system with rejuvenation. In
a fashion similar to the Markovian argument in
Section 2, we obtain the pointwise system avail$\lambda_{11}$

If the failure property of two software systems isstatistically independent, then the joint distribution function is given by$FxY(x, y)=\mathrm{P}\mathrm{r}\{X\leq x, Y\leq y\}$$=1-\{1-F_{X}(x)\}\{1-F_{Y}(y)\}(15)$$=1-\exp\{-\lambda_{1}x-\lambda_{2}y\}$.

Since it is impossible to develop the completely independent software systems with same functions,however, the correlation between the failure ProPerties for each software system should be taken into
consideration.
In this paper, we use the bivariate exponential
distribution in the sense of Marshall and Olkinphenomena
to represent bothfor two software systems. The main reason to aPply the Marshall and Olkin distribution is that
it is easy to represent the simultaneous deterioin the framework and apply it to the
CTMC analysis [20] . For the deterioration times $X$
and , the deterioration time distribution is givenby the foliowing bivariate exponential$[1\mathrm{S}|$$\mathrm{d}\mathrm{e}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{o}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}/\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{u}\mathrm{r}\mathrm{e}$$\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}/\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{u}\mathrm{r}\mathrm{e}$$Y$$\mu_{2},$$r\mathrm{s}$$r_{2}$$\mu_{1}$$r_{1}$$\mathrm{r}_{4}$$\lambda_{31}$$(\lambda_{33})$

ability:$A(t)$$=$$Q_{0,0}(t)+Q_{0,1}(t)+Q_{02}\rangle(t)+Q_{0,3}(t)$$+Q_{0,4}(t)+Q_{0,5}(t)+Q_{0,6}(t)$$F(x, y)$ $=\mathrm{P}\mathrm{r}\{X\leq x, Y\leq y\}$$=1-\exp$ { $-\lambda_{1}x-\lambda_{2}y-$ A3 $\max$ ( , )},
$x$

$y$

(16)

denotes the correlation parameter.
where,
then two software systems are indeWhen
pendent from each other, the system failure time
distribution is given in Eq. (16).
Define the following 15 states:$\lambda_{3}(\geq 0)$$\lambda_{3}=0$$+Q_{0,7}(t)+Q_{0,9}(t)$ $+Q_{0,10}(t)$$+Q_{0,11}(t)+Q_{0_{?}12}(t)$State 4; Both systems deteriorate

State 8: Both systems are down

(17)

where the stationary transition probabilities$Q_{0,j}(t)$ , $(j=0,1, \cdots, 14)$ are the solutions of theKolmogorov’s differential equations in Eqs.(36)(50) (see Appendix). If there exist the limiting
probabilities$p_{j}= \lim_{tarrow\infty}\mathrm{Q}\mathrm{O}\mathrm{j}(\mathrm{t})$State 0: Both systems are operating,$(j=0,1, \cdots, 14)$ ,(18)

then we derive the following simultaneous (algebraic) equations:$-(\lambda_{11}+\lambda_{21}+\lambda_{31})p0+r_{3}p_{2}+r_{4}p_{6}+r_{1}p_{9}$204

Figure 3. Markovian transition diagram for fault-tolerant software system with rejuvenation.
(19)$+r_{2}p_{10}=0$ ,Numerical Illustrations

4.

$-(\lambda_{12}+\lambda_{21}+\lambda_{32}+\mu_{1})p_{1}+\lambda_{11}p_{0}+r_{4}p_{7}$(20)$-(\lambda_{21}+r_{3})p_{2}+\lambda_{12}p_{1}+r_{4}p_{\mathrm{S}}+r_{2}p_{14}=0$ , (21)$+r_{2}p_{12}=0$ ,$-(\lambda_{11}+\lambda_{22}+\lambda_{33}+\mu_{2})p_{3}+\lambda_{21}p_{0}+r_{3}p_{5}$(22)$+r_{1}p_{11}=0$ ,$-(\lambda_{12}+\lambda_{22}+\lambda_{34}+\mu_{1}+\mu_{2})p_{4}+\lambda_{31}p_{0}$$+\lambda_{21}p_{1}+\lambda_{11}p_{3}=0$

–

,

23)

$\langle$,(24)$(\lambda_{22}+r_{3})p_{5}+\lambda_{32}p_{1}+\lambda_{21}p_{2}+\lambda_{12}p_{4}=0$$-(\lambda_{11}+r_{4})p_{6}+\lambda_{22}p_{3}+r_{3}p_{8}+r_{1}p_{13}=0$, (25)$-(\lambda_{12}+r_{4})p_{7}+\lambda_{33}p_{3}+\lambda_{22}p_{4}+\lambda_{11}p_{6}=0$,(26)$-(r_{3}+r_{4})p_{8}+\lambda_{34}p_{4}+\lambda_{22}p_{5}+\lambda_{12}p_{7}=0,(27)$$-(r_{1}+r_{4})p_{13}+\lambda_{22}p_{11}=0$

,

(28)
29)
(30)
(31)
(32)

,

{33)

–

$(\lambda_{21}+r_{1})p_{9}+\mu_{1}p_{1}+r_{4}p_{13}=0$,$-(\lambda_{11}+r_{2})p_{10}+\mu_{2}p_{3}+r_{3}p_{14}=0$$-(\lambda_{22}+r_{1})p_{11}+\mu_{1}p_{4}+\lambda_{21}p_{9}=0$,,$-(\lambda_{12}+r_{2})p_{12}+\mu_{2}p_{4}+\lambda_{11}p_{10}=0$$-(r_{2}+r_{3})p_{14}+\lambda_{12}p_{12}=0$$\sum_{j=0}^{14}p_{j}=1$.

$\langle$,(34)

Finally, by solving the above equations numerically, we can get the steady-state system availability:
$A$

$=$

$p_{0}+p_{1}+p_{2}+p_{3}+p_{4}+p_{5}+p_{6}+p_{7}$$+p_{9}+p_{10}+p_{11}+p_{12}$

.

(35)

Here, we compare the present model with Huang

et at. [12] and investigate the effect of redundancy
in terms of dependability measures. To simplify
the analysis, it is assumed that A $3=\lambda_{31}=\lambda_{32}=$
A34. Also, we assume the parametric circumstance mentioned in Table 1. Figure 4 illustrates
the dependence of software rejuvenation rate on
the steady-state system availability for Huang etal. model [12]. From this figure, for a single version
software system, the steady-state system availability can be improved from 0.997 to 0.998 (0.1003%)
by adjusting the software rejuvenation rate fromOn the other hand, in$\mu_{1}=$ 0.0458 to 0.02665.
Figs. 5 and 6, the behavior of the steady-state system availability with varying software rejuvenation
1/500 andis plotted in two cases:
rate
implies that two software, wheresystem are completely independent in terms ofsystem failure occurrence. Comparing Fig.5 with
Fig.6, it can be observed that the correlation Pastrongly influences to the steady-state
rametersystem availability, . as A3 increases much more,
two software systems have greater correlation on
the system failure from each other and the system$\lambda_{33}=$$\mu_{1}$$\lambda_{3}=$$\mu_{1}$$\lambda_{3}=0$$\lambda_{3}=0$$\mathrm{s}$$\lambda_{3}$$\mathrm{i}.e$

availability decreases.
Finally, it is concluded that the software dependability can be controlled with two model Parameters based on design and environment diversity techniques. Namely, if the alternative software
version is designed from the standpoint of dependability measures, the correlation parameters like$\lambda_{3}$205
Table 1: Parameter Values$\frac{\mathrm{a}}{<\frac{\overline}{}\frac{\S}{\alpha}>}$Figure 5. Dependence of software rej uvenation rateon the steady-state system availability for two ver.
sion software system:$\lambda_{3}^{-1}=500(\mathrm{h}\mathrm{r}\mathrm{s})$$\triangleleft D=\mathrm{g}=\alpha>\alpha$.
$< \frac{\Xi}{B}>\frac{B}{\triangleleft}$

Figure 4: Dependence of software rejuvenation rateon the steady-state system availability for single
version software system.
plays a significant role to attain the target dependability level. On the other hand, after a sufficient
cost was spent in the design of redundant structure, the environment diversity technique such assoftware rejuvenation should be carried out and theshould be detersoftware rejuvenation rates lke
mined to trigger the preventive maintenance of degraded software systems due to aging phenomenon.
$\mu_{1}$5.

Conclusion

In this paper we have dealt with a fault-tolerant
software system with alternative redundant version and random rejuvenation, and investigated its
stochastic behavior. Based on the simple CTMC
approach, we have numerically derived the steadystate system availability, and have examine the effect of two diversity techniques; design and environment diversity techniques. In practice, it is wellknown that much effort and cost are needed in thedesign phase to develop the effective two version
software system with lower correlation. However,
we have shown that by combining two diversity
techniques effectively, the dependability level canbe improved. In the next step, we will consider
the case with the deterministic software rejuvenation schedule and extend the present CTM model$\mathrm{C}$Figure 6: Dependence of software rejuvenation rateon the steady-state system availability for two ver.
sion software system:$\lambda_{3}=0$

to the semi-Markov one Then, the other bivariate family e.g. such as bivariate gamma distribution should be applied to model the system failure
phenomenon for the fault-tolerant software system
under several restrictive assumptions. If two software systems are expected to be statistically inde
pendent, it is not so hard to formulate the optimal
software rejuvenation scheduling problem. However, as tried in this paper, the modeling of correlated software systems will involve several technicalproblems to be overcome.

AppendixA.

Stationary transition probabili-

A.I

ties
The Kolmogorov differential equations which thestationary transition probabilities $Qo,j$ (?)$0,1$ ,, 14) satisfy are given by
$(j$

$=$

$\cdots$$\frac{dQ_{0,0}(t)}{dt}$$=$$-(\lambda_{11}+\lambda_{21}+\lambda_{31})Q_{0,0}(t)$$+r_{3}Q_{0,2}(t)+r_{4}Q_{0,6}(t)$$+r_{1}Q_{0,9}(t)+r_{2}Q_{0_{2}10}(t)$

,

(36)

208
$\frac{dQ_{0,1}(t)}{dt}$$=$$-(\lambda_{12}+\lambda_{21}+\lambda_{32}+\mu_{1})Q_{0,1}(t)$$+\lambda_{11}Q\mathrm{o},\mathrm{o}(t)+r_{4}Q_{0,7}(t)$$+r_{2}Q_{0}$$\frac{dQ_{0,2}(t)}{dt}$

$=$

(37)

,s2 (t),$-(\lambda_{21}+r_{3})Q_{0,2}(t)+\lambda_{12}Q_{0,1}\langle t)$$+r_{4}Q_{0,8}(t)+r_{2}Q_{\mathit{0},14}(t)$$\frac{dQ_{0,3}(t)}{dt}$

$=$

,

(38)

$-(\lambda_{11}+\lambda_{22}+\lambda_{33}+\mu_{\underline{9}})Q_{0.3}(t)$$+\lambda_{21}Qo,o(t)$ $+r_{3}Q_{0,5}(t)$$+r_{1}Q_{0,11}(t\rangle$$\frac{dQ_{0,4}\langle t)}{dt}$

$=$

(39)

,

$-(\lambda_{12}+\lambda_{22}+\lambda_{34}+\mu_{1}+\mu_{2})$$\mathrm{x}$$Q_{0,4}(t)+\lambda_{31}Qo,o(t)$$+\lambda_{21}Q_{0,1}(t)+\lambda_{11}Q_{0,3}(t)$$\frac{dQ_{0,5}(t)}{dt}$

$=$

$=$

$=$

,

$=$

(41)

(42)

$-(\lambda_{12}+r_{4})Q_{0,7}(t)+\lambda_{33}Q_{0,3}(t)$$+\lambda_{22}Q_{0,4}(t)+\lambda_{11}Q_{0,6}(t)$$\frac{dQ_{0,8}(t)}{dt}$,$-(\lambda_{11}+r_{4})Q_{0,6}(t)+\lambda_{22}Q_{0,3}(t)$$+r_{3}Q_{0,8}(t)+r_{1}Q_{0,13}(t)$$\frac{dQ_{0,7}(t)}{dt}$(40)$-(\lambda_{22}+r_{3})Q_{0,5}(t)+\lambda_{32}Q_{0,1}(t)$$+\lambda_{21}Q_{0,2}(t)+\lambda_{12}Q_{0,4}(t)$$\frac{dQ_{0,6}(t)}{dt}$

,

,

(43)

$-(r_{3}+r_{4})Q_{0,8}(t)+\lambda_{34}Q_{0,4}(t)$$+\lambda_{22}Q_{0,5}(t)+\lambda_{12}Q_{0,7}(t)$

,

(44)

[2] Aung, K.-M.-M. (2004), The optimum time toperform software rejuvenation for survivability, Proc. 7th IASTED InVl Conf. on Softutare
Eng., 292-296.

[3] Avritzer, A. and Weyuker, E. J. (1997), Monitoring smoothly degrading systems for increased dependability, Empirical SoftwareEng., 2, 59-77.
[4] Bao, Y., Sun, X. and Trivedi, K. S. (2003),
Adaptive software rejuvenation: degradation
model and rejuvenation scheme, Proc. Inte’lConf. on Dependable Systems and Ne rworks,241-248, IEEE CS Press.
[5] Castelli, V., Harper, R. E., Heidelberger, P.,
Hunter, S. W., Hivedi, K. S., Vaidyanathan,K. V. and Zeggert, W. P. (2001), Proactive
management of software aging, IBM J. Research & Development, 45, 311-332.
[6] Dohi, T., Goseva-Popstojanova, K. andTrivedi, K. S. (2001), Estimating software
rejuvenation schedule in high assurance systems, The Computer Journal, 44, 473-485.
K.,
Goseva-Popstojanova,
T.,[7] Dohi,
Vaidyanathan, K., Trivedi, K. S. andOsaki, S. (2003), Software rejuvenation
modeling and applications, Springer Rdiabilzty Engineering Handbook (H. Pham, ed.),Springer-Verlag, 245-263.

-$\frac{dQ_{0,9}(t)}{dt}$$=$$-(\lambda_{21}+r_{1})Q_{0,9}\{t)$ $+\mu_{1}Q_{0,1}(t)$$+r_{4}Q_{0,13}(t)$$\frac{dQ_{0,10}(t)}{dt}$$=$$-(\lambda_{11}+r_{2})Q_{0,10}(t)+\mu_{2}Q_{0,3}(t)$$+r_{3}Q_{0,14}(t)$$\frac{dQ_{0_{l}11}(t)}{dt}$

$=$

$=$

$=$

(47)

),

$-(\lambda_{12}+r_{2})Q_{0,12}(t)+\mu_{2}Q_{0,4}(t)$$+\lambda_{11}Q_{0,10}(t)$$\frac{dQ_{0,13}(\ell)}{dt}$

(46)

,

$-(\lambda_{22}+r_{1})Q_{0,11}(t)+\mu_{1}Q_{04}(t)$$+\lambda_{21}Q_{0,9}\langle t$$\frac{dQ_{0_{)}1}\underline{\circ}(t)}{dl}$

(45)

,

,

(48)

$-(r_{1}+r_{4})Q_{0,13}(t)+\lambda_{22}Q_{0,11}(t)$,(49)$\frac{dQ_{0,14}(t)}{dt}$$=$$-(r_{2}+r_{3})Q_{0,14}(t)+\lambda_{12}Q_{0,1^{\underline{\eta}}}(t)$(50)

with the initial conditions:$Q\mathrm{o},\mathrm{o}(0)$$=1$ ,$Q_{0,j}(0)=0$

j$=1,2,\cdots,14(.51)$

References[1] Adams, E (1984), Optimizing preventive service of the software products, IEM J. Research & Development, 28, 2-14,[8] Garg, S., Telek, M., Puliafito, A. and Trivedi,
K. S. (1995), Analysis of software rejuvenation using Markov regenerative stochastic
Petri net, Proc. 6th Int’l Symp. on Software
Reliab. Eng., 24-27 IEEE CS Press.
[9] Garg, S., Huang, Y., Kintala, C. and Trivedi,
K. S. (1996), Minimizing completion time ofa program by checkpointing and rejuvenation,
Proc. 1996 ACM SIGMETRICS Conf, 252261, ACM.

[10] Garg, S., Van Moorsel, A., Vaidyanathan, K.
and Trivedi, K. S. (1998), A methodology
for detection and estimation of software aging,
Proc. 9th Int’l Symp. on Software Reliability
Eng., 282-292, IEEE CS Press.
[11] Gray, J. (1986), Why do computers stop andwhat can be done about it?, Proc. 5th Int \prime lSympo. on Reliab. Distributed Softw are andDatabase Systems, 3-12, IEEE CS Press.

[12] Huang, Y., Kintala, C, Kolettin, N and Funton, N. D. (1995), Software rejuvenation:
analysis, module and applications, Proc. 25th
Int ’l Symp. on Fault Tolerant Computing, 381390, IEEE CS Press.

207[13] Lei, L., Vaidyanathan, K. and Trivedi, K. S.
(2002), An approach for estimation of software aging in a web server, In Proc. 2002
Int ’l Symp. on Empirical Software Eng., 91100, IEEE CS Press.

[26] Suzuki, H., Dohi, T., Kaio, N. and hivedi,
K. S. (2003), Maximizing interval reliability
in operational software system with rejuvenation, Proc. 14th Int Symp. on Softrnare Reliab. Eng., 246-256, IEEE CS Press.

[14] Liu, Y., Ma, Y., Han, J. J., Levendel, H. andTrivedi, K. S. (2002), Modeling and analysis of software rejuvenation in cable modem
termination system, Proc. 13th Int ll Symp.
on Software Reliab. Eng., 159-170, IEEE CS[27] Tai, A. T., Alkalai, L. and Chau, S. N. (1998),
On-board preventive maintenance for long-life
deep-space missions: a model-based analysis,
Proc. 3rd Annual IEEE Int Symp. on Computer Performance & Dependability Sympo.,
196-205, IEEE CS Press.

[15] Liu, Y., Mendiratta, V. and Trivedi, K.
(2004), Survivability analysis of telephone access network, Proc. 15th Int’l Symp. on Software Reliab. Eng. (in press), IEEE CS Press.

[28] ’Divedi, K. S., Vaidyanathan, K. and GosevaModeling andPostojanova, K. (2000),
analysis of software aging and rejuvenation,
Annual Simulation Symp., 270Proc.
20, IEEE CS Press.

Press.

[i6] Lyu, M. R. (1995), Sof rware Fault Tolerance,
John Wiley & Sons.
[17] Marshall, E. (1992), Fatal error: how Patriot
overlooked a scud, Science, 255, 1347.
[18] Marshall, A. W. and Olkin, I. (1967), A multivariate exponential distribution, J. American
Statist Assoc. 62, 30-40.
Reliability Evaluation[19] Osaki, S. (1980),
of Some Fault-Tolerant Computer Architectures, Lecture Notes in Computer Science 97,
Springer-Verlag.

[20] Osaki, S. (1980), Two unit parallel redundant system with bivariate exponential iifetimes, Microelectron. Reliab. 20, 521-523.
[21] Parnas, D. L. (1994), Software aging, Proc.
16th Int il Conf. on $Sof$ rware Eng., 279-287,
IEEE CS Press.
[22] Park, K. and Kim, S. (2002), Availability
analysis and improvement ofcluster systems using software rejuvenation,
J. Systems and $Sof$ rware, 61, 121-128.

$\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}/\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{b}\mathrm{y}$[23] Pullum, L. L. (2001), $Sof$ tware Fault Tolerance: Techniques and Impiernentation, Artech
House,[24]

hereshevsky, M., ukic, B., Crowel, J. andGandikota, V. (2003), Software aging andmultifractality of memory resources, Proc.
Int}l Conf. on Dependable Systems and Networks, 721-730, IEEE CS Press.

$\mathrm{S}$$\mathrm{C}$[25] Suzuki, H., Dohi, T., Goseva-Popstojanova,
K. and Trivedi, K. S. (2002), Analysis of multistep failure models with periodic software rejuvenation, Advances in Stochastic Modelling),(J. R. Artalejo and A. Krishnamoorthy,
Notable Publications, Inc., 85-108.
$e,\mathrm{d}\mathrm{s}.$$\prime l$$Jl$$\mathit{3}\mathit{3}rd$[29] Vaidyanathan, K. and ’bivedi, K. S. (1999),
A measurement -based model for estimationof resource exhaustion in operational softwaresystems, Proc. 10th $Int’ l$ Symp. on Software
Reliab. Eng., 84-93, IEEE CS Press.
[30] Vaidyanathan, K., Harper, R. E., Hunter,
S. W. and Trivedi, K. S. (2001), Analysis of software rejuvenation in cluster sysLei, Proc. A CM SIGMETRICS 2001/Performance 2001, 62-71, ACM