Failu e Dis ance Based Bounds o S eady-s a e A ailabili y wi hou he
Knowledge o Minimal Cu s
V´ıc o Su˜n´e and Juan A. Ca asco
Depa amen d’Enginye ia Elec `onica
Uni e si a Poli `ecnica de Ca alunya
Diagonal 647, pl a. 9, 08028 Ba celona, Spain
sunye, ca asco
g
@eel.upc.es
Abs ac
We p opose an algo i hm o compu e bounds o he s eady-
s a e una ailabili y using con inuous- ime Ma ko chains,
which is based on he ailu e dis ance concep . The algo-
i hm gene a es inc emen ally a subse o he s a e space
un il he igh ness o he bounds is he speci ied one. In
con as wi h a p e ious algo i hmalso based on he ailu e
dis anceconcep , hep oposedalgo i hmuses lowe bounds
o ailu e dis ances which a e compu ed on he aul ee o
he sys em, and does no equi e he knowledgeo he mini-
mal cu s. This is ad an ageouswhen he numbe o minimal
cu s is la ge o hei compu a ionis ime-consuming.
1. In oduc ion
Con inuous- imeMa ko chain models (CTMC)a e a lexi-
ble, powe ul ool o compu ing s eady-s a e dependabili y
measu es o aul ole an sys ems such as he s eady-s a e
a ailabili y,
A
. Howe e , he s eady-s a e p obabili ydis i-
bu ion o he CTMC modeling ealis ic sys ems, and, hus,
A
, canno be compu ed exac ly in many cases because o he
eno mous size o he s a e space o he CTMC. Bounding
echniques a e an a ac i e app oach. Using hose ech-
niques, only a subse
G
o he s a e space o he CTMC
is gene a ed and he beha io o he sys em ou side
G
is
bounded somehow. Bounding echniques ha e been de el-
oped in he las ew yea s and cu en ly he e exis se e al
bounding me hods [2, 3, 4, 12, 13, 14, 15, 19]. In he
i s o such me hods [15], bounds o he s eady-s a e un-
a ailabili y UA
=1
,
A
a e ob ained by pa i ioning he
non-gene a ed po ion
U
acco ding o he numbe o ailed
componen s and bounding he beha io o he chain in
U
usinguppe bounds o he ailu e ansi ion a es and lowe
bounds o he epai ansi ion a es. The me hod is, how-
e e , compu a ionally e y cos ly because a linea sys em o
size
j
G
j
has o be sol ed o each e u n s a e, i.e. each
s a e h ough which
G
can be en e ed om
U
.In hesame
pape , a s a e cloning echnique is p oposed which educes
he numbe o linea sys ems which ha e o be sol ed bu
in oduces some looseness in he bounds. In [12] a e ine-
men o he me hod is p oposed o he pa icula case in
which all s a es bu he one wi hou ailed componen s a e
cloned. The echnique a oids a comple e eapplica ion o
he algo i hm each ime
G
is enla ged in he sea ch o he
desi ed accu acy bu looses up u he he bounds. This ad-
di ional looseness has been educed in ano he pape om
he same au ho s [13]. In he me hod p oposed in [4], he
bounds o [15] a e compu ed wi hou cloning s a es sol ing
only ou linea sys ems o size
j
G
j
. In [19] ano he bound-
ing me hod is de eloped in which he bounds a e i e a i ely
e ined using de ailed knowledge abou he model in
U
in
he p oximi ies o
G
. In [2] a bounding me hod based on
he ailu edis ance concep isp oposed whichgi es bounds
o UA which a e ne e wo se, and ypically be e , han
hose gi en by[15]. The me hod uses hecloning echnique
o [15] bu adap s one o he algo i hms de eloped in [4] so
ha only i e linea sys ems o size
j
G
j
ha e o be sol ed o
compu e he p oposed bounds.
The p e ious me hods assume ha he s a e space o he
CTMC is ini e and ha he e is a ansi ion o he le in all
non-gene a ed s a es o he CTMC. Bo h es ic ions ha e
been emo ed in hegene aliza ion o [15] p oposedin [14].
Ano he gene aliza ion o [15] o ini e CTMCs has been
ecen ly p oposed in [3]. In ha me hod, g oup epai and
phase ype epai dis ibu ionsa e allowed.
In he me hods e iewed so a
G
includes all s a es o
he CTMC ha ing up o
K
ailed componen s. The issue o
how ogene a e
G
so ha i includesas ew s a esas possible
o achie e he equi ed accu acy has also been in es iga ed.
In [9], s a e space explo a ion echniques ha e been de el-
oped o he bounding me hod p oposed in [15] wi h he
cloning echnique. Howe e , hese s a e space explo a ion
echniques a e expensi e since hey equi e he solu iono a
linea sys em o size
j
G
j
a e he expansion o e e y s a e.
Mo e e icien s a e space explo a ion echniques based on
he concep o wa e expansion and speci ically a ge ed o
he me hod de eloped in [2] ha e been p oposed in [5].
Theboundingme hodp oposedin[2] equi es heknowl-
edge o he se o minimal cu s o he sys em, MC.The e
exis a numbe o algo i hms o ob ain MC [6, 8, 11, 17].
Compu a ion o MC is, howe e , NP-ha d [18], so hose
algo i hms may b eak down. In addi ion, MC can be e y
la ge, hus causing a la ge memo y o e head due o he
need o holdingMC. In his pape we de elop a new bound-
ing me hod which uses lowe bounds o ailu e dis ances
which a e compu ed on he aul ee o he sys em, and
hus does no equi e he knowledge o MC. The me hod is
use ul as an al e na i e o he me hod p oposed in [2] when
he algo i hms o ob ain MC b eak down o he numbe o
minimal cu s is la ge. The es o he pape is o ganized
as ollows. Sec ion 2 de ines he modeling amewo k and
gi es necessa y backg ound. Sec ion 3 ob ains he bounds
o UA using lowe bounds o ailu e dis ances. Sec ion 4
desc ibes healgo i hm o compu e lowe bounds o ailu e
dis ances on he aul ee. Sec ion 5 analyzes he p oposed
boundingme hodandcompa esi wi h heboundingme hod
p oposed in [2] and he bounding me hod p oposed in [15]
wi h s a e space explo a ion. Finally, Sec ion 6 includes he
conclusions.
2. P elimina ies
We conside aul - ole an sys ems made up o componen s
which ail and a e epai ed. The ope a ional/down s a e
o he sys em is de e mined by he un ailed/ ailed s a e o
i s componen s by means o a cohe en [1] s uc u e unc-
ion ep esen ed by a cohe en aul ee. Componen s a e
g ouped in o ypes, being indis inguishable he componen s
o he same ype. The e o e, collec ionso componen s can
be deal wi h as bags [16]. Any bag o componen ypes
which can ail simul aneously will be called a ailu e bag.
We assume known he se o ailu e bags o he sys em,
E
,
and, o each
e
2
E
, an uppe bound,

