Failure distance based bounds for steady-state availability without the kwnowledge of minimal cuts

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.