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

Failure Distance Based Bounds for Steady-state Availability without the Knowledge of Minimal Cuts V´ıctor Su˜n´e and Juan A. Carrasco Departament d’Enginyeria Electr`onica Universitat Polit`ecnica de Catalunya Diagonal 647, plta. 9, 08028 Barcelona, Spain f sunye, carrasco g @eel.upc.es Abstract We propose an algorithmto compute bounds for the steadystate unavailability using continuous-time Markov chains, which is based on the failure distance concept. The algorithm generates incrementally a subset of the state space until the tightness of the bounds is the specified one. In contrast with a previous algorithmalso based on the failure distanceconcept, theproposedalgorithmuses lowerbounds for failure distances which are computed on the fault tree of the system, and does not require the knowledgeof the minimal cuts. This is advantageouswhenthe number of minimal cuts is large or their computationis time-consuming. 1. Introduction Continuous-timeMarkov chain models (CTMC)are a flexible, powerful toolfor computing steady-state dependability measures for fault tolerant systems such as the steady-state availability, A . However, the steady-state probabilitydistribution of the CTMC modeling realistic systems, and, thus, A , cannot be computed exactly in many cases because of the enormous size of the state space of the CTMC. Bounding techniques are an attractive approach. Using those techniques, only a subset G of the state space of the CTMC is generated and the behavior of the system outside G is bounded somehow. Bounding techniques have been developed in the last few years and currently there exist several bounding methods [2, 3, 4, 12, 13, 14, 15, 19]. In the first of such methods [15], bounds for the steady-state unavailability UA =1 , A are obtained by partitioning the non-generated portion U according to the number of failed components and bounding the behavior of the chain in U usingupper bounds for the failure transitionrates and lower bounds for the repair transition rates. The method is, however, computationally very costly because a linear system of size j G j has to be solved for each return state, i.e. each state through which G can be entered from U .Inthesame paper, a state cloning technique is proposed which reduces the number of linear systems which have to be solved but introduces some looseness in the bounds. In [12] a refinement of the method is proposed for the particular case in which all states but the one without failed components are cloned. The technique avoids a complete reapplication of the algorithm each time G is enlarged in the search for the desired accuracy but looses up further the bounds. This additional looseness has been reduced in another paper from the same authors [13]. In the method proposed in [4], the bounds of [15] are computed without cloning states solving only four linear systems of size j G j . In [19] another bounding method is developed in which the bounds are iteratively refined using detailed knowledge about the model in U in the proximities of G . In [2] a bounding method based on the failuredistance concept isproposed whichgives bounds for UA which are never worse, and typically better, than those given by[15]. The method uses thecloning technique of [15] but adapts one of the algorithms developed in [4] so that only five linear systems of size j G j have to be solved to compute the proposed bounds. The previous methods assume that the state space of the CTMC is finite and that there is a transitionto the left in all non-generated states of the CTMC. Both restrictions have been removed in thegeneralization of[15] proposedin [14]. Another generalization of [15] for finite CTMCs has been recently proposed in [3]. In that method, group repair and phase type repair distributionsare allowed. In the methods reviewed so far G includes all states of the CTMC having up to K failed components. The issue of howtogenerate G so that itincludesas few statesas possible to achieve the required accuracy has also been investigated. In [9], state space exploration techniques have been developed for the bounding method proposed in [15] with the cloning technique. However, these state space exploration techniques are expensive since they require the solutionof a linear system of size j G j after the expansion of every state. More efficient state space exploration techniques based on the concept of wave expansion and specifically targeted to the method developed in [2] have been proposed in [5]. Theboundingmethodproposedin[2]requirestheknowledge of the set of minimal cuts of the system, MC.There exist a number of algorithms to obtain MC [6, 8, 11, 17]. Computation of MC is, however, NP-hard [18], so those algorithms may break down. In addition, MC can be very large, thus causing a large memory overhead due to the need of holdingMC. In this paper we develop a new bounding method which uses lower bounds for failure distances which are computed on the fault tree of the system, and thus does not require the knowledge of MC. The method is useful as an alternative to the method proposed in [2] when the algorithms to obtain MC break down or the number of minimal cuts is large. The rest of the paper is organized as follows. Section 2 defines the modeling framework and gives necessary background. Section 3 obtains the bounds for UA using lower bounds for failure distances. Section 4 describes thealgorithm to compute lower bounds forfailure distances on the fault tree. Section 5 analyzes the proposed boundingmethodandcomparesitwiththeboundingmethod proposed in [2] and the bounding method proposed in [15] with state space exploration. Finally, Section 6 includes the conclusions. 2. Preliminaries We consider fault-tolerant systems made up of components which fail and are repaired. The operational/down state of the system is determined by the unfailed/failed state of its components by means of a coherent [1] structure function represented by a coherent fault tree. Components are grouped intotypes, being indistinguishablethe components of the same type. Therefore, collectionsof components can be dealt with as bags [16]. Any bag of component types which can fail simultaneously will be called a failure bag. We assume known the set of failure bags of the system, E , and, for each e 2 E , an upper bound,  ub ( e ) ,fortherateof any transitionassociated with e . Repair actions involve just one component and we assume also known a lower bound, g ( k ) > 0 , k> 0 , for the rate of any transition associated with a repair action in a state with k failed components. Let X = f X ( t ); t  0 g be the finite CTMC modeling thesystem and let  be its statespace. We assume thatthere is only onestate in  , which will be referred to as o , without failed components and that there is at least one repair action in any state in  ,f o g . Then, X will be irreducible and, thereby, ergodic. Since the steady-state availability is typically very close to one, it is often preferable to compute the steady-state . . . U 3 U 2 o G U 1 U N Figure 1. State transition diagram of the modified CTMC X . unavailability,UA.Let D be the subset of down states of X and let p =( p i ) i 2  be the steady-state probability vector of X .Wehave UA = X i 2 D p i : Bounds for UA will be computed using detailed knowledge of X in the generated subset, G , and bounding the behavior of X in U = , G . It will be used the state cloning technique proposed in [15]. The technique consists inmodifying X byaddingto U clones ofthe statesin G with more than F failed components, accounting for the visitsto the corresponding states of G after X exits G and before the number of failed components has fallen below F +1 . We will use the state cloning technique with F =0 ,i.e. clones of all states s 2 G ,f o g will be added to U .The selection of F =0 is made to ease the generation of G . With F =0 , G includes states which are reachable through G fromstate o and generationof G fromahigh-levelmodelingformalism. With F> 0 , G may contain states which are reachable from o through U and generation of G requires a priori knowledgeabout the set of states of X . The modified X has the structure depicted in Figure1, where U k includes all states in U with exactly k failed components and N is the number of components of the system. In the following, X will denote the modified X . Throughout the paper we will denote by  s;s 0 , s; s 0 2  , the transition rate from state s to state s 0 ,by  s = P s 0 2  s 6 = s 0  s;s 0 , s 2  , the output rate of s , and by  s;C = P s 0 2 C  s;s 0 , s 2  , C   , the transition rate from s to the subset of states C , all referred to X unless otherwise stated. We will also consider several transient CTMC Y . Each such Y has state space B [f a g , where all states in B are transient and a is an absorbing state, and has a welldefined initialprobabilitydistributionwith P [ Y (0) 2 B ]= 1 .  ( s; Y ) , s 2 B , willdenotethemean timespentby Y in s before absorption, and  ( C; Y )= P s 2 C  ( s; Y ) , C  B , will denote the mean time to absorption in subset C .It is well-known that the mean time to absorption vector  = (  ( s; Y )) s 2 B isthesolutionofthelinearsystem A  = , q , where A istherestrictionto B of the infinitesimalgenerator of Y ,and q =( P [ Y (0) = s ]) s 2 B . It is also known that  ( s; Y )  s;s 0 istheexpected numberoftimesthatatransition from s to s 0 , s 2 B , s 0 2 B [f a g , is followed. 3. Bounds for the Steady-stateUnavailability Consider the regenerative behavior of X , taking as regeneration points the times at which X enters o from U .Let T G and T U be the contributions of G and U to the mean time between regenerations of X ,andlet C G and C U be the respective contributions to the mean down time. From regeneration process theory (see, for instance [7]), we have UA = C G + C U T G + T U : Assume that upper bounds [ T U ] ub and [ C U ] ub for, respectively, T U and C U are known. Then [2, Theorem 2] [ UA ] lb = C G T G +[ T U ] ub ; (1) [ UA ] ub = C G +[ C U ] ub T G +[ C U ] ub ; (2) are, respectively, a lower and an upper bound for UA. Let Y G be the transient CTMC with state space G [ f a g and initial state o built from X by directing to a the transitions from states in G to states in U . T G and C G can be expressed in terms of the mean time to absorption vector of 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 er b ound [ T U ] ub The upper bound [ T U ] ub is the same as that of [2, 15]. Let FC be the set of different cardinalities of the failure bags of the model, let E i be the subset of E including all failure bags of cardinality i and let f i = P e 2 E i  ub ( e ) . Consider the transientCTMC Y u k with state space S N k =1 f u k g[f a g , initial state u k and the state transition diagram shown in Figure 2. For each state u k and each i 2 FC , k + i  N , there is a transition to u k + i with rate f i , and a transition to u k , 1 if k> 1 and a otherwise with rate g ( k ) .Let T ( k ) be the mean time to absorption of Y u k and let  k = X s 2 G  ( s; Y G )  s;U k (5) be the probability that X enters U through U k . Then [2, Theorem 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) f 1 f 1 f 2 f 2 f 1 f 1 g (1) u N a Figure 2. State transition diagram of the transient CTMC Y u k . upper bounds T U . An efficient method to compute T ( k ) , 1  k  N , is described in [2]. 3.2. Upp er Bound [ C U ] ub Theupperbound [ C U ] ub isbasedonlowerboundsforfailure distances. The failure distance from a state s 2  , d ( s ) ,is defined [2] as the minimum number of components which have to fail in addition to those already failed in s to take the system down. Let F ( s ) be the bag of failed components in s 2  . Assume that a lower bound for d ( s ) , e d ( s ) ,is available satisfying: A1. 0  e d ( s )  d ( s ) , A2. e d ( s )=0 if and only if 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 ) . NotethatassumptionA3impliesthatgiven atransitionfrom s to s 0 , s; s 0 2  , associated with a failure bag e 2 E , e d ( s ) ,j e j e d ( s 0 )  e d ( s ) . Let e U k;d be the subset of U including all states s with k failed components and e d ( s )= d ,andlet e L = e d ( o ) .Theset e R of ( k; d ) pairs for which e U k;d might be 6 = ; is given by the constraints 1  k  N; max f 0 ; e L , k g d  min f e L; N , k g : The constraintson k are obvious. The constraints e L , k  d and d  e L followfromassumption A3 and the definitionof e L ; 0  d follows from assumption A1. Finally, d  N , k follows from assumption A3 and the fact that the structure functionof thesystem is coherent by taking s 0 the state with all components failed and noting that e d ( s 0 )  d ( s 0 )= 0 and, therefore, e d ( s 0 )=0 . Let Y s U , s 2 U be the transient CTMC with state space U [f a g and initial state s built from X by directing to a the transitions from states in U to o .Let C s U be the mean down time to absorption of Y s U . Recalling that P s 0 2 G  ( s 0 ;Y G )  s 0 ;s , s 2 U , is the probability that X enters U through s ,wehave 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) Let e C ( k; d ) be upper bounds for 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) Let [ C U ] ub = X ( k;d ) 2 e R e  k;d e C ( k; d ) : (9) We have Theorem 1. Assume C s U  e C ( k; d ) , s 2 e U k;d ,Then, C U  [ C U ] ub . Proof. Using (7), the fact that 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 : Let L be the exact failuredistance from state o ,i.e. L = d ( o ) ,andlet e C ( k )= N X i = e L  ( u i ;Y u k ) : (10) We have Theorem 2. C s U  e C ( k ) , s 2 U k . Proof. By assumption A1, e L  L . Using that [2, Theorem 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 computed efficiently using the method described in [2] for C ( k ) , 1  k  N , with L replaced by e L . The bounds e C ( k; d ) are computed usingan iterativeprocedure which starts with e C ( k; d )= e C ( k ) and improves the bounds using potentially better bounds e C 0 ( k; d ) until no significant improvement is achieved. Let s 2 e U k;d and consider a transition from s to s 0 2 U associated with a failure bag e 2 E i , i 2 FC . Clearly, s 0 2 e U k + i;d 0 forsuitable d 0 values. Imposing ( k + i; d 0 ) 2 e R , i  N , k and d 0  min f e L; N , k , i g . Moreover, from assumptions A1 and A3, max f 0 ;d , i g d 0  d . Therefore, the only feasible destination subsets e U k + i;d 0 , i 2 FC , are those satisfying i  N , k and (recall that d  e L ) max f 0 ;d , i g d 0  min f d; N , k , i g .Let e R 0 = f ( k ; d; i; d 0 ) j ( k; d ) 2 e R , i 2 FC , max f 0 ;d , i g d 0  min f d; N , k , i gg . Assume that upper bounds e F ( k ; d; i; r ) , ( k ; d; i; r ) 2 e R 0 ,for P r d 0 =0  s; e U k + i;d 0 , s 2 e U k;d , are available and let e f 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 = !; where  = max f 0 ;k + d + i , N g and ! = min f i; d g . The upper bounds e C 0 ( k; d ) are computed 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 f i;j ( k; d ) e C ( k + i; d , j ) ; (11) where I c is the indicator function returning1 if c is true and 0 otherwise. The algorithm to compute the e C ( k; d ) bounds is given in Figure 3. The parameter  is a tolerance factor which determines when the improvement is small enough for the algorithm to stop. Next, we prove that the e C ( k; d ) computed by the algorithm of Figure 3 upper bound C s U , s 2 e U k;d ,provided that e F ( k ; d; i; r ) , ( k ; d; i; r ) 2 e R 0 ,and e F ( k ; d; i; d ) , ( k ; d; i; d ) 2 e R 0 , are decreasing on d . The proofwillconsist of a sequence of three propositionsand a theorem. Proposition 1. Let ( k; d ) 2 e R . Assume that C l U  e C ( k; d ) , l 2 e U k;d , and that e C ( k; d ) is decreasing on d . Then, C l U  e C 0 ( k; d ) , l 2 e U k;d . Proof. Let l 2 e U k;d . By assumption A2, d =0 if and only if l 2 D . Therefore, C l U is equal to the mean time in for (all ( k; d ) 2 e R ) e C ( k; d )= e C ( k ) ; do f  0 =0 ; for ( k =1; k  N ; k ++) for ( d = max f 0 ; e L , k g ; d  min f e L; N , k g ; d ++) f Compute e C 0 ( k; d ) using (11); if ( e C 0 ( k; d ) < e C ( k; d )) f  0 = max f  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   ) ; Figure 3. Algorithmto compute the e C ( k; d ) bounds. l ,if d =0 , plus the mean down time from the next state m ,if m 2 U . Let us discuss next to which subsets e U k 0 ;d 0 m may belong. By assumption A3, a transition associated with a repair action involvingone component can only lead to m 2 e U k , 1 ;d 0 , k> 1 (if k =1 , m = o= 2 U ), d  d 0  d +1 . d 0 = d is possible only if ( k , 1 ;d ) 2 e R , i.e. d> e L , k ; similarly, d 0 = d +1 requires d< e L . Consider now transitions associated with failure bags e 2 E i , i 2 FC . Clearly, m 2 e U k + i;d , j for suitable j values. Imposing ( k + i; d , j ) 2 e R , i  N , k and d , j  min f e L; N , k , i g . Furthermore, from assumptions A1 and A3, max f 0 ;d , i g d , j  d . Therefore, the only feasible e U k + i;d , j subsets are those satisfying (recall that d  e L ) max f 0 ;k + d + i , N g j  min f i; d g . Based on this discussion we can write 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 f i;d g X j =max f 0 ;k + d + i , N g X m 2 e U k + i;d , j  l;m  l C m U : Using that, by assumption, C m U  e C ( k 0 ;d 0 ) , m 2 e U k 0 ;d 0 , and introducing the notation g j ( l )=  l; e U k , 1 ;d + j , f ij ( l )=  l; e U k + i;d , j , J m ( i ) = max f 0 ;k + d + i , N g ,and J M ( i )= min f i; d g , C l U  T 1 + T 2 + X i 2 FC i  N , k T 3 ( i ) ; with 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 ) f ij ( l )  l e C ( k + i; d , j ) : From this point, the proof continues exactly as in [2, Proposition 1] setting F =0 and substituting L , C ( k; d ) , F ( k ; d; i; r ) ,and f i;j ( k; d ) by, respectively, e L , e C ( k; d ) , e F ( k ; d; i; r ) ,and e f i;j ( k; d ) . Proposition 2. Assume that e C ( k; d ) , ( k; d ) 2 e R , e F ( k; d; i; r ) , ( k ; d; i; r ) 2 e R 0 , and e F ( k ; d; i; d ) , ( k ; d; i; d ) 2 e R 0 , are decreasing on d .Then e A ( k ; d; i )= min f i;d g X j =max f 0 ;k + d + i , N g e f i;j ( k; d ) e C ( k + i; d , j ) ; i 2 FC ;i  N , k , is decreasing on d . Proof. The proof is exactly as in [2, Proposition 2] replacing A ( k ; d; i ) , R , C ( k; d ) , F ( k ; d; i; r ) , F ( k ; d; i; d ) ,and f i;j ( k; d ) by, respectively, e A ( k ; d; i ) , e R , e C ( k; d ) , e F ( k; d; i; r ) , e F ( k ; d; i; d ) and e f i;j ( k; d ) . Proposition 3. Assume that e C ( k; d ) , ( k; d ) 2 e R , e F ( k; d; i; r ) , ( k ; d; i; r ) 2 e R 0 , and e F ( k ; d; i; d ) , ( k ; d; i; d ) 2 e R 0 , are decreasing on d .Then e C 0 ( k; d ) , ( k; d ) 2 e R , is decreasing on d . Proof. Let ( 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 ) ; with 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 ) ; where e A ( k ; d; i ) is as defined in Proposition 2. We will show that T 1 , T 2 and T 3 ( i ) are all  0 .Since ( k; d ) 2 e R , d  0 and d +1 > 0 . Therefore, T 1 = I d =0 =g ( k )  0 . Regarding T 2 , three cases must be considered: 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 decreasing on d ; in case c, d +1 > e L , k because ( k; d ) , ( k; d +1) 2 e R , and, thereby, T 2 ( i )= e C ( k , 1 ;d +1) , e C ( k , 1 ;d +1) = 0 . Finally, T 3 ( i )  0 by Proposition2. Theorem 3. Assume that e F ( k ; d; i; r ) , ( k ; d; i; r ) 2 e R 0 , and e F ( k ; d; i; d ) , ( k ; d; i; d ) 2 e R 0 , are decreasing on d . Then, the e C ( k; d ) computed by the algorithm of Figure 3 upper bound C s U , s 2 e U k;d , and are decreasing on d . Proof. Consider the algorithm split into phases, where each phase includes the operations performed within the k -loop, and let e C m ( k; d ) , m  0 , be the bounds e C ( k; d ) available after phase m . The proof will be by induction over m . e C 0 ( k; d )= e C ( k ) , which are (non-strictly) decreasing on d and, by Theorem 2, upper bound C s U , s 2 U k . Assume now that the e C m ( k; d ) upper bound C s U , s 2 e U k;d ,and are decreasing on d .Let k 0 be the value of k for which the bounds are updated in phase m +1 . According to (11), C m +1 ( k 0 ;d ) only depend on C m ( k; d ) for k 6 = k 0 , and all C m +1 ( k 0 ;d ) are computed using the same set of bounds C m ( k; d ) . Then, Proposition 1 guarantees that C 0 ( k 0 ;d ) are correct, and Proposition 3 that they are decreasing on d . Using the induction hypothesis, this implies that C m +1 ( k 0 ;d ) = min f C m ( k 0 ;d ) ;C 0 ( k 0 ;d ) g are correct and decreasing on d . We conclude this section by deriving suitable upper bounds e F ( k ; d; i; r ) for P r d 0 =0  s; e U k + i;d 0 , s 2 e U k;d .Trivially, e F ( k ; d; i; min f d; N , k , i g )= f i upper bounds P min f d;N , k , i g d 0 =max f 0 ;d , i g  s; e U k + i;d 0 .Let e  ( e ) , e 2 E , bethelowerboundforthefailuredistancefromastatewhose bag of failed componentsis e .Let s 0 2 U be a state reached from s 2 e U k;d through a transition which has associated with it the failure bag e .Since F ( s 0 )= F ( s )+ e ,wehave, by assumptionA3, that e d ( s 0 ) cannot have been reduced with respect to e  ( e ) by more than k ,i.e. e d ( s 0 )  e  ( e ) , k .Then e F ( k ; d; i; r )= X e 2 E i e  ( e )  k + r  ub ( e ) ; max f 0 ;d , i g r< min f d; N , k , i g upper bounds P r d 0 =max f 0 ;d , i g  s; e U k + i;d 0 , r< min f d; N , k , i g .Trivially, both e F ( k ; d; i; r ) , ( k ; d; i; r ) 2 e R 0 and e F ( k ; d; i; d )= f i , ( k ; d; i; d ) 2 e R 0 , are (non-strictly) decreasing on d , thus fulfillingthe conditionsimposed by Theorem 3. 4. Lower Bounds for Failure Distances In this section we derive lower bounds for failure distances fulfillingassumptionsA1–A3ofSection3.2. Wealsoderive efficient algorithms to compute the bounds. 4.1. Denition of Lower Bounds for Failure Distances We assume, without loss of generality, that the fault tree of the system is made up of a set P of AND and OR gates and aset I of inputs. We will denote by C the set of component types of the system, and by g r the rootgate of the fault tree. Eachinputhastheform c [ n ] , c 2 C ,meaningthefailureof n componentsoftype c . Theexistence oftypesofcomponents introducessome dependencies among the inputs of the fault tree. It willbe said that two inputsare related if they involve components of the same type, i.e. are of the form c [ n ] , c [ n 0 ] , n 6 = n 0 . To avoid trivialities,we assume that there are no related inputs feeding the same gate. This is not a real restriction since for n 0 >n and denoting by ^ and _ the logical “and” and “or” operators, respectively, c [ n ] _ c [ n 0 ] can be substituted by c [ n ] and c [ n ] ^ c [ n 0 ] by c [ n 0 ] . Each node x (i.e. an input or a gate) of the fault tree feeds a set of gates fo( x ) and each gate y is fed by a set of nodes ( y ) .Let val( x ) 2f 0 ; 1 g be the value of node x .If x is a gate, val( x ) is determined as usual from the values of its inputs. If x = c [ n ] is an input, val( x )= 1 if and only if n or more components of type c have failed. Since the value of a node is equal to 1 if and only if a suitable collection of componentsof thesystem being modeled have failed, nodes will also be referred to as events. In this regard, the event x 2 I [ P will be said to be realized if val( x )=1 . Let us denote a bag of failed components, F ,as F = c 1 [ n 1 ] c 2 [ n 2 ] :::c k [ n k ] , c l 6 = c m , l 6 = m , meaning that F contains n i instances of component type c i . It will be said that c i [ n i ] is part of F . The distance from a bag of failed components F to an event x 2 I [ P , d b ( F; x ) ,isdefined as the minimum number of components which have to fail in addition to those which are already part of F to realize x . From that definition, given the bag of failed components F ( s ) of a state s 2  , d ( s )= d b ( F ( s ) ;g r ) .Let e d b ( F; x ) , x 2 I [ P , be a lower bound for d b ( F; x ) .Thelower bounds e d ( s ) , s 2  ,are e d ( s )= e d b ( F ( s ) ;g r ) .Suchlower bounds will be computed on the fault tree using the concept of module, defined as a gate such that the subtree hanging from it has that gate as only exit point and every input of the subtree does not have related inputs outside the subtree. The gates which are modules can be determined using the algorithmLTA/DR of [10] witha small modificationto take into account types of components: during the first depthfirst, left-most traversal of the fault tree (step no. 2 of the algorithm), a visit to c [ n ] 2 I implies simultaneous visits (i.e. withthesame “timestamp” as for c [ n ] )toallitsrelated inputs. Let F beabagoffailedcomponents. e d b ( F; x ) , x 2 I [ P , is recursively defined as follows. If x = c [ n ] 2 I : e d b ( F; x )  ( n if no c [ n 0 ] is part of F max f 0 ;n , n 0 g otherwise ; (12) if x is an OR gate: e d b ( F; x )  min y 2 ( x ) f e d b ( F; y ) g ; (13) and if x is an AND gate, 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 ) f 0 ; e d b ( F; y ) g o ; where A ( x ) f y 2 ( x ) j y is a module ^j fo( y ) j = 1 g , B ( x ) f y 2 ( x ) j y is a module ^j fo( y ) j > 1 _ y is not a module ^ y 2 I g and C ( x ) f y 2 ( x ) j y is not a module ^ y 2 P g . The lower bounds for failure distances recursively defined by (12), (13) and (14) fulfill assumptions A1–A3 of Section 3.2 [20, Theorems 2 and 4]. 4.2. An Algorithm for the Computation of Lower Bounds for Failure Distances Expressions (12), (13) and (14) allow to compute e d b ( F; g r ) traversing the fault tree depth-first, left-most starting at g r . However, this procedure could be expensive if the fault tree is large. Next, we develop more efficient algorithms to compute e d ( s ) . Each node x of the fault tree holds a “distance variable”, dv ( x ) , and thefault tree is initializedso that dv ( x )= e d b ( ; ;x ) . Such an initialization is performed traversing depth-first, left-most the fault tree starting at g r and using (12), (13) and (14). Note that after the initialization procedure, e L = e d b ( ; ;g r ) is known. e d b ( F ( s ) ;x ) < e d b ( ; ;x ) , x 2 P , requires e d b ( F ( s ) ;y ) < e d b ( ; ;x ) for some y 2 ( x ) . Therefore, since e d ( s )  e L , e d ( s )= e d b ( F ( s ) ;g r ) will be equal to e L unless e d b ( F ( s ) ;y ) < e L for some y 2 ( x ) .The same argument can be iteratively applied going down the fault tree until the inputs. This justifies the following algorithm which computes e d ( s ) processing the fault tree from inputs to g r . For each c [ n ] which is part of F ( s ) , based on (12) we make dv ( c [ n 0 ]) = max f 0 ;dv ( c [ n 0 ]) , n g for each input c [ n 0 ] . Each update of dv ( x ) for an input x which resultsin dv ( x ) < e L ispropagateddepth-first,left-mostupthe faulttreeusing(13)and(14)while dv ( z ) < e L forthevisited node z . Note that the algorithm computes the correct lower bounds for distances from F ( s ) to the nodes x for which e d b ( F ( s ) ;x ) < e L , so, at the end, dv ( g r ) will hold e d ( s ) . Note also that the initialization dv ( x )= e d b ( ; ;x ) needs to beperformedonlyonceifwhilecomputing e d ( s ) thechanges in the dv ( x ) variables are incrementally kept in a suitable datastructure,e.g. astack. Wecallgenericallythealgorithm comp d ( F; ub ; DS ) ,where F is a bag of failedcomponents, ub is an upper bound for the distance to be computed and DS is a stack. The algorithm returns e d b ( F; g r ) if that value is < ub . Inthis regard, e d ( s )= comp d ( F ( s ) ; e L; DS ) .Once e d ( s ) hasbeencomputed,thefaulttreeisrestored toitsinitial state simply undoing the changes kept in DS. We call this procedure restore d(DS). Let s be a state in the frontier of G and let S be the set of states s 0 reached from s in a single failure transition. Computation of [ C U ] ub using (8) and (9) requires the computation of e d ( s 0 ) , s 0 2 S . We describe next how e d ( s 0 ) , s 0 2 S are computed assuming that e  ( e ) is known for all e 2 E ( e  ( e )= comp d ( e; e L; DS ) ). Each transition from s to s 0 2 S has associated with it a failure bag e s 0 2 E and F ( s 0 )= F ( s )+ e s 0 . Moreover, we have that lb s 0 = max f 0 ; e d ( s ) ,j e s 0 jg  e d ( s 0 )  min f e d ( s ) ; e  ( e s 0 ) g = ub s 0 .The dv ( x ) variables of the fault tree are set to e d b ( F ( s ) ;x ) if e d b ( F ( s ) ;x ) < e L and e d b ( ; ;x ) otherwise by calling comp d ( F ( s ) ; e L; DS ) . Next, for each s 0 2 S , e d ( s 0 )= lb s 0 if lb s 0 = ub s 0 . Otherwise, we set d  = comp d ( e; ub s 0 ; DS 0 ) . Because of the characteristics of the algorithm comp d (  ) , we will have d  = e d ( s 0 ) if e d ( s 0 ) < ub s 0 and d  = e d ( s ) otherwise. Therefore, since ub s 0  e d ( s ) , e d ( s 0 ) = min f d  ; ub s 0 g . Next, we call restore d(DS’) to allow another e d ( s 0 ) to be computed, and once e d ( s 0 ) has been computed for all s 0 2 S , we call restore d(DS) to restore the fault tree. 5. Analysis and Comparison In this section we analyze the performance of the proposed boundingmethod and compare it with thebounding method proposed in [2] using the same state space exploration algorithm. The bounding method proposed in [2] is analogous to the one proposed here except that it uses exact failuredistances computed using the set of minimal cuts of the fault tree of the system, and boundingstructures F ( k ; d; i; r ) upper bounding P r d 0 =0  s;U k + i;d 0 , s 2 U k;d , the subset U k;d including the states with k failed components and failure distance d . We willalso compare the method proposedhere withthe boundingmethod proposed in [15]. In that method, 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 Figure 4. Architecture of the first example. the lower bound for UA is also [ UA ] lb but the upper bound is [ UA ] 0 ub = C G +[ T U ] ub T G +[ T U ] ub : In all cases the subset G is incrementally generated until the relative unavailability band, ([ UA ] ub , [ UA ] lb ) = [ UA ] lb , is smaller than orequal to thedesired one. For the proposed bounding method and the method proposed in [2] the generation is done using the algorithmCONT TG W proposed in [5]. For the bounding method described in [15] we use an analogous algorithm CONT TG W, where the contributions to the relative unavailability band are associated only with the parameter k (number of failed components of the successors). Both algorithms allow to tradeoff the number of times (  ( s; Y G )) s 2 G is computed against how accurately the state space is explored by means of a control parameter BR , 0  BR < 1 (the larger BR , the more accurate but more costly the exploration). After some experimentation we have found BR =0 : 1 to be a reasonable choice. The R parameter used in the algorithm for the computation of exact failure distances described in [2] was set to 2. The analysis and comparison will be made using two examples. The first example, whose architecture is depicted in Figure 4, includes three processing clusters which communicate through two independent double-ringnetworks A and B . Processing cluster i , 0  i  2 , includes three identical processing units PU i .Network A includes six nodes NA i , 0  i  5 , and direct (clockwise) and reverse (counter-clockwise) links, DA i and RA i , respectively, linking nodes NA i and NA i +1 mo d 6 .Network B has the same structure as network A and its direct and reverse links are called, respectively, DB i and RB i . Thesystemisoperational if each processing cluster has at least an unfailed processing unit and all processing clusters can communicate using one of the networks. The operational configuration of the systemincludestwoprocessingunitsfortheprocessingclusters with two or three unfailed processing units, one processing unitfor the processing clusters withone unfailedprocessing unit, and the components of either network A or B , with priority given to network A , required to build one of the operational configurations of the networks described next. The networkconfigurationwhichis triedfirst is a direct ring including all nodes and direct links. The second configuration which is tried is a reverse ring including all nodes and reverse rings. The third configuration is used when parallel direct and inverse link i fail and it includes all nodes and links except the links between nodes i and i +1mod6 . The last configuration is used when node i fails and it includes all nodes except node i and all links except those between node i and nodes i  1mod6 . A fault in a processing unit of a cluster contaminates another unfailed unit in the same cluster with probability 0.05. The components included in the operational configuration of the system are called active. Active processing units, active nodes and active links fail with rates 4 : 6  10 , 4 h , 1 , 2 : 3  10 , 4 h , 1 and 1 : 1  10 , 4 h , 1 . Inactive components fail with the same rates multiplied by a dormancy factor of 0.2. We assume that there is a single repairman who takes for repair failed components at random. Repair rates for processing units, nodes and links are, respectively, 0 : 5 h , 1 , 0 : 7 h , 1 and 1 : 0 h , 1 . Components continue to fail when the system has failed. The second example is as the first one but with the number of nodes of both networks increased up to ten and the number of processing clusters increased up to five. For both examples L =3 and e L =2 . The fault tree has 8,653 minimal cuts for the first example and 87,031 for the second one. We show in Figure 5 the relative unavailabilityband as a functionofthenumberofstatesin G fortheproposedbounding method and the methods described in [2] and [15]. The results have been obtained in a 128 MB UltraSparc workstation. It can be seen that the proposed bounding method outperforms significantly the bounding method described in [15] in terms of the size of G . Thus, for the first example, the number of states required by the method described in [15] to achieve a given relative unavailabilityband ranges from 4.9 to 12.6 times the number of states required by the proposed bounding method. With regard to the method described in [2], the proposed method requires a number of statesabout2.6timeslarger. However,theboundingmethod describedin[2]requirestobookkeepinmemorytheminimal cuts and related datastructures, and thisoverhead may make the memory consumption (which is really the parameter of interest) larger than that of the proposed method. Both the 0.01 0.1 0 10000 20000 30000 relative band states proposed [2] [15] 0.01 0.1 0 15000 30000 45000 60000 75000 90000 relative band states proposed [2] [15] Figure5. Relative unavailabilityband as a functionof thenumber of states in G for the proposed boundingmethod, the method described in [2] and the method described in [15], for the example with three processing clusters (left) and five processing clusters (right) and BR =0 : 1 . proposed boundingmethod and the method described in [2] have to hold, for each state in the frontier of G , lists of contributionsto the unavailability band associated with the parameters k and d while the lists of contributionswhich have to be held for those states in the method described in [15] are associated only with the parameter k . Then, it is meaningful to compare the three bounding methods in terms of memory consumption. The comparison is done in Figure 6, which plots unavailability relative band against (estimated) memory consumption. The proposed bounding method is again far more efficient than the method described in [15] and more efficient than the method described in [2]. The smallertherelativeunavailabilityband,however, thesmaller thedifferenceintermsofmemoryconsumptionbetween the proposed method and the method described in [2]. This is due to the fact that j G j increases and, thereby, the memory consumption due to storing the state descriptions of G and the listsof contributionsto theunavailabilityband becomes relatively more important than the overhead introduced by storing the minimal cuts and related data structures. The overhead due to the computation of lower bounds for failure distances is negligible regarding memory consumption. The overhead in terms of CPUtime consumption depends onthesizeof thefaulttree. Thefaulttreeofthefirst example has 39 inputs, 32 gates and 431 edges. The fault treeof thesecondexample has 65inputs,48 gates and 1,193 edges. We have profiled our code and have found a time overhead due to the computation of lower bounds for failure distances of 7.8% in the first example with j G j = 8,608 states and 15.8% in the second example with j G j = 9,568 states. Then, although increasing with the size of the fault tree, the overhead in CPU time due to the computation of lower bounds for failure distances is reasonable. 6. Conclusions In this paper we have proposed a new method to compute bounds for the steady-state unavailability, which is based on lower bounds for failure distances. We have developed algorithms to compute such distances on the fault tree of the system. The proposed bounding method generates incrementally a subset of the state space using a previously proposedstatespaceexplorationalgorithm. Numericalanalysis has shown that in terms of number of states needed to achieve a given accuracy, the proposed method outperforms a previously proposed method not based on the failure distance concept and is worse than a previously proposed method which uses exact failure distances. However, when compared in terms of memory consumption, the proposed bounding method can outperform the bounding method which uses exact failure distances if the number of minimal cuts is large. Therefore, the proposed method is a good tradeoff between bounds tightness and memory consumption when the number of minimal cuts of the system is large. References [1] R. E. Barlow and F. Proschan. Statistical Theory of Reliability and Life Testing. Probability Models. McArdle Press, Silver Spring, 1981. [2] J. Carrasco. Tight steady-state availability boundsusing the failuredistanceconcept.PerformanceEvaluation,34:27–64, 1998.