ub
(
e
)
, o he a eo
any ansi ionassocia ed wi h
e
. Repai ac ions in ol e jus
one componen and we assume also known a lowe bound,
g
(
k
)
>
0
,
k>
0
, o he a e o any ansi ion associa ed
wi h a epai ac ion in a s a e wi h
k
ailed componen s.
Le
X
=
X
(
);

0
g
be he ini e CTMC modeling
hesys em and le

be i s s a espace. We assume ha he e
is only ones a e in

, which will be e e ed o as
o
, wi hou
ailed componen s and ha he e is a leas one epai ac ion
in any s a e in

,
o
g
. Then,
X
will be i educible and,
he eby, e godic.
Since he s eady-s a e a ailabili y is ypically e y close
o one, i is o en p e e able o compu e he s eady-s a e
. . .
U
3
U
2
o
G
U
1
U
N
Figu e 1. S a e ansi ion diag am o he modi ied
CTMC
X
.
una ailabili y,UA.Le
D
be he subse o down s a es o
X
and le
p
=(
p
i
)
i
2

be he s eady-s a e p obabili y ec o
o
X
.Weha e
UA
=
X
i
2
D
p
i
:
Bounds o UA will be compu ed using de ailed knowl-
edge o
X
in he gene a ed subse ,
G
, and bounding he
beha io o
X
in
U
=
,
G
. I will be used he s a e
cloning echnique p oposed in [15]. The echnique consis s
inmodi ying
X
byadding o
U
clones o he s a esin
G
wi h
mo e han
F
ailed componen s, accoun ing o he isi s o
he co esponding s a es o
G
a e
X
exi s
G
and be o e
he numbe o ailed componen s has allen below
F
+1
.
We will use he s a e cloning echnique wi h
F
=0
,i.e.
clones o all s a es
s
2
G
,
o
g
will be added o
U
.The
selec ion o
F
=0
is made o ease he gene a ion o
G
.
Wi h
F
=0
,
G
includes s a es which a e eachable h ough
G
oms a e
o
and gene a iono
G
omahigh-le elmodel-
ing o malism. Wi h
F>
0
,
G
may con ain s a es which a e
eachable om
o
h ough
U
and gene a ion o
G
equi es a
p io i knowledgeabou he se o s a es o
X
. The modi ied
X
has he s uc u e depic ed in Figu e1, whe e
U
k
includes
all s a es in
U
wi h exac ly
k
ailed componen s and
N
is
he numbe o componen s o he sys em. In he ollowing,
X
will deno e he modi ied
X
.
Th oughou he pape we will deno e by

s;s
0
,
s; s
0
2

, he ansi ion a e om s a e
s
o s a e
s
0
,by

s
=
P
s
0
2

s
6
=
s
0

s;s
0
,
s
2

, he ou pu a e o
s
, and by

s;C
=
P
s
0
2
C

s;s
0
,
s
2

,
C


