Compu a ionally E icien and
Nume ically S able Reliabili y Bounds o
Repai able Faul -Tole an Sys ems
Juan A. Ca asco, Membe ,IEEE
Abs ac ÐThe ansien analysis o la ge con inuous ime Ma ko eliabili y models o epai able aul - ole an sys ems is
compu a ionally expensi e due o model s i ness. In his pape , we de elop and analyze a me hod o compu e bounds o a measu e
de ined on a pa icula , bu qui e wide, class o con inuous ime Ma ko models, encompassing bo h exac and bounding con inuous
ime Ma ko eliabili y models o aul - ole an sys ems. The me hod is nume ically s able and compu es he bounds wi h well-
con olled and speci iable-in-ad ance e o . Compu a ional e o can be aded o wi h bounds accu acy. Fo a class o con inuous
ime Ma ko models, class C00, including ypical ailu e/ epai eliabili y models wi h exponen ial ailu e and epai ime dis ibu ions and
epai in e e y s a e wi h ailed componen s, he me hod can yield easonably igh bounds a a e y small compu a ional cos . The
me hod builds upon a ecen ly p oposed nume ical me hod o he ansien analysis o con inuous ime Ma ko models called
egene a i e andomiza ion.
Index Te msÐFaul - ole an sys ems, epai able sys ems, eliabili y, con inuous ime Ma ko models, bounds, andomiza ion.
æ
1INTRODUCTION
INCREASING demand o sys em dependabili y has c ea ed
g ea in e es in aul - ole an sys ems. In many applica-
ions, e.g., c i ical applica ions, an app op ia e measu e o
quan i y a sys em's dependabili y is he eliabili y, de ined
as he p obabili y ha he sys em has no ailed by ime ,
o , al e na i ely, he complemen a y un eliabili y measu e,
u  , de ined as he p obabili y ha he sys em has ailed
by ime . Homogeneous con inuous ime Ma ko chain
(CTMC) models a e commonly used o p edic he
un eliabili y o aul - ole an sys ems, pa icula ly when
he sys em is epai able. Compu a ion o he un eliabili y
hen equi es he ansien analysis o he CTMC model.
A ailable nume ical me hods o pe o m ha ansien
analysis include ODE (o dina y di e en ial equa ion)
sol e s and andomiza ion (also called uni o miza ion)
[12], [13], [19]. The andomiza ion me hod is a ac i e
because i is nume ically s able and he compu a ion e o is
well con olled and can be speci ied in ad ance. Howe e ,
he pe o mance o andomiza ion is se iously a ec ed by
model s i ness. Fo CTMC models, a p ac ical measu e o
s i ness is  [19], whe e is he maximum ou pu a e o he
model. Fo la ge  , andomiza ion equi es a numbe o
s eps  and will be highly ine icien i he model is la ge.
CTMC eliabili y models o epai able aul - ole an
sys ems end o be e y s i when he mission ime o
in e es is la ge. To illus a e he poin , Fig. 1 shows a small
CTMC eliabili y model X X ; 0go a epai able
aul - ole an sys em using he pai -and-spa e echnique [9]
in which ac i e modules ha e ailu e a e M, he spa e
module does no ail, he ailu e o an ac i e module is
ªso º wi h p obabili y SMand ªha dº wi h p obabili y
1SM, and, whe he so o ha d, he ailu e o an ac i e
module is co e ed wi h p obabili y CM. Modules in so
ailu e a e independen ly eco e ed a a e Sand modules
in ha d ailu e a e epai ed by a single epai man a a e H.
The un eliabili y o he sys em is u  PX  . Fo
he model, 2SM120 h1and, o a mission ime
1 yea 8;760 h, 1;051;200.
Se e al a ian s o he (s anda d) andomiza ion me hod
ha e been p oposed o imp o e i s e iciency: selec i e
andomiza ion [14], [15], mul is epping [19, Sec ion 3.1.2],
adap i e uni o miza ion [16], adap i e/s anda d uni o mi-
za ion [17], uni o miza ion wi h s eady-s a e de ec ion [12],
[21], and egene a i e andomiza ion [5], [6]. Fo la ge
CTMC eliabili y models o epai able aul - ole an
sys ems and long mission imes, egene a i e andomiza-
ion seems o be he bes o hem. The me hod has he
same good p ope ies as he s anda d andomiza ion
me hod (nume ical s abili y, well-con olled compu a ion
e o , and abili y o speci y he compu a ion e o in ad ance)
and can be much as e han s anda d andomiza ion.
The egene a i e andomiza ion me hod co e s CTMC
models X X ; 0gwi h s a e space
S[ 1;
2;...;
Ag;jSj2;A0;
whe e ia e abso bing s a es and ei he 1) all s a es in S
a e ansien o 2) Shas a single apping componen
1
and he chosen egene a i e s a e 2Sbelongs o ha
componen , and all s a es a e eachable om some s a e
wi h nonnull ini ial p obabili y. I is also assumed ha X
254 IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 3, MARCH 2002
.The au ho is wi h he Depa men d'Enginye ia Elec o
Ánica, Uni e si a
Poli e
Ácnica de Ca alunya, Diagonal 647, pl a. 9, 08028 Ba celona, Spain.
E-mail: [email p o ec ed].
Manusc ip ecei ed 1 Ap . 2000; e ised 21 Feb. 2001; accep ed 7 Ap . 2001.
Fo in o ma ion on ob aining ep in s o his a icle, please send e-mail o:
[email p o ec ed], and e e ence IEEECS Log Numbe 111155.
1. Two s a es i,jo a CTMC a e s ongly connec ed i he e a e pa hs in
he s a e ansi ion diag am o he CTMC om i o jand om j o i; a s a e
is s ongly connec ed wi h i sel ; a componen is a maximal subse o
s ongly connec ed s a es; a componen is apping i no s a e o he
componen has ansi ion a es o s a es ou side he componen .
0018-9340/02/$17.00 ß2002 IEEE
has some ansi ion a e om o S0 g, al hough ha
condi ion can be easily ci cum en ed in p ac ice [5]. The
gene ic measu e conside ed in [5] is
m X
A
i1
iPX  i;
A1, whe e ia e di e en ewa d a es 0(in [6], mo e
gene al measu es a e conside ed and A0is allowed).
Those models wi h A1and he gene ic measu e m 
co e bo h exac and bounding CTMC eliabili y models o
aul - ole an sys ems (bounding models a e use ul when
an exac model would ha e an unmanageable size). In an
exac eliabili y model, Awould be equal o 1, Swould
include all ope a ional s a es, en y in 1would ep esen
he ailu e o he sys em, 1would be equal o 1, he ini ial
p obabili y o 1would be equal o he p obabili y o he
sys em being ini ially ailed, and m would be he
un eliabili y u  (an example o such an exac eliabili y
model is he model gi en in Fig. 1 wi h S 1;2;3;4;5;6g
and 1 ). In a lowe bounding eliabili y model, Awould
be equal o 2, Swould be a p ope subse o he se o
ope a ional s a es, en y in 1would ep esen he ailu e o
he sys em om a s a e in S, en y in 2would ep esen
en y in an ope a ional s a e ou side S, 1would be
equal o 1, 2would be equal o 0, he ini ial p obabili y o
1would be equal o he p obabili y o he sys em being
ini ially ailed, he ini ial p obabili y o 2would be he
p obabili y o he sys em being ini ially in an ope a ional
s a e ou side S, and m would be a lowe bound o u  .
Finally, in an uppe bounding eliabili y model, Awould be
equal o 1, Swould be a p ope subse o he se o
ope a ional s a es, en y in 1would ep esen exi om S,
1would be equal o 1, he ini ial p obabili y o 1would be
he p obabili y o he sys em being ini ially ei he ailed o
in an ope a ional s a e ou side S, and m would be an
uppe bound o u  . The egene a i e andomiza ion
me hod equi es he selec ion o a egene a i e s a e 2S.
The pe o mance o he me hod depends on ha selec ion.
In his pape , we conside CTMC models wi h he same
s uc u e and p ope ies as he models conside ed in
egene a i e andomiza ion wi h A1and de elop a
me hod called bounding egene a i e andomiza ion o ob ain
bounds o he gene ic measu e m . The me hod yields a
lowe bound o m , an uppe bound o m , o bo h.
The lowe bound is ob ained by sol ing, by egene a i e
andomiza ion, a lowe bounding CTMC, Xlb. The uppe
bound is ob ained by sol ing, by egene a i e andomiza-
ion, an uppe bounding CTMC, Xub. Bo h Xlb and Xub a e
ob ained om Xby scaling some o i s ansi ion a es.
The me hod has he same good p ope ies as s anda d
andomiza ion.
Al hough no es ic ed o hem, he bounding egen-
e a i e andomiza ion me hod is in ended o be used o a
class o models C00. Le i;j deno e he ansi ion a e o X
om s a e i o s a e j,i6 j, le iPj2 igi;j deno e
he ou pu a e om s a e i, and le i;B Pj2Bi;j,
B ig. Class C00 includes he models Xwi h he
p ope ies assumed in he egene a i e andomiza ion
me hod wi h A1 o which he e exis s a pa i ion S0[
S1[[SNC o Ssa is ying he ollowing h ee p ope ies:
P1. S0 og(i.e., jS0j1).
P2. max0kNCmaxi2Ski;Sk ig[Sk1[[SNCis signi ican ly
smalle han
min
0<kNC
min
i2Sk
i;S0[[Sk1[ 1;...; Ag>0:
P3. omini2S ogi.
The class co e s ailu e/ epai eliabili y models wi h
exponen ial ailu e and epai ime dis ibu ions and epai
in e e y s a e wi h ailed componen s when ailu e a es a e
signi ican ly smalle han epai a es ( he ypical case),
such as he model gi en in Fig. 1. Fo hose models, a
pa i ion o which p ope ies P1, P2, and P3 a e sa is ied is
Sk{s a es in Swi h k ailed componen s}. The class also
CARRASCO: COMPUTATIONALLY EFFICIENT AND NUMERICALLY STABLE RELIABILITY BOUNDS FOR REPAIRABLE FAULT-TOLERANT... 255
Fig. 1. CTMC eliabili y model o a epai able aul - ole an sys em using he pai -and-spa e echnique.
co e s ailu e/ epai eliabili y models wi h exponen ial
ailu e ime dis ibu ions, epai imes wi h acyclic phase-
ype dis ibu ions [18] (which can be used o i dis ibu-
ions o nonexponen ial posi i e andom a iables [3]), and
epai in e e y s a e wi h ailed componen s, p o ided ha
he ansi ion a es o he ansien CTMCs de ining he
phase- ype dis ibu ions a e su icien ly la ge compa ed
wi h ailu e a es. Fo hose models, he p oposed me hod
can be ex emely e icien and, ye , p o ide qui e igh
bounds. Tigh e bounds can be ob ained a he cos o
inc eased compu a ional e o .
An app oach o deal wi h s i ness is he agg ega ion
echnique p oposed in [2]. Fo class C00 models, ha
echnique could be used o agg ega e he s a es in S og,
yielding an agg ega ed CTMC model wi h a ansien s a e
and Aabso bing s a es wi h symbolic solu ion. The
agg ega ion would be done by eplacing each s a e in
S ogby a swi ch and is equi alen o scale he
ansi ion a es i;j,i2S ogwi h i!1, keeping he
ela i e alues o he ansi ion a es om a gi en s a e.
The agg ega ed model would gi e an uppe bound o he
measu e m loose han he uppe bounds ha a e
compu ed by he bounding egene a i e andomiza ion
me hod p oposed in his pape .
The es o he pape is o ganized as ollows: Sec ion 2
p esen s a b ie e iew o bo h he s anda d andomiza ion
and he egene a i e andomiza ion me hods ( he la e
pa icula ized o he compu a ion o he measu e m ),
including algo i hmic desc ip ions o bo h me hods.
Sec ion 3 desc ibes he p oposed bounding egene a i e
andomiza ion me hod, p o es ha i yields bounds o
he measu e m , and gi es heo e ical esul s assessing
he e iciency o he me hod o class C00 models. Sec ion 4
analyzes he pe o mance o he bounding egene a i e
andomiza ion me hod using a la ge eliabili y model
belonging o class C00 and compa es he compu a ional cos
o he me hod wi h ha o egene a i e andomiza ion
and s anda d andomiza ion. Finally, Sec ion 5 concludes
he pape .
2REVIEW OF STANDARD AND REGENERATIVE
RANDOMIZATION
The e iew o he s anda d andomiza ion me hod will be
made o a bi a y ewa ded CTMC models X X ; 
0gwi h ini e s a e space and o he expec ed ansien
ewa d a e measu e
ETRR E X X
i2
iPX i;
whe e i0,i2is he ewa d a e associa ed wi h s a e i.
The quan i y ihas he meaning o ª a eº a which ewa d
is ea ned while Xis in s a e i. The measu e m is a
pa icula case o ETRR . The s anda d andomiza ion
me hod is based on he ollowing esul (see, o ins ance,
[10, Theo em 4.19]). Conside any maxi2iand de ine
he homogeneous disc e e ime Ma ko chain (DTMC) ^
X
^
Xk;k0;1;2;...gwi h same s a e space and ini ial
p obabili y dis ibu ion as Xand ansi ion p obabili ies
Pi;j i;j=,i6 j,Pi;i 1i=. The DTMC ^
Xis called
he andomized DTMC o Xwi h andomiza ion a e .
The CTMC Xis said o be he de andomized CTMC o ^
X
wi h andomiza ion a e . Le Q Q ; 0gbe a
Poisson p ocess wi h a i al a e independen o ^
X
(PQ ke  k=k!). Then, X X ; 0gis
p obabilis ically iden ical o ^
XQ ; 0g.Tha esul
allows exp essing ETRR in e ms o he ansien egime
o ^
Xas:
ETRR X
i2
iX
1
k0
P^
XkiPQ k
X
1
k0X
i2
iP^
Xkie  k
k!
X
1
k0
dke  k
k!;1
wi h dkPi2 iP^
Xki. Le  PX0ii2be
he ini ial p obabili y ow ec o o Xand le qk
P^
Xkii2be he p obabili y ow ec o o ^
Xa s ep k.
We ha e q0. F om q0,qk,k>0can be ob ained
using qk1qkP, whe e PPi;ji;j2is he ansi-
ion p obabili y ma ix o ^
X.
An app oxima e alue o ETRR ,ETRRa
N , can be
ob ained by unca ing se ies (1):
ETRRa
N X
N
k0
dke  k
k!:2
Using dk max maxi2 i, he unca ion e o can be
uppe bounded as
ETRR ETRRa
N  max X
1
kN1
e  k
k!:3
Then, "being he allowed e o o he compu a ion o
ETRR , in he s anda d andomiza ion me hod Nis
chosen as
Nminnm0: max X
1
km1
e  k
k!"o;
and ETRR is app oxima ed wi h e o "by he
ETRRa
N gi en by (2). The compu a ional cos o
s anda d andomiza ion is essen ially he cos o pe o m-
ing he N ec o -ma ix mul iplica ions qk1qkP,
k0;1;...;N1.Q has, o  !1, an asymp o ic
no mal dis ibu ion wi h mean and a iance  [20], and,
o la ge  and "1, he equi ed Nis  , making
s anda d andomiza ion compu a ionally e y expensi e i
bo h Xand  a e la ge. Since he pe o mance o s anda d
andomiza ion deg ades as inc eases, is usually aken
equal o maxi2i. An algo i hmic desc ip ion o he
s anda d andomiza ion me hod is gi en in Fig. 2. The
algo i hm has as inpu s he CTMC X, he ewa d a es
i,i2, he ini ial p obabili y ow ec o , he
allowed e o ", he numbe o ime poin s na which
ETRR has o be compu ed, and he ime poin s
1;
2;...;
n. The algo i hm has as ou pu s he compu ed
256 IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 3, MARCH 2002
alues o ETRR ,g
ETRR 1;g
ETRR 2;...;g
ETRR n.
The unca ion e o bound gi en by (3) inc eases wi h
and, he e o e, ha e o is con olled o
max max 1;
2;...;
ng:
We e iew nex he egene a i e andomiza ion me hod
o he CTMC models Xconside ed in his pape and he
measu e m . Le S0S gand le iPX0i,
i2. We will use he no a ion BPi2Bi. In he me hod,
he beha io o X om S0up o s a e o a s a e iand om
un il he nex hi o o a s a e iis app oxima ely
cha ac e ized by a unca ed ans o med model om
which an app oxima e alue wi h bounded e o o m 
can be compu ed and ha app oxima e alue is compu ed
sol ing he unca ed ans o med model by he s anda d
andomiza ion me hod. To build he unca ed ans o med
model, wo DTMCs, Zand Z0[5], ob ained om he
andomized DTMC ^
Xo Xwi h a e and a e sion ^
X0o
^
Xin which he ini ial p obabili y dis ibu ion is concen-
a ed in s a e , ha e o be s epped in gene al. The
andomiza ion a e is aken sligh ly la ge han maxi2Si
(i.e., 1maxi2Si,being a small alue, say 104).
This simpli ies conside ably he desc ip ion and implemen-
a ion o he me hod and has negligible impac on i s
pe o mance. The ansi ion p obabili y ma ix o ^
Xwill be
deno ed as be o e by PPi;ji;j2.TheDTMCZ
Zk;k0;1;2;...g ollows ^
X om ill een y in .Z
has s a e space S[ 1;
2;...;
A;ag, whe e iand aa e
abso bing s a es and all s a es in Sa e ansien , ini ial s a e
, and i s (possibly nonnull) ansi ion p obabili ies a e:
PZk1jjZkiPi;j;i2S;j 2S0[ 1;
2;...;
Ag;
PZk1ajZkiPi; ;i2S;
PZk1 ijZk iPZk1ajZka1;1iA:
The DTMC Z0 Z0
k;k0;1;2;...g ollows ^
Xun il i s i s
isi o s a e .Z0has s a e space S0[ 1;
2;...;
A;ag,
whe e iand aa e abso bing s a es and all s a es in S0a e
ansien . The ini ial p obabili y dis ibu ion o Z0is
PZ0
0ii,i2S0[ 1;
2;...;
Ag,PZ0
0a , and
i s (possibly nonnull) ansi ion p obabili ies a e:
PZ0
k1jjZ0
kiPi;j;i2S0;j2S0[ 1;
2;...;
Ag;
PZ0
k1ajZ0
kiPi; ;i2S0;
PZ0
k1 ijZ0
k iPZ0
k1ajZ0
ka1;1iA:
Le ikPZki,0
ikPZ0
kiand conside he
ow ec o s kiki2Sand 0k0
iki2S0. Le PZ
be he ansi ion p obabili y ma ix o Z es ic ed o S
and le PZ0be he ansi ion p obabili y ma ix o Z0
es ic ed o S0. F om 0,k,k>0can be ob ained
using k1kPZ. F om 00,0k,k>0can be
ob ained using 0k10kPZ0. Le
akX
i2S
ik;
j
kX
i2S
ikPi; j=ak;
qkX
i2S
ikPi; =ak;
wkX
i2S
ikPi;S0=ak;
and, i S0>0, le
a0kX
i2S0
0
ik;
0j
kX
i2S0
0
ikPi; j=a0k;
q0
kX
i2S0
0
ikPi; =a0k;
w0
kX
i2S0
ikPi;S0=a0k;
whe e Pi;S0Pj2S0Pi;j (akand, i S0>0,a0ka e
gua an eed o be >0(see [5])). Then, o he case S0>0,
CARRASCO: COMPUTATIONALLY EFFICIENT AND NUMERICALLY STABLE RELIABILITY BOUNDS FOR REPAIRABLE FAULT-TOLERANT... 257
Fig. 2. Algo i hmic desc ip ion o s anda d andomiza ion.
he unca ed ans o med model is he CTMC VK;L 
VK;L ; 0gwi h s a e space
sk;0kKg[ s0
k;0kLg[ 1;
2;... A;ag;
ini ial p obabili y dis ibu ion
PVK;L0s0 ;
PVK;L0s0
0S0;
PVK;L0 i i;
PVK;L0i0;i62 s0;s
0
0;
1;
2;...;
Ag;
and he s a e ansi ion diag am illus a ed in Fig. 3 o
A1. Fo he case S00, he unca ed ans o med
model is he CTMC VK VK ; 0gwi h ini ial p ob-
abili y dis ibu ion PVK0s0S,PVK0 i i,
PVK0i0,i62 s0;
1;
2;...;
Agand a s a e ansi-
ion diag am iden ical o he s a e ansi ion diag am o
VK;L, bu wi hou s a es s0
k.
Fo he case S0>0, he app oxima e alue o m 
gi en by VK;L is
ma
K;L X
A
i1
iPVK;L  i
and we ha e
m ma
K;L  maxa0LX
1
kL1
e  k
k!
 maxSaKX
1
kK1
kKe  k
k!;
4
whe e max max1iA i. Fo he case S00, he app ox-
ima e alue o m gi en by VKis:
ma
K X
A
i1
iPVK  i
and we ha e
m ma
K  maxSaKX
1
kK1
kKe  k
k!:5
The model unca ion e o bounds gi en by (4) and (5)
dec ease o inc easing Kand Land can be made
a b i a ily small by choosing la ge enough alues o K
and L. In egene a i e andomiza ion, "being he allowed
e o o he compu a ion o m , sui able unca ion
pa ame e s K,La e chosen so ha he model unca ion
e o bounds a e smalle han "=2and, hen, an app ox-
ima e alue o m is ob ained by compu ing ma
K;L 
(ma
K ) by sol ing he unca ed ans o med model VK;L
(VK) by s anda d andomiza ion wi h e o uppe bounded
by "=2.
An algo i hmic desc ip ion o he egene a i e andomi-
za ion me hod is gi en in Fig. 4, whe e Icdeno es he
indica o unc ion e u ning he alue 1 i condi ion cis
sa is ied and he alue 0 o he wise. The algo i hm has as
inpu s he CTMC X, he numbe Ao abso bing s a es i,
he ewa d a es 1;
2;...;
A, an ini ial p obabili y
dis ibu ion ec o  ii2wi h S>0, he egene a i e
s a e , he allowed e o ", he numbe o ime poin s na
which m has o be compu ed, and he ime poin s
1;
2;...;
n. The algo i hm has as ou pu s he compu ed
alues o m ,e
m 1;e
m 2;...;e
m n. Since he model
unca ion e o bounds inc ease wi h , hey a e con olled
o max max 1;
2;...;
ng. Fo he case S0>0, he "=2
alloca ed o he model unca ion e o bound is di ided
equally be ween i s wo con ibu ions. The unca ion e o
bound associa ed wi h he solu ion o he unca ed
ans o med model by s anda d andomiza ion also in-
c eases wi h and ha e o is con olled o max. The
me hod equi es s epping he andomized DTMC ^
VK;L (^
VK)
o VK;L (VK) wi h a e . The s a e ansi ion diag am o ^
VK;L
is illus a ed in Fig. 5 o A1. The s a e ansi ion diag am
o ^
VKis iden ical, bu wi hou he s a es s0
k.
The egene a i e andomiza ion me hod (as he s anda d
andomiza ion me hod) equi es he compu a ion o he
Poisson p obabili ies e  k=k!. S able and e icien
compu a ion o hose Poisson p obabili ies, a oiding o e -
lows and in e media e unde lows, is a delica e issue and
258 IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 3, MARCH 2002
Fig. 3. S a e ansi ion diag am o he CTMC VK;L o A1.

se e al al e na i es ha e been p oposed [4], [8], [11], [17].
The me hod desc ibed in [11, pp. 1028±1029] (see also [1])
has good nume ical s abili y and is he one we ollow in ou
implemen a ions. The egene a i e andomiza ion me hod
in ol es he compu a ion o
Sm X
1
km1
e max  maxk=k!
and
S0m X
1
km1
kme max  maxk=k!
o inc easing alues o m( he s anda d andomiza ion
me hod also equi es he compu a ion o Sm o inc eas-
ing alues o m). Ou implemen a ions use he algo i hms
desc ibed in [5], which a e nume ically s able and e icien .
The compu a ional cos o egene a i e andomiza ion
has wo componen s: cos associa ed wi h he cons uc ion
o he unca ed ans o med model and cos associa ed
wi h he solu ion o he unca ed ans o med model by
s anda d andomiza ion. The i s is oughly p opo ional
o he numbe o s eps on he DTMCs Z,Z0,KLi S0>0
and Ki S00, wi h a cos pe s ep which, o la ge X, will
ypically be sligh ly la ge han he cos pe s ep in s anda d
andomiza ion. The second componen is oughly p opo -
ional o he unca ion pa ame e N(app oxima ely equal
o he unca ion pa ame e No s anda d andomiza ion)
and o he size o he unca ed ans o med model. I is
shown in [5] ha he equi ed Kis Olog =" and, i
S0>0, he equi edLis Olog1=".Tha iscalled
ªbenignº beha io and implies ha , o la ge enough X
and la ge enough  , egene a i e andomiza ion will be
signi ican ly as e han s anda d andomiza ion.
The pe o mance o egene a i e andomiza ion depends,
o cou se, on he selec ion o he egene a i e s a e . Tha
selec ion should be made so ha akand a0kdec ease as
as as possible and he equi ed Kand La e as small as
possible. Since class C00 models mo e as o ei he s a e oo
an abso bing s a e i, a na u al selec ion o hose models is
o. Le R0maxi2S ogi=mini2S ogi. Then, we can
s a e he ollowing esul :
Theo em 1. Fo class C00, models wi h selec ion o,ak
hkand a0kS0h0k, whe e, o k!1,
CARRASCO: COMPUTATIONALLY EFFICIENT AND NUMERICALLY STABLE RELIABILITY BOUNDS FOR REPAIRABLE FAULT-TOLERANT... 259
Fig. 4. Algo i hmic desc ip ion o egene a i e andomiza ion.
hkBk
p1

k;
and
h0kB0k
p01

0k;
wi h B>0,B0>0,p,p0in ege s 1,11=R0, and
011=R0.
2
P oo . The model class C00 is a subse o he model class C
conside ed in [5]. In [5], i is conside ed he pa ame e
Rmaxi2Si=mini2S0i. Fo class C00 models, i ollows
om P ope y P3 ha , wi h selec ion o,RR0and
he esul ollows om Theo em 4 o [5] and he
discussion ollowing i . u
Theo em 1 asse s ha , o class C00 models, he
pe o mance o egene a i e andomiza ion wi h he na -
u al selec ion oshould be mainly de e mined by he
pa ame e R0: he la ge R0, he mo e cos ly he me hod. In
pa icula , o R01,0and 00and he me hod
should be e y e icien . Those obse a ions mo i a e he
bounding egene a i e andomiza ion me hod.
3THE BOUNDING REGENERATIVE RANDOMIZATION
METHOD
The bounding egene a i e andomiza ion me hod ob ains
a lowe bound o m , an uppe bound o m , o bo h.
The bounds a e compu ed wi h an e o uppe bounded by
a"gi en by he use . Depending on he na u e o he CTMC
model X, one o he o he bound o bo h bounds could be o
in e es . Thus, i Xis an exac eliabili y model, bo h
bounds would be o in e es o ha e an assessmen o he
e o on u  . Howe e , i an exac eliabili y model canno
be used because i s size would be unmanageable, hen we
could use a lowe bounding eliabili y model and an uppe
bounding eliabili y model and use bounding egene a i e
andomiza ion o compu e a lowe bound o he lowe
bound o he un eliabili y gi en by he i s model and an
uppe bound o he uppe bound o he un eliabili y gi en
by he second model: he exac un eliabili y would be
b acke ed by hose alues.
The bounding egene a i e andomiza ion me hod
equi es he selec ion o a egene a i e s a e 2Sand
has an inpu pa ame e Dcon olling he accu acy o he
bounds. Le min mini2S0iand max maxi2S0i. The
me hod assumes ha he con olling pa ame e Dis
es ic ed by 1D<
max=min.
3
To ob ain he lowe bound
o m , he me hod modi ies he CTMC X o ob ain a
CTMC Xlb. The CTMC Xlb is ob ained om Xby
scaling he ansi ion a es om s a es in S0so ha ,
calling lb
i he ou pu a es o Xlb,lb
ii,i2S0and
maxi2S0lb
i=mini2S0lb
iD. Tha scaling is de ined by
lb
i;j i;jlb
i=i,lb
imin i;D
ming,i2S0,whe elb
i;j
a e he ansi ion a es in Xlb. The lowe bound o m is
gi en by
mlb X
A
i1
iPXlb  i:
Tha lowe bound is ob ained by sol ing Xlb by egen-
e a i e andomiza ion wi h egene a i e s a e . To ob ain
he uppe bound o m , he me hod modi ies he CTMC
X o ob ain a CTMC Xub. The CTMC Xub is ob ained om
Xby scaling he ansi ion a es om s a es in S0so ha ,
calling ub
i,i2S0 he ou pu a es o Xub,ub
ii,i2S0and
maxi2S0ub
i=mini2S0ub
iD. Tha scaling is de ined by
ub
i;j i;jub
i=i,ub
imax i;
max=Dg,i2S0. The uppe
bound o m is gi en by
mub X
A
i1
iPXub  i:
Tha uppe bound is ob ained by sol ing Xub by egen-
e a i e andomiza ion wi h egene a i e s a e .
The pa icula case in which bo h bounds a e o be
compu ed, D1and min  allows a mo e e icien
implemen a ion o he bounding egene a i e andomiza-
ion me hod han ha desc ibed in he p e ious pa ag aph.
To jus i y ha pa icula implemen a ion, we will use he
ollowing esul :
260 IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 3, MARCH 2002
Fig. 5. S a e ansi ion diag am o he DTMC ^
VK;L o A1.
2. ckdk o k!1deno es limk!1 ck=dk1.
3. Fo class C00 models wi h he selec ion o, when max min and no
selec ion o Dis possible, egene a i e andomiza ion should be e y
e icien because o Theo em 1 and he ac ha R01, ob ia ing he need
o he bounding egene a i e andomiza ion me hod.
Lemma 1. Fo x>0,K0, and R>1,
1
RX
1
kK1
kKeRx Rxk
k!>X
1
kK1
kKexxk
k!:
P oo . See he Appendix. u
Fo ha pa icula case, deno ing by supe sc ip s lb and ub
he e ms e e ed o, espec i ely, Xlb and Xub and he
objec s in ol ed in hei solu ion by egene a i e andomi-
za ion, and le ing R00 max=min >1(because D1and
D<
max=min), we ha e lb
;j ub
;j and, no ing ha lb
i
min and ub
imax,i2S0, we ha e lb
i;j ub
i;j =R00,i2S0.We
also ha e lb ub=R00 (because lb
ub
 min,
lb
imin,i2S0,ub
imax,i2S0, and max >
min). I
ollows ha he ansi ion p obabili ies o he andomized
DTMCs ^
Xlb and ^
Xub a e ela ed as Plb
;j R00Pub
;j ,j6 ,
Plb
; 1R001Pub
; and, o i2S0,Plb
i;j Pub
i;j . Then,
aking in o accoun ha he ansi ion p obabili ies o he
DTMCs Zlb and Zub om o j2S0a e, espec i ely, Plb
;j
and Pub
;j , ha he ansi ion p obabili ies o Zlb and Zub wi hin
S0a e, espec i ely, Plb
i;j and Pub
i;j and ha he ini ial s a e o Zlb
and Zub is , we ha e, o k1,lb
ikR00ub
ikand
albkR00aubk. Then, using alb0aub01, we ha e
jlb
0Plb
; jR00Pub
; jR00 jub
0;
qlb
0Plb
; 1R001Pub
; 1R001qub
0;
wlb
0Plb
;S0R00Pub
;S0R00wub
0;
and, aking in o accoun ha lb
kub
k0,k1, o
k1, we ha e
jlb
kPi2S0lb
ikPlb
i; j
albkPi2S0R00ub
ikPub
i; j
R00aubk
Pi2S0ub
ikPub
i; j
aubk jub
k
and, simila ly, qlb
kqub
kand wlb
kwub
k. On he o he
hand, he DTMCs Z0lb and Z0ub ha e iden ical ini ial
p obabili y dis ibu ions and ansi ion p obabili ies and,
hen, a0lbka0ubk,and,usingPlb
i;j Pub
i;j ,i2S0,
0jlb
k 0jub
k,q0lb
kq0ub
k,w0lb
kw0ub
k. Fo m1,
maxSaubmX
1
km1
kmeub max ub maxk=k!
 maxSalbm=R00X
1
km1
kmeR00lb max R00lb maxk=k!
>
maxSalbmX
1
km1
kmelb max lb maxk=k!;
by Lemma 1 wi h Km,xlb max and RR00, implying
Kub Klb.I S0>0, o m1,ub >lb implies
4
maxa0ubmX
1
km1
eub max ub maxk=k!
 maxa0lbmX
1
km1
eub max ub maxk=k!
>
maxa0lbmX
1
km1
elb max lb maxk=k!;
implying Lub Llb. Then, i we s a by compu ing he
uppe bounds mub using Xub and sa e aubk, jub
k,qub
k,wub
k,
and, i S0>0,a0ubk, 0jub
k,q0ub
k,w0ub
k,wecanuse he
ela ionships be ween hose pa ame e s and he co espond-
ing pa ame e s o Xlb o a oid s epping Zlb and Z0lb when
compu ing he lowe bounds mlb .
An algo i hmic desc ip ion o he bounding egene a i e
andomiza ion me hod, including he p e iously discussed
pa icula implemen a ion, is gi en in Fig. 6. The algo i hm
has as inpu s he CTMC X, he numbe Ao abso bing
s a es i, he ewa d a es 1;
2;...;
A,anini ial
p obabili y dis ibu ion ec o  ii2wi h S>0,
pa ame e s lb and ub indica ing, espec i ely, whe he he
lowe and uppe bounds o m a e desi ed o no , he
egene a i e s a e , he con olling pa ame e D, he
allowed e o ", he numbe o ime poin s na which
mlb ,mub ha e o be compu ed, and he ime poin s
1;
2;...;
n. The algo i hm has as ou pu s he compu ed
alues o mlb ,e
mlb 1;e
mlb 2;...;e
mlb nand o mub ,
e
mub 1;e
mub 2;...;e
mub n. The algo i hmic desc ip ion
makes e e ence o DTMCs ^
VK;L (S0>0) and ^
VK(S00).
Those DTMCs a e he andomized DTMCs wi h andomi-
za ion a e lb o he unca ed ans o med models o Xlb
used in he solu ion o Xlb by egene a i e andomiza ion.
Fo he case S0>0,^
VK;L has s a e space
sk;0kKg[ s0
k;0kLg[ 1;
2;...;
A;ag;
ini ial p obabili y dis ibu ion
P ^
VK;L0s0 ;
P ^
VK;L0s0
0S0;
P ^
VK;L0 i i;
P ^
VK;L0i0;i62 s0;s
0
0;
1;
2;...;
Ag
and he s a e ansi ion diag am illus a ed in Fig. 5 o he
case A1, whe e K,L, j
k,qk,wk, 0j
k,q0
k, and w0
kha e he
alues compu ed in he algo i hm. Fo he case S00,^
VK
is he DTMC wi h ini ial p obabili y dis ibu ion
P ^
VK0s0S;
P ^
VK0 i i;
P ^
VK0i0;i62 s0;
1;
2;...;
Ag
CARRASCO: COMPUTATIONALLY EFFICIENT AND NUMERICALLY STABLE RELIABILITY BOUNDS FOR REPAIRABLE FAULT-TOLERANT... 261
4. The inequali y comes om he ac ha P1
km1e  k=k!is he
p obabili y ha he numbe o a i als in he in e al 0; in a Poisson
p ocess wi h a i al a e is m1, which is inc easing wi h , and,
he e o e, wi h .
and s a e ansi ion diag am iden ical o he s a e ansi ion
diag am o ^
VK;L, bu wi hou s a es s0
k.
In he ollowing, we p o e he co ec ness o he me hod,
i.e., mlb m mub . To ha end, we conside he
embedded DTMC o X, k;k0;1;2;...g:has
same s a e space and ini ial p obabili y dis ibu ion as X
and ansi ion p obabili ies i;j i;j=i,i2S,j2 ig,
i;i 0,i2S, i; i1,1iA, i;j 0,j6 i. The
beha io o Xcan be desc ibed in e ms o he DTMC by
saying ha he sequence o s a es isi ed by Xis gi en by 
wi h sojou n imes in each s a e io Xexponen ially
dis ibu ed wi h pa ame e i, independen ly on he pa h
ollowed by . Tha in e p e a ion is usually e e ed o as
he ªs uc u eº o X[7, Sec ion 8.3]. Since Xlb and Xub ha e
262 IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 3, MARCH 2002
Fig. 6. Algo i hmic desc ip ion o bounding egene a i e andomiza ion.