, he ansi ion a e om
s
o
he subse o s a es
C
, all e e ed o
X
unless o he wise
s a ed. We will also conside se e al ansien CTMC
Y
.
Each such
Y
has s a e space
B
[
a
g
, whe e all s a es in
B
a e ansien and
a
is an abso bing s a e, and has a well-
de ined ini ialp obabili ydis ibu ionwi h
P
[
Y
(0)
2
B
]=
1
.

(
s; Y
)
,
s
2
B
, willdeno e hemean imespen by
Y
in
s
be o e abso p ion, and

(
C; Y
)=
P
s
2
C

(
s; Y
)
,
C

B
,
will deno e he mean ime o abso p ion in subse
C
.I
is well-known ha he mean ime o abso p ion ec o

=
(

(
s; Y
))
s
2
B
is hesolu iono helinea sys em
A

=
,
q
,
whe e
A
is he es ic ion o
B
o he in ini esimalgene a o
o
Y
,and
q
=(
P
[
Y
(0) =
s
])
s
2
B
. I is also known ha

(
s; Y
)

s;s
0
is heexpec ed numbe o imes ha a ansi ion
om
s
o
s
0
,
s
2
B
,
s
0
2
B
[
a
g
, is ollowed.
3. Bounds o he S eady-s a eUna ailabili y
Conside he egene a i e beha io o
X
, aking as egen-
e a ion poin s he imes a which
X
en e s
o
om
U
.Le
T
G
and
T
U
be he con ibu ions o
G
and
U
o he mean
ime be ween egene a ions o
X
,andle
C
G
and
C
U
be
he espec i e con ibu ions o he mean down ime. F om
egene a ion p ocess heo y (see, o ins ance [7]), we ha e
UA
=
C
G
+
C
U
T
G
+
T
U
:
Assume ha uppe bounds
[
T
U
]
ub
and
[
C
U
]
ub
o , espec-
i ely,
T
U
and
C
U
a e known. Then [2, Theo em 2]
[
UA
]
lb
=
C
G
T
G
+[
T
U
]
ub
;
(1)
[
UA
]
ub
=
C
G
+[
C
U
]
ub
T
G
+[
C
U
]
ub
;
(2)
a e, espec i ely, a lowe and an uppe bound o UA.
Le
Y
G
be he ansien CTMC wi h s a e space
G
[
a
g
and ini ial s a e
o
buil om
X
by di ec ing o
a
he
ansi ions om s a es in
G
o s a es in
U
.
T
G
and
C
G
can
be exp essed in e ms o he mean ime o abso p ion ec o
o
Y
G
,
(

(
s; Y
G
))
s
2
G
,as
T
G
=
X
s
2
G

(
s; Y
G
)
;
(3)
C
G
=
X
s
2
G
D

(
s; Y
G
)
:
(4)
3.1. Upp e b ound
[
T
U
]
ub
The uppe bound
[
T
U
]
ub
is he same as ha o [2, 15]. Le
FC
be he se o di e en ca dinali ies o he ailu e bags
o he model, le
E
i
be he subse o
E
including all ailu e
bags o ca dinali y
i
and le
i
=
P
e
2
E
i

ub
(
e
)
. Conside
he ansien CTMC
Y
u
k
wi h s a e space
S
N
k
=1
u
k
g[
a
g
,
ini ial s a e
u
k
and he s a e ansi ion diag am shown in
Figu e 2. Fo each s a e
u
k
and each
i
2
FC
,
k
+
i

N
,
he e is a ansi ion o
u
k
+
i
wi h a e
i
, and a ansi ion o
u
k
,
1
i
k>
1
and
a
o he wise wi h a e
g
(
k
)
.Le
T
(
k
)
be
he mean ime o abso p ion o
Y
u
k
and le

k
=
X
s
2
G

(
s; Y
G
)

s;U
k
(5)
be he p obabili y ha
X
en e s
U
h ough
U
k
. Then [2,
Theo em 4]
[
T
U
]
ub
=
N
X
k
=1

k
T
(
k
)
(6)
. . .
u
2
u
3
u
1
g
(
N
)
g
(4)
g
(3)
g
(2)
1
1
2
2
1
1
g
(1)
u
N
a
Figu e 2. S a e ansi ion diag am o he ansien
CTMC
Y
u
k
.
uppe bounds
T
U
. An e icien me hod o compu e
T
(
k
)
,
1

k

N
, is desc ibed in [2].
3.2. Upp e Bound
[
C
U
]
ub
Theuppe bound
[
C
U
]
ub
isbasedonlowe bounds o ailu e
dis ances. The ailu e dis ance om a s a e
s
2

,
d
(
s
)
,is
de ined [2] as he minimum numbe o componen s which
ha e o ail in addi ion o hose al eady ailed in
s
o ake
he sys em down. Le
F
(
s
)
be he bag o ailed componen s
in
s
2

. Assume ha a lowe bound o
d
(
s
)
,
e
d
(
s
)
,is
a ailable sa is ying:
A1.
0

e
d
(
s
)

d
(
s
)
,
A2.
e
d
(
s
)=0
i and only i
s
2
D
,and
A3.
e
d
(
s
)
,j
F
(
s
0
)
,
F
(
s
)
j
e
d
(
s
0
)

e
d
(
s
)
,
F
(
s
)

F
(
s
0
)
.
No e ha assump ionA3implies ha gi en a ansi ion om
s
o
s
0
,
s; s
0
2

, associa ed wi h a ailu e bag
e
2
E
,
e
d
(
s
)
,j
e
j
e
d
(
s
0
)

e
d
(
s
)
.
Le
e
U
k;d
be he subse o
U
including all s a es
s
wi h
k
ailed componen s and
e
d
(
s
)=
d
,andle
e
L
=
e
d
(
o
)
.These
e
R
o
(
k; d
)
pai s o which
e
U
k;d
migh be
6
=
;
is gi en by
he cons ain s
1

k

N;
max
0
;
e
L
,
k
g
d

min
e
L; N
,
k
g
:
The cons ain son
k
a e ob ious. The cons ain s
e
L
,
k

d
and
d

e
L
ollow omassump ion A3 and he de ini iono
e
L
;
0

d
ollows om assump ion A1. Finally,
d

N
,
k
ollows om assump ion A3 and he ac ha he s uc u e
unc iono hesys em is cohe en by aking
s
0
he s a e wi h
all componen s ailed and no ing ha
e
d
(
s
0
)

d
(
s
0
)= 0
and, he e o e,
e
d
(
s
0
)=0
.
Le
Y
s
U
,
s
2
U
be he ansien CTMC wi h s a e space
U
[
a
g
and ini ial s a e
s
buil om
X
by di ec ing o
a
he ansi ions om s a es in
U
o
o
.Le
C
s
U
be he
mean down ime o abso p ion o
Y
s
U
. Recalling ha
P
s
0
2
G

(
s
0
;Y
G
)

s
0
;s
,
s
2
U
, is he p obabili y ha
X
en e s
U
h ough
s
,weha e
C
U
=
X
s
0
2
G
X
s
2
U

(
s
0
;Y
G
)

s
0
;s
C
s
U
=
X
s
0
2
G
X
(
k;d
)
2
e
R
X
s
2
e
U
k;d

(
s
0
;Y
G
)

s
0
;s
C
s
U
:
(7)
Le
e
C
(
k; d
)
be uppe bounds o
C
s
U
,
s
2
e
U
k;d
,and
e

k;d
=
X
s
2
G

(
s; Y
G
)

s;
e
U
k;d
:
(8)
Le
[
C
U
]
ub
=
X
(
k;d
)
2
e
R
e

k;d
e
C
(
k; d
)
:
(9)
We ha e
Theo em 1. Assume
C
s
U

e
C
(
k; d
)
,
s
2
e
U
k;d
,Then,
C
U

[
C
U
]
ub
.
P oo . Using (7), he ac ha
C
s
U

e
C
(
k; d
)
,
s
2
e
U
k;d
,(8),
and (9):
C
U
=
X
s
0
2
G
X
(
k;d
)
2
e
R
X
s
2
e
U
k;d

(
s
0
;Y
G
)

s
0
;s
C
s
U

X
s
0
2
G
X
(
k;d
)
2
e
R
X
s
2
e
U
k;d

(
s
0
;Y
G
)

s
0
;s
e
C
(
k; d
)
=
X
s
0
2
G
X
(
k;d
)
2
e
R

(
s
0
;Y
G
)

s
0
;
e
U
k;d
e
C
(
k; d
)
=
X
(
k;d
)
2
e
R
X
s
0
2
G

(
s
0
;Y
G
)

s
0
;
e
U
k;d
e
C
(
k; d
)
=
X
(
k;d
)
2
e
R
e

k;d
e
C
(
k; d
)= [
C
U
]
ub
:
Le
L
be he exac ailu edis ance om s a e
o
,i.e.
L
=
d
(
o
)
,andle
e
C
(
k
)=
N
X
i
=
e
L

(
u
i
;Y
u
k
)
:
(10)
We ha e
Theo em 2.
C
s
U

e
C
(
k
)
,
s
2
U
k
.
P oo . By assump ion A1,
e
L

L
. Using ha [2, Theo em
6]
C
s
U

P
N
i
=
L

(
u
i
;Y
u
k
)
and (10):
C
s
U

N
X
i
=
L

(
u
i
;Y
u
k
)

N
X
i
=
e
L

(
u
i
;Y
u
k
)=
e
C
(
k
)
:
e
C
(
k
)
,
1

k

N
can be compu ed e icien ly using
he me hod desc ibed in [2] o
C
(
k
)
,
1

k

N
, wi h
L
eplaced by
e
L
.
The bounds
e
C
(
k; d
)
a e compu ed usingan i e a i ep o-
cedu e which s a s wi h
e
C
(
k; d
)=
e
C
(
k
)
and imp o es he
bounds using po en ially be e bounds
e
C
0
(
k; d
)
un il no
signi ican imp o emen is achie ed.
Le
s
2
e
U
k;d
and conside a ansi ion om
s
o
s
0
2
U
associa ed wi h a ailu e bag
e
2
E
i
,
i
2
FC
. Clea ly,
s
0
2
e
U
k
+
i;d
0
o sui able
d
0
alues. Imposing
(
k
+
i; d
0
)
2
e
R
,
i

N
,
k
and
d
0

min
e
L; N
,
k
,
i
g
. Mo eo e ,
om assump ions A1 and A3,
max
0
;d
,
i
g
d
0

d
.
The e o e, he only easible des ina ion subse s
e
U
k
+
i;d
0
,
i
2
FC
, a e hose sa is ying
i

N
,
k
and ( ecall ha
d

e
L
)
max
0
;d
,
i
g
d
0

min
d; N
,
k
,
i
g
.Le
e
R
0
=
(
k ; d; i; d
0
)
j
(
k; d
)
2
e
R
,
i
2
FC
,
max
0
;d
,
i
g
d
0

min
d; N
,
k
,
i
gg
. Assume ha uppe bounds
e
F
(
k ; d; i;
)
,
(
k ; d; i;
)
2
e
R
0
, o
P
d
0
=0

s;
e
U
k
+
i;d
0
,
s
2
e
U
k;d
, a e a ailable and le
e
i;j
(
k; d
)=
8
>
<
>
:
e
F
(
k ; d; i; d
,
j
)
,
e
F
(
k ; d; i; d
,
j
,
1)
; 

j<!
e
F
(
k ; d; i; d
,
j
)
; j
=
!;
whe e

= max
0
;k
+
d
+
i
,
N
g
and
!
= min
i; d
g
.
The uppe bounds
e
C
0
(
k; d
)
a e compu ed using
e
C
0
(
k; d
)=
I
d
=0
g
(
k
)
+
I
k>
1
h
I
d>
e
L
,
k
e
C
(
k
,
1
;d
)
+
I
d

e
L
,
k
e
C
(
k
,
1
;d
+1)
i
+
1
g
(
k
)
X
i
2
FC
i

N
,
k
!
X
j
=

e
i;j
(
k; d
)
e
C
(
k
+
i; d
,
j
)
;
(11)
whe e
I
c
is he indica o unc ion e u ning1 i
c
is ue and
0 o he wise. The algo i hm o compu e he
e
C
(
k; d
)
bounds
is gi en in Figu e 3. The pa ame e

is a ole ance ac o
which de e mines when he imp o emen is small enough
o he algo i hm o s op.
Nex , we p o e ha he
e
C
(
k; d
)
compu ed by he al-
go i hm o Figu e 3 uppe bound
C
s
U
,
s
2
e
U
k;d
,p o-
ided ha
e
F
(
k ; d; i;
)
,
(
k ; d; i;
)
2
e
R
0
,and
e
F
(
k ; d; i; d
)
,
(
k ; d; i; d
)
2
e
R
0
, a e dec easing on
d
. The p oo willconsis
o a sequence o h ee p oposi ionsand a heo em.
P oposi ion 1. Le
(
k; d
)
2
e
R
. Assume ha
C
l
U

e
C
(
k; d
)
,
l
2
e
U
k;d
, and ha
e
C
(
k; d
)
is dec easing on
d
.
Then,
C
l
U

e
C
0
(
k; d
)
,
l
2
e
U
k;d
.
P oo . Le
l
2
e
U
k;d
. By assump ion A2,
d
=0
i and
only i
l
2
D
. The e o e,
C
l
U
is equal o he mean ime in
o (all
(
k; d
)
2
e
R
)
e
C
(
k; d
)=
e
C
(
k
)
;
do

0
=0
;
o
(
k
=1;
k

N
;
k
++)
o
(
d
= max
0
;
e
L
,
k
g
;
d

min
e
L; N
,
k
g
;
d
++)
Compu e
e
C
0
(
k; d
)
using (11);
i
(
e
C
0
(
k; d
)
<
e
C
(
k; d
))

0
= max

0
;
(
e
C
(
k; d
)
,
e
C
0
(
k; d
))
=
e
C
0
(
k; d
)
g
;
e
C
(
k; d
)=
e
C
0
(
k; d
)
;
g
g
g
while
(

0


)
;
Figu e 3. Algo i hm o compu e he
e
C
(
k; d
)
bounds.
l
,i
d
=0
, plus he mean down ime om he nex s a e
m
,i
m
2
U
. Le us discuss nex o which subse s
e
U
k
0
;d
0
m
may belong. By assump ion A3, a ansi ion associa ed
wi h a epai ac ion in ol ingone componen can only lead
o
m
2
e
U
k
,
1
;d
0
,
k>
1
(i
k
=1
,
m
=
o=
2
U
),
d

d
0

d
+1
.
d
0
=
d
is possible only i
(
k
,
1
;d
)
2
e
R
,
i.e.
d>
e
L
,
k
; simila ly,
d
0
=
d
+1
equi es
d<
e
L
.
Conside now ansi ions associa ed wi h ailu e bags
e
2
E
i
,
i
2
FC
. Clea ly,
m
2
e
U
k
+
i;d
,
j
o sui able
j
alues.
Imposing
(
k
+
i; d
,
j
)
2
e
R
,
i

N
,
k
and
d
,
j

min
e
L; N
,
k
,
i
g
. Fu he mo e, om assump ions A1
and A3,
max
0
;d
,
i
g
d
,
j

d
. The e o e, he only
easible
e
U
k
+
i;d
,
j
subse s a e hose sa is ying ( ecall ha
d

e
L
)
max
0
;k
+
d
+
i
,
N
g
j

min
i; d
g
. Based
on his discussion we can w i e
C
l
U
=
I
d
=0

l
+
I
k>
1
h
I
d>
e
L
,
k
X
m
2
e
U
k
,
1
;d

l;m

l
C
m
U
+
I
d<
e
L
X
m
2
e
U
k
,
1
;d
+1

l;m

l
C
m
U
i
+
X
i
2
FC
i

N
,
k
min
i;d
g
X
j
=max
0
;k
+
d
+
i
,
N
g
X
m
2
e
U
k
+
i;d
,
j

l;m

l
C
m
U
:
Using ha , by assump ion,
C
m
U

e
C
(
k
0
;d
0
)
,
m
2
e
U
k
0
;d
0
,
and in oducing he no a ion
g
j
(
l
)=

l;
e
U
k
,
1
;d
+
j
,
ij
(
l
)=

l;
e
U
k
+
i;d
,
j
,
J
m
(
i
) = max
0
;k
+
d
+
i
,
N
g
,and
J
M
(
i
)=
min
i; d
g
,
C
l
U

T
1
+
T
2
+
X
i
2
FC
i

N
,
k
T
3
(
i
)
;
wi h
T
1
=
I
d
=0

l
T
2
=
I
k>
1
h
I
d>
e
L
,
k
g
0
(
l
)

l
e
C
(
k
,
1
;d
)
+
I
d<
e
L
g
1
(
l
)

l
e
C
(
k
,
1
;d
+1)
i
;
T
3
(
i
)=
J
M
(
i
)
X
j
=
J
m
(
i
)
ij
(
l
)

l
e
C
(
k
+
i; d
,
j
)
:
F om his poin , he p oo con inues exac ly as in [2,
P oposi ion 1] se ing
F
=0
and subs i u ing
L
,
C
(
k; d
)
,
F
(
k ; d; i;
)
,and
i;j
(
k; d
)
by, espec i ely,
e
L
,
e
C
(
k; d
)
,
e
F
(
k ; d; i;
)
,and
e
i;j
(
k; d
)
.
P oposi ion 2. Assume ha
e
C
(
k; d
)
,
(
k; d
)
2
e
R
,
e
F
(
k; d;
i;
)
,
(
k ; d; i;
)
2
e
R
0
, and
e
F
(
k ; d; i; d
)
,
(
k ; d; i; d
)
2
e
R
0
,
a e dec easing on
d
.Then
e
A
(
k ; d; i
)=
min
i;d
g
X
j
=max
0
;k
+
d
+
i
,
N
g
e
i;j
(
k; d
)
e
C
(
k
+
i; d
,
j
)
;
i
2
FC
;i

N
,
k
, is dec easing on
d
.
P oo . The p oo is exac ly as in [2, P oposi ion 2] eplac-
ing
A
(
k ; d; i
)
,
R
,
C
(
k; d
)
,
F
(
k ; d; i;
)
,
F
(
k ; d; i; d
)
,and
i;j
(
k; d
)
by, espec i ely,
e
A
(
k ; d; i
)
,
e
R
,
e
C
(
k; d
)
,
e
F
(
k; d;
i;
)
,
e
F
(
k ; d; i; d
)
and
e
i;j
(
k; d
)
.
P oposi ion 3. Assume ha
e
C
(
k; d
)
,
(
k; d
)
2
e
R
,
e
F
(
k; d;
i;
)
,
(
k ; d; i;
)
2
e
R
0
, and
e
F
(
k ; d; i; d
)
,
(
k ; d; i; d
)
2
e
R
0
,
a e dec easing on
d
.Then
e
C
0
(
k; d
)
,
(
k; d
)
2
e
R
, is dec eas-
ing on
d
.
P oo . Le
(
k; d
)
,
(
k; d
+1)
2
e
R
. Using (11):
e
C
0
(
k; d
)
,
e
C
0
(
k; d
+1) =
T
1
+
T
2
+
X
i
2
FC
i

N
,
k
T
3
(
i
)
;
wi h
T
1
=
I
d
=0
,
I
d
+1=0
g
(
k
)
;
T
2
=
I
k>
1
h
I
d>
e
L
,
k
e
C
(
k
,
1
;d
)
+
I
d

e
L
,
k
e
C
(
k
,
1
;d
+1)
,
I
d
+1
>
e
L
,
k
e
C
(
k
,
1
;d
+1)
,
I
d
+1

e
L
,
k
e
C
(
k
,
1
;d
+2)
i
;
T
3
(
i
)=
e
A
(
k ; d; i
)
,
e
A
(
k; d
+1
;i
)
g
(
k
)
;

whe e
e
A
(
k ; d; i
)
is as de ined in P oposi ion 2. We will
show ha
T
1
,
T
2
and
T
3
(
i
)
a e all

0
.Since
(
k; d
)
2
e
R
,
d

0
and
d
+1
>
0
. The e o e,
T
1
=
I
d
=0
=g
(
k
)

0
.
Rega ding
T
2
, h ee cases mus be conside ed: a)
k
=1
,b)
k>
1
,
d>
e
L
,
k
,andc)
k>
1
,
d

e
L
,
k
. In case a,
T
2
=0
; in case b,
T
2
=
e
C
(
k
,
1
;d
)
,
e
C
(
k
,
1
;d
+1)

0
because
e
C
(
k
0
;d
0
)
,
(
k
0
;d
0
)
2
e
R
, is assumed dec easing on
d
; in case c,
d
+1
>
e
L
,
k
because
(
k; d
)
,
(
k; d
+1)
2
e
R
,
and, he eby,
T
2
(
i
)=
e
C
(
k
,
1
;d
+1)
,
e
C
(
k
,
1
;d
+1) = 0
.
Finally,
T
3
(
i
)

0
by P oposi ion2.
Theo em 3. Assume ha
e
F
(
k ; d; i;
)
,
(
k ; d; i;
)
2
e
R
0
,
and
e
F
(
k ; d; i; d
)
,
(
k ; d; i; d
)
2
e
R
0
, a e dec easing on
d
.
Then, he
e
C
(
k; d
)
compu ed by he algo i hm o Figu e 3
uppe bound
C
s
U
,
s
2
e
U
k;d
, and a e dec easing on
d
.
P oo . Conside he algo i hm spli in o phases, whe e each
phase includes he ope a ions pe o med wi hin he
k
-loop,
and le
e
C
m
(
k; d
)
,
m

0
, be he bounds
e
C
(
k; d
)
a ailable
a e phase
m
. The p oo will be by induc ion o e
m
.
e
C
0
(
k; d
)=
e
C
(
k
)
, which a e (non-s ic ly) dec easing on
d
and, by Theo em 2, uppe bound
C
s
U
,
s
2
U
k
. Assume
now ha he
e
C
m
(
k; d
)
uppe bound
C
s
U
,
s
2
e
U
k;d
,and
a e dec easing on
d
.Le
k
0
be he alue o
k
o which
he bounds a e upda ed in phase
m
+1
. Acco ding o
(11),
C
m
+1
(
k
0
;d
)
only depend on
C
m
(
k; d
)
o
k
6
=
k
0
,
and all
C
m
+1
(
k
0
;d
)
a e compu ed using he same se o
bounds
C
m
(
k; d
)
. Then, P oposi ion 1 gua an ees ha
C
0
(
k
0
;d
)
a e co ec , and P oposi ion 3 ha hey a e de-
c easing on
d
. Using he induc ion hypo hesis, his implies
ha
C
m
+1
(
k
0
;d
) = min
C
m
(
k
0
;d
)
;C
0
(
k
0
;d
)
g
a e co ec
and dec easing on
d
.
We conclude his sec ion by de i ing sui able uppe
bounds
e
F
(
k ; d; i;
)
o
P
d
0
=0

s;
e
U
k
+
i;d
0
,
s
2
e
U
k;d
.T i -
ially,
e
F
(
k ; d; i;
min
d; N
,
k
,
i
g
)=
i
uppe bounds
P
min
d;N
,
k
,
i
g
d
0
=max
0
;d
,
i
g

s;
e
U
k
+
i;d
0
.Le
e

(
e
)
,
e
2
E
,
be helowe bound o he ailu edis ance omas a ewhose
bag o ailed componen sis
e
.Le
s
0
2
U
be a s a e eached
om
s
2
e
U
k;d
h ough a ansi ion which has associa ed
wi h i he ailu e bag
e
.Since
F
(
s
0
)=
F
(
s
)+
e
,weha e,
by assump ionA3, ha
e
d
(
s
0
)
canno ha e been educed wi h
espec o
e

(
e
)
by mo e han
k
,i.e.
e
d
(
s
0
)

e

(
e
)
,
k
.Then
e
F
(
k ; d; i;
)=
X
e
2
E
i
e

(
e
)

k
+

ub
(
e
)
;
max
0
;d
,
i
g
<
min
d; N
,
k
,
i
g
uppe bounds
P
d
0
=max
0
;d
,
i
g

s;
e
U
k
+
i;d
0
,
<
min
d; N
,
k
,
i
g
.T i -
ially, bo h
e
F
(
k ; d; i;
)
,
(
k ; d; i;
)
2
e
R
0
and
e
F
(
k ; d; i; d
)=
i
,
(
k ; d; i; d
)
2
e
R
0
, a e (non-s ic ly) dec easing on
d
, hus
ul illing he condi ionsimposed by Theo em 3.
4. Lowe Bounds o Failu e Dis ances
In his sec ion we de i e lowe bounds o ailu e dis ances
ul illingassump ionsA1–A3o Sec ion3.2. Wealsode i e
e icien algo i hms o compu e he bounds.
4.1. Deni ion o Lowe Bounds o Failu e
Dis ances
We assume, wi hou loss o gene ali y, ha he aul ee o
he sys em is made up o a se
P
o AND and OR ga es and
ase
I
o inpu s. We will deno e by
C
he se o componen
ypes o he sys em, and by
g
he oo ga e o he aul ee.
Eachinpu has he o m
c
[
n
]
,
c
2
C
,meaning he ailu eo
n
componen so ype
c
. Theexis ence o ypeso componen s
in oducessome dependencies among he inpu s o he aul
ee. I willbe said ha wo inpu sa e ela ed i hey in ol e
componen s o he same ype, i.e. a e o he o m
c
[
n
]
,
c
[
n
0
]
,
n
6
=
n
0
. To a oid i iali ies,we assume ha he e a e
no ela ed inpu s eeding he same ga e. This is no a eal
es ic ion since o
n
0
>n
and deno ing by
^
and
_
he
logical “and” and “o ” ope a o s, espec i ely,
c
[
n
]
_
c
[
n
0
]
can be subs i u ed by
c
[
n
]
and
c
[
n
]
^
c
[
n
0
]
by
c
[
n
0
]
. Each
node
x
(i.e. an inpu o a ga e) o he aul ee eeds a
se o ga es
o(
x
)
and each ga e
y
is ed by a se o nodes
(
y
)
.Le
al(
x
)
2
0
;
1
g
be he alue o node
x
.I
x
is
a ga e,
al(
x
)
is de e mined as usual om he alues o i s
inpu s. I
x
=
c
[
n
]
is an inpu ,
al(
x
)= 1
i and only i
n
o mo e componen s o ype
c
ha e ailed. Since he alue
o a node is equal o 1 i and only i a sui able collec ion o
componen so hesys em being modeled ha e ailed, nodes
will also be e e ed o as e en s. In his ega d, he e en
x
2
I
[
P
will be said o be ealized i
al(
x
)=1
.
Le us deno e a bag o ailed componen s,
F
,as
F
=
c
1
[
n
1
]
c
2
[
n
2
]
:::c
k
[
n
k
]
,
c
l
6
=
c
m
,
l
6
=
m
, meaning ha
F
con ains
n
i
ins ances o componen ype
c
i
. I will be said
ha
c
i
[
n
i
]
is pa o
F
. The dis ance om a bag o ailed
componen s
F
o an e en
x
2
I
[
P
,
d
b
(
F; x
)
,isde ined
as he minimum numbe o componen s which ha e o ail
in addi ion o hose which a e al eady pa o
F
o ealize
x
. F om ha de ini ion, gi en he bag o ailed componen s
F
(
s
)
o a s a e
s
2

,
d
(
s
)=
d
b
(
F
(
s
)
;g
)
.Le
e
d
b
(
F; x
)
,
x
2
I
[
P
, be a lowe bound o
d
b
(
F; x
)
.Thelowe
bounds
e
d
(
s
)
,
s
2

,a e
e
d
(
s
)=
e
d
b
(
F
(
s
)
;g
)
.Suchlowe
bounds will be compu ed on he aul ee using he concep
o module, de ined as a ga e such ha he sub ee hanging
om i has ha ga e as only exi poin and e e y inpu o
he sub ee does no ha e ela ed inpu s ou side he sub ee.
The ga es which a e modules can be de e mined using he
algo i hmLTA/DR o [10] wi ha small modi ica ion o ake
in o accoun ypes o componen s: du ing he i s dep h-
i s , le -mos a e sal o he aul ee (s ep no. 2 o he
algo i hm), a isi o
c
[
n
]
2
I
implies simul aneous isi s
(i.e. wi h hesame “ imes amp” as o
c
[
n
]
) oalli s ela ed
inpu s.
Le
F
beabago ailedcomponen s.
e
d
b
(
F; x
)
,
x
2
I
[
P
,
is ecu si ely de ined as ollows. I
x
=
c
[
n
]
2
I
:
e
d
b
(
F; x
)

(
n
i no
c
[
n
0
]
is pa o
F
max
0
;n
,
n
0
g
o he wise
;
(12)
i
x
is an OR ga e:
e
d
b
(
F; x
)

min
y
2
(
x
)
e
d
b
(
F; y
)
g
;
(13)
and i
x
is an AND ga e,
e
d
b
(
F; x
)

X
y
2
A
(
x
)
e
d
b
(
F; y
)
(14)
+ max
n
X
y
2
B
(
x
)
e
d
b
(
F; y
)
;
max
y
2
C
(
x
)
0
;
e
d
b
(
F; y
)
g
o
;
whe e
A
(
x
)

y
2
(
x
)
j
y
is a module
^j
o(
y
)
j
=
1
g
,
B
(
x
)

y
2
(
x
)
j
y
is a module
^j
o(
y
)
j
>
1
_
y
is no a module
^
y
2
I
g
and
C
(
x
)

y
2
(
x
)
j
y
is no a module
^
y
2
P
g
.
The lowe bounds o ailu e dis ances ecu si ely de-
ined by (12), (13) and (14) ul ill assump ions A1–A3 o
Sec ion 3.2 [20, Theo ems 2 and 4].
4.2. An Algo i hm o he Compu a ion o
Lowe Bounds o Failu e Dis ances
Exp essions (12), (13) and (14) allow o compu e
e
d
b
(
F; g
)
a e sing he aul ee dep h- i s , le -mos s a ing a
g
.
Howe e , his p ocedu e could be expensi e i he aul ee
is la ge. Nex , we de elop mo e e icien algo i hms o
compu e
e
d
(
s
)
.
Each node
x
o he aul ee holds a “dis ance a i-
able”,
d
(
x
)
, and he aul ee is ini ializedso ha
d
(
x
)=
e
d
b
(
;
;x
)
. Such an ini ializa ion is pe o med a e sing
dep h- i s , le -mos he aul ee s a ing a
g
and using
(12), (13) and (14). No e ha a e he ini ializa ion p o-
cedu e,
e
L
=
e
d
b
(
;
;g
)
is known.
e
d
b
(
F
(
s
)
;x
)
<
e
d
b
(
;
;x
)
,
x
2
P
, equi es
e
d
b
(
F
(
s
)
;y
)
<
e
d
b
(
;
;x
)
o some
y
2
(
x
)
.
The e o e, since
e
d
(
s
)

e
L
,
e
d
(
s
)=
e
d
b
(
F
(
s
)
;g
)
will be
equal o
e
L
unless
e
d
b
(
F
(
s
)
;y
)
<
e
L
o some
y
2
(
x
)
.The
same a gumen can be i e a i ely applied going down he
aul ee un il he inpu s. This jus i ies he ollowing algo-
i hm which compu es
e
d
(
s
)
p ocessing he aul ee om
inpu s o
g
. Fo each
c
[
n
]
which is pa o
F
(
s
)
, based on
(12) we make
d
(
c
[
n
0
]) = max
0
;d
(
c
[
n
0
])
,
n
g
o each
inpu
c
[
n
0
]
. Each upda e o
d
(
x
)
o an inpu
x
which e-
sul sin
d
(
x
)
<
e
L
isp opaga eddep h- i s ,le -mos up he
aul eeusing(13)and(14)while
d
(
z
)
<
e
L
o he isi ed
node
z
. No e ha he algo i hm compu es he co ec lowe
bounds o dis ances om
F
(
s
)
o he nodes
x
o which
e
d
b
(
F
(
s
)
;x
)
<
e
L
, so, a he end,
d
(
g
)
will hold
e
d
(
s
)
.
No e also ha he ini ializa ion
d
(
x
)=
e
d
b
(
;
;x
)
needs o
bepe o medonlyoncei whilecompu ing
e
d
(
s
)
hechanges
in he
d
(
x
)
a iables a e inc emen ally kep in a sui able
da as uc u e,e.g. as ack. Wecallgene ically healgo i hm
comp d
(
F;
ub
;
DS
)
,whe e
F
is a bag o ailedcomponen s,
ub
is an uppe bound o he dis ance o be compu ed and
DS is a s ack. The algo i hm e u ns
e
d
b
(
F; g
)
i ha alue
is
<
ub
. In his ega d,
e
d
(
s
)=
comp d
(
F
(
s
)
;
e
L;
DS
)
.Once
e
d
(
s
)
hasbeencompu ed, he aul eeis es o ed oi sini ial
s a e simply undoing he changes kep in DS. We call his
p ocedu e es o e d(DS).
Le
s
be a s a e in he on ie o
G
and le
S
be he
se o s a es
s
0
eached om
s
in a single ailu e ansi-
ion. Compu a ion o
[
C
U
]
ub
using (8) and (9) equi es
he compu a ion o
e
d
(
s
0
)
,
s
0
2
S
. We desc ibe nex how
e
d
(
s
0
)
,
s
0
2
S
a e compu ed assuming ha
e

(
e
)
is known
o all
e
2
E
(
e

(
e
)=
comp d
(
e;
e
L;
DS
)
). Each an-
si ion om
s
o
s
0
2
S
has associa ed wi h i a ail-
u e bag
e
s
0
2
E
and
F
(
s
0
)=
F
(
s
)+
e
s
0
. Mo eo e ,
we ha e ha
lb
s
0
= max
0
;
e
d
(
s
)
,j
e
s
0
jg 
e
d
(
s
0
)

min
e
d
(
s
)
;
e

(
e
s
0
)
g
=
ub
s
0
.The
d
(
x
)
a iables o he aul
ee a e se o
e
d
b
(
F
(
s
)
;x
)
i
e
d
b
(
F
(
s
)
;x
)
<
e
L
and
e
d
b
(
;
;x
)
o he wise by calling comp d
(
F
(
s
)
;
e
L;
DS
)
. Nex , o each
s
0
2
S
,
e
d
(
s
0
)=
lb
s
0
i
lb
s
0
=
ub
s
0
. O he wise, we se
d

=
comp d
(
e;
ub
s
0
;
DS
0
)
. Because o he cha ac e is ics
o he algo i hm comp d
(

)
, we will ha e
d

=
e
d
(
s
0
)
i
e
d
(
s
0
)
<
ub
s
0
and
d

=
e
d
(
s
)
o he wise. The e o e, since
ub
s
0

e
d
(
s
)
,
e
d
(
s
0
) = min
d

;
ub
s
0
g
. Nex , we call e-
s o e d(DS’) o allow ano he
e
d
(
s
0
)
o be compu ed, and
once
e
d
(
s
0
)
has been compu ed o all
s
0
2
S
, we call e-
s o e d(DS) o es o e he aul ee.
5. Analysis and Compa ison
In his sec ion we analyze he pe o mance o he p oposed
boundingme hod and compa e i wi h hebounding me hod
p oposed in [2] using he same s a e space explo a ion algo-
i hm. The bounding me hod p oposed in [2] is analogous
o he one p oposed he e excep ha i uses exac ailu edis-
ances compu ed using he se o minimal cu s o he aul
ee o he sys em, and boundings uc u es
F
(
k ; d; i;
)
up-
pe bounding
P
d
0
=0

s;U
k
+
i;d
0
,
s
2
U
k;d
, he subse
U
k;d
including he s a es wi h
k
ailed componen s and ailu e
dis ance
d
. We willalso compa e he me hod p oposedhe e
wi h he boundingme hod p oposed in [15]. In ha me hod,
PU
0
PU
1
NA
5
NB
5
NB
4
NA
0
NB
0
NB
3
NA
3
NB
1
NB
2
NA
2
NA
1
DA
1
RA
1
DB
1
RB
1
PU
2
NA
4
Figu e 4. A chi ec u e o he i s example.
he lowe bound o UA is also
[
UA
]
lb
bu he uppe bound
is
[
UA
]
0
ub
=
C
G
+[
T
U
]
ub
T
G
+[
T
U
]
ub
:
In all cases he subse
G
is inc emen ally gene a ed un il
he ela i e una ailabili y band,
([
UA
]
ub
,
[
UA
]
lb
)
=
[
UA
]
lb
,
is smalle han o equal o hedesi ed one. Fo he p oposed
bounding me hod and he me hod p oposed in [2] he gen-
e a ion is done using he algo i hmCONT TG W p oposed
in [5]. Fo he bounding me hod desc ibed in [15] we use
an analogous algo i hm CONT TG W, whe e he con ibu-
ions o he ela i e una ailabili y band a e associa ed only
wi h he pa ame e
k
(numbe o ailed componen s o he
successo s). Bo h algo i hms allow o adeo he numbe
o imes
(

(
s; Y
G
))
s
2
G
is compu ed agains how accu a ely
he s a e space is explo ed by means o a con ol pa ame e
BR
,
0

BR
<
1
( he la ge
BR
, he mo e accu a e bu
mo e cos ly he explo a ion). A e some expe imen a ion
we ha e ound
BR
=0
:
1
o be a easonable choice. The
R
pa ame e used in he algo i hm o he compu a ion o
exac ailu e dis ances desc ibed in [2] was se o 2.
The analysis and compa ison will be made using wo ex-
amples. The i s example, whose a chi ec u e is depic ed
in Figu e 4, includes h ee p ocessing clus e s which com-
munica e h ough wo independen double- ingne wo ks
A
and
B
. P ocessing clus e
i
,
0

i

2
, includes h ee
iden ical p ocessing uni s PU
i
.Ne wo k
A
includes six
nodes NA
i
,
0

i

5
, and di ec (clockwise) and e e se
(coun e -clockwise) links, DA
i
and RA
i
, espec i ely, link-
ing nodes NA
i
and NA
i
+1 mo d 6
.Ne wo k
B
has he same
s uc u e as ne wo k
A
and i s di ec and e e se links a e
called, espec i ely, DB
i
and RB
i
. Thesys emisope a ional
i each p ocessing clus e has a leas an un ailed p ocessing
uni and all p ocessing clus e s can communica e using one
o he ne wo ks. The ope a ional con igu a ion o he sys-
emincludes wop ocessinguni s o hep ocessingclus e s
wi h wo o h ee un ailed p ocessing uni s, one p ocessing
uni o he p ocessing clus e s wi hone un ailedp ocessing
uni , and he componen s o ei he ne wo k
A
o
B
, wi h
p io i y gi en o ne wo k
A
, equi ed o build one o he
ope a ional con igu a ions o he ne wo ks desc ibed nex .
The ne wo kcon igu a ionwhichis ied i s is a di ec ing
including all nodes and di ec links. The second con igu a-
ion which is ied is a e e se ing including all nodes and
e e se ings. The hi d con igu a ion is used when pa allel
di ec and in e se link
i
ail and i includes all nodes and
links excep he links be ween nodes
i
and
i
+1mod6
.
The las con igu a ion is used when node
i
ails and i in-
cludes all nodes excep node
i
and all links excep hose
be ween node
i
and nodes
i

1mod6
. A aul in a p o-
cessing uni o a clus e con amina es ano he un ailed uni
in he same clus e wi h p obabili y 0.05. The componen s
included in he ope a ional con igu a ion o he sys em a e
called ac i e. Ac i e p ocessing uni s, ac i e nodes and ac-
i e links ail wi h a es
4
:
6

10
,
4
h
,
1
,
2
:
3

10
,
4
h
,
1
and
1
:
1

10
,
4
h
,
1
. Inac i e componen s ail wi h he
same a es mul iplied by a do mancy ac o o 0.2. We as-
sume ha he e is a single epai man who akes o epai
ailed componen s a andom. Repai a es o p ocessing
uni s, nodes and links a e, espec i ely,
0
:
5
h
,
1
,
0
:
7
h
,
1
and
1
:
0
h
,
1
. Componen s con inue o ail when he sys em
has ailed. The second example is as he i s one bu wi h
he numbe o nodes o bo h ne wo ks inc eased up o en
and he numbe o p ocessing clus e s inc eased up o i e.
Fo bo h examples
L
=3
and
e
L
=2
. The aul ee has
8,653 minimal cu s o he i s example and 87,031 o he
second one.
We show in Figu e 5 he ela i e una ailabili yband as a
unc iono henumbe o s a esin
G
o hep oposedbound-
ing me hod and he me hods desc ibed in [2] and [15]. The
esul s ha e been ob ained in a 128 MB Ul aSpa c wo k-
s a ion. I can be seen ha he p oposed bounding me hod
ou pe o ms signi ican ly he bounding me hod desc ibed
in [15] in e ms o he size o
G
. Thus, o he i s exam-
ple, he numbe o s a es equi ed by he me hod desc ibed
in [15] o achie e a gi en ela i e una ailabili yband anges
om 4.9 o 12.6 imes he numbe o s a es equi ed by
he p oposed bounding me hod. Wi h ega d o he me hod
desc ibed in [2], he p oposed me hod equi es a numbe o
s a esabou 2.6 imesla ge . Howe e , heboundingme hod
desc ibedin[2] equi es obookkeepinmemo y heminimal
cu s and ela ed da as uc u es, and hiso e head may make
he memo y consump ion (which is eally he pa ame e o
in e es ) la ge han ha o he p oposed me hod. Bo h he
0.01
0.1
0 10000 20000 30000
ela i e band
s a es
p oposed
[2]
[15]
0.01
0.1
0 15000 30000 45000 60000 75000 90000
ela i e band
s a es
p oposed
[2]
[15]
Figu e5. Rela i e una ailabili yband as a unc iono henumbe o s a es in
G
o he p oposed boundingme hod, he
me hod desc ibed in [2] and he me hod desc ibed in [15], o he example wi h h ee p ocessing clus e s (le ) and i e
p ocessing clus e s ( igh ) and
BR
=0
:
1
.
p oposed boundingme hod and he me hod desc ibed in [2]
ha e o hold, o each s a e in he on ie o
G
, lis s o con-
ibu ions o he una ailabili y band associa ed wi h he pa-
ame e s
k
and
d
while he lis s o con ibu ionswhich ha e
o be held o hose s a es in he me hod desc ibed in [15]
a e associa ed only wi h he pa ame e
k
. Then, i is mean-
ing ul o compa e he h ee bounding me hods in e ms o
memo y consump ion. The compa ison is done in Figu e 6,
which plo s una ailabili y ela i e band agains (es ima ed)
memo y consump ion. The p oposed bounding me hod is
again a mo e e icien han he me hod desc ibed in [15]
and mo e e icien han he me hod desc ibed in [2]. The
smalle he ela i euna ailabili yband,howe e , hesmalle
hedi e encein e mso memo yconsump ionbe ween he
p oposed me hod and he me hod desc ibed in [2]. This is
due o he ac ha
j
G
j
inc eases and, he eby, he memo y
consump ion due o s o ing he s a e desc ip ions o
G
and
he lis so con ibu ions o heuna ailabili yband becomes
ela i ely mo e impo an han he o e head in oduced by
s o ing he minimal cu s and ela ed da a s uc u es.
The o e head due o he compu a ion o lowe bounds
o ailu e dis ances is negligible ega ding memo y con-
sump ion. The o e head in e ms o CPU ime consump ion
depends on hesizeo he aul ee. The aul eeo he i s
example has 39 inpu s, 32 ga es and 431 edges. The aul
eeo hesecondexample has 65inpu s,48 ga es and 1,193
edges. We ha e p o iled ou code and ha e ound a ime
o e head due o he compu a ion o lowe bounds o ail-
u e dis ances o 7.8% in he i s example wi h
j
G
j
=
8,608
s a es and 15.8% in he second example wi h
j
G
j
=
9,568
s a es. Then, al hough inc easing wi h he size o he aul
ee, he o e head in CPU ime due o he compu a ion o
lowe bounds o ailu e dis ances is easonable.
6. Conclusions
In his pape we ha e p oposed a new me hod o compu e
bounds o he s eady-s a e una ailabili y, which is based
on lowe bounds o ailu e dis ances. We ha e de eloped
algo i hms o compu e such dis ances on he aul ee o
he sys em. The p oposed bounding me hod gene a es in-
c emen ally a subse o he s a e space using a p e iously
p oposeds a espaceexplo a ionalgo i hm. Nume icalanal-
ysis has shown ha in e ms o numbe o s a es needed
o achie e a gi en accu acy, he p oposed me hod ou pe -
o ms a p e iously p oposed me hod no based on he ail-
u e dis ance concep and is wo se han a p e iously p o-
posed me hod which uses exac ailu e dis ances. How-
e e , when compa ed in e ms o memo y consump ion, he
p oposed bounding me hod can ou pe o m he bounding
me hod which uses exac ailu e dis ances i he numbe o
minimal cu s is la ge. The e o e, he p oposed me hod is a
good adeo be ween bounds igh ness and memo y con-
sump ion when he numbe o minimal cu s o he sys em is
la ge.
Re e ences
[1] R. E. Ba low and F. P oschan. S a is ical Theo y o Relia-
bili y and Li e Tes ing. P obabili y Models. McA dle P ess,
Sil e Sp ing, 1981.
[2] J. Ca asco. Tigh s eady-s a e a ailabili y boundsusing he
ailu edis anceconcep .Pe o manceE alua ion,34:27–64,
1998.