Failure distance based bounds of dependability measures

4MMMMMMMMMMM MMMMMMMMMMMr 4MMMMMMMMMMM Failure Distance Based Bounds of Dependability Measures Victor Manuel Suñé Socías Departament d'Enginyeria Electrònica Universitat Politécnica de Catalunya Doctoral dissertation submitted in fulfillment of the requirements for the Doctor degree in Industrial Engineering 2000 Contents Preface vii 1 Introduction 1 1.1 Fault-Tolerant Systems and Modeling 2 1.2 CTMC and the Largeness Problem 4 1.3 Bounding Methods 6 1.4 A Brief Review of Bag Theory 8 1.5 Class of Models Considered in the Dissertation 10 1.6 Outline of the Dissertation 13 2 Failure Distances and Minimal Cuts 17 2.1 The Problem of Computing the Failure Distance from a State 17 2.2 Algorithms to Compute Failure Distances 20 2.3 An Algorithm to Compute Minimal Cuts 23 2.4 Algorithm Analysis 36 2.5 Conclusions 40 3 Reliability Bounds of Non-repairable Systems using FD 43 3.1 Method Description and Justification 43 iii 3.2 Analysis and Comparison 50 3.3 Conclusions 53 4 Reliability Bounds of Non-repairable Systems using FD Bounds 55 4.1 Bounding Method 57 4.2 Lower Bounds for Failure Distances 62 4.2.1 Recursive Definition of Lower Bounds for Failure Distances .... 63 4.2.2 Correctness of the Lower Bounds for Failure Distances and Related Results 64 4.2.3 Algorithms for the Computation of the Lower Bounds for Failure Distances 72 4.3 Analysis and Comparison 83 4.4 Conclusions 91 5 Availability Bounds of Repairable Systems using FD 93 5.1 Extension to Group Repair 93 5.2 Improved Failure Rate Bounding Structures 106 5.3 State Space Exploration Algorithm 114 5.4 Analysis and Comparison 116 5.5 Conclusions 124 6 Availability Bounds of Repairable Systems using FD Bounds 125 6.1 Bounding Method 125 6.2 Failure Rate Bounding Structures 134 6.3 Analysis 135 6.4 Conclusions 139 V 7 Conclusions and Future Work 141 vi Preface A la meva família. The topic of this dissertation is efficient bounding methods for Markovian dependability models of fault-tolerant systems. Ultimately, the complexity of the fault-tolerant systems for which reasonably tight bounds can be computed is limited by the memory consumption of the methods, which depends on their efficiency. The work described in this dissertation has as baseline the idea that by exploiting the failure distance concept more efficient bounding methods could be developed. The research described in this dissertation has confirmed that intuitive idea. Although a lot of work remains to be done, we think that the work described in this dissertation is a good starting point for what is left. I am grateful to Prof. Juan A. Carrasco for having introduced me in the area of this dissertation (Markovian modeling of fault-tolerant systems), for having proposed me such an exciting research topic, and for his help along the work, especially in the more difficult spots. VIH Preface Chapter 1 Introduction Increasing complexity of information processing systems and increasing importance of the dependability of those systems has fostered the use of fault-tolerance. Fault-tolerance is a methodology to achieve high dependability using components with moderate reliability and, thus, moderate cost. Fault-tolerance is achieved through the use of redundancy, that is information, resources, or time beyond what is strictly required for operation in the absence of faults. Redundancy can take one of several forms [54]: • Hardware redundancy: extra hardware, usually for the purpose of either detecting or tolerating faults. • Software redundancy: extra software, beyond what is needed to perform a given function, to detect and possibly tolerate faults. • Information redundancy: extra information beyond that required to implement a given function; for example, error detecting codes. • Time redundancy: time to perform functions such that fault detection and often fault tolerance can be achieved. Through the use of redundancy a fault-tolerant system is able to detect and tolerate faults, so that the system still continues in correct operation in the presence of faulty components. Redundancy implies extra cost over a non-fault-tolerant system. However, fault-tolerance is an attractive alternative to the use of highly reliable components with high cost, and often results in less costly systems with similar or higher dependability. It is for this reason that fault-tolerance has achieved increasing popularity and its use 2 1 Introduction is not restricted to applications requiring very high dependability. Unmanned space flights, satellites, avionics, nuclear power plants, distributed systems, communication networks, routers, multiprocessors, interconnection networks and high-density memories are examples of application areas where fault-tolerance has found wide acceptance. 1.1 Fault-Tolerant Systems and Modeling A fault-tolerant system is designed to achieve a certain degree of dependability. To achieve such a degree of dependability, it is necessary to put redundancy in the system. The addition of redundancy to the system increases its cost. Under that perspective, the design and implementation of a fault-tolerant system can be seen as an optimization problem, with the goal of achieving the desired dependability level at the minimum cost. Fault-tolerance is an art, making the problem very difficult. In practice, the design and implementation of a fault-tolerant system is strongly guided by heuristics and previous experience. Nevertheless, usually several candidate architectures with different degrees of redundancy are considered and their cost and dependability are analyzed. The one that better solves the optimization problem is the one selected at the considered design detail. The process continues till the design of the system is completed. After the system is implemented, it is necessary to certificate that the system achieves the required dependability level. Dependability is a generic concept encompassing many measures, such as the steadystate availability, the mean time to failure, and the reliability. Depending on the application, one or several of such measures will be the more appropriate ones and will be selected to quantify system dependability. Often, the system has graceful degradation. This means that, as faults occur, the performance of the system degrades before failing. For that class of systems, a combined evaluation of the system's performance and dependability is appropriate. Such a combined measure is generically called performability [69]. Performability is itself a generic concept (as dependability is) and can be particularized into many measures. Many of those measures can be defined assuming a reward structure over a stochastic process [87]. In summary, the system ability to offer correct service is quantified using some or several dependability/performability measures. Experimental quantification of the selected dependability/performability measure is difficult or impossible. It is clearly impossible in a design stage, since the real system is not available for experimentation. Even when the real system or a prototype is available, direct experimental evaluation of system's dependability/performability is often extremely 1.4 A Brief Review of Bag Theory 9 element c¿, 1 < i < k. With that notation, the previous example bags are described as Ò! = o[l]6[l]c[l], h = a[l]b[l]c[2], and b3 = b[2]c[2]. In set theory, the basic concept is membership. In bag theory, that concept is replaced by the number of instances function. For an element x £ V and a bag b, we denote the number of instances of a; in 6 by #(x,ò). The cardinality \b\ of a bag b is simply the number of instances of elements in the bag, i.e. |6| = £#(*,&). An element a; is a member of a bag 6 if #(x,b) > 0. This is denoted as x Ç b. If #(x, 6) = 0, then x £b. The empty bag, 0, is the bag with no members, i.e. #(a;, 0) = 0, x € V. A bag a is a subbag of a bag b (denoted o C b) if every element of a is also an element of 6 at least as many times, i.e. if and only if #(a;,a) < #(x,ò), x G V. Two bags a and 6 are equal (denoted a — b) if and only if #(a;, a) = #(x, b), x Ç.V. The following four operations are defined on bags: bag union a U ò is the bag defined as #(Í,OU6) = max{#(i,a),#(x,ò)}, x eV. bag intersection a D b is the bag defined as #(i,aflo) = min{#(x,a), #(x,6)}, x Ç.V . bag sum a + b is the bag defined as #(x,a + b) = #(x,a) + #(x,b), xeV. bag difference a — b is the bag defined as #(x, a — b) = #(x, a) — #(x, a ("l b) — max{#(i, a) - #(x, b), 0}, x € V. These operators have most of the properties that would be expected. Union, intersection, and sum are commutative and associative. In addition, the expected inclusions hold: oflôCûCoUô, a — b C a C a-\-b. 10 1 Introduction The distinction between union and sum is clearly stated by |aUò| < \a\ + \b\, \a+b\ = \a\ + \b\. No such simple statement distinguishes ano from a — b. 1.5 Class of Models Considered in the Dissertation The topic of this dissertation is bounding methods for dependability measures. The bounding methods we will develop apply to a certain, wide class of dependability models. That class of models is described formally in this section. We will also discuss how coverage failures, which are important in the modeling of fault-tolerant systems, can be accommodated within the assumed modeling framework. Also, as it has been commented in Section 1.3, bounding methods require some high-level knowledge about the behavior of the CTMC model out of the generated state space G. The high-level knowledge required by the bounding methods developed in the dissertation will also be detailed in this section. We consider dependability models that result from conceptualizing a fault-tolerant system as made up of components (hardware or software). In order to capture elementary symmetries, we allow component classes, a particular component being an instance of some component class. Formally, the system includes a bag C of component classes over a certain domain V. We assume that the up/down state of the system is determined from the unfailed/failed state of the components of the system through a coherent structure function (see, for instance, [8]) specified by a fault tree with basic event classes made up of OR and AND gates and with inputs atoms of the form c[n], c € C, n > 1, which evaluate to true if and only if at least n instances of component class c are failed. We allow arbitrary connections between the gates of the fault tree (as far as the fault tree has only one output and it has not feedback). As an example, Figure 1.1 gives the fault tree corresponding to a fault-tolerant system that is failed if and only if one instance of component class a and two instances of component class b or two instances of component class a and one instance of component class b are failed. The CTMC models we will consider have "failure" and, for repairable systems, "repair" transitions. Each state s of the CTMC (except the absorbing state indicating failure of the system when the measure under consideration is the unreliability at time t, ur(t)) has associated with it a bag of failed component classes F(s). There is a single 1.5 Class of Models Considered in the Dissertation 11 a[l] b[2] a[2] b[l] Figure 1.1: Example fault tree. state o without failed components (F(o) = 0). Each failure transition of the CTMC has associated with it a bag of component classes (the components that fail when the transition is followed). Similarly, in the case of models of repairable systems, each repair transition has associated with it a bag of component classes (the components that are repaired when the transition is followed). In addition, for models of repairable systems, we assume that every state s ^ o has some outgoing repair transition. Finally, we assume that the CTMC is finite. The considered class of models is quite wide and encompasses, for instance, all CTMC models which can be specified in the SAVE modeling language [46], a well-known tool. For repairable systems we do not allow deferred repair, i.e. the deferring of repair till some condition such as having a number of failed components > K is achieved. Note that the CTMC may have several states with the same bag of failed components, allowing the consideration of several failure modes for the same component class. Also, in the case of repairable systems, very complex repair policies are supported: limited repairmen, priorities, repair preemption, etc. Group repair, i.e. the simultaneous repair of several components is allowed. One might think the class of models just described does not encompass coverage failures, which are important when modeling fault-tolerant systems. Such failures can be however captured making a "trick". The trick is to introduce a class of "recovery" components with n instances, at least one of which has to be unfailed for the system to be up, which do not fail on their own, and to which uncovered failures of other components are propagated, causing a system failure. Although n — 1 would suffice, that choice may reduce the failure distances from the operational states to a value smaller than the value they would have there were not coverage failures and result in a degradation of the bounds given by the methods. The advisable choice is to take for n a value equal to the redundancy level of the system, i.e. the minimum number of components that have to be failed for the system to be failed. In the case of repairable systems, coverage failures are typically recovered by a restart or similar action, which returns the system to a correct 12 1 Introduction state. Such actions can be modeled by the repair of all the recovery components. Then, the importance of allowing group repair is clear: without it, n should be chosen equal to 1 and the bounds would be worse. Also, the introduction of recovery components allows to model more complex situations such as the coverage failures that take a subsystem down. Given a fault-tolerant system, we define a failure bag as any bag of component classes over C that is associated with some failure transition of the model of the system. Similarly, for repairable systems, a repair bag will be any bag of component classes over C that is associated with some repair transition of the model of the system. We detail next the high-level information that is required by the bounding methods developed in this dissertation. The required information is the following: • N = \C\, i.e. the number of components of the system, • set E of failure bags of the model, • for each failure bag e € E, an upper bound, Aub(e), for the sum of the failure transition rates from any state of the model that have associated with them the failure bag e, • for 1 < k < N, a lower bound, g(k), for the total repair rate from any state with k failed components. That information could be extracted from an appropriate high-level specification of the model, such as the model specification language available in the SAVE tool [46], perhaps with some user intervention. In our experiments we have used METFAC-2 [21] and have integrated the bounding methods with that tool. The model specification language of that tool is based on production rules that may have annotations. Such annotations have been used to specify the "failure" or "repair" nature of the transitions and the failure or repair bags associated with them. The tool generates the CTMC from a "start" state, which, when the bounding methods are used, is always the state o. In that context, it is easy to keep track of the bag of failed components associated with the states and to identify E. N and the upper bounds Aub(e), e £ E are provided directly by the user. The lower bounds g(k), 1 < k < N are obtained calling a function provided by the user that is compiled and linked to the tool. 1.6 Outline of the Dissertation 13 1.6 Outline of the Dissertation The subject of the dissertation are failure distance based bounding methods for CTMC dependability models. The failure distance from a state of the fault-tolerant system is defined as the minimum number of components that have to fail in addition to those already failed to take the system down. That concept was introduced in [18] to devise efficient importance sampling based simulation methods for CTMC dependability models and has been used in [22] to devise a bounding method for the steady-state availability. Both the simulation and the bounding methods significantly improved the performance of previous non-failure distance based simulation and bounding methods. Those encouraging results were the motivation for the work included in this dissertation. As we will show in Chapter 2, computing failure distances is an NP-hard problem. The currently proposed method to perform that computation requires the knowledge of the minimal cuts 3 of the fault tree of the system. However, we will prove in Chapter 2 that there is no polynomial algorithm that solves the problem of computing the minimal cuts of a fault tree with the assumed structure. Thus, for some fault-tolerant systems computation of the failure distances may be very costly or infeasible. Also, the number of minimal cuts can be extremely large, introducing a significant memory overhead. The recognition of those facts led us to the development of failure distance-based bounding methods not requiring exact failure distances (and, thus, knowledge of the minimal cuts), but easily computable lower bounds for them. Two dependability measures/scenarios are considered in the dissertation: 1. The unreliability at time t, ur(t), for non-repairable systems. 2. The steady-state unavailability, UA, for repairable systems. The unreliability at time t, ur(t) is defined as the probability that the system will have failed by time t. It is an important dependability measure for many systems and, in particular, for non-repairable systems. The measure can be computed by using a CTMC X = {X(t);t > 0} with state space Q U {/}, where fi includes all operational states of the system and entry in the absorbing state / means failure of the system. Then, clearly ur(t) = P[X(t) = f). 3 We use the term minimal cut instead of the more common minimal cutset because our minimal cuts are bags. 14 1 Introduction The steady-state unavailability, UA, is an important dependability measure for repairable fault-tolerant systems. It is defined as the steady-state probability that the system is down (failed). It can be computed by using an irreducible CTMC X.= {X(t);t > 0} with state space Í7 = U U D, where U is the subset of up states and D is the subset of down states as UA= lim P[X(t) €£>]. Í-+0O As it has been explained in Section 1.2, the state spaces of the CTMC X can be far beyond available computational resources, mainly due to memory limitations. The goal of bounding methods is to obtain accurate enough estimations for the dependability measure using substantially smaller CTMC models, which, hopefully, can be held in memory. Bounds tightness increases as more states are generated and the efficiency of the bounding method (i.e. the extent to which it provides tighter bounds with the same number of states or, in other words, the extent to which fewer states have to be generated to obtain the same bounds tightness) ultimately determines the complexity of the fault-tolerant systems that can be evaluated with reasonable accuracy. The outline of the dissertation is as follows. Chapter 2 analyzes and solves the problem of computing failure distances. First, we prove that the problem is NP-hard. Then, we describe typically efficient algorithms to compute the failure distances assuming the knowledge of the minimal cuts of the structure function of the system. The efficiency of that algorithm translates the "complexity" of the problem of computing failure distances to the problem of obtaining the minimal cuts of the fault tree of the system, a problem for which there is no polynomial algorithm. Currently proposed algorithms for computing minimal cuts assume standard fault trees with simple basic events, while our bounding methods use fault trees with basic event classes (a basic event class is the failure of a component of a component class). In Chapter 2 we develop an algorithm to compute the minimal cuts for fault trees with basic event classes. The algorithm seems to be efficient and has minimum memory requirements. Chapters 3 and 4 presents and analyzes bounding methods for the unreliability of non-repairable fault-tolerant systems. The method described in Chapter 3 requires the computation of exact failure distances. The method described in Chapter 4 uses easily computable lower bounds for failure distances. Both methods have the interesting property that the bounds are obtained from the transient solution of "bounding" CTMC, and, thus, the methods can be used with relative ease in any general-purpose Markovian modeling tool. Chapters 5 and 6 describe and analyze bounding methods for the steady-state unavailability of repairable fault-tolerant systems. The work described in those chapters has [22] and [20] as starting points. Chapter 5 generalizes the bounding method described in [22] by allowing group 1.6 Outline of the Dissertation 15 repair, which, as commented in Section 1.5, is an important generalization. In addition, the efficiency of the method is increased by improving the failure rate bounding structures used in the method proposed in [22]. Chapter 6 describes a bounding method with the same generality as the bounding method described in the previous chapter that uses the easily computable lower bounds for failure distances derived in Chapter 4. Finally, Chapter 7 contains the conclusions of the dissertation and highlights related future work. 16 1 Introduction Chapter 2 Failure Distances and Minimal Cuts In this chapter we build the basis for the bounding methods which will be developed in Chapters 3 and 5. We start by stating formally the problem of computing the failure distance from a state. Next, we prove that the problem is NP-hard. Then, we describe typically efficient algorithms to compute the failure distances assuming the knowledge of the minimal cuts of the structure function of the system. The efficiency ofthat algorithm translates the "complexity" of the problem of computing failure distances to the problem of obtaining the minimal cuts of the structure function of the system, a problem for which there is no polynomial algorithm. Currently proposed algorithms for computing minimal cuts assume standard fault trees with simple basic events, while our bounding methods use fault trees with basic event classes (a basic event class is the failure of a component of a component class). Therefore, we develop an algorithm to compute the minimal cuts for fault trees with basic event classes. The algorithm seems to be efficient and has minimum memory requirements. 2.1 The Problem of Computing the Failure Distance from a State The bounding methods developed in the dissertation use the failure distance concept. Two of them require the computation of failure distances from states of the CTMC. As it has been mentioned in Section 1.6, the failure distance, d(s), from a state s is the 18 2 Failure Distances and Minimal Cuts minimum number of components that have to fail in addition to those already failed (F(s)) to take the system down. Since the up/down state of the system is determined by a fault tree T, with the structure described in Section 1.5, we can paraphrase the problem as Problem FD Given a set of component classes D, a fault tree T including AND and OR gates and having as inputs atoms of the form c[n], c 6 D, n > 1 that evaluate to true if and only if at least n instances of component class c are failed, and a bag over £), 6, determine the minimum number of components that have to be failed in addition to those in 6 for the fault tree to evaluate to true. That problem seems to be hard, in general. We will solve it assuming that the minimal cuts of the fault tree T are known. A cut is any bag over D such that the failure of the components in the bag makes T evaluate to true (i.e. takes the system down). A cut b is minimal if and only if no bag strictly contained in 6 is a cut. In Section 2.3 we will develop a typically efficient algorithm to compute the minimal cuts of the structure function represented by a fault tree T. It is known that, for ordinary fault trees, having as inputs simple events, the problem of computing the minimal cuts is NP-hard [81]. In fact, we will prove that for our fault trees the problem is not in P (there is no polynomial algorithm that solves it). Then, a question arises: is our procedure to solve Problem FD based on the knowledge of the minimal cuts of T more inefficient than it should be? We will give next a partial answer to that question, proving that Problem FD is NP-hard. Our algorithms to solve Problem FD have linear complexity on the number of minimal cuts of F and, thus, are not polynomial, but, since Problem FD is NP-hard, there is no polynomial algorithm to solve it unless NP = P, which would mean that for all NP-complete problems there would exist a polynomial algorithm (see [43] for background). Let MC be the set of minimal cuts of T. Then, since a state is down if and only if the failed components in the state make T evaluate to true and a bag b of failed components imply T to true if and only if b includes some minimal cut, it is clear that the failure distance d(s) from a state s can be computed as d(s)= min \m-F(s)\. (2.1) mfzMC Use of (2.1) is expensive if the number of minimal cuts is large, as it can be. In Section 2.2 we will describe typically much more efficient algorithms to compute failure distances. Our algorithms to compute failure distances require the knowledge of all minimal cuts of the fault tree. We have the following result. 2.3 An Algorithm to Compute Minimal Cuts 25 a preprocessing step that yields reduced level fault trees that are processed in descending level order. The new algorithm can speed up significantly the basic bottom-up algorithm when the fault tree has gates with fanout. The concept of module [27] can be exploited to reduce significantly for some fault trees the computational cost of finding the minimal cuts. A module is a portion of the fault tree having basic events as inputs and a single gate (the output of the module) fanning out of the module. Efficient algorithms have been proposed to find modules [40], [57], [82], [98]. The analysis of a fault tree with modules can be reduced to the analysis of each module and the fault tree obtained by substituting each module by an independent input. More recently, algorithms based on BDD representations [15] of the logic function implemented by the fault tree have been proposed. In [80], [93] the fault tree is assumed 5-coherent and a BDD is constructed for it. That BDD is then transformed to obtain another BDD such that each path from the root to the leave 1 represents a minimal cut. The MetaPrime tool [33] uses a similar approach that can deal with non s-coherent fault trees, the BDD encoding the minimal cuts being called metaproduct. More recently [77], another algorithm has also been developed for non s-coherent fault trees that in many cases gives more compact BDD representations than the metaproducts obtained by MetaPrime. All these algorithms have been shown to be typically much faster than the early top-down and bottom-up algorithms. The algorithm developed in this section considers generalized fault trees with basic event classes, being the basic events of each class indistinguishable. With classes, the fault tree does not longer represent a logic function with binary arguments. Also, cuts and minimal cuts are not longer sets but bags. The algorithm uses a decision tree to generate cuts of the fault tree. Cuts thus obtained are not guaranteed to be minimal and a test of minimality has to be carried out. However, instead of inclusion tests, we make an independent minimality test for each generated cut. Since cuts are generated one by one, this allows to write sequentially in secondary storage minimal cuts, making the memory requirements of the algorithm small and independent of the number of minimal cuts. These small memory requirements are an unique feature of our algorithm (BDD representations of fault trees are in the worst case of size exponential with the number of basic events). In this section we will use the following notation and definitions. Notation and Definitions 26 2 Failure Distances and Minimal Cuts C set of basic event classes of the fault tree ci[ni]c2[n2].. .Ck[rik] bag with n,- > 0 instances of basic event class c¿, 1 < i < k; it will be said that Ci[ni] is part of the bag I set of inputs of the fault tree; each input is a bag c[n], c G C, n > 1, meaning the realization of n basic events of class c G set of gates of the fault tree gr root (top) gate type(<7) type of gate g; it may be AND or OR val(.) value of an implied input or gate; it may be 0 or 1 node an input or a gate fo(a:) fanout of node x: set of gates fed by x fi(¿f) fanin of gate g: set of gates or inputs that feed g irrelevant a node x is irrelevant if all edges branching out of x are irrelevant; an edge e is irrelevant if either the gate g to which e goes is irrelevant or has been previously implied by a node connected to g by another edge dfo(ar) dynamic fanout of an unimplied node x: set of relevant edges fed by x fx fanout excess of an unimplied and relevant node x: |dfo(2)| — 1 / fanout excess of the fault tree: J2 *€/UG fx x unimplied and relevant 6X for an unimplied and relevant gate, 6X = fx; for an unimplied and relevant inpUt C[n], Sx = £ e[n']€/,n'<n fc[n'] c[n'] unimplied and relevant input pattern any compatible combination of assignments of 0, 1 values to inputs of the fault tree (by compatible we mean that the existence of the assignment (c[n], 1) implies the existence of the assignments (c[nr\, 1), n' < n, c[n'] G /, and that the existence of the assignment (c[nj, 0) implies the existence of the assignments (c[n'],0), n' > n, c[n'] € /) reduction of / being / = {cjfni], C2[n2J,... , Cjt[n¿]} a set of inputs implied at 1, generation of a bag b by traversing / and putting into b each c[n] € / such that no c[n'], n' > n is in / cont(x) controllability of an unimplied node x: if x Ç /, cont(x) = 1; if x G G and type(x) = OR, cont(a;) = min xieñ(x¡ {cont(x')}; if x e G and type(x) = x' unimplied AND, cont(x) = £ ,,6fl(x, cont(a:') x* unimplied 2.3 An Algorithm to Compute Minimal Cuts 27 a[l] 6[1] a[2] d[l] 5[1] a[3] /[2] x> =[1] Î>7D =[1] D C^ 5> 5[1] Figure 2.3: Example fault tree. We consider s-coherent fault trees involving OR and AND gates. Figure 2.3 gives a small example that will be used for illustration purposes. We begin by clarifying several concepts. Generalization to basic event classes introduces dependences among the inputs related to the same event class. An input Ci[rii] is implied at 1 if n¿ events of class c, are realized. An input c,[nj] is implied at 0 if ntevents of class C{ are not realized. Then, val(c,[n,]) = 1 implies val(c,[ji]) = 1 for all j < n¿ because the realization of n,- basic events of class c, obviously implies the realization of any number j < n,- of basic events of that class. Similarly, val(c¿[n,]) = O implies val(c,-[j']) = 0 for all j > ni. Implications in the fault tree are performed from inputs to gr in the usual way: an input of an OR gate at 1 implies the output of the gate at 1; an input of an AND gate at 0 implies the output of the gate at 0; the output of an OR gate is implied at 0 when all inputs are implied at 0, and the output of an AND gate is implied at 1 when all inputs are implied at 1. Since the fault tree is s-coherent and all gates are either OR or AND such a procedure is enough to know the implication state of gr. To see that it suffices to note that 0's imply 0's and l's imply l's and, therefore, an unimplied output gr can be implied to 0 or 1 by simply implying the unimplied inputs of the fault tree to 0 or 1, respectively. Therefore, when the procedure does not imply gr, the root gate gr is really unimplied. For the example fault tree of Figure 2.3, / = {a[l],a[2],a[3],6[l],c[l],4l],e[l],/[2], g[l]}. Two possible input patterns might be h = {(a[l], 1), (a[2], 1), (a[3], 0), (6[1], 0), (c[l], 0), (d[l], 0), (e[l], 1), (/[2], 1), (fl[l], 0)} and l2 = {(a[l], 0), (a[2], 0), (a[3], 0), (6[1], 0), (c[l], 0), (¿[I], 0), (e[l], 1), (/[2], 1), (g[l], 0)}. For /lt gr is implied at 1. Then, that input pattern "contains" the cut m = a[2]e[l]/[2] obtained by reducing the set of inputs 28 2 Failure Distances and Minimal Cuts implied at 1 {a[l], o[2], e[l], /[2]}. The problem to be solved is to find all minimal cuts of a given s-coherent fault tree. Such a problem may be viewed as a search in a finite space. The. search space is given by the next Theorem: Theorem 2.3 All minimal cuts are oftheform Ci[ni]c2[n2¡.. .Cfc[n¿], where eachci[ni\ G Proof By contradiction. Let m = Ci[nj]c2[n2].. -Ck[nk] be a minimal cut not satisfying the condition. Then, there exists CÍ[TIÍ] part of m such that c,[n,] £ /. Assume that there exists Ci\j] G I with j < n¿. Let J,- be the greatest of such integers and consider the bag m' obtained from m by substituting Ci[ni\ by Ci[Ji\. If there not exists c,[j] G / with j < nt-, let m' be bag obtained by eliminating c¡[n¿] from m. Clearly, m! performs the same implications as m does. Therefore, m' is a cut, but being m' C m, m is not minimal. Q From the irrelevance definitions, the value of an irrelevant node does not affect val(<7r). The following theorem relates irrelevance and minimality and will be exploited in the algorithm. Theorem 2.4 Let S be the set of implied fault tree inputs. If there exists Ci[ni\ G S that is implied at 1 and is irrelevant, and there not exists any Ci[j] G / with j > n,-, no input pattern obtained by implying more inputs will contain a minimal cut. Proof Let m be any cut obtained by implying more inputs and reducing the set of inputs implied at 1. Because no C{\j] G /, j > ntexists, c,[n,] G m. Assume that there exists at least one c,-[/] Ç. I, j < n,- and let «/,• be the greatest integer j < n,- with c,[j] € /. Consider the bag m' obtained from m by substituting C{[ni\ by Ci[Ji\. If there not exists any Ci[j] G /, j < ni, let m' be the bag obtained from m by eliminating Ci[ni\. Because Ci[n{] is irrelevant, the value of gr is not affected by the value of Ci[ni] and m! is also a cut. Furthermore, m' C m, implying that m is not minimal. Q To avoid performing inclusion tests, which are time and memory consuming, a criterion to determine when a cut is minimal or not without knowing any other cut would be useful. The next theorem gives such a criterion. Theorem 2.5 A cut m = Ci[ni]c2[n2].. -Ck[nk] is minimal if and only if, after implying at 1 each Ci[nî\, each unimplication of Ci[ni\, 1 < i < k, followed by, if such J,- exists, 2.3 An Algorithm to Compute Minimal Cuts 29 implication of Ci[Ji\, where J{ is the greatest integer < n¿ with Ci[Ji\ 6 /, leaves gr unimplied. Proof We will show necessity and sufficiency. Necessity: If there exists any Ci[n{] 6 m such that its unimplication followed, if existent, by the implication of Ci[J{], where J, is the greatest integer < n, with Ci[Ji\ G /, leaves gr implied at 1, the bag m! obtained from m by either deleting Ci[nj] or replacing Ci[ni\ by ci[Ji] is also à cut, and being m' C rn, m is not minimal. Sufficiency: Assume that gr is unimplied for each unimplication, followed, if existent, by implication of Ci[Ji\, and assume that there exists a bag m' C m that is a cut. Being m' C m, there exists m", m' Ç m" C m such that m" is obtained from m by either deleting Ci[ni] for some 1 < i < k or replacing for some 1 < i < k c,[n,] by Ci[n'{] with n¿ < n¿. In both cases gr is not implied at 1 by m" and m" is not a cut, implying that neither is m' a cut. Then, there not exists any cut m! Cm and m is minimal. Q From Theorem 2.3, the search space is the space of input patterns of the fault tree. All minimal cuts can be found by exhaustively searching that space and, for each input pattern for which val(<7r) = 1, obtaining its associated cut m by reduction of the set of inputs implied at.l, and testing m as Theorem 2.5 indicates. However, the algorithm does not explicitly generate all input patterns, since in some circumstances it detects that no input pattern containing the current set of implications would yield a minimal cut. The algorithm also detects when the fault tree becomes fanout free (/ becomes 0) and uses the top-down algorithm to obtain all potential minimal cuts that can be generated by performing more implications at the inputs of the fault tree. The algorithm we propose traverses a decision tree such as the one shown in Figure 2.5. Initially, all nodes of the fault tree are unimplied and the current node is the root of the DT. A backtrace procedure selects an input Cj[ni]. The selected input is implied at v = 1, a successor of the current node is constructed with the pair (c,-[n,-], v) assigned to it, and the successor is visited. The process continues in a similar way from that node. After each implication, the relevance status of edges and nodes, fx, /, Sx, and cont(a:) are updated. In some cases, the search can be pruned. When the search is pruned, the DT is traversed up to the root till a node y is found that has only a successor with v = 1. If no such a node y is found, the algorithm finishes. Otherwise, the search is backtracked up to node y. Backtracking involves the deletion of all the implications done as a direct consequence of the input assignments associated with the nodes in the path from the current node to y. It also involves the restoring of the old values of the relevance status 30 2 Failure Distances and Minimal Cuts of the edges and nodes, fx, /, 8X, and cont(x). Deletion of implications and restoring of old values of the relevance status of edges and nodes, fx, /, 6X and cont(x) is made easily because the algorithm stores for each node of the DT the implications performed and the old values of the relevance status of edges and nodes, fx, /, Sx and cont(a:) which change as a result of the input implication performed at the node. After backtracking, a successor of y associated with the input assignment (c,-[n,-],0), where Ci[rii] is the input of the successor of y, is created, the assignment implied, and the process continues from that successor. If the implied input value v is 1 the search can be pruned in the following cases: 1. val(<7r) = 1. Extra input implications at 1 will give cuts which are guaranteed to be non-minimal. 2. / = 0. The fault tree has been reduced to a fault tree that is fanout free2 and all minimal cuts beyond that point of the search have to be included in the cuts that are obtained by adding to the current set of inputs implied at 1 the inputs that are found using the basic top-down algorithm on the reduced fanout free fault tree and reducing those sets of inputs. 3. An input c[n] implied at 1 is irrelevant and there not exists c[n'] Ç I, n' > n. According to Theorem 2.4, no minimal cut will be found by implying more inputs. For v = 0, case 1 is impossible. Besides cases 2 and 3, there is another situation in which no more implications are necessary: 4. val(<7r) = 0. Further input assignments will not change the value of gr and no minimal cut exists from that point. In case 1, a potential minimal cut is obtained by reducing the set / of inputs implied at 1. In case 2, the top-down algorithm is used to find potential minimal cuts. The cuts thus obtained are checked for minimality using the procedure of Theorem 2.5 and recorded if they are minimal. Our algorithm has similarities with some ATPG algorithms [2], [41], [44]. Figure 2.4 shows a recursive high-level description of the algorithm that uses a stack to store the path in the DT to the currently processed node. The algorithm is invoked with an empty stack. In the worst case the stack will have |/| cells. This together with the fact that 2The reduced fault tree is defined by the relevant and unimplied nodes of the original fault tree. 2.3 An Algorithm to Compute Minimal Cuts 31 Algorithm compute.cuts (INPUTS-ASSIGNMENTSSTACK s) backtrace (pr, c,-[n,-]); u=l; end = NO; while (lend) { imply Ci[ni\ at v; push((cf[7i,-],u), s); if(va%.)==l||/==0){ if (val(ffr) == 1) { get cut m; if (test_minimality(m)) store m; /* m is minimal */ } else { /* / == 0 */ collect potential minimal cuts by adding to the current set of inputs implied at 1 the inputs found by the top-down algorithm and reducing those sets, for each cut perform the minimality test and store the cut if it is minimal; } } else if (!(val(<7r) == 0 or an input c[n] implied at 1 has become irrelevant and does not exist c[n'] 6 J, n' > n)) compute_cuts(s); unimply all c,[j] with either j < n,- (case v = 1) or j > n¿ (case v = 0) that were implied as a direct consequence of setting Ci[ni\ at v; pop((c¿[n,-],«),«); if (v == 1) v = 0 else end = YES; } .Figure 2.4: High-level description of the algorithm. only a minimal cut has to be stored at a given time (possible because the minimality check does not involve inclusion tests) makes the memory requirements of the algorithm small. It has been assumed that the fault tree to be solved is not fanout free. To take into account the special case in which the fault tree is fanout free, it suffices to check the value of / before calling compute.cuts and invoke the top-down algorithm if / = 0. The backtrace procedure that selects input assignments is crucial for the performance of the algorithm and is inspired in ATPG algorithms. The procedure starts at the output gr of the fault tree and follows a path to a fault tree input by selecting at each gate one of its unimplied inputs. Gate inputs are selected using the following criteria: 32 2 Failure Distances and Minimal Cuts (7)^(c[l],l) fanout free c[l]a[l] mc c[l]b[l] mc c[l]e[l]a[3] c[l]a[2]e[l]f[2] c[l]d[l]e[l]a[3] c[l]d[l]e[l]f[2] c[l]g[l] mc ""VT) (c[l],0) 3 ) (e[l], D (8) (em. 0) output at 0 (T)(a[3],l) ?T)(a[3].0) output at 1 S ^v e[l]a[3] mc (T) (f[2]f i) (7) (fr2], 0) fanout free et13 irrelevant output at 0 e[l]f[2]a[l] mc e[l]f[2]d[l] mc e[l]f[2]g[l] mc Figure 2.5: Decision tree for the example of Figure 2.3. 1. Choose the input a; with highest Sx/cont(x). 2. Among the inputs with same Sx/cont(x) choose the input connected to the node with lowest cont(a;). If several inputs are identical according to both criteria, then the gate input is chosen following a predefined ordering (for the fault tree of Figure 2.3 the ordering is from top to bottom of the figure). The heuristics used in the backtrace procedure try to reach as soon as possible nodes with backtracking, either because the fault tree becomes fanout free or because gr is implied at 1. The Sx is a local measure of how much / will be decreased if x is implied at 1. The cont(a;) is a measure of the ease with which the considered node will be implied at 1 (the higher cont(x) the more difficult) and is taken directly from heuristic measures used to guide ATPG algorithms [45], being the measure in that context called 1-controllability. We tried other combinations, such as selecting first according to cont(x) and then according to 6X and found that the chosen heuristics gave better performance. In order to illustrate the algorithm we give in Figure 2.5 the DT corresponding to the fault tree of Figure 2.3. Nodes are numbered following the creation order. For each node except the root we give the corresponding input assignment. Also, for nodes with 2.3 An Algorithm to Compute Minimal Cuts 33 a[l]01 6[1] 01 Figure 2.6: Illustration of the backtrace procedure in the case in which there is no input assignment (node 0 of the DT of Figure 2.5). The 5X and cont(x) are written next to each node from left to right, respectively. backtracking we give the reason for backtracking and, for the nodes in which the fault tree became fanout free or gr was implied at 1, we give the cuts found, indicating by "rac" those that are minimal. The fault tree has only 7 minimal cuts. Figure 2.6 illustrates the backtrace procedure in the case in which there is no input assignment (node 0 of the DT). The input selected is c[l]. Figure 2.7 gives the implication status of the fault tree when c[l] is implied at 1. That implication makes irrelevant the edge marked as i, making the fault tree fanout free (/ = 0). The corresponding reduced fault tree is given in Figure 2.8. Use of the top-down algorithm on the reduced fault tree gives the set of inputs {a[l]}, {ò[l]}, {a[2],e[l],a[3]}, {a[2],e[l],/[2]}, {d[l],e[l],a[3]}, {d[l],e[l],/[2]} and {^[1]}. The input currently implied at 1 (c[l]) is added to each sets and the resulting sets are reduced, yielding the cuts shown in Figure 2.5. To illustrate the minimality test, Figure 2.9 gives the implication status for the cut c[l]e[l]a[3], showing crossed the unimplications which result when a[3] is unimplied, keeping implied a[2] and o[l]. Since gr remains implied at 1, according to Theorem 2.5, the cut is not minimal. Finally, in order to illustrate backtracking by detection of an irrelevant input implied at 1, we give in Figure 2.10 the implication status and irrelevant nodes and edges corresponding to node 7 of the DT. Input e[l] is implied at 1, is irrelevant and there not exists any other input e{j] with j > 1. Then, according to Theorem 2.4, no minimal cut can be found from that point and the search can be backtracked. At that node of the DT the search could also be backtracked for gr being implied at 0. 34 2 Failure Distances and Minimal Cuts «[I]" Ml]- a[2] d[l] =[1]-L On e[l] a[3]- /[2]- D c[l]JJ ^O-1 *[i] Figure 2.7: Implication status at node 1 of the DT of Figure 2.5 with indication of irrelevant edges. a[l] Mi] a[2\- 4i]- e[l] a[3] /[2] TD- D *[i] Figure 2.8: Reduced fault tree corresponding to node 1 of the DT of Figure 2.5. 2.5 Conclusions 41 Table 2.2: Algorithm performance: number of minimal cuts, number of processed cuts, number of backtracks, CPU time in seconds, and number of cuts that would be processed by the basic top-down and bottom-up algorithms. tree MS5 MS10 BR40 BR80 DR35 DR70 EDF ELFI ELF2 ELF3 minimal cuts 511 1,911 3,160 12,720 3,698 14,157 2,463 46,188 4,805 24,386 processed cuts 1,473 5,208 3,161 12,721 118,444 808,953 3,435 112,606 13,754 69,488 backtracks 1,936 23,135 821 3,241 60,099 395,907 1,683 169,278 16,842 150,601 CPU time (s} 1.74 13.6 11.4 175 51.1 536 4.26 235 23.6 150 cuts top-down 34,225 136,900 3.86255 x 1077 1.24936 x 10178 1.22672 x 1026 8.32281 X 1030 8.75983 x 1024 1.26358 x 1020 4.17538 x 1017 1.45039 x 1016 cuts bottom-up 8,285 29,345 3.86255 x 107T 1.24936 x 10178 2.90796 x 107 4.75491 X 108 3.81949 x 1010 2.86939 x 108 5.48907 x 108 7.66257 X 107 Table 2.3: Algorithm performance: number of backtracks in the algorithm, and when either fault tree inputs are selected at random or the irrelevance test is disabled. tree MS5 MS10 BR40 BR80 DR35 DR70 EDF ELFI ELF2 ELF3 algorithm 1,936 23,135 821 3,241 60,099 395,907 1,683 169,278 16,842 150,601 w/ random selection 67,619 — 1,849 10,985 233,663 1,798,840 266,611 9,115,802 226,704 — w/o relevance test 309,245 — 3,943 15,883- 248,414 1,791,888 22,159 — 101,994 — 42 2 Failure Distances and Minimal Cuts well even in difficult examples. The number of processed cuts is usually not much larger than the number of minimal cuts of the fault tree, and, in many cases, it is much smaller than the number of cuts processed by the basic top-down and bottom-up algorithms. Compared with recent algorithms based on BDD representations of the fault tree [80, 33, 77], the algorithm seems to be somehow slower. However, the algorithm has very modest memory requirements whereas in the worst-case the algorithms based on BDD representations require memory that is exponential in the number of basic events. Chapter 3 Reliability Bounds of Non-repairable Systems using FD In this chapter we will develop the first failure distance based bounding method of the dissertation. The method obtains bounds for the unreliability at time t, ur(t), of a nonrepairable fault-tolerant system and requires the computation of failure distances. It has the interesting property that the bounds are obtained from the transient solution of a "bounding" CTMC and, thus, the bounding method can be accommodated in any general-purpose Markovian modeling tool. We will start by describing and justifying theoretically the bounding method. Then, we will analyze its performance and will compare it with the performance of the trivial bounding method described in Section 1.3, showing that the proposed method can outperform significantly the trivial method. 3.1 Method Description and Justification The measure ur{t) can be computed exactly using a CTMC X = {X(t);t > 0} that is acyclic, has a finite state space Q U {/}, where / is an absorbing state that represents the failure of the system and Q is the set of states in which the system is operational, and has transition rates with failure bags e £ E associated with them. We have ur(t) = P[X{t) = /]. Given ¿ € Í2, j € fi U {/} we will denote by A,j the transition rate of X from state i to state j and by A,- = ]C/eiiu{/} ^»'.'tne outPut rate of -X" from state i. Being B a subset of states, we will denote by X^B = Y^ieB ^«'-' tne transition rate from state i to B. 44 3 Reliability Bounds of Non-repairable Systems using FD Figure 3.1: State transition diagram of X' for L = 3 and FC = {1,2}. The bounds for ur(i) will be obtained using a CTMC X' = {X'(t);t > 0} with state space G U {/} U {u0, • • • , UL}, L — m'mmGMC \m\. G is the subset of Ü that is generated and the method assumes P[X(0) G G] = 1; / represents the failure of the system from a state belonging to G; the states uj, 0 < d < L "bound" the behavior of X after it exits G through a non-failed state. Let U = Í2 — G. The formal proof of the method assumes that there are not transitions from U to G, For a given partition fi = GUl7, depending on G it could well be that X had transitions from U to G, violating the assumption. However, the assumption does not in fact impose any real restriction to the selection of G, since it is enough to redefine X so that U includes copies of the states of G reachable from U to satisfy the assumption. Thus, the only limitation imposed to G is P[X(0) € G) = 1. The transition rates among the states of G are as in X; the transition rates from states o € G to ÍÍ¿, 1 < ¿ < L have values Xa,ud, being Ud the subset of U including the states with failure distance d; finally, denoting by FC the set of different cardinalities of the failure events of the model and by E{ the subset of failure events with cardinality i, and defining /,• = YleeE, ^ub(e), for each 1 < d < L, i € FC there is a transition rate /,- from u¿ to Mmax{o,ii-i}- Figure 3.1 illustrates the structure of X'. The initial probability distribution of X' is P[X'{0) = i] = P[X(0) = i], i e G; P[X'(0) = /] = 0; P[X'(0) = ud) = 0, 0 < d < L. The bounds are: [ur(i)]ib = P[X'(t) = /], (3.1) {ur(t)]ab = P[X'(t)€{u0,f}}. (3.2) The correctness of the lower bound (3.1) is trivial, since X' enters / when X enters / from G; the correctness of the upper bound (3.2) will be shown next. 3.1 Method Description and Justification 45 l-hâJi i /•+/» i /•+/» 1 Figure 3.2: State transition diagram of DTMC Y' for L = 3 and FC = {1,2}. The proof of the upper bound will be done through a lemma, two propositions and a theorem and will make reference to the discrete-time Markov chains (DTMC) Y = {Yn;n — 0,1,...} and Y' = {Y^n = 0,1,...} obtained by randomizing [49], respectively, X and X' with a rate A, greater than or equal to the maximum output rate of X (for instance, A = SeeE^ub(e)). The DTMC Y has the same state space and initial probability distribution as X and transition probabilities qa¿ = A0i¡,/A, a ^ b, qa>a = 1 — Aa/A. The DTMC Y' has the same state space and initial probability distribution as X! and transition probabilities q'a b = A^ ¡,/A, a ^ b, q'aa = 1 — A^/A, where A^ b and A^ are, respectively, the transition and output rates of X'. Figure 3.2 illustrates the state transition diagram of Y'. It is well-known (see, for instance, [83]) that X(t) = y/v(t) and X'(t) = Yj^,^, where A^ = {A^i);^ > 0} is a Poisson process with rate A. These results allow to express the transient solution of X (X') in terms of the transient solution of y (Y'): P[X(t) = a] = f^{-^fe-AtP[Yn = a], (3.3) n=0 P[X'{t) = a] = ¿ M^e-A'P[Fn' = a]. (3.4) Intuitively, it is clear that the probability that Y' will reach the absorbing state UQ from Ud, d > 0 in m steps decreases with d. The result is established in the following lemma. Let R'm(d) = P[Y^ = u0\Y¿ = ud}. Lemma 3.1 R'm(d),m > 0, d > 0 is decreasing on d. 46 3 Reliability Bounds of Non-repairable Systems using FD Proof From the structure of Y' we can write ¿C(0) = l,m>0, (3.5) ieFC i>d and for m > 1, d > 0, R'm(d) = (l - i E fi)R'm-M + E f ^-i(max{0,d- ¿}). (3.7) ieFC ieFC The proof is by induction on m. Base case (m = 1): We show R'^d) < R'^d - 1), d > 0. For d = 1, using (3.6) and (3.5) we have: Äi(1)= E x< 1 = ^(0). ¿eFC For d > 1, using (3.6), ^)=Ei^ E £ = *!(*-D• «eFC ¿efC t>cf ¿>á-l Induction step: Let m > 0; we will assume that R'm(d), d > 0 is decreasing on d and will show R'm+1(d) < R'm+l(d - 1), d > 0. For d = 1, using (3.7), Ä^(l) < 1 and (3.5) we have: ¿4+i(i) = (i-iE^w+Eftt ieFC ieFC * i-lS/.+ Ef = 1= ^+1(o). ieFC ieFC For d > 1, using (3.7) and the induction hypothesis, R'm+1 = (l-T E fi)R'm(d)+ E jR'm(^x{0,d-i}) ieFC ieFC Ï (i-lE fi)R'm(d-l)+ E jRUm^iO.d-i-l}) ieFC ieFC = C+i(¿-i)-D Let us define i?m(a) = P[Ym = f\Y0 = a]. We have the following result. 3.1 Method Description and Justification 47 Proposition 3.1 Rm{a) < R'm(d), a € U¿, m > 0, d > 0. Proof Let \laj be the contribution to Xaj associated with failure bags e 6 E{. We have ^â / — /»'• Since a failure bag e € E{ reduces the failure distance at most by i, Xaj will not have contributions X'a , for i < d, and ^w-Eir- (3-8) ieFC i>d Let us denote by Uk,d the subset of U including the states with k failed components and failure distance d. For m > I, taking into account that / is absorbing, Rm(a) = (l-^W:(a)+£[^+£ £ ^Ä»-i(6) i>d d + £ £ £ ^Äm-i(ft). (3.9) The proof is by induction on m. Base case (m = 1): We will show ñi(a) < Äi(d), a 6 í/¿, d > 0. Using (3.8), A*B>/ < /¡, and (3.6), *.<•>= E^s Er«- ¿eFC ÍÇ.FC %>d i>d Induction step: Let m > 0; we will assume Rm(a) < R'm(d),a € U¿,d > 0 and show Rm+i(a) < R'm+l(d),a G Ud,d> 0. Using (3.9) and the induction hypothesis, ¿w«) < (i-^)R'm(d)+ £[% + £ £ ^»(«0 v ' ieFC d'=\ beuk.i¡d, + £ £ £ ^*.eo 48 3 Reliability Bounds of Non-repairable Systems using FD Taking into account that R'm(d') < 1, ^2beu , K,b = ^a,uk+id,, and using Lemma 3.1, 7 ieFC i>d + ER'm(d-i) E %^. (3.10) ieFC d'=d-¿ Let £/fc be the subset of U including the states with k failed components. The inequality (3.10) can be written as Rm+1(a) < (l-^WW+ E A^+AA°^ V ' ieFC i>d + J2R'm(d-i) ^p. (3.11) ieFC i<d Taking into account that Aa = Xaj + YlieFC Aa,r/*+<, __2^ ^ +2^-^—. (3.12) ieFC ieFC i>d i<d Combining (3.11) and (3.12), ieFC i>d + E [R'm(d - i) - R'm(d)} Aa[yfc+, A «eFC t'<d Finally, noting that, for i > d, X'aj + XaUk+i < fi and that, for i < d, XatUk+i < /,-, and using (3.5) and (3.7), Rm+1(a) < R'm(d)+J2i1-R^]j+J2iR'm(d-i)-R'm(d))§: ieFC ieFC i>d i<d = (I-A-E/'K^ AieFC + E jR'm(m^{0,d-i}) = R'm+ï(d).ü ieFC A Using Proposition 3.1 it is possible to show the following result. 3.1 Method Description and Justification 49 Proposition 3.2 P[Yn = f) < P[Y¿ e {u0, /}], n > 0 . Proof Y can enter / through U or directly from G. Taking into account that / is absorbing and conditioning the entry of Y in / through U to the step in which Y leaves G and the entry state in U, we have: n-l L P[Yn = f] = EEEP[y— ieGAYm = a}P[Yn = f\Ym = a) m=l d=l a£U¿ n + Y,piY™-ieGAYm=zft 771=1 71-1 L -m (a) 77i=l d=\ a£Ud 71 + EpCy— i€GAym = /]. 771 = 1 Invoking Proposition 3.1 and using the relationships between Y and Y', 71-1 L P[Yn = f] < YlJ2JlP^-^GAY^=a^Rn-m(d) 77i=l d=l a£Ud n + J2PlY™-l£GAY™=f] 771 = 1 n-l L = £ E P[y--1 6GAy™ = MK-mid) m=ld=l + Ep[y--i€GAy- = /] 771=1 n-l L = EEp[y--ieGAy- = ^p[y" = Uoiy- = ^ m=l d=l n + Epfy--ieGAy- = /] m=l = PK = «o] + PK = /] = P[Yl € {«o, /}]• D The last proposition allows us to prove the following, desired result. Theorem 3.1 ur(i) < [ur(i)]ub. Proof Since Y is the result of randomizing X, using (3.3), taking into account that 50 3 Reliability Bounds of Non-repairable Systems using FD P[Yo = f) = P[X(0) = f] = 0, ur(t) = P[X(t) = /] = ¿ Wle-AtP[Yn = f]. n=l Invoking Proposition 3.2 and using (3.4) with P[Y¿ 6 {«o, /}] = P[X'{0) € {w0, /}] = 0, and (3.2): «"•W * E ^re"AtWÍe H./>] = ^^'(*) e to./>! = MOWD n=l n- 3.2 Analysis and Comparison In this section we analyze the performance of the proposed bounding method using a complex example with dependencies that prevent from using combinatoric and hierarchical solution methods, and compare the quality of the bounds obtained with the proposed method with the bounds obtained using the trivial method in which the upper bound assumes that the system fails when the model exits G. That bound can be expressed in terms of the transient regime of X' as: [ur(t)}'uh = P[X'(t)€{u0,---,uLJ}}. The transient regime of X' has been solved using the randomization method [49]. The example is a system made up of 38 components. The architecture of the system is shown in Figure 3.3. The system is made up of a cluster of redundant master processing units MPUi and MPU2 that are communicated with n = 5 clusters of redundant slave processing units SPUt(i and SPU¡,2, 1 < ¿ < n. Communication is done through two redundant buses BA and BB to which the master and slave units are connected through dedicated interfaces. The system is operational if some fault-free master processing unit can communicate directly (i.e. through one fault-free bus and two fault-free interfaces) with at least one fault-free slave processing unit of each slave cluster. The active configuration of the system includes a master processing unit, with priority given to MPUi, all fault-free slave processing units which can communicate with the active master processing unit, and the busses and interfaces among these units and the active processing master unit. Master processing unit MPU2 is activated only if MPUi IS faulty or it is impossible to build up an operational configuration with MPUi (for instance, because both interfaces associated with MPUi are failed). Active master processing units, slave processing units, interfaces and busses fail with rates AA/, AS, A/, and Aß, respectively. Passive components fail with rates 5M\M, 4.1 Bounding Method 57 fi Ee€£¡ A«b(e) 4.1 Bounding Method We give in Figure 4.1 the architecture of an example system, adapted from [61], which will be used for illustration purposes. The system consists of two memory modules MM i and MM2, three identical CPU chips CPUC and two identical port chips PTC. One CPU chip and one port chip are spares. Each memory module MMj is made up of ten memory chips MCj, two of which are spares, and one interface chip ICj. Active memory chips MCj and interface chips ICj fail, respectively, with rate XMCJ and Xjcr Active port chips PTC and CPU chips CPUC fail, respectively, with rates Xprc and XCPUC- Spare chips fail with rates v x XMC,, V X XJC}, V X XPTC, and v x Xcpuc, being v, 0 < v < 1 a dormancy factor. Recovery is hierarchical. A fault in a memory chip is covered with probability CMC- A faulty memory module, CPU chip and port chip are successfully covered with probabilities CMMI CCPUC and Cprc, respectively. To model imperfect coverage, an uncovered fault in a memory chip of memory module MMj is propagated to a fictitious component RMMj, and an uncovered failure of a memory module MMj, a CPU chip or a port chip is propagated to two fictitious components RCM. Memory module MMj is operational if at least eight memory chips MCj, the interface chip ICj and the fictitious component RMMj are unfailed. The system is operational if at least one memory module MMj is operational, and at least two CPU chips CPUC, one port chip PTC and one fictitious component RCM are unfailed. Table 4.1 gives the failure bags of the example system and, for each failure bag e, a suitable upper bound Aub(e) expressed in terms of the above failure rates, coverage probabilities and dormancy factor. Thus, for instance, failure bag e\ stands for the fault of a memory chip of the first memory module that is covered at memory module level, e2 stands for the fault of that chip that is uncovered at memory module level and covered at system level, and e^ stands for the uncovered fault of the chip. Note that FC = {1,2,3,4} and that /i = Aub(ei) + Aub(e4) + Aub(e6) + Aub(e9) + Aub(en) + Aub(e13), f2 = Aub(e2) + Aub(e7), /3 = Aub(e5) + Aub(ei0) + Aub(ei2) + Aub(ei4), and f4 - Aub(e3) + Aub(e8). The CTMC X' used to compute [ur(f)]ib and [ur(i)]ub has state space G U {/} U {UQ,... ,W¿}- Although other selections for G would be possible, we assume that G includes all the states of the model with up to K failed components and that P[X(0) £ G] = 1. The states u¿, 0 < d < L pessimistically approximate the behavior of X in U. The transition rates in X' from a to b, a, b e G and from a to /, a € G are as in 58 4 Reliability Bounds of Non-repairable Systems using FD Bounds Figure 4.1: Architecture of the example system. Table 4.1: Failure bags of the example system and, for each failure bag e, a suitable upper bound Aub(e). ei e2 Ê3 e4 es e& eT €8 eg eio en ei2 ei3 e14 description MC i[l] MCi[l]ÄMMi[l] MCi[l] RMMi[l] RCM[2] ICxil] ICi[l]RCM[2] MC2[1] MC2[1]RMM2[1] MC2[1] RMM2[1] RCM[2] IC2[1] IC2[1] RCM[2] CPUC[1] CPUC[1] RCM[2] PTC[1] PTC[l) RCM[2] Aub(e) (8 + 2Í/)AMC1CMC (8 + 2V)\MCI (1 - CMC)CMM (8 + 2v)\MCl (1 - CMC)(1 - CMM) ^ICXCMM A/d(l -CMM) {8 + 2V)\MC2CMC (8 + 2V)\MC2 (1 - CMC)CMM (8 + 2v)\Mc2{l - CMC)(1 - CMM) ^IC2CMM A/c2(l -CMM) (2 + V)\CPUCCCPUC (2 + v)\cpuc{1- - CCPUC) (1 + v)\pTcCpTC (l + i/)Aprc(l -CPTC) 4.1 Bounding Method 59 Figure 4.2: State transition diagram of X' for the example system (L = 2, FC = {1,2,3,4}). X. The transition rates from states a e G to Ud, 1 < d < Z have values A„ ,7 , and for each 1 < d < L, i £ FC there ¡s a transition rate /¡- from u¿ to «max{o,d-{}- The initial probability distribution of X' in G is the same as the initial probability distribution of X in G. As it will be shown in Section 4.2, L = 2 for the example system. Figure 4.2 shows the structure of X' for the example system. The bounds are [ur(t)]lh = P[X'(t) = f], [«r(i)]ub = -P[A-,(i)e{tt0,/}]. (4.1) The correctness of [ur(í)]¡b is trivial. The correctness of [ur(£)]ub is proved next under the conditions: 1. 1 < d(a) < d{a),ae U, 2. d(a) < L. We will construct the proof with the aid of the DTMC Y and Y'. Since [83] X(t) = YN(t) and X'(t) = Y^rmi where N = {N(t);t > 0} is a Poisson process with arrival rate A, we have P[X(t) = a} = JTe-*A-^P[Yn = a], (4.2) n=0 P[X'{t) = a] = J2 e-At(-^f-PK = a]. (4.3) n=0 60 4 Reliability Bounds of Non-repairable Systems using FD Bounds Let R'm(d) = P[yl = uo\Y¿ = ud], (4.4) Rm{a) = P\Yn = f\Y0 = a]. (4.5) The following two results related to the "bounding" states u, are taken from Chapter 3. Lemma 4.1 R'm{d), m > 0, d > 0 is decreasing on d. Proposition 4.1 Rm(a) < R'm{d), a £ U¿, m > 0, d > 0. In Chapter 3 it has also been shown that if X' is built using transition rates \a,ud from states a £ G to ud, 1 < d < L, then P[Yn = /] < P[Y¿ £ {u0, f}]. Since R'm{d) decreases on d, it seems intuitively clear that after substituting rates \a,Ud by rates Xafj (i.e. leading to t¿,-, i < d part of the transitions which went from a £ G to ud), -PIXÍ £ {uo,f}] will also upper bound P[Yn = /]. This result is formally proved next. Proposition'4.2 Assume 1 < d(a) < d(a), a £ U, d(a) < L and P[X(0) £ G] = 1. Then, P[Yn = f] < P[Y¿ £ {tío,/}], n > 0. Proof Y can enter / through U or directly from G. Taking into account that / is absorbing, conditioning the entry of Y in / through U to the step in which Y enters U and the entry state, and using (4.5), n-l P[Yn = /] = E E^7—1 € GAY™ = a^Yn = f\ym = «] ro=l a€U n + Ep[y— i€GAym = /] m=l n-l n = E E P[y— » € G A ym = a]Rn.m(a) + E W»-i € G A Km = /]. ro=l aGi/ m=l Since 1 < d(a) < d(a), d[a) <L, a £ U, U¿ can be partitioned as min{d,¿} ud= (J Vdti. t=i 4.1 Bounding Method 61 Then, since L = d(o) < d(o) = L, L L min{d,L} L L u=\jud = \j ù ^ = UU^- d-1 d=l t'=l ¿=1 d=i Using the above partition of U and Proposition 4.1, n-l L L p[Yn = f] = E EE E p[y—1 € G Ay- =a^"—(°) m=l t=l d=t „gj; . + ¿?[ym.ieGAym = /] m=l i-l Z L <EEEE p[y—i e G A7m = a]i?;_m(d) m=l ¿=1 d=i aei/d ; n + ^F[Fm_1eG'Aym = /] m=l Then, using Lemma 4.1, Üi = Ud=¿ &d,i, the relations between Y and Y' and (4.4), PK = /] < E EE E p[y—i € G AFm = a]i2;_m(i) mil i=l d=i a€Üdii + J2P{ym-ieGAYm = f] m=l n-l L = E E E pty—1 e G A ym = a]fi;_m(¿) m=l t=l aÇjj. n + Epty—i€GAym = /] m=l = E E p[y--ie G A y- = «W-ÍO + E p[y--i e G A F: = /] m=l »=1 m=l = E E p[y--i eGAy- = u¿]pK = «o i v^ = ti,] m=l t=l m=l = PK = «o] + PK = /] = PK 6 {«o, /}]-D Finally, 62 4 Reliability Bounds of Non-repairable Systems using FD Bounds Theorem 4.1 Assume 1 < d(a) < d(a), aeU, d(a) < L and P[X{0) G G] - 1. Then, ur(t) < [ur(t)]uh. Proof Using (4.2) and P[Y0 = /] = P[X(Q) = /] = 0, ur(t) = F[X(i) = /] = ¿ e-Ati-^P[Yn = f]. n=l Using Proposition 4.2, P[Y0' € {u0,/}] = P[X'{Q) € {«o,/}] = 0, (4.3), and (4.1), „(t) < ¿,-Ml/W e {«„,/,] - Êe-^PK e {«o,/}] n=l n=0 = P[X'(í)6{«o,/}] = [«r(í)]ub.D 4.2 Lower Bounds for Failure Distances In this section we obtain lower bounds d(a) = db(F(a),gr) for failure distances from states a. We prove that the bounds fulfill the necessary requirements: d(a) = 0 if and only if d(a) = 0 (to know from d(a) if a is operational or down) and 1 < ¿(a) < <f(a), a € U, d(a) <,¿ (Theorem 4.1). We give a sufficient condition for d(a) = d(a) and a lower and an upper bound for dt,(F, x), F = F' + F" in terms of di>(F', x). Finally, an efficient algorithm to compute the lower bounds for failure distances on the fault tree is derived and illustrated. Throughout the section we will use the following specific notation and definitions. Notation and Definitions C set of component classes / set of inputs (basic events) of the fault tree; each input x has associated a different bag, b(z), of the form c[n], c € C, n > 1, meaning the failure of n components of class c P set of gates (complex events) of the fault tree gr root gate (top event) of the fault tree node or event gate or input of the fault tree type(a;) type of node a;: AND, OR if x £ G; input if x 6 / related two inputs x, y are related if b(x) = c[n] and b(y) = c[n'], n / n' fo(:r) fanout of (set of nodes fed by) node x 4.2 Lower Bounds for Failure Distances 63 fi(x) fanin of (set of nodes that feed) node x val(-) value of an input or a gate, which may be 1 or 0. For inputs x £ I, b(x) = c[n], val(x) = 1 if and only if n or more components of class c are failed; for gates x € P, its value is determined as usual from the values of y € fi(x) realized an event x is said to be realized if val (a:) = 1 lev(-) level of an input or a gate. For inputs x Ç. I, lev(x) = 0; for gates y € P, lev(y) = 1 + maxz6fi(j/){lev(z)} path a sequence of nodes x\...Xk such that x,- € fo(a;,+i), i = 1,..., k — 1 reachable node a node x is reachable from node y if there exists a path from y to a; Reach (a;) set of nodes reachable from node x plus x itself Support(x) ID Reach(x), iÇ/UP independent two nodes x, y G I D P are said to be independent if Support(x) n Support(y) = 0 and for each z € Support(x), b(z) = c[n], no t € Support(y), b(t) = c[n'} exists S(F, X) F D (]CyeSupport(i) b(y)) , being F a bag of failed component classes and x a node module a node x G / U P is a module if and only if every path z.. .y, z £ Reach(x), y € Reach(x) contains node x, and for each input y € Support(x), no related inputs exist outside Support(x) db(F,x) being F a bag of component classes and x an event, minimum number of components which have to fail in addition to those in F to realize x; it is called distance from bag F to event x db(F,x) lower bound for dt,(F,x) f?(e) = ¿b(e,yr) lower bound for the failure distance from a failure bag e € E to gr 4.2.1 Recursive Definition of Lower Bounds for Failure Distances Note that from the above definitions, d(a) = dt,(F(a),gr). The computed lower bounds are d(a) = cib(F(a),yr). The lower bounds d^[F(a),gr) are computed on the fault tree of the system using the concept of module, which generalizes to component classes the definition given in [57, 40], in the sense that a module is a node such that the subtree hanging from it has that node as only entry point and every input of the subtree does not have related inputs outside the subtree. To determine which gates or inputs of the 64 4 Reliability Bounds of Non-repairable Systems using FD Bounds fault tree are modules, we use the algorithm LTA/DR of [40] with a small modification to take into account component classes: during the first depth-first left-most traversal of the fault tree (step no. 2 of the algorithm), visit to x € I implies simultaneous visit (i.e. with the same "time stamp" as for x) to all inputs related to it. Given a bag of component classes F, db(F,x), x € I\JP is recursively defined by the following expressions: x € I, b(x) = c[n] ~ , „ . Í n if no c[n'\ is part of F . „, db(F,x) = \ \ J * . (4.6) [ max{0, n — n j if c[n'\ is part of F i6f; type(ir) = OR db{F,x) = min (db(F,y)}. (4.7) x 6 P; type(ar) = AND db (F, x)= ^2 db (F, y) + max j J] db (F, y), max j 0, db(F, y)} 1, yeA(x) Ky€B(x) y€ {x) } (4,8) with A{x) = {y6 fi(a:)| y is a module A |fo(y)| = 1}, B{x) = {¡/G fi(a;)| y is a module A |fo(y)| > 1 V y is not a module A y € /} and C(a;) = {y 6 fi(a;)| y is not a module A y € Expressions (4.6), (4.7) and (4.8) allow to compute db(F,gr) by traversing the fault tree depth-first left-most starting at gr. We depict in Figure 4.3 the fault tree of the example system and show in Table 4.2 how L = db(®,gr) would be computed for that fault tree. Note that all gates and inputs of the fault tree are modules and, therefore, (4.8) reduces to db(F,x) = Eyefi(x) ¿b{F, y). 4.2.2 Correctness of the Lower Bounds for Failure Distances and Related Results First, we prove that given a bag of component classes F and x Ç IU P, 0 < db(F, x) < db(F, x) and db(F, x) = 0 if and only if db(F, x) — 0. The proof consists of a sequence of a lemma, two propositions and a theorem. Lemma 4.2 Let x,y € I U P, and let x be a module. Then, if x,y £ I, Reach(x) (1 Reach (y) = 0; otherwise, Reach (x) n Reach (y) ^ 0 if and only if either x € Reach (y) or y 6 Reach (x). 4.2 Lower Bounds for Failure Distances 65 Xi X2 X¡ MCi[3] ICi[l] RMMx[l] X7 X8 Xg CPUC[2] PTC[2] RCM[2] 1 X4 X5 X6 MC2[3] IC2[i] RMM2[l] Figure 4.3: Fault tree of the example system. Bags associated with inputs are given below to them. Table 4.2: Computation of L = ¿b(0,5r) traversing depth-first left-most the fault tree of the example system and using expressions (4.6), (4.7) and (4.8). step node x ¿b(0,x) step node a: ¿b(0,aO 1 9r - 10 %5 1 2 fi'l - 11 X6 1 3 92 - 12 93 1 4 xx 3 13 9i 2 5 x2 1 14 x7 2 6 £3 1 15 Z8 2 7 52 1 16 XQ 2 8 53 - 17 9r 2 9 #4 3 66 4 Reliability Bounds of Non-repairable Systems using FD Bounds Proof If x, y G /, the result is trivial. The three remaining cases we have to deal with are: x G I,y G P; x G P, y G I; and x,y e P. The if implication for these cases is also trivial since x G Reach(y) or y € Reach (x) implies (recall that x G Reach (x) and y G Reach(y)) Reach (x) n Reach (y) ^ 0. Regarding the only if implication, consider first the case x G I, y G P. Reach(x) n Reach(y) = {a;} n Reach(y) ^ 0 implies x G Reach(y). The case x G P, y G I is analogous: Reach (x) f~l Reach (y) = Reach(x) D {y} ^ 0 implies y G Reach(x). Now, consider the case a;, y G P. Assume that Reach(x) n Reach(y) £ 0 and neither a: G Reach(y) nor y G Reach(x), and take z G Reach(x) n Reach(y). Then, since x $ Reach(y), the path y...z does not contain event x, which contradicts the fact that x is a module because y £ Reach(x) and z G Reach (x). Q Proposition 4.3 ¿ei x,y e IU P, z € P, x,y Ç. fi(z), and let x be a module. Then, x and y are independent if one of the following conditions holds: a) y el, b) y € P and y is a module, c) y G P and |fo(x)| = 1. Proof If Support(a:) nSupport(y) = 0, the inputs in Support(x) are not related to those in Support(y) because x is a module and, thus, x and y are independent. Therefore, it suffices to prove Support(a:) D Support (y) = 0 or, equivalently, Reach(x) D Reach(y) = 0. Condition a: If x G 7, Reach (x) (1 Reach (y) = 0 by Lemma 4.2. If x G P, Reach (x) D Reach (y) = Reach (x) n {y} ^ 0 if and only if y G Reach (x) by Lemma 4.2 (x G Reach (y) is not possible). But y G fi(z) implies the existence of the path zy not containing x, and, then, y G Reach(x) would contradict the fact that x is a module. Condition b: Assume that Reach (x) n Reach (y) ^ 0. Using Lemma 4.2, either x G Reach (y) or y G Reach (x). x G Reach (y) and the existence of the path zx contradicts the assumption that y is a module. If x G /, y G Reach(x) is not possible. If x G P, y G Reach(x) and the existence of the path zy contradicts the assumption that x is a module. Condition c: Assume as before that Reach (x) n Reach (y) •£ 0. From Lemma 4.2, either y G Reach (x) or x G Reach (y). If x G /, y G Reach (x) is not possible. If x G F, y G Reach (x) and the existence of the path zy contradicts the assumption that x is 4.2 Lower Bounds for Failure Distances 73 as consequence of Theorem 4.2, b is a down state if and only if d(b) = 0). We have that F(b) = F(a) + e and, therefore, d(b) = dh(F(b),gr) could be computed traversing the fault tree depth-first left-most starting at gr and using (4.6), (4.7) and (4.8). However, this procedure could be expensive if the fault tree is large. Next, we describe an algorithm and, based on it, two procedures to compute d(b) more efficiently. We first describe the algorithm. The algorithm takes as inputs a bag of component classes F and a positive integer ub. Each node x of the fault tree holds a "distance variable" dv(x) properly initialized. The fault tree is processed from inputs to gr as follows. For each c[n] that is part of F, we make dv(x) = max{0, dv(x) — n} for each input x, b(x) — c[n']. Each change of dv(x) for an input a; that results in dv(x) < ub is propagated up the fault tree while dv(z) changes to a value < ub for the visited gate z. Distance variables of gates are not updated unless the new value is distinct from the previous one and < ub. dv(z), z £ P is computed from (4.7) for OR gates and (4.8) for AND gates using dv(y), y G fi(z) instead of d^F,y), y G fi(-z). The first procedure is called comp.d(F, lb, ub, CS), where F is a bag of component classes, lb, ub, lb < ub are non-negative integers and CS is a stack. If lb = «ò, the procedure returns lb without doing anything else. If lb < ub, the fault tree is processed using the above algorithm. During the traversal of the fault tree, the nodes x whose distance variable changes as well as the corresponding old value dv(x) are bookkept in CS. At the end, the procedure returns min{dv(gr), ub). The second procedure is called restored (CS), where CS is a stack. The procedure simply restores the distance variable of the nodes kept in CS to its old value. We prove next two results. The first one shows that if invoked with appropriate arguments, the procedure comp.d returns db(F, gr). The second result shows how d\>(F, gr) can be computed calling the procedure consecutively twice. The usefulness of the latter result will become apparent when describing the way the CTMC X' is generated. The proof consists of a sequence of three propositions and two theorems. Proposition 4.5 Assume that the distance variable of each node x has been initialized to db(0,x). After running the algorithm with inputs a bag of component classes F and a positive integer ub, d^(F,x) — dv(x) if dv(x) < ub and dh(F,x) > ub if dv(x) > ub, xelUP. Proof By complete induction on lev (a;), x € IU P. 74 4 Reliability Bounds of Non-repairable Systems using FD Bounds Base case (lev(x) = 0). We have x £ /, b(x) = c[n]. After running the algorithm, dv(x) = n if no c[n'] is part of F and du(ï) = max{0, n - n'} if c[n'] is part of F. Then (4.6), cft?(x) = db(F,x), showing both db^z) = dv(x) if du(x) < u6 and db(F,x) > ub if dv{x) > ub. Induction step. We will assume that the result holds for all x £ / U P, lev(x) < /, / > 0 and show that it also holds for all x £ P, lev(x) = I + 1 (x £ I because I + 1 > 0). Let x £ P, \ev(x) = / + 1 and consider the partition fi(x) = a U ß with a = {y £ fi(x) | dv(y) < ub after running the algorithm} and ß = fi(z) — a = {y ç fi(x) | dt;(y) > u6 after running the algorithm}. We will show the result first for type(a;) = OR and next for type(x) = AND. Let type(x) = OR. Assume a ^ 0. Since, trivially, the values held by the distance variables cannot increase, dv(y) > ub, y Ç. ß throughout the execution of the algorithm and, hence, any update of dv(y), y G ß (only possible if y is an input) cannot lead to updating dv(x). Therefore, only updates of dv(y), y 6 a to values < ub may result in updating dv(x). Note that, using the induction hypothesis, at the end of the algorithm, db(F,y) = dv(y) < ub, y £ a and db(F,y) > ub, y € ß. Then (4.7), db(F,x) = m'my€a{dv(x)} < ub after running the algorithm. If no dv(y), y £ a has been updated, since dv(x) = miny6fi(a.){du(y)} at the beginning of the algorithm, we have that, at the end of the algorithm, dv(x) = minyça{dv(y)} — db{F,x) < ub. If some dv(y), y £ a has been updated, consider the last time a dv(y), y £ a is updated to a value < ub (since at the end of the algorithm dv{y) < ub for all y £ a, at least one such update must have happened). All dv(y), y £ a will hold their final values, which are < «6, and dv(x) will be set to dv' = minyga{du(y)} unless dv(x) were already equal to dv'. Then, at the end of the algorithm, dv(x) = m'my£Q{dv(y)} = d^^x) < ub. Assume now a — 0 and, therefore, ß •£ 0. As it has been discussed before, any update of dv(y), y £ ß cannot have led to updating dv(x). Therefore, dv(x) has not been updated and after running the algorithm its value is equal to its initial value, which, given the way the distance variables are initialized and that the values they hold cannot increase, is > ub. Since fi(x) = ß and, by the induction hypothesis, db(F,y) > ub, y £ ß, it follows (4.7) that d~b{F,x) > ub. Let type(ar) = AND. Assume ß ^ 0. As it has been discussed for the case type(x) = OR, dv(y) > ub, y £ ß throughout the execution of the algorithm. The computed values for dv(x) will be J2 dv(y) + max{ ^ dv(y), max {0, dv(y)}} , y£A(x) y€B(x) V€ (X) 4.2 Lower Bounds for Failure Distances 75 which are not smaller than dv(y), y £ ß. Then, the computed values for dv(x) will be > ub and dv(x) will never be updated. Given the way the distance variables are initialized and that the values they hold cannot increase, the final value of dv(x) will be > ub. Moreover, from (4.8) and the fact that, by the induction hypothesis, db(F, y) > ub, y £ ß, it follows that d\>(F,x) > ub. Assume now ß = 0. We have ñ(x) = a. If no dv(y), y £ a has been updated, after running the algorithm dv(x) and dv(y), y £ a hold their initial values. By the induction hypothesis and the fact that fi(x) = a, dv(y) = db(F,y), y £ fi(x). Then, from (4.8) and the way the distance variables have been initialized, dv(x) = </b(F,x) after running the algorithm, which shows both db(F,x) = dv(x) if dv(x) < ub and db(F, x) > ub if dv(x) > ub. If some dv(y), y £ a has been updated, consider the last time a dv(y), y £ a is updated to a value < ub (since at the end of the algorithm dv(y) < ub for all y 6 a, at least one such update must have happened). Since fi(x) = a, all dv(y), y £ fi(x) will hold their final values and the value dv' to which dv(x) might be set will be computed as dv' = YJ dv(y) + m&x{ YJ dv(y), max {0, dv(y)}} . yeA(x) yeB(x) yeC{x) From (4.8), the fact that fi(x) = a and that, by the induction hypothesis, dv(y) = db{F, y), y £ a, it follows that db(F, x) = dv'. Also, since the values held by the distance variables cannot increase, the current dv(x) will be > dv'. If dv' > ub, dv(x) will not be set to dv' and, hence, db(F, x) = dv' > ub and dv(x) > dv' > ub. If dv' < ub, dv(x) will be set to dv' unless it were already equal to dv' and, thus, db(F, x) = dv' = dv(x) < ub. Ü Proposition 4.6 Let F, F' and F" be bags of component classes with F = F' + F" and let ub, ub' with ub' < ub be positive integers. Let dvi(x), x £ I U P be the values of the distance variables that will result after initializing them to dh($,x) and next running the algorithm with inputs F and ub', and let dv2{x), x £ I U P be the corresponding values that will result if after performing the same initialization the algorithm is run consecutively twice, first with inputs F' and ub and next with inputs F" and ub'. Then, dvi(x) = dv2(x) or dvy{x) > ub' and dv2(x) > ub', x £ Il)P Proof For the sake of conciseness, let case 1 stand for "the distance variable of each node x £ IUP has been initialized to ¿b(0, x) and next the algorithm has been run with inputs F and ub'" and let case 2 stand for "the distance variable of each node x £ Il)P has been initialized to d\> (0, x) and next the algorithm has been run consecutively twice, first with inputs F' and «6 and next with inputs F" and ub'". Note that if ub' = ub the 76 4 Reliability Bounds of Non-repairable Systems using FD Bounds fault tree is dealt with the same in both cases and dvi(x) = dv2(x), x G I UP. Next, we show the result for the case ub' < ub using complete induction on lev (a;), x G IU P. Base case (lev(x) = 0). We have x £ I. Since the initial value of dv(x) is the same in both cases, dv(x) is updated depending only on b(x) and the bag of failed component classes, and F = F' + F", it follows that dv\(x) = dv2{x). Induction step. We will assume that the result holds for all x G / U P, lev(x) < /, / > 0 and show that it also holds for all x G P, lev (a;) = / + 1 (a; cannot be an input since / + 1 > 0). Let x G F, lev (s) = / + 1 and consider the partition fi(x) = a + ß with a = {y G fi(x) | dvi(y) = du2(y)} and ß = {y G fi (a;) | dvx{y) ^ dv2(y)}. Note that, using the induction hypothesis, dvi(y) > ub' and dv2{y) > ub', y G ß and since the values held by the distance variables cannot increase, dv(y), y G ß will always be > ub' in both cases. We will show the result first for type(a;) = OR and next for type(a;) = AND. Let type(a;) = OR. Assume a = 0. We have fi(x) = ß. Since dv(y) > ub', y G fi(z), dv(x) has not been updated in case 1 and, thereby, it holds the initial value, which, since dv(y), y G fi(^) cannot increase, is > ub'. Therefore, we have dvi(x) > ub'. Regarding case 2, either dv(x) has not been updated and, hence, dv2{x) = dvi(x), or it has been updated (recall that ub' < ub) and, since dv(y) > ub', y G fi(x), dv2(x) > ub'. Assume now a ,¿ 0. If there exist y G a such that dvi(y) = dv2(y) < ub', since «6' < ub, we have dvi(x) = min {dv\(y)} = min {dv2{y)} = dv2(x). dvi(y)<ub' dv2(y)<ub' If no such y G a exists, dvi(x) holds the initial value, which, since dv(y), y G fi(x) cannot increase, is > ub', and either dv2(x) also holds the initial value and, hence, cb2(x) = dvi(x), or dv(x) has been updated in case 2 and, since dv(y) > ub', y G fi(^), dv2(x) > ub'. Let type(ar) = AND. If ß ^ 0, in both cases the computed values for dv(x) will be Y2 dv(y) + max{ J^ dv(y), max {0, dv{y)}} > ub'. yeA(x) yeB(x) y6 (x) Then, dv(x) will not be updated in case 1. Therefore, dvi(x) will hold the initial value, which, since dv(y), y G fi(a?) cannot increase, is > ub'. If dv(x) is not updated in case 2, dvi(x) = <ft;2(a;); if dv(x) is updated in case 2, since dv(y) > ub', y G ß, dv2(x) > ub'. Assume now ß = 0 and, therefore, fi(a;) = a. If dv(x) is updated in case 1, dvi(x)- Y] dv1{y) + max{ V dv^y), max {0, dv^y)}} yÇA(x) yeB(x) y* y ' = S dv2(y) + m&x{ ^ dv2(y), max {0, dv2(y)}} < ub'. y£A(x) yeB(x) y£ (X) 4.2 Lower Bounds for Failure Distances 77 Therefore, since ub' < ub, dv(x) is also updated in case 2 and dv2(x) = dvi(x). If dv(x) is not updated in case 1, it may or may not be updated in case 2. If dv(x) is updated in case 2, dv2(x)= ]T dv2(y) + max{ ^ dv2(y), max {0,dv2(y)}} yeA(x) yeB(x) veC(*) - Yl ¿üi(y) + max{ Y^ rf»i(y)> max ÍO.íí^íy)}}, with either ub' < dv2(x) < ub or £¿«2(2) < «&'. Note, however, that if dv2(x) were < ub', dv(x) would have been updated to dv2(x) by the end of the algorithm in case 1. Therefore, dv2(x) > ub' and since the values held by the distance variables cannot increase and they are initialized the same in both cases, dv\(x) > dv2(x) > ub'. Finally, if dv(x) is not updated in either case, dvi(x) = dv2(x). Q Proposition 4.7 Let F, F' and F" be bags of component classes with F = F' + F" and let ub, ub' with ub' < ub be positive integers. Assume that the distance variable of each node x of the fault tree has been initialized to dh($, x). After running the algorithm consecutively twice, first with inputs F' and ub and next with inputs F" and ub', we have that di)(F,x) = dv(x) if dv(x) < ub' anddb{F,x) > ub' if dv(x) > ub'. Proof Let x € IUP and let dvi(x) and dv2(x) as in Proposition 4.6. In this regard, we have to show that db(F,x) = dv2(x) if dv2(x) < ub' and di,(F,x) > ub' if dv2(x) > ub'. Using Proposition 4.6, dv2{x) = dvi(x) or dv2(x) > ub' and dv\(x) > ub', and the results follows immediately from Proposition 4.5. Q Theorem 4.5 Let F be a bag of component classes, lb and ub non-negative integers with lb < dh(F,gr) < ub, and CS a stack. Assume that the distance variable of each node x of the fault tree has been initialized to db(®,x). Then, the call comp.d(F,lb,ub, CS) returns d^ [F, gr). Proof If lb = ub, the call comp.d(F, lb, ub, CS) returns lb and since, by assumption, lb < db(F,gr) < ub, db{F,gr) = lb. If lb < ub, the call returns m'm{dv(gr), ub}.. Two cases are possible: a) dv(gr) < «6 and b) dv(gr) > ub. Since lb < ub and, by assumption, lb > 0, we have that ub is > 0 and, therefore, Proposition 4.5 with x = gr can be invoked in both cases. In case a, m'm{dv(gr), ub} = dv(gr) = db(F,<7r). In case b, m'm{dv(gr), ub} = ub and db(F,gr) > ub, and since, by assumption, dt,(F,gr) < ub, db(F,gr) = ub. D 78 4 Reliability Bounds of Non-repairable Systems using FD Bounds Theorem 4.6 Let F, F' and F" be bags of component classes with F = F' + F", lb and ub' non-negative integers and ub a positive integer with lb < db(F,gr) < ub' < ub, and let CS, CS' be stacks. Assume that the dv variable of each node x of the fault tree has been initialized to d\,($,x). Then, after invoking comp.d(F',0, ub, CS), the call comp.d(F", lb, ub', CS') returns db(F,gr). Proof If lb = ub', the call comp.d(F", lb, ub', CS') returns lb and, since by assumption, lb < d\>{F,gr) < ub', db(F,gr) = lb. If lb < ub', the call returns m\n{dv(gr), ub'}. Two cases are possible: a) dv(gr) < ub' and b) dv(gr) > ub'. We have, by assumption, that ub > 0 and lb > 0. The fact that ub > 0 implies that the call comp.d(F', 0, ub, CS) results in processing the fault tree with the described algorithm with inputs F' and ub; the fact that lb > 0 together with lb < ub' implies that ub' > 0. Therefore, Proposition 4.7 with x = gr can be invoked in both cases. In case a, mln{dv(gr), ub'} = dv(gr) = db{F,gr). In case b, mm{dv(gr), ub'} = ub' and db(F,gr) > ub', and since, by assumption, d\,(F,gr) < ub',db{F,gr) = ub'. D Computation of d(b) = dh(F(b),gr) using the procedure comp.d requires to know a lower and an upper bound bound for d(b). From what was shown at the end of Section 4.2.2, 0 < d(b) < L. If we recall that b is a successor of a reached in a single transition associated with failure bag e, i.e. F(b) = F(a) + e, these bounds can be tightened up with the aid of Theorem 4.4 (the tighter the bounds, the faster comp.d). Let x = gr. Taking F' = F(a) and F" = e, the theorem yields d(a) > d(b) > d(a) — S(e,gr); taking F' = e and F" = F{a), rj(e) > d(b) > rj(e)-S{F(a),gr). Then, since S(e,gr) < \e\, S(F(a),gr) < \F(a)\ and d(a) < L, we have max{0,5(a) - \e\,rj(e) - \F(a)\} < d(b) < m'm{d(a) ,rj(e)}. The L and 77(e), e € E are computed prior to the generation of the CTMC X'. The distance variable of each node x of the fault tree is initialized to ¿b(0,z) by traversing the fault tree depth-first left-most starting at gr and using (4.6), (4.7) and (4.8). After the initialization, L = dv(gr). Computation of rj(e) = db(e,gr), e € E using comp.d requires to know a lower and an upper bound for ??(e). From part a of Theorem 4.2 with x = gr and F = e, 0 < db(e,gr) — rj(e); from the left inequality of Theorem 4.4 with x = gr, F' = 0 and F" = e, L — db(Ç>,gr) > db(e,5v) = f?(e). Therefore, based on Theorem 4.5 with F = e, lb = 0 and «6 = L, rj{e), e £ E are computed calling, for each e, comp.d{e, 0, L, CS) followed by a call to restore.d (CS). Note that after computing all 77(e), e € E, the distance variable of each node x still holds its initial value ¿t>(0, a:)- We sketch next how the CTMC X' is generated breadth-first using 77(e), e € E and 4.2 Lower Bounds for Failure Distances 79 the procedures comp.d and restored. The state o in which all components are unfailed is put in G and, with d(o) = L, in an empty first-in first-out (FIFO) queue. That queue contains the states to be processed and each state a in the queue has associated with it its lower bound for the failure distance d(a). From that point, the generation process continues as follows. The first state a in the queue is pulled out, comp.d(F(a), 0, d(a), CS) is called and the list of failure bags which are active in a is obtained. Each such active e € E has associated with it one or more transitions to states b satisfying F(b) = F(a)+e. For each active e, lb = max{0,¿(a) — |e|, 77(e) - |F(a)|} and ub' = min{d(a), 77(e)} are computed and, based on Theorem 4.6 with F' = F(a), F" = e, F = F' + F" = F(b), and ub = d(a) (it is trivial to check that ub' — min{d(a), 77(e)} < d(a) = ub, ub > 0 and ub' > 0), d(b) for the successors b of a associated with e is computed by calling comp.d(e, lb, ub', CS'). If d(b) = 0, states b are down and the corresponding transition rates A0i& are directed to /; if d(b) > 0 and \F(a) + e| > K, states b belong to U and the corresponding transition rates Aa>6 are directed to uj,^; if d(b) > 0 and \F(a) + e| < K, states b are put in G and, with the corresponding d(b), in the FIFO queue if they were not in G yet and the corresponding transition rates \a¿ are directed to b. Once all the successors 6 of a associated with e have been processed, restored (CS') is invoked to allow another failure bag active in a to be dealt with. When all active failure bags in a have been processed, restore.d(CS) is invoked before processing another state of the FIFO queue. The.generation of X' finishes when the FIFO queue becomes empty. To illustrate how the procedures comp.d and restore.d work, consider again the example system described in Section 4.1 and its fault tree depicted in Figure 4.3. Let a Ç: G with F(a) = AfCi[l] and let us discuss the processing of two successors, b and c, where transition from a to 6 is associated with failure bag e\ = ICi[l) (see Table 4.1) and transition from a to c is associated with failure bag er = AfC2[l] RMMill]. For the example, L = 2, J7(e4) = 1, rjiej) = 1, and d(a) = 2. Let CS and CS' be empty stacks. As it has been explained before, computation of d(b) and d(c) requires to invoke comp.d(F(a), 0, d(a) = 2, CS) first. Figure 4.4 illustrates the processing of the fault tree during that invocation. Recall that dv(x) is initialized to e?b(0,x) for all nodes a;. The procedure starts by making (4.6) dv(xi) = max{0,3 - 1} = 2. Since this value is not smaller than d(a) = 2, the change is not propagated up the fault tree and the procedure finishes. The only contents of the stack CS is the pair (xi,3). The d(b) is the value returned by the call comp.d(e4, lb, ub, CS') with /6 = max{0, d(a) - |e4|, 7/(e4) - |F(a)|} = max{0,2- 1,1 - 1} = 1 and «6 = min{d(a),^(e4)} = min{2,1} = 1. Since lb = ub, the invocation returns lb = 1 without traversing the fault tree. Finally, d(c) is the value returned by the call comp.d(e7, lb, ub, CS') with lb = max{0, d(a) - \e7\, rj(e7) - \F(a)\} = 80 4 Reliability Bounds of Non-repairable Systems using FD Bounds dv=2 x\ x2 x3 dv = 3 -+ 2 dv = 1 dv = 1 MCX\2,] 7C,[1] ÄAfAfill] 2?7 Xs X9 dv = 2 dv = 2 dv = 2 CPUC[2] PTC[2] RCM[2) dv = l x4 xh x6 dv = 3 dv = 1 dv = 1 MC2[3) IC2[l] RMM2[1] Figure 4.4: Up traversal (thick line) of the fault tree of the example system during the call comp.d(F(a), 0,2, CS), F(a) = MCi[l]. The values of the distance variables are given next to each node. A rightward arrow signals the values of the distance variables that change during the traversal. max{0,2-2,1-1} = 0 and «6 = min{d(a), 57(67)} = min{2,1} = 1. Figure 4.5 illustrates the processing of the fault tree during the invocation comp-d(e7,0,1, CS'). The procedure starts with the part MC2[1] of ey. Using (4.6) and the dv value of input X4, the procedure makes dv(x4) = 2. This change is bookkept in the stack CS' but it is not propagated up the fault tree since this new dv value is not smaller than ub = 1. Next, the procedure deals with the remaining part RMMzil]- Using (4.6) and the value of dv(xe), the procedure makes dv(x&) = 0 < 1 and propagates the change up to 53. Using (4.7), dv(g3) changes from 1 to 0, which is again < 1. Since this new value of dv(gz) would result (4.8) in dv(gi) = 1, which is not smaller than «6 = 1, dv(gi) is not updated and the procedure finishes returning min{dt;(<7r), ub} = min{2,1} = 1. The contents of the stack CS' are, from top to bottom, the pairs (33,1), (xß, 1) and (£4,3). The fault tree is restored to its original state by calling, in this order, restore.d (CS') and restore.d (CS). The trivial bounding method requires the knowledge of the operational/down state of the single-transition successors 6 of an operational state a. We describe next the procedures to determine that which have been used in our implementation of the trivial bounding method. The procedures are analogous to the procedures used in the proposed bounding method to compute lower bounds for failure distances and allow to make a fair comparison of both methods regarding CPU time consumption. The procedures are 4.2 Lower Bounds for Failure Distances 81 dv = 2 Xj X$ Xg dv = 2 dv = 2 dv = 2 CPUC[2] PTC[2] RCM{2) dv = 1 -> 0 X\ X-i Xz dv = 2 dv = 1 du = 1 M<7![3] 7(7i[l] ÄMM41] X4 X5 Xß iv = 3 -» 2 dv = 1 <fo = 1 -» 0 AfC2[3] JC2[1] ÄMM2[1] Figure 4.5: Up traversal (thick lines) of the fault tree of the example system during the call comp.d(e7,0,1, CS1), e7 = MC2IL] MM2[1]. The values of the distance variables are given next to each node. A rightward arrow signals the values of the distance variables that change during the traversal. evahft and restorer. The procedure evaLfl returns val(#r) for a given bag of failed component classes. Using both procedures as described next, we imply to 1 the inputs x, b(x) = c[n] such that cln1], n' > n is part of the bag of failed component classes under consideration. Implications in the fault tree are done from inputs to gr in the usual way: if type(x) = OR, val(y) = 1 for some y € fi(2:) implies val(x) = 1; if type(x) = AND, val(y) = 1 for all y € fi(z) implies val(x) = 1. Since all gates are either OR or AND, that procedure is enough to know val((?r) (if gr is implied to 1, val(<7r) = 1; if gr is not implied, val(<5rr) = 0 since implication to 0 of the unimplied inputs of the fault tree would imply gr to 0). Each input x, b(x) = c[n] of the fault tree holds a "value" variable vv{x) = max{0, n — n'}, where n' is the number of components of class c that are failed. Initially, vv(x) = n and all gates of the fault tree are set to the unimplied state. The procedure eval.ft(F, CS), where F is a bag of failed component classes and CS is a stack, works as follows. For each input x, b(x) = c[n] for which c^n7] is part of F, we make vv(x) = max{0, vv(x) - n'} and imply x to 1 if vv(x) becomes 0. Each implication of an input x is propagated up the fault tree while the visited gate z becomes implied. Inputs x whose value variable changes as well as gates z that become implied are bookkept in CS. A call to restore.v(CS) undoes the changes done within the previous call to evaLft(F, CS). Recall that in the trivial method the CTMC is modified so that exits of 82 4 Reliability Bounds of Non-repairable Systems using FD Bounds X from G not going to / are directed to an absorbing state u0. Such a modified CTMC is generated breadth-first in a similar way as X' is generated in the proposed bounding method. Starting from the point in which a state a has been pulled out of the FIFO queue and the list of failure bags that are active in a has been obtained, the generation procedure proceeds as follows. The fault tree is set up by calling eval.ft(F(a), CS). For each active failure bag e, the operational/down state of all successors b of a associated with e is obtained by calling evaLfl(e, CS'). If the call results in val(<?r) = 1, successors ò are down and the corresponding transition rates Aai(, are directed to /. If val(gr) = 0, successors b are up. In that case, the corresponding transition rates Aa)¡, are directed to u0 if \F(b)\ = \F(a) + e\ > K; otherwise, successors b are put in G and in the FIFO queue if they were not in G yet and transitions A0i¡, are directed to ò. Each call evaLft(e, CS') is followed by a call restore.v(CS'), and once all successors of a have been processed, restore.v(CS) is invoked. The generation of the modified CTMC finishes when the FIFO queue becomes empty. We next compare for the particular case L = 1 the effort in the proposed bounding method associated with the computation of the lower bound for the failure distances from states with the effort in our implementation of the trivial method associated with the evaluation of the fault tree. Note that d(a) = 1 for up states a and that 0 < 77(e) < 1. Beginning at the point in which a state a has been pulled out of the FIFO queue and the list of failure bags that are active in a has been obtained, the proposed bounding method continues by calling comp.d(F(a), 0,1, CS). From the description of comp.d, this call results in traversing up the fault tree following the nodes z such that dv(z) changes to 0, i.e. the nodes that would become implied, exactly as eval.ft(F(a), CS) does in our implementation of the trivial bounding method. Next, in the proposed bounding method lb = max{0,if(a) — |e|, 77(e) — |F(a)|} and ub = min{d(a), 77(e)} are computed for each active e, and d(b) for the successors b of a associated with e is obtained by calling comp.d(e, lb, ub, CS') once. Since a is an up state, d(a) = 1. Furthermore, 0 < 77(e) < 1 and |e|,|F(a)| > 1. Then, lb - 0 and 0 < ub < 1, with ub = 0 only if 77(e) = 0. Therefore, if 77(e) > 0, the call comp.d(e, 0,1, CS') again involves traversing up the fault tree following the nodes which would become implied, exactly as eval.fi(e, CS') does in our implementation of the trivial bounding method; if ub = 0, comp.d returns 0 without traversing the fault tree. Therefore, for the particular case L — 1 the effort in the proposed bounding method associated with the computation of the lower bounds for the failure distances from states is at most equal to the effort in our implementation of the trivial method associated with the evaluation of the fault tree. 4.3 Analysis and Comparison 89 Table 4.3: Relative unreliability band obtained with the proposed bounding method, urb(t) (top) and with the trivial method, urb"(t) (bottom) for the first example. time 1 month 2 months 6 months 1 year 2 years 5 years K (states) 2 (325) 3 (2,922) 4 (20,256) 5 (114,243) 5.6074 x 10~3 1.9121 x 101 1.4916 x 10"2 1.9310 x 101 8.8675 x lO"2 2.0721 x 101 3.0844 x 10"1 2.4590 x 101 1.1610 3.7307 x 101 7.9242 9.5814 x 101 9.0751 x 10~4 5.3599 x lO"1 3.4877 x 10"3 7.5534 x lO-1 3.0034 x lO"2 1.6262 1.1625 x lO-1 2.9683 4.4492 x 10"1 6.0617 2.6360 1.9943 x 101 2.4718 x 10~5 5.9234 x 10"3 1.1790 x 10"4 1.4218 x lO"2 1.7085 x 10"3 7.0069 x lO"2 1.0286 x lO"2 2.1744 x 10_1 6.3144 x lO"2 7.2137 x 10"1 6.0118 x 10"1 3.6513 2.4558 x 10"7 5.1234 x 10~5 1.7226 x 10"6 1.9082 x 10~4 5.1856 x 10-5 2.0870 x lO-3 5.2415 x 10"4 1.1154 x lO-2 5.5772 x 10"3 6.4111 x lO-2 1.0547 x 10"1 6.0539 x 10"1 for the second one. In addition, the proposed method allows to compute bounds that are almost as tight or even tighter than those given by the trivial method using significantly fewer states. Thus, for the first example and t = 2 years, the relative band obtained by the proposed method with K = 4 (\G\ = 20,256) is better than that obtained by the trivial method with K = 5 (|G| = 114,243). For the second example and f = 2 years, the relative band obtained by the proposed method with K = 3 (\G\ = 23,231) is only slightly worse than that obtained by the trivial method with K = 4 (|G| = 251,920). The bounds looseness introduced by the proposed method with regard to the method described in Chapter 3 is reasonable. For the first example, urb(t) — urb'(t) because the fault tree satisfies the conditions of Theorem 4.3; for the second example, the use of minimal cuts to compute exact failure distances less than halves the relative unreliability band. In Table 4.5 we give the CPU time in seconds to generate the CTMC and compute the unreliability bounds for t = 5 years for both examples and the three methods. The CPU time has been measured in a 167 MHz, 128 MB SPARC Ultra 1 workstation. With respect to the trivial method, our method introduces a CPU time overhead due to the computation of lower bounds for failure distances from states only when L > 1. This 90 4 Reliability Bounds of Non-repairable Systems using FD Bounds Table 4.4: Relative unreliability band obtained with the proposed bounding method, urb(t) (top), with the method described in Chapter 3, urb'(t) (middle) and with the trivial method, urb"(t) (bottom) for the second example. time 1 month 2 months 6 months 1 year 2 years 5 years K (states) 2 (1,383) 3 (23,231) 4 (251,920) 8.0995 x lO"6 4.2519 x lO"6 3.4966 x lO"3 6.4332 x 10"5 3.4014 x lO-5 1.3816 x lO"2 1.6870 x lO"3 9.1670 x 10"4 1.1952 x 10"1 1.2903 x lO"2 7.2810 x lO"3 4.5153 x lO-1 9.4070 x lO-2 5.6666 x 10"2 1.6114 1.0991 7.6243 x 10"1 7.1970 2.7765 x 10~8 1.9822 x lO"8 1.0013 x 10~5 4.3975 x 10~7 3.1450 x 10~7 7.9310 x 10~5 3.4190 x 10-5 2.4625 x 10~5 2.0576 x lO-3 5.1391 x HT4 3.7395 x lO"4 1.5491 x lO"2 7.2234 x lO-3 5.3589 x lO-3 1.0930 x 10-1 1.8392 x 10-1 1.4348 x lO-1 1.1300 5.9186 x HT11 5.1065 x 10-" 2.1062 x lO-8 1.8731 x 10~9 1.6169 x 10~9 3.3356 x 10~7 4.3531 x 10-7 3.7652 x lO-7 2.5930 x 10~5 1.3015 x 10~5 1.1291 x lO"5 3.8967 x 10~4 3.6184 x lO-4 3.1572 x lO-4 5.4737 x lO-3 2.1999 x 10~2 1.9505 x lO-2 1.3744 x lO-1 4.4 Conclusions 91 Table 4.5: CPU time in seconds to generate the CTMC and compute the unreliability bounds for t = 5 years for both examples using the proposed bounding method (top), the method described in Chapter 3 (middle) and the trivial method (bottom). example first second K 2 0.271 1.72 0.197 3.21 16.4 2.42 3 2.12 4.38 1.52 44.8 68.8 36.4 4 14.8 29.3 11.0 510 998 427 5 90.4 268 73.2 — overhead is reasonable, ranging from 20% in the second example with K = 4 to 40% in the first example with K = 3. Regarding the method proposed in Chapter 3, the method proposed in this chapter is always faster. For the first example, the proposed bounding method should be the method of choice since it is faster than the method described in Chapter 3 and gives the same unreliability bounds. For the second example, at the price of introducing some looseness in the bounds, the proposed bounding method is faster than that described in Chapter 3. In addition, the method described in Chapter 3 has a significant memory overhead due to storage of minimal cuts, so the proposed method is also the method of choice. 4.4 Conclusions In this chapter, we have developed a bounding method for the unreliability at time t, ur(t), which exploits the concept of failure distance, but does not require the knowledge of the minimal cuts of the fault tree of the system. The method is based on lower bounds for failure distances that can be computed inexpensively on the fault tree. The method can be preferable to both the trivial method and the method proposed in Chapter 3 with the same generated subset of states in several cases. Thus, the proposed method gives tighter bounds than the trivial method with a moderate CPU time overhead if L > 1 and without any overhead if L = 1. Regarding the method described in Chapter 3, the proposed method seems to be faster and in some cases it gives exactly the same bounds. 92 4 Reliability Bounds of Non-repairable Systems using FD Bounds In many other cases, though, the proposed method gives bounds that are looser than the bounds given by the method proposed in Chapter 3. However, that method requires the knowledge of the minimal cuts of the system, whose computation can be infeasible in a reasonable amount of time. Also, the number of minimal cuts can be very large and, in those cases, the method proposed in this chapter may be more efficient from a memory usage point of view. Chapter 5 Availability Bounds of Repairable Systems using FD Chapters 3 and 4 have been devoted to develop bounding methods for the unreliability of non-repairable systems. In this chapter we develop a method to upper bound the steady-state unavailability, UA, for repairable systems. The method requires the computation of failure distances. The method developed here takes a particular case of the method described in [22] as starting point and uses one of the state exploration algorithms developed in [20]. The method proposed in [22] was developed for the same class of models considered in this dissertation except that it assumed that repairs involved just one component. We begin by extending that method and showing that it allows group repair, which, as it has been commented in Section 1.5, is an important generalization. Secondly, we improve that method by deriving failure rate bounding structures that are typically better and never worse than the ones used in [22]. Next, we review the state space exploration algorithm developed in [20] we use in our method. Finally, we analyze the performance of the proposed bounding method and compare it with the performances of the methods described in [22] and [70]. 5.1 Extension to Group Repair Let Ü be the state space of the CTMC modeling the system. The method proposed in [22] obtains bounds for the steady-state unavailability generating a subset, G, of Q. That method also uses a cloning technique that consists in the modification of Q by adding to U = Q — G clones of states of G with more than F failed components. Note that the 94 5 Availability Bounds of Repairable Systems using FD cloning technique does not modify UA. In this section we review that method for the particular case F — 0, i.e. when all states of G but o (the only state of Q, without failed components) are cloned, and show that it allows group repair. We start by introducing some notation. Let X = {X(t);t > 0} be the CTMC modeling the system with the state cloning technique applied and let Q be the state space of X. Throughout the section we will denote by A,j, i,j € f2 the transition rate from state i to state j, by At- = Sign ^t'j) ' € ^ the output rate of state ¿, and by ^t,B = X^jeB^î'ji • É fií ß C !î the transition rate from state i to subset B, all referred to X unless stated otherwise. We will also consider a number of transient CTMCs Y. Each such CTMC Y has a state space of the form B U {a}, where all states in B are transient and a is an absorbing state, and has a well-defined initial probability distribution with P[Y(0) £ B] = 1. We will denote by T(Í,Y), i £ B the mean time spent by Y in i before absorption (r(i, Y) = J"0°° P[Y(t) = i]dt). We will also use the notation T(B',Y) = J2ieB' r(z>^r)i B' C B. It is well known (see, for instance, [13]) that the mean times to absorption vector r = (r(i, F)),e£ is the solution of the linear system TTA = — qT, where A is the restriction of the transition rate matrix of Y to B and q = (P[Y(0) = i])ieB- The expected number of times that a transition (i,j) with rate AtJ- is followed is ßij = r(i, F)A,j. The result follows easily: W = Jo°° p[Y(0 = i\\A = Ati /0°° P[Y(t) = i]dt = \ijT(i, Y). Consider the regenerative behavior of X defined by the times at which X hits state o from U. Let To and Tu be, respectively, the contributions of the subsets G and U to the mean time between regenerations. Let CG and Cjj be, respectively, the contributions of the subsets G and U to the mean down time between regenerations. Let [ïi/]ub be an upper bound for Tu and let [C[/]ub be an upper bound for Cu- Then, we have [22] the following lower and upper bounds for the steady-state unavailability UA: [UA]]h= Ca t (5J) J-G + [J-Ulub r,Mi CG + [Cu]ub ,_9v [UA\ub = r 1 . (5.2) J-G + L^C/Jub Let D be the subset of down states of X and let YG be the transient CTMC with state space G U {a} and initial state o, built from X by directing to a transitions from states in G to states in U. The quantities TG and CG can be computed from the mean 5.1 Extension to Group Repair 95 m) m) (a) Figure 5.1: State transition diagrams of the transient CTMCs Y' (top) and Y (bottom) of Lemma 5.1. time to absorption vector of YQ, (T(i,YG))ieG, as TG = J]r(i>yG), (5.3) ieG CG= Y. T^YG)- (5-4) ieGnD In the following we will denote by C, N and MC the bag of component classes, the number of components and the set of minimal cuts of the system, respectively. We will also denote by FC the set of distinct cardinalities of the failure bags of the system and by E{, i € FC the set of failure bags e, e 6 E with cardinality i. Let Uk be the subset of U including the states with k failed components. Let YUk be a transient CTMC with state space {u\,..., UN} U {a}, initial state u^ and state transition diagram like the one shown in Figure 5.1, b: there is a transition with rate #(1) from u\ to a, a transition with rate g(k), 2 < k < N from u¿ to u^-i, and, for each i € FC, i < N — k, a transition with rate /,• = YleeE ^ub(e) from Uk to Uk+i- The upper bound [T[/]ub is N [TuU = J2nkT(k), (5.5) fc=i where n- = YlT(h YG) \ijjk (5.6) ieG 96 5 Availability Bounds of Repairable Systems using FD is the probability that X with initial state o will enter U through subset Uk and T(k) is the mean time to absorption of YUk. An efficient procedure for computing T(k), k = 1,... , N is described in [22]. Next, we prove the correctness of [T[/]ub when repairs may involve an arbitrary number of components. Let N' < N and let Y' = {Y'(t); t > 0} be a transient CTMC with state space {ul5.. .,«#'} U {a}, initial probability distribution P[Y'(0) = «¡] = TT¡, 1 < i < N', J2i=i ""»' = 1, and the state transition diagram shown in Figure 5.1, a: there is a transition with rate g¡(k), 1 < k < N', 1 < i < k from uk to t/fc-i, a transition with rate gk(k), 1 < k < N' from uk to a, and a transition with rate //(&), i < N' - k, 1 < k < N' from uk to uk+i. Let Y = {Y(t); t > 0} be a transient CTMC with state space {«i,..., ujv} U {a}, initial probability distribution P[Y(0) = ut] = 7r¿, 1 < i < iV', P[y(0) = u,] = 0, N' < i < N, and same state transition diagram as YUk (the one shown in Figure 5.1, b). We have the following result. Lemma 5.1 Assume fj > 0, fj > /j(¿), 1 < * < N' and 0 < g(i) < £j=iffj(0> 1 < i < N'. Then, T{UUY) > T{UUY'), \<i<N'. Proof The proof is by induction on k. We will use the balance equation applied to a subset of states of a transient CTMC, which states that the initial probability of the subset plus the expected number of entries in it is equal to the final probability of the subset plus the expected number of exits of it. Note that the states ut-, 1 < i < N of Y and the states ÍÍ¿, 1 < i < N' oí Y' are transient and, therefore, have final probabilities equal to zero. Let Ty = r(u,-,y) and T¡ = T(UÍ,Y'). The balance equation applied to the subset of states ufL^i of Y' yields N' 1 = Er^,'(0, (5-7) t=i T, _ l-E^r¡g¡(i) g[(l) • (5-8) The balance equation applied to the subset of states U^u,- of Y yields 1 = ng{l), (5.9) n = jiy. (5.10) Using (5.8), T[ > 0, 1 < i < N', g(l) < g[(l) and (5.10), ri'-^ï)-^)=ri' 5.1 Extension to Group Repair 97 which proves the result for k = 1. Next, we assume r[ < r¿, 1 < i < k — 1, k > 2 and show r'k < Tfc. The balance equation applied to the subset of states U^T^u,- of Y' yields k-l N' t-1 k-l k-l N'-i E-.+E^ E sK^E^'w+E^EW- i=l i=k j—i—k+1 t=l t=l j—k—i Using 1 = E-Ji1 ÍT¿ + ES* ** and (5-7)> JV' k-l AT' i-l N' k-1 N'-i i-E^+^E^)+ IN £ ^w = i-E^i'w+E^ E #o. t = fc j = l t=fc+l j=t —fc+1 t = fc 1=1 j = k — i ri _ ¿2i=k ni ~ 2-/i=fc+i r¿ 2Jj=i-fc+i gj(0 + 2-/i=i r¿ 2Jj=fe-i /j(0 Zj=i9j(k) (5.H) rL = Similarly, applying the balance equation to the subset of states Ui=^U{ oí Y and using 1 = ZU *i + ££* *¿ and (5.9) gives 2^i=A: ^ + ¿JI=1 "«' L·j-k-i Jj /r ION T1 = iw • (5'12) Finally, using (5.11), r[ > 0, 1 < i < N\ the induction hypothesis, fj > 0, fj > ñ{i), l<i< N', N' < N, g{i) < £}=1 9j{i), 1 < * < W, and (5.12), v-^A" „ , -r^k-1 ^ -c^N'-i f ir^N' „ , v-^fc-1 ,. v-^A/-¿ f L·i=k ni + 2^t=i Ti L·j=k-i Jj < 2^i=fc "t T 2^i=i ri' L·j=k-i Jj 2J:=fc 7r« + Et=l T« Z/j=fc-i /?' r—i 7TT = Tk . U The remaining of the proof is based on the concept of exact aggregation for transient CTMCs. The following result, which defines the exact aggregation of a transient CTMC, is proved in [22, Theorem 3]. Theorem 5.1 (Exact aggregation for transient CTMCs) Let Y = {Y(t)\ t > 0}- be a transient CTMC with state space B U {a}, where all states in B are transient and a is an absorbing state, transition rates A,,j, i € B, j Ç. B U {a}, i ^ j, and initial probability distribution P[Y(0) = i] = TT,-, i G B, YlieB K¡ — 1- Assume r(i, Y) > 0 for ail i e B. Let B\ U Bi U • • • U Bn be a partition of B. Then, there exists a transient CTMC Y' = {Y'(t); t > 0} (the exact aggregation of Y) with state space {61,62,.. -,bn} U {a}, 98 5 Availability Bounds of Repairable Systems using FD transition rates A'^ = £ieBjk w* AiiB|, 1 < A, / < n, A; ^ /, and A'^ = £i6Bjk «>* A,-,«,, 1 < k < n, with u!¡ > 0, YlieB ui ~ 1» and initial probability distribution P[Y'(0) = h] = K = T,ieBk ni> such that Tih,Y') = T{Bk,Y). Let YJJ, s G U be the transient CTMC with state space Us U {a}, Us including the states reachable from s before exit from U, and initial state s, built from X by directing to a the transitions from states in Us to o. Let Tv be the mean time to absorption of Y{j. Noting that J^Í^G r(í> YG)^Í,J 1S the probability that X with initial state o will enter U through state j and grouping the contributions of the states j G U according to the subsets Uk they belong to, we can write Tu = EET(i'yG)A··^ = EET(i·yG)A,·lj2é jeUieG ieGjeu N i€G fc=l s€Uk Theorem 5.2 Tu < [Ï£/]ub> where [Tu)ub is given by (5.5) and (5.6). Proof Let s G Uk and consider the exact aggregation Y¿ of Y¿ under the partition N' Ufjji/f, where Uf is the subset of U¡ including the states reachable from s before exit from U and 1 < N's < N. The state transition diagram of Y¿ looks like the one depicted in part a of Figure 5.1, with N' replaced by N's. Using the notation of the figure we have, by Theorem 5.1, W = Eu',sA«.f«+>- i<i<Kj<N'.-i, ieu> í/í(0=Ewí,,Aw->' 1<líK 3<i, i€U> ieu- and T{U;,Yu) = T{ui,Yu'). (5.14) The transition rates Atit/(+j, i G Uf are associated with failure bags involving j components and, therefore, are upper bounded by fj. The repair rate of i G Uf, A,)0 + !Cj=i A«,£/i-¿i is l°wer bounded by #(/). Then, using u>j's > 0, i G £/* and ^¡^.u,-'5 = 1, 5.1 Extension to Group Repair 105 be the bounds C(k, d) available after phase m. We start by proving that the bounds are decreasing on d. The proof is by induction on m. For m = 0, C(°)(M) = C(k), which, trivially, are (non-strictly) decreasing on d. Assume that C^m'\k, d), 0 < m! < ra, m > 0 are decreasing on d and let k' be the value of k for which the bounds are updated in phase m + 1. We have (5.22) that C'{k',d) only depend on C^m">{k,d), 0 < m' < m, k ^ k'. Using the induction hypothesis, this implies [22, Proposition 3] that C'(k',d) are decreasing on d. Therefore, since, by hypothesis, C^m\k',d) are decreasing on d, C(m+1\k',d) = min{C'(k',d),C^m\k',d)} are decreasing on d. Next, we prove by induction on m that the bounds C(k, d) are increasing on k. Let (k, d), (k — 1, d) G 71. For m = 0, using Lemma 5.2, C<°>(fc,d) = C{k) > C{k - 1) = Cl°\k -l,d). Assume that C^m \k, d), 0 < m' < m, m > 0 are increasing on k. Let k' be the value of k for which the bounds are updated in phase m + 1. Let (k' — l,d) € 1Z, which implies k' > 1 and d > max{0, L - k'+ 1} > L - k'. We have (5.22) c'{k''d) = W)+c(m){k'~hd) + W) £ ^W)' \Ç~F C i<N-k' JM{<1,Í) A(k',d,i) = J2 fiAk',d)C{m'Hk' + i,d-j), mi<m. j=Jm(k',d,i) Using (5.20), (5.21) and recalling that C^m\k,d) are decreasing on d, JM{d,i)-i A(k',d,i) = J2 \.Fi¿-¡<*''d) - F¿.^-1 ^'d)]C(m,){k' + i,dj) j=Jm(k',d,i) + Fitd_jM{d,i}(k',d)C^(k' + i,d- JM(d,i)) JM(d,i) J2 Fiid^(k',d)[C^(k' + i,d-j)-C^'Hk' + i,d-j + l)] j=Jm(k',d,i)+l + Fi4_jm{k,4<i){k',d)C^{k' + i,d- Jm(k',d,*)) > 0. Therefore, C'(k',d) > C^m\k' — l,d). Using the induction hypothesis, this implies C(m+l>(k',d) = min{C'(k',d),C(m\k',d)} > C^m)(k'-l,d).U Theorem 5.3 Assume that Fiir(k,d), (k,d,i,r) € TV and Fi4{k,d), (k,d,i,d) 6 TV are decreasing on d. Then, Cfj < C(k,d), s Ç. Uk,d- 106 5 Availability Bounds of Repairable Systems using FD Proof Consider the algorithm the algorithm that improves the bounds C(k, d) split into phases as in the proof of Proposition 5.2. The proof is by induction on m. For m = 0, C(°)(M) = C(k), which [22, Theorem 6] upper bound Cfj, s G Uk,d- Assume that C(m">(k,d), 0 < m! < m, m > 0 upper bound Cfj, s € Uk4. Let k' be the value of k for which the bounds are updated in phase m + 1. According to (5.22), C(k',d) only depend on C^m^{k,d), 0 < m' < m, k ^ k'. Proposition 5.2 guarantees that C(m\k,d) are increasing on k and decreasing on d. Then, using the induction hypothesis and invoking Proposition 5.1, C'(k',d) upper bound Cfj, s G Uk',d- Finally, recalling that, by hypothesis, C^m\k\ d) upper bound Cfj, s € f4',<¿, we have that C(m+1î(k',d) = min{C'(A;',íí),C("l)(A;,,d)} upper bound Cfj, s € Uk>4. \J 5.2 Improved Failure Rate Bounding Structures The set of bounds i*i,r (fc, d), (k, d, i, r) 6 TV used in [22] was Fi,min{d,N-k-i}(k, d) = /,-, (k, d, i, mm{d, N - k - i}) £ W, (5.31) Fitr(k,d)= Y2 Aub(c), {k,d,i,r)€TZ',r <min{d,N-k-i}, eeEi (5.32) m n e ^ 0 for some m G MC Imp(e)<k+r Act(e)>d-r where Imp(e) — min |m — e|, mEMC mneyíí Act(e) = max Imfl el. In this section we derive bounds Fi,r(k,d), (k,d,i,r) 6 1Z', r < m'm{d,N — k — i} that are potentially better than the bounds given by (5.32). In the following we will call F{r(k,d) the bounds given by (5.32) and F-'r(k,d) the new bounds. The bounding method will use (5.31) and Fitr(k,d) = min{Fiir(k,d),F?r(k,d)}, (k,d,i,r) €lZ',r< min-{d,N-k- i}. (5.33) The bound [£M]ib does not depend on C(k, d) and, thus, that bound will be identical for the method described in [22] and the method proposed here. However, the bound 5.2 Improved Failure Rate Bounding Structures 107 [£^4]ub does depend on C(k, d) and that bound may be different for the method described in [22] and the method proposed here. We start proving that smaller bounds Fi<r(k,d) potentially give a smaller and thus tighter [CM]ub. Theorem 5.4 Smaller Fiir(k,d) bounds give a potentially smaller [UA]ub- Proof Combining (5.20), (5.21) and (5.22) we obtain C'(k, d) = ^0- + Ik>1 [ld>L.kC(k - 1, d) + Id<L-kC(k - 1, d + 1)] JM(d,i)-i + -7Ü E E {Fi^i^d)- F^-^d^Cik + ^dj) ieFC j-Jm(k,d,i) i<N-k + Fi4-jM(dti)(k, d)C{k + i,d- JM{d, i)) = ^ + Ik>i[ld>L-kC(k-l,d) + Id<L.kC(k-l,d+l)] + ^7M E Fi,d-Jm(k,d,i)(k>d)C(k + i'd- Jm{k,d,i)) 9(K) ieFC L i<N-k JM(d,i) + E Fi4-j{k,d)(C{k + i,d-j)-C(k + i,d-j + l)) j=Jm(k,d,i)+l But, since the bounds C(k,d) are decreasing on d by Proposition 5.2, it follows that smaller Fi,r(k,d) bounds give smaller C'(k,d) bounds, potentially smaller final C(k,d) bounds, a potentially smaller (5.16) [CV]ub and, since [£/^]ub is increasing on [Ct/]ub (5.2), a potentially smaller [tMjub- Ö In the following we derive the new bounds F-'r(k,d). The intuition on which the new bounds are based is the following. Consider a fault-tolerant system composed of 3 instances of component classes ct-, 1 < i < n, with n large. The failure bags of the model are c,[l], 1 < i < n. The system is failed if and only if all 3 instances of the same component class are failed. Thus, the minimal cuts are c,[3], 1 < i < n. Assume that we want to upper bound the transition rate to states with 2 failed components and failure distance < 1 from any state with 1 failed component and failure distance 2 and that the Aub(e), e € E are approximately equal. Using (5.32), all failure bags will be included in the summatory. This is, really, a consequence of the fact that F¡r(k,d) is obtained by adding up the Aub(e) for all failure bags e for which there exists some state with 108 5 Availability Bounds of Repairable Systems using FD k = 1 and d = 2 for which the failure of the components in e make the failure distance < 1. For the example and failure bag c,[l], such a state is the state x with F(x) = c,[l]. However, this is very pessimistic, since it is clear that no state with k = 1 and d = 2 exists in which all failure bags make the failure distance < 1. In fact, for the example, for a state x with F{x) = c,[l] only the failure bag e = c,[l] makes the failure distance < 1, and a significantly tighter upper bound (since n is large and the Aub(e), e G E are approximately equal) to the rate to states with 2 failed components and failure distance < 1 from any state with 1 failed component and failure distance 2 is maxeç£Àub(e). For other values of k and d, the situation is more complex, but the basic intuition still applies: we have to take into account the failure bags that may reduce simultaneously the failure distance. Let 5 be a bag (set). A collection T = {Si, S2,... , Sn} of subbags (subsets) of 5 is a Sperner collection on S if no subbag (subset) of T contains another. Let T be a collection of bags (sets). We will denote by Ni(T) the number of bags (sets) in T of cardinality i. Using Lubell's theorem [62], we will prove a sequence of two lemmas. The first lemma extends Lubell's theorem to bags; the second lemma is a direct consequence of the first one and will be used in future developments. Lemma 5.3 Let V be a Sperner collection on a bag S. Then h (?) - Proof Let T = {Si, S2,... , 5„}. Let D be the domain of S (set of different elements in 5). Consider the set S' obtained from S by replacing for each x Ç D the #(x,5) occurrences of x in S by distinct elements xi,X2,.-. ,%#(X,S)- For instance, if S = a[2]ò[3]c[l], S' would be {ai,a2i^i)^2i^3; ci}. Consider the collection T' of subsets of 5' obtained from F by replacing each subbag 5¿ of 5 by all different subsets S¡!,£,• 2, • • • that can be obtained by replacing the #{x, 5t) occurrences of a; in 5,- by distinct elements from xi,X2,... ,£#(x,s)- For instance, for S = a[2]6[3]c[l] and 5¿ = a[l]6[2] we would have S'itl = {01,61,62}, 5¿,2 = {01,61,63}, 5/i3 = {ai,62,63}, S¡A = {a2,6i,62}, S'ifi = {02,61,63}, and S'i6 = {02,62,63}. Since T is a Sperner collection on 5, T' is a Sperner collection on S'. In addition, iV,(r) < iV,-(r') and \S\ = \S'\. Then, we have ^ Nj(r) j£l NW) h Cf') - h ci'1) * 5.2 Improved Failure Rate Bounding Structures 109 But, using LubelPs Theorem [62], U (T) and the result follows. Q L·i f\s'\\ - Lemma 5.4 Let T be a Sperner collection on a bag S and let Mi > 0, i — 1,2,... , |5| Then ÍTNi(r)Mi< max f'^'W. Proof Let j be any index 1 < j < \S\ for which ('¿')M¿ = max^^i ('f')M,-. For 1 < i < \S\ we have (If )M¿ < ('f^Mj, i.e. (|S|) Mi < j^Mj. Then, using Lemma 5.3 ~ V 3 J 1<*<|5| V * / Let F,(r) be the set of failure bags of cardinality i such that the failure of the components in the failure bag makes the failure distance < r, i.e. the set of failure bags e € E{ with m'mmeMC \m — e\ < r. Let F be a subbag of C, let / be an integer > 0, and consider the collections of subbags of F, Alj(F), j = 1,2,..., \F\ defined recursively as follows. Al,p,(F) is {F} if F is included in some minimal cut of cardinality \F\ + I and 0 otherwise. For 1 < j < |F|, Alj(F) includes the subbags of F of cardinality j included in some minimal cut of cardinality j + I and not included in any subbag of U'pJj+1Ap(F). We have the following result. Theorem 5.5 Let e 6 Ei~Ei(r), i € FC and let F be a subbag ofC with m'mm€Mc \m — F\ = d. Then, for 0 < r < d, minmeMC \m - F — e\ < r if and only if minm€MC \m - s- e\ <r for some s € UI<J<\F\ Ud<i<r+i Al-{F). 110 5 Availability Bounds of Repairable Systems using FD Proof The sufficiency is obvious since the bags s in UKJ<|JT| L>d<i<r+i AlAF) are subbags of F and, therefore, minmeMC \m-F-e\ < minm£MC |m — s — e| < r. We prove next the necessity. If minmeMC \m — F — e\ <r, there exists m' G MC with \m' — F — e\ < r. Let n = \(m'-F)ne\ and j = \m'\ -r-n. Since e G Ei-Ei(r), n = \(m'-F)r\e\ < \e\ = i. Also, recall from Section 1.4 that given bags x, y, \x - y\ = \x\ - \x(~)y\. (5.34) Then, using (5.34) with x = m'-F and y = e, m\nmeMC \m — F\ = d and \m' — F—e\ < r, n = \(m' - F)De\ = \m' - F\ - \m' - F - e\ > dr. To summarize, d-r <n<i. (5.35) Regarding j, we have 1 <j < \m'r\F\ < \F\. (5.36) The left-hand side of the previous inequality follows using (5.34) with x = m' and y = e, and noting that, since e££¡- Ei(r), minm&MC |m — e| > r: j = \m'\ — r — n = \m' — e\ + |m'n e| - r - n > |m' — e| + \{m' — F) (~\e\ — r — n > r + |(m' — F)De| — r — n — r + n — r — n = 0 . The right-hand side of (5.36) can be shown using (5.34) twice, first with x = m' — F and y — e, and next with x = m' and y = F, and recalling that minmgA/C |m' — F — e| < r: j = |m'| - r - n = |m' - F - e| + |m' n F\ + \(m' - F) D e| - r - n < r+ \m'nF\ + \(m' - F)De\-r-n = r + \m' n F\ + n - r - n = \m' n F\ < \F\. Consider any subbag b of m' D F of cardinality j. Since (5.36) j > 1, such a subbag Im'I— i exists and, obviously, it is included in both m' and F. Then, either (1) b € A'¡ ' (F) or (2) b is (strictly) contained in some bag, s, of u'_-+1/lp (F). Note that (5.35), d<r + n<r + i. Then, since \m'\ — j = r + n, d<\m'\-j <r + i. (5.37) In case 1, using (5.34) twice, first with x = m' — b and y = e and next with x = w! and y = ò, and recalling that ò C m', 6 C F, and |m'| = j + r + n, min \mb- e\ < \m' - b- e\ = \m'\ - |m'nò| - \{rri - 6)f"ïe| mÇ.MC = \m'\ - \b\ - \(m' - b) n e| < \m'\ - \b\ - |(m' - F) n e| = j + r + n— j — n = r. (5.38) 5.2 Improved Failure Rate Bounding Structures 111 Therefore (5.36), (5.37), there exists s = 6 G öi<j<\F\Ud<i<r+iAj(F) for which minmgA/c |ro - s - e| < r. In case 2, there exists p,j + l<p<\F\ and (5.37), s G Al™'hJ(F) = Ud</<r+¡.Ap(F) that strictly includes ò. But, since 6 C s and (5.38), minmGMC |m—s—e| < minmÇA/c |m — 6 — e| < r. Therefore, (5.36), (5.37), there exists s G VJ+KP<\F\ U<¿</<r+»' Ap(F) G Ui^xiKi Ud<;<r+t- Alj(F) for which minm6Airc \m - s - e| < r. • Denote by MCC the set of minimal cuts of cardinality c and let A(c, n, i, r) max ^.,n < T* Aub(e) > if MCC ± 0 and 1 < n < c ¿asil . e€V'(í ,< J " ~(5-39) cv. »,i»l v minm/6AiC |m'-6-e|<r ' v y 0 otherwise For MCC T¿ 0 and 1 < n < c, A(c, n, ¿, r) is the maximum sum of Aub(e) corresponding to the failure bags e G £¡ - F,(r) that assuming n components included in some minimal cut of cardinality c failed make the failure distance after e smaller than or equal to r. Note that, for r > L, Ei(r) = E¡, and, therefore, only A(c, n, ¿, r), r < L have to be computed. We have the following result. Theorem 5.6 Let E¡(r), i G FC be the set of failure bags e G Ei - F,(r) for which minmçMC \m — s — e\ < r. Let F be a subbag of C with mmmeMC \m — F\ = d. Then, E *ub(e)< ¿ ^M ,- }MJ + r + l,j,i,r). Proof Using Theorem 5.5 Ef(r)= (J U U ^(r). l<j<|F|¿-r</<«s6i4r+í(F) Therefore, \F\ i E ^)-<EE E E A^)- çgBf (r) J=l '=«*-r ,6yi;+'(F) «eE?(r) Assume MCj+r+¡ # 0. By definition, J2eçE?(r) Aub(e), s G Ar-+l(F) is upper bounded by A(j + r + l,j,i,r). In the case MCi+r+/ = 0, ^+'(F) = 0, A(j + r + /,j, i,r) = 0 and we 112 5 Availability Bounds of Repairable Systems using FD can write £a6i4r+i(F) £eeE?(r) Aub = 0 < J2seAr+'(F) A(J + r + lJ,¿»r) = °- Then \F\ i Y Kb(e)<J2J2 Y A(i + r + /,i,i,r) eeEF(r) ¿=1 l=d-r a€Ar+'(F) = EE |Af'(F)|A(j + r+ /,;,*>) = £ £|Af'(F)|A(j + r + /,j,i,r). j=l l-=d—r l—d—r j—1 But the collection {s : s Ç /l^ (F), 1 < j < \F\} is a Sperner collection on F and, since thesubbagssG Aj+'(F) have cardinality j, using Lemma 5.4, Y Aub(e)< ¿ max (|F|)A(j + r + /,j,¿,r).n We are now in position to derive the new bounds F"r(k, d). Let x € Uk,d, (k, d) Ç.1Z and let (k, d, ¿, r) € 7£', r < min{d, N - k — i}. Failure transitions from x associated with failure bags e € Ei(r) lead to states with failure distance minmeMC I'm — F(x) — e\ < minmeMC \fn — e\ < r. The failure transitions associated with failure bags in E¡ — E{(r) that lead to states with failure distance < r are those associated with failure bags in E{ (r). Then, we have K,urdl=0uk+i¡d, < Y Aub(e)+ ]T Aub(c), e€Ei(r) e£E?{x\r) and since |F(a:)| = k, using Theorem 5.6, A^.ud'=o^+.,d' - Y Aub(e) + Y ima<xfc ( j ) AÜ + r + '' •?' *» r) = ^'ri*»d) • ee£.(r) /=á-r ~J- U/ (5.40) It is immediate to see that F¡r(k,d) and F[[r{k,d), (k,d,i,r) € W are (5.32), (5.40) decreasing on d and, thereby, Fi<r(k,d) — mm{F{r(k,d),F"r(k,d)}, (k,d,i,r) £ TZ' are decreasing on d. Also, for (k,d,i,d) G 7S', we have (5.31) Fitd(k,d) = £e€£. Aub(e), independent on d and, therefore, Fi¿(k, d), (k,d,i,d) € 72' are (non-strictly) decreasing on d. Then, the new bounds Fi¡r(k,d) satisfy the conditions required by Theorem 5.3. Computation of A(c, n, i, r) using (5.39) may introduce an unaffordable overhead especially when the number of minimal cuts is large. First, all subbags of cardinality n of each minimal cut must be generated and, for each such subbag b and for each e G E{ — Ei(r) T¿ 0, all minimal cuts have to be visited to know whether m'mmiçMC \m'-b-e\ < r. Note that if we regard minmiç\fc \m' — b\ as the failure distance from a state s with 5.2 Improved Failure Rate Bounding Structures 113 F(s) = b, then minmi€Mc \mr — b — e\ can be viewed as the failure distance from a state s' reached from s in a single transition associated with failure bag e. Therefore, computation of minm'ejvfc \m' — b — e| can be done efficiently using the algorithms compute„d() and compute-alLad() reviewed in Section 2.2. Besides the previous comment, the main idea to improve the efficiency of the expensive trivial procedure to compute A(c, n, i, r) is the observation that, typically, many minimal cuts will share the same subbag, especially when |ò| is small, and that computation of minm<ejv/<7 \m' — b — e\ < r should not be repeated. Recall from Section 2.2 that the control parameter R of algorithm compute„d( ) stands for the maximum cardinality of selectors (bags included in some minimal cut) that are stored. Then, we proceed as follows. Let R\ maxm£MC \m\ > R' > R- First, we generate and store all distinct subbags of cardinality up to R' included in some minimal cut. Let B be the set of such subbags. For each b 6 B, we also generate and store the list, / (6), of distinct cardinalities of minimal cuts including b. We initialize all A(c, n, i, r) to 0. Then, for each b G B, we compute S(b) = mmm>€MC lTO' ~ b\ invoking computed (b, S (b)), compute Vb{e) = minm/eMc|w' — b — e\, e £ E invoking compute-alLad(5(b),b,i>b{e)), and for each c 6 1(b), set (5.39) A(c, |6|, i, r) = max{A(c, |6|, i, r),J2eçA ^ub(e)}i A = {e e E{ — Ei(r) : v\¡(e) < r}. The remaining updates associated with subbags b ^ 1Z are done generating and processing for each m £ MC all subbags b £ m, \b\ > R'. Subbags b € B with |6| > R are freed once the coefficients A(c, n, i, r) are computed (compute.d( ) requires the knowledge of all subbags b, \b\ < R). Selection of an appropriate value for R' involves a tradeoff between memory consumption and CPU time. As R' gets higher, the algorithm to compute the A(c, n,i,r) coefficients becomes faster but the memory requirements increase. Memory requirements are only significant when \MC\ is large. We will illustrate the tradeoff using an example with 87,031 minimal cuts. We finish this section by showing how to reduce the effort required to compute the set of bounds F{ir(k, d), r < min{ci, N - k - i} once F¡r(k, d) and A(c, n, i, r) have been computed. To that end, we need the following result. Proposition 5.3 The set of bounds F"r(k,d), r < min{d,N - k - i), (k,d,i,d) € TV, . are increasing on k. Proof Let (fc, d, i, r'), (k + 1, d, i, r') € 11', r' < min{d, N - (k + 1) - i). Then, using 114 5 Availability Bounds of Repairable Systems using FD (5.40) and noting that r' < min{d, N — k — i}, *£.,(*+ l,rf) = Y] Aub(e)+ ¿ max/max fÄ + 1)A(i+r' + /,i,z,r'), A(k+l + r' + l,k + l,i,r')} = J2 Aub(e)+ Y] max{ max -—— :( . )A{j + r' + l,j,i,r'), A(k+l + r' + l,k + l,i,r')j > ^2 Aub(e)+ ^2 maxj max I .jA(j + r' + lJ,i,r% A(k+l + r' + l,k + l,i,r')} > £ A"b(e)+ ¿ max:(k)A(j+ r'+ l,j,i,r') = F¡'y(k,d) .Q eeE,(r>) l=d-r> -'- U/ Let k > maxee£Imp(e) and assume F-'r(k,d) > F!r(k,d) for all (tí,¿, r). It is immediate to see (5.32) that F¡r(k,d) = F{r(k',d), k' > k. Then, for k' > k we have, using Proposition 5.3, *£(*', ci) > F¡'¡r(k, d) > F¡,(k, d) = Fitr(k', d). Therefore, for k' > k we can stop computing F"r(k', d) and set i%)f.(A:', eQ = F{r(k', d). 5.3 State Space Exploration Algorithm In the method proposed in this chapter the subset G is enlarged incrementally until the relative unavailability band, rb = ([UA]^ - \UA\\b)/[UA]\\„ is smaller than or equal to the desired one, ròr, using the state space exploration algorithm CONT-TG-W proposed in [20]. In this section we review that algorithm. The algorithm uses approximate estimates for the unavailability band, [(Z4]ub — [(7i4]ib, and performs the expansions by waves. A wave includes a set of consecutive additions of states into G without computing (r(s, Yo))seG- Let G* and r* = (r(s, YG»))3qG' 5.4 Analysis and Comparison 121 Figure 5.7: Block diagram of the second example. cessing units, one processing unit for the processing clusters with one unfailed processing unit, and the components of either network .4 or B, with priority given to network A, required to build one of the operational configurations of the networks described next. The network configuration that is tried first is a direct ring including all nodes and direct links. The second configuration that 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 links between nodes i and i + 1 mod 10. 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 ± 1 mod 10. 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 ac- • tive. Active processing units, active nodes and active links fail with rates 4.6 X 10-4 h-1, 2.3 x 10~4 h-1 and 1.1 x 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 repair person 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 122 5 Availability Bounds of Repairable Systems using FD Table 5.2: Memory overhead in MB due to storing all distinct subbags of cardinality > R and < R' included in some minimal cut and CPU time in seconds required to compute the A(c, n, i, r) coefficients for the second example as a function of R' . R' overhead (MB) CPU time (s) 2 0 3,611 3 3.0 1,906 4 10 1,216 5 11 1,197 6 11 1,197 when the system has failed. For this example L = 3 and the structure function has 87,031 minimal cuts, 6 of cardinality 3, 75,625 of cardinality 4, 11,000 of cardinality 5, and 400 of cardinality 6. In this example the number of minimal cuts, and, therefore, the number of subbags that would have to be processed to compute the A(c, n, ¿, r) coefficients using the trivial procedure is quite large. We start by illustrating the tradeoff involved by the selection of an appropriate value for R'. In Table 5.2 we show, for R' = 2, 3, 4, 5 and 6 the memory overhead in MB due to storing all distinct subbags of cardinality > R and < R' included in some minimal cut, and the CPU time in seconds required to compute the A(c, n, i, r) coefficients. Note that, as it was anticipated in Section 5.2, the larger R' the more faster and memory consuming the computation of the coefficients. Note also that beyond R' = 4 no significant improvement is achieved. This is mainly due to the fact that subbags with small cardinalities tend to be shared by several minimal cuts much more often than subbags with larger cardinalities do. Thus, for instance, among the 420,506 subbags of cardinality 3, only 18,946 are really distinct, while 12,600 subbags of cardinality 5 out of 13,400 are distinct. In Figure 5.8 we give the relative unavailability band as a function of the number of states in the generated subset G. The results have been obtained with R' — 6. For this example, the reduction in the size of G achieved by the proposed method with regard to the method described in [70] is still appreciable. However, that reduction is more modest when the proposed method is compared with the method described in [22]. We have analyzed the bounds F{r(k,d) and F-'r(k,d) and found that because of the particular structure of the minimal cuts of the example, the bounds F"r(k,d) are not much smaller than the bounds F{r(k,d) and, consequently, the reduction in the C(k,d) bounds is more modest than it was for the previous example. The relative unavailability band as a function of the memory consumption in MB is given in Figure 5.9. Note, again, that the method described in this chapter and the one proposed in [22] compare the same in 5.4 Analysis and Comparison 123 0.1 C XS X> .2 > C 3 « 1> 0.01 ^ , ^ ! I E3-. ft "a... Vi- "Q- ' E. '"B- f\ 9 + \ \ \ \. proposed -©— > -H [22] --t-- \ \+ [70] •B-- % * **v +\ 1—_^s i*i 1 "B... u - • i 30000 60000 90000 states Figure 5.8: Relative unavailability band for the second example as a function of the size of the generated subset. 0.1 -a c X) Xi '3 > c 3 <D ^> "jU 0.01 - 20 , ' ' • ' - proposed -©— [22] -+- [70] -B- , —-c¡-, B- 1 , , TV till "B- 9+ -s.. U -Q. < h Q B.. . ""B.. % Q • > * V 4* V \ + A t \ + > -t; \ ^ >, X % \ <& He <& '-K. ^\"^"----. . ^^^~-_ " ~+ "-"---n' 40 60 80 100 MB Figure 5.9: Relative unavailability band for the second example as a function of the memory consumption in MB. 124 5 Availability Bounds of Repairable Systems using FD terms of memory consumption as they did in terms of size of the generated subset, while the improvement in terms of memory consumption achieved by the proposed method with respect to the one of [70] is appreciably smaller than it was in terms of size of G, especially for medium and large values of the relative unavailability band. For this example the reduction in the improvement is due not only to the different size of the lists of contributions both methods have to bookkeep for each state in the frontier of G, but also to the amount of memory required to store the set of minimal cuts and related structures for the computation of the failure distances. For this example, \MC\ = 87,031 and its storage takes about 35 MB. 5.5 Conclusions In this chapter we have developed a bounding method for the steady-state unavailability that exploits the failure distance concept and requires the knowledge of the minimal cuts of the system. From a memory consumption point of view, the method seems to be better than the method described in [70], which is not based on the failure distance concept. The proposed method may also outperform significantly a previous method [22] based on the failure distance concept. It is difficult, however, to predict the improvement in advance since it depends on the sparseness of the down states in the frontier of G and the structure of the minimal cuts of the fault tree of the system. The method suffers from a memory overhead due to holding the minimal cuts and subbags required for the computation of failure distances and A(c, n, i, r) coefficients, which, as it has been shown by means of the second example analyzed in this chapter, can be significant if the number of minimal cuts is large. At this point one might ask whether it would not be possible to devise another bounding method for the steady-state unavailability based on lower bounds for failure distances, similarly as we did for the first method presented in this dissertation. The next chapter is devoted to give an affirmative answer to that question. Chapter 6 Availability Bounds of Repairable Systems using FD Bounds In this chapter we will develop a method to compute bounds for the steady-state unavailability, UA, based on the lower bounds for failure distances developed in Section 4.2. The motivation is similar to the one that brought us to develop the method to compute bounds for the unreliability described in Chapter 4: we want to have a bounding method that does not rely on solving a hard problem (the determination of the minimal cuts) and, secondly, it is desirable to be able to bound UA without incurring the memory overhead due to storing minimal cuts and related structures, especially when the number of minimal cuts is large. The first section of this chapter will be devoted to describe the method and prove its correctness. Next, we will derive suitable failure rate bounding structures based on lower bounds for failure distances. Finally, we will analyze the method by means of several examples and compare it with the method described in the previous chapter and the methods described in [22, 70]. 6.1 Bounding Method Let X = {X(t); t > 0} be the finite CTMC modeling the system and let fi be its state • space. The method computes bounds for UA using detailed knowledge of X in the generated subset, G, and bounding the behavior of X in U = Í2 - G. The method uses the state cloning technique proposed in [70]. The technique consists in modifying X by adding to U clones of the states in G with more than F failed components, accounting for the visits to the corresponding states of G after X exits G and before the number of 126 6 Availability Bounds of Repairable Systems usingJD Bounds Figure 6.1: State transition diagram of the CTMC X after applying the state cloning technique with F = 0. failed components has fallen below F + 1. Note that the application of the state cloning technique does not modify the steady-state unavailability UA. We apply the technique with F = 0 in order to ease state space exploration. The modified X has the structure depicted in Figure 6.1, where Uk includes all states in U with exactly k failed components and N' < N, being N the number of components of the system. In the following, X will denote the modified X. The notation we will use throughout this chapter is essentially the same we used in Chapter 5. Thus, we will denote by XStS>, s,s' € Í2, the transition rate from state s to state s', by A„ = Yïs'çnK,*', s € O, the output rate of s, and by XStc = £<'<=<? ^5,s'> aïs' s6fi,Ccfi, 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 U {a}, where all states in B are transient and a is an absorbing state, and has defined initial probability distribution with P[Y(0) G B] = 1. T(S,Y),S £ B, will denote the mean time spent by y in 5 before absorption, and r(C,Y) = £iecr(s>^)> C C B, will denote the mean time to absorption in subset C. Finally, recall that r(s,Y)Xs<s> is the expected number of times that a transition from s to s', s 6 B, s' Ç B U {a}, is followed. Consider the regenerative behavior of X, taking as regeneration points the times at which X enters o from U. Let TG and Tv be the contributions of G and U to the mean time between regenerations of X, and let CG and Cv be the respective contributions to the mean down time. From regeneration process theory (see, for instance [31]), we have: UA=CG + CU TG + TU upper bounds [2V]ub and [Q/]ub for, respectively, Tv and Cv are known. 6.1 Bounding Method 127 Then [22, Theorem 2] [UA]lb= °? , • (6.1) -LG + L-tt/Jub rrnl _CG + [Cu]ub ip.0s [UA\uh = , (6.2) -ÍG + [C[/Jub are, respectively, a lower and an upper bound for UA. The quantities TQ and CG are computed as in Section 5.1 from the transient CTMC YG as TG = 5>(S,YG), (6.3) seG CG= Y, T(s,yG), (6.4) seGnü where D is the subset of down states of X. In the following, we will denote by FC and RC the set of distinct cardinalities of, respectively, failure and repair bags of the system, and by E{ the set of failure bags with cardinality i. The bound [2V]ub and, therefore , the lower bound [£Ot]ib are the same as those of the method developed in Chapter 5. Since the transient CTMC YUk introduced in Section 5.1 to compute [ÍL4]ib will be referred to later on in this section, let us recall its definition. The chain has state space {ui,..., u¡y} U {a}, initial state Uk and state transition diagram like the one shown in Figure 5.1, b: there is a transition with rate g(l) from uy to a, a transition with rate g(k), 2 < k < N from Uk to Uk-i, and, for each i G FC, i < N - k, a transition with rate /,• = 2ee£ ^ub(e) from Uk to Ufc+¿. The upper bound [C[/]Ub is based on the lower bounds for failure distances derived in Section 4.2. Let s G Çî and let d(s) be a lower bound for the failure distance from s, d(s). Since theorems 4.2 and 4.4 we have: 0 < d{s) < d{s), (6.5) d{s) = 0 if and only if s G D, (6.6) d(s) - \F(s') - F{s)\ < d{s') < d(s), F{s)cF(s'). (6.7) Let s' G ÍÍ be a state reached from s in a single-step transition associated with failure bag e G E and let s" G O, be a state reached from s in a repair transition involving i components. Then, (6.7) implies d(s) - \e\ < d{s') < d{s), (6.8) 128 6 Availability Bounds of Repairable Systems using FD Bounds and d{s) < d(s") < d{s) + i. (6.9) Let Uk,d be the subset of U including all states s with k failed components and d(s) = d, and let L — d(o). The set TÍ of (k, d) pairs for which Uk,d might be ^ 0 is given by the constraints l<k<N, max{0, L - k} < d < min{Z, N - k) . The constraints on k are obvious. The constraints L — k < d and d < L follow from (6.7) and the definition of L; 0 < d follows from (6.5). Finally, d < N - k follows from (6.7) and the fact that the structure function of the system is coherent by taking s' the state with all components failed and noting that d(s') < d(s') = 0 and, therefore, d(s') = 0. Let Yy, s € U be the transient CTMC with state space Us U {a}, (Is including the states reachable from s before exit from U, and initial state s, built from X by directing to a the transitions from states in U to o. Let Cy be the mean down time to absorption of Yy. Recalling that J2s'eGT(s''^G)^s',s; s £ U, is the probability that X enters U through s, we have cu = £ J2r(s'>yo)A.»,.c&=E E E r(s''y«)x°'<°cu• s'eGset/ s'^G(k4)&ñseüKd (6.10) Let C(k,d) be upper bounds for Cy, s G Uk,d, and ÏM = Er(a'yG)A..oM- (6-U) Let [Ct/]ub= £ ñk,dC(k,d). (6.12) We have the following result. Theorem 6.1 Assume C{¡ < C{k,d), s £ Uk,d, Then, Cu < [Cu]ub- 6.1 Bounding Method 129 Proof Using (6.10), the fact that Cfj < C{k,d), s G Ûk4, (6.11), and (6.12): Cu=J2 Y, T, r(s',YG)Xsl,sCsu<Y^ E E T(s',YG)\s,,sC(k,d) s'eG (k,d)eñ seük¡d ^'GG (k,d)eñ seükid = E E T(s>,YG)\slAdc(k,d)= E E^^-Ä^M) «'eG(fc,ti)eÄ (k,d)eñs'eG = E ^M^.d) = [C[/]ub.n (k,d)£Ü Let L be the exact failure distance from state o, i.e. L = d(o), and let N C(fc) = E r(«¿. I™')- (6.13) ¿=L Theorem 6.2 C£ < C(fc), s G £4- Proof Since (6.5), Z < L. Using that [22, Theorem 6] Cfj < Yl^=LT(uùYUk) and (6.13): JV N cb < Er(u«-yUfc) ^ ET(Ui'yttfc) = Ô(*)-D i=L t=L The bounds C(&, d) are computed using an iterative procedure that starts with C(k,d) = C(k) and improves the bounds using potentially better bounds C'(k,d) until no significant improvement is achieved. Let s G Uk,d and consider a transition from s to s' G U associated with failure bag e G Ei, i G FC. Clearly, s' G Uk+i,d> for suitable <¿' values. Imposing (k + i, d') G TZ yields i < iV - Jfc and d' < min{Z, N -k-i}. Moreover (6.5), (6.8), max{0, d - i} < d' < d. Therefore, the only feasible destination subsets Uk+i,d' , i G FC, are those satisfying i < N - k and (recall that d < L) max{0,d - i) < d' < min{d, JV - k - i}. Let ñ'= {(k,d,i,d')\ (k,d) eÜ,ie FC, max{0,d-¿} < d' < min{<¿, N-k-i}}. Assume that upper bounds Fiir(k,d), (k,d,i,r) G TZ' for Y?d'=o^sü • »' s ^ ^fc-d' are available and let ~ \Fi}d-j(k,d)-Fi4-j-1{k,d), Jm(k,d,i) < j < JM{d,i) fi,j(k,d)= i [Fitd-j{k,d), j = Jni{d,i), ^6<14^ 130 6 Availability Bounds of Repairable Systems using FD Bounds where Jm(k,d,i) = max{0,ft + d + i - N} and JM(d, i) = min{z, d}. The upper bounds C'(k, d) are computed using C'(k,d) = ^ + Ik>1[ld>z_kC(k-l,d) + Id^L_kC(k-l,d+l) JM(d,i) ^ ^ + ¡?ü J2 J2 /¿¿(M^ + ^-J), (6.15) i<7v — k where Ic is the indicator function returning 1 if c is true and 0 otherwise. The algorithm to compute the C(k, d) bounds is exactly the same as the one given in Figure 5.2 replacing L, TZ, C(k), C{k,d), and C'{k,d) by, respectively, L, % C{k), C{k,d), and C'{k,d). Next, we prove C^ < C(k, d),s G Uk,d, (k, d) £TZ provided that Fi,r(k, d), (A;, e?, i, r) G TZ', and Fti(fc, cQ, (k,d,i,d) G TZ' are decreasing on d. The proof consists of a sequence of two lemmas, three propositions and a theorem. We start with two technical results. The first one has been adapted from [22, Proposition 2] and is included here for the sake of completeness. The second result is very similar to Lemma 5.2. Lemma 6.1 Assume that C(k,d), (k,d) G TZ, Fi¡r(k,d), (k,d,i,r) G TZ' and Fi¿{k,d), (k, d, i, d) G TZ' are decreasing on d. Then, JM(<Í,Í) _ Ä{k,d,i)= J^ fitj(k,d)C{k + i,d-j), ¿G FC,i<N -k, j=Jm(k,d,i) is decreasing on d. Proof Let (k,d), (k,d+ 1) G TZ. Using (6.14) and making the index change r = d — j, JM(d,i)-i Ä{k, d, i) = J2 iFi,d-Ak> d) - Fij-j-í (k, d)]C{k + i,dj) j-Jm(k,d,i) + Fi4-JM(d,i){k, d)C{k + i,d- JM(d, i)) £ FiÀ.j(k,d)[C(k + i,d-j)-C(k + i,d-j + l)} j=Jm(k,d,i) + l + Fi,d-Jm(k¿,i){k,d)C(k + i,d- Jm(k,d, i)) d-Jm(k,d,i)-l __ £ Fi,r (k, d) [C(k + i, r) - C(k + t, r + 1)] r=d-JM(d,i) + FiÀ-Jm(k,d,i)(k> dÏC{k + i,d- Jm{k, d, i)). 6.3 Analysis 137 0.1 C es X> Xi eu 1 > ca c 3 Sí 0.01 0.001 i v ? * 3> X l· R «\ -fe \ '4ù \ Aá V \B \ \Q \ + 0 * i_i i % X X k * k \ N 1 X. X X. • i x 1 1 1 ' "l proposed -o— Chapter 5 --*-— [22] "S-- [70] x _ • "x x """"•X"-. " x....... • ' ' 10000 20000 30000 40000 50000 60000 70000 states Figure 6.3: Relative unavailability band as a function of the number of states in G for the first example. 0.1 c XI XI .3 > c 3 o _> js 13 0.01 0.001 :<f m ' ' " \ Î* •o I k <> 41 k ' <> $ X <> 43 k ;: i \ V * | í k. - ^ $ X. \ è \ \ f? X. &i \s \h \ö i \\ i i ""X... i. i -i i • i —i • proposed -e— Chapter 5 -+—- [22] --a-- [70] x - • "X "x "~-x x '""X I I I I . Ï :-i— 10 15 20 25 30 35 40 45 50 MB Figure 6.4: Relative unavailability band as a function of memory consumption for the first example. 138 6 Availability Bounds of Repairable Systems using FD Bounds 30000 60000 90000 states Figure 6.5: Relative unavailability band as a function of the number of states in G for the second example. memory. As it can be seen in Figure 6.4, this is approximately the difference in terms of memory consumption between the proposed method and the methods described in [22] and Chapter 5 for a relative band equal to 0.1. The smaller the relative band, however, the larger the generated subset and, thereby, the memory consumption due to storing state descriptions and list of contributions becomes relatively more important than the overhead introduced by storing the minimal cuts and related data structures. This explains why the difference in terms of memory consumption between the proposed method and the methods described in [22] and Chapter 5 decreases as the target band gets smaller and, eventually, the proposed method becomes more memory consuming. In figures 6.5 and 6.6 we show the relative unavailability band for the second example in terms of, respectively, size of the generated subset and memory consumption. The same comments we did for the previous example apply here: the proposed method outperforms the method described in [70] and, in terms of memory consumption, it is more efficient than the methods described in [22] and Chapter 5 for large to moderate relative unavailability bands. 6.4 Conclusions 139 0.1 •M > ni c D 0.01 Y ' T - proposed Chapter 5 [22] [70] -e— -H "B—- -X-— *h *T- 1 1 ;n X >Ù '-X •HD X 't? * ft + S \ G) ^ Q * ip + Q t. ; Q TÎ^^O X, Q^6^^ v, """-sTr 1 1 1 "X "~--. • - ' • " : "•'E 20 40 60 80 100 MB Figure 6.6: Relative unavailability band as a function of memory consumption for the second example. 6.4 Conclusions In this chapter we have developed a bounding method for the steady-state unavailability that is based on lower bounds for failure distances and, therefore, does not require the knowledge of the minimal cuts of the system. The method seems to be better than the method described in [70], which is not based in the failure distance concept. Regarding the methods described in [22] and Chapter 5, which require to know and hold in memory the set of minimal cuts of the system, the proposed method can outperform both of them for moderate values of the relative unavailability band when the number of minimal cuts is large. 140 6 Availability Bounds of Repairable Systems using FD Bounds Chapter 7 Conclusions and Future Work The goal of the dissertation was the development of failure distance based bounding methods for two dependability measures/scenarios: 1) the unreliability at time t, ur(£), for non-repairable fault-tolerant systems, and 2) the steady-state unavailability, UA, for repairable fault-tolerant systems. The goal has been achieved for a quite wide class of models and the required high-level knowledge about the model is reasonable and modest. We have developed four methods: two using failure distances, and two using lower bounds for failure distances that can be inexpensively computed on the fault tree of the system. For the same number of generated states, the first two give, in general, tighter bounds, but those methods have the potential limitation that computing failure distances is an NP-hard problem. The algorithms we have used to compute the failure distances assume the knowledge of the minimal cuts of the fault tree. The algorithms seem to be very efficient from a time point of view even when the number of minimal cuts is large (tens of thousands). However, computation of the minimal cuts in a reasonable amount of time may be impossible and, then, the methods could not be used. Also, the number of minimal cuts can be very large and, in that case, the memory overhead associated with them may be important, making the other bounding methods more efficient from a memory usage point of view. As the examples we have presented show, all four methods can outperform significantly previously available methods and extend significantly the complexity of the fault-tolerant systems for which tight bounds for the considered dependability measures can be computed. In that regard, we want to note that the method described in Chapter 5 has obtained very tight bounds for a fault-tolerant system with 372 components using 100 MB of memory. Workstations with 1 GB of memory are common today and, we estimate, with such a workstation tight bounds should be attainable for fault-tolerant systems having of the order of 1,000 components. Fault-tolerant 142 7 Conclusions and Future Work interconnection networks [36] are fault-tolerant systems having that complexity. Once solving the difficulty of building a fault tree for those systems, their dependability could be analyzed precisely using the methods described in the dissertation. Much research work related with the dissertation remains and the author wants to undertake it in the future. First, it is tempting to develop bounding methods for ur(t) for non-repairable fault-tolerant systems using structures Fi<r(k, d) similar to those used by the proposed bounding methods for UA. Secondly, efficient state space exploration algorithms for those methods could be developed. Finally, other dependability measures/scenarios could be considered such as ur(t) for repairable systems, the point unavailability and the expected interval unavailability for repairable systems, and the distribution of the interval availability for repairable systems. The latter would have special interest, since available numerical methods for computing that measure [23, 84, 85, 94] are expensive and keeping the size of the generated state space as small as possible is an important issue. Finally, all these methods should be offered in a tool with an as flexible as possible modeling language encompassing the class of models for which the bounding methods have been developed. Bibliography [1] J. A. Abraham, "An improved algorithm for network reliability," IEEE Trans, on Reliability, vol. R-28, April 1979, pp. 58-61. [2] M. Abramovici, J. J. Kulikowski, P. R. Menon, and D. T. Miller, "SMART and FAST: Test Generation for VLSI Scan-Design Circuits,", IEEE Design and Test of Computers, vol. 3, no. 4, August 1986, pp. 43-54. [3] K. K. Aggarwal, K. B. Misra, and J. S. Gupta, "A fast algorithm for realiability evaluation," IEEE Trans, on Reliability, vol. R-24, April 1975, pp. 83-85. [4] Ch. Alexopoulos and B. C. Shultes, "The Balanced Likelihood Ratio Method for Estimating Performance Measures of Highly Reliable Systems," in Proc. Winter Simulation Conference, Piscataway, New Jersey, 1998. [5] Ch. Alexopoulos and B. C. Shultes, "Estimating Reliability Measures for Highly-reliable Markovian Systems Using Balanced Likelihood Ratios," Technical Report, Georgia Institute of Technology, March 1999. [6] S. V. Amari, J. B. Dugan and R. B. Misra, "A separable method for incorporating imperfect fault-coverage into combinatorial models," IEEE Trans, on Reliability, vol. 48, no. 3, September 1999, pp. 267-274. [7] J. Arlat, M. Agüera, L. Amat, Y. Crouzet, J. C. Fabre, J. C. Laprie, E. Martins, and D. Powell, "Fault Injection for Dependability Validation—A Methodology and Some Applications," IEEE Trans, on Software Engineering, vol. 16, no. 2, pp. 166-182, February 1990. [8] R.E. Barlow and F. Proschan, Statistical Theory of Reliability and Life Testing. Probability Models, McArdle Press, Silver Spring, 1981. [9] J. H. Barton, E. W. Czeck, Z. Z. Segall, and D. P. Siewiorek, "Fault Injection Experiments Using FIAT," IEEE Trans, on Computers, vol. 39, no. 4, pp. 575-582, April 1990. [10] N. N. Bengiamin, B. A. Bowen, and K. F. Schenk, "An Efficient Algorithm for Reducing the Complexity of Computation in Fault Tree Analysis," IEEE Trans, on Nuclear Science, vol. NS-23, no. 5, October 1976, pp. 1442-1446. 144 BIBLIOGRAPHY [11] R. G. Bennets, "On the analysis of fault trees," IEEE Trans, on Reliability, vol. R-24, August 1975, pp. 175-185. [12] C. Béounes, M. Agüera, J. Arlat, S. Bachman, C. Bourdeau, J. E. Doucet, K. Kanoun, J. C. Laprie, S. Metge. J. Moreira de Souza, D. Powell, and P. Spiesser, "SURF-2: A Program for Dependability Evaluation of Complex Hardware and Software Systems," Proc. 23rd IEEE Int. Symp. on Fault-Tolerant Computing (FTCS-23), Toulouse, 1993, pp. 668-673. [13] U. N. Bhat, Elements of Applied Stochastic Processes, John Wiley and Sons, 1984. [14] W. G. Bouricious, W. C. Carter and P. R. Scheider, "Reliability modeling techniques for self-repairing computer systems," in Proc. 24th Annual ACM Nat. Conf., 1969, pp. 295-309. [15] R. Bryant, "Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams," ACM Computing Surveys, vol. 24, 1992, pp. 293-318. [16] J.A. Carrasco and J. Figueras, "METFAC: Design and Implementation of a Software Tool for Modeling and Evaluation of Complex Fault-Tolerant Computing Systems," Proc. of the 16th Int. Symp. on Fault-Tolerant Computing FTCS-16, 1986, pp. 424-429. [17] J. A. Carrasco, "Efficient Transient Simulation of Failure/Repair Markovian Models," in Proc. 10th IEEE Symp. on Reliable Distributed Systems, 1991, pp. 152-161. [18] J. A. Carrasco , "Failure Distance-based Simulation of Repairable Fault-Tolerant Systems," in Computer Performance Evaluation, Elsevier, 1992, pp. 351-365. [19] J. A. Carrasco, A. Calderón, and J. Escrivà, "Two new algorithms to compute steady-state bounds for Markov models with slow forward and fast backward transitions," in Proc. 4th Int. Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'96), February 1996, pp. 89-95. [20] J.A. Carrasco, J. Escriba and A. Calderón, "Efficient Exploration of Availability Models Guided by Failure Distances", Performance Evaluation Review, vol. 24, no. 1, May 1996. [21] J. A. Carrasco and J. L. Domingo, "METFAC-2: A Tool for Specification and Solution of Markov Performance, Dependability and Performability Models," in Proc. XII Design of Circuits and Integrated Systems Conference, Sevilla, Spain, November 1997, pp. 195-200. [22] J. A. Carrasco, "Tight Steady-state Availability Bounds using the Failure Distance Concept," Performance Evaluation, vol. 34, September 1998, pp. 27-64. [23] J. A. Carrasco, "Solving Large Interval Availability Models using a Model Transformation Approach," Technical Report, Universitat Politècnica de Catalunya, March 1999, available at ftp://ftp-eel.upc.es/techreports under the nameDMSD_99_3.ps [24] J. A. Carrasco, "Bounding steady-state availability models with group repair and phase type repair distributions," Performance Evaluation, vol. 35, no. 4, 1999, pp. 193-214. BIBLIOGRAPHY 145 [25] J. A. Carrasco, "Failure-distance-based importance sampling schemes for simulation of repairable fault-tolerant computer systems," 1998, under review for IEEE Trans, on Computers. [26] J. Carreira, H. Madeira and J. G. Silva, "Xception: Software Fault Injection and Monitoring in Processor Functional Units," in Proc. 5th Int'l Working Conf. on Dependable Computing for Critical Applications (DCCA-5), September 1995, pp. 135-149. [27] P. Chatterjee, "Modularization of fault trees: A method to reduce the cost of analysis," Reliability and Fault Tree Analysis, SIAM, 1975, pp. 101-137. [28] G. Chiola. C. Dutheillet, G. Franceschinis, and S. Haddad, "Stochastic Well-Formed Colored Nets and Symmetric Modeling Applications," IEEE Trans, on Computers, vol. 42, no. 11, November 1993, pp. 1343-1360. [29] G. S. Choi, R. K. Iyer and V. Carreno, "FOCUS: An Experimental Environment for Fault Sensitivity Analysis," IEEE Trans, on Computers, vol. 41, no. 12, pp. 1,515-1,526, December 1992. [30] G. Ciardo, J. Muppala and K. Trivedi, "SPNP: Stochastic Petri Net Package," Proc. 3rd IEEE Int. Workshop on Petri Nets and Performance Models (PNPM89), Kyoto, 1989, pp. 142-150. [31] E. Çinlar, Introduction to Stochastic Processes, Prentice-Hall, 1975, Englewood Cliffs, NJ, USA. [32] A. E. Conway and A. Goyal, "Monte Carlo Simulation of Computer Systems Availability/Reliability Models," in Proc. 17th IEEE Int. Symp. on Fault-Tolerant Computing, 1987, pp. 230-235. [33] O. Coudert and J. C. Madre, "MetaPrime: An Interactive Fault-Tree Analyzer," IEEE Trans, on Reliability, vol. 43, no. 1, March 1994, pp. 121-127. [34] J. Couvillion, R. Freiré, R. Johnson, W. Obal II, A. Qureshi, M. Rai, W. Sanders, and J. Tvedt, "Performability modelling with UltraSAN," IEEE Software, September 1991, pp. 69-80. [35] S. A. Doyle, J. B. Dugan and F. A. Patterson-Hine, "A combinatorial approach to modeling imperfect coverage," IEEE Trans, on Reliability, vol. 44, March 1995, pp. 87-94. [36] J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks, an engineering approach, IEEE Computer Society, 1997. [37] J. B. Dugan, K. S. Trivedi, M. K. Smotherman, and R. M. Geist, "The hybrid automated reliability predictor," AIAA J. Guidance, Contr., Dynam., vol. 9, May-June 1986, pp. 319- 331. 146 BIBLIOGRAPHY [38] J. B. Dugan and K. S. Trivedi, "Coverage Modeling for Dependability Analysis of Fault- Tolerant Systems," IEEE Trans, on Computers, vol. 38, no. 6, June 1989, pp. 775-787. [39] J. B. Dugan, "Fault trees and imperfect coverage," IEEE Trans, on Reliability, vol. 38, no. 2, June 1989, pp. 177-185. [40] Y. Dutuit and A. Rauzy, "A Linear-Time Algorithm to Find Modules of Fault Trees", IEEE Trans, on Reliability, vol. 45, no. 3, September 1996, pp. 422-425. [41] H. Fujiwara and T. Shimano, "On the Acceleration of Test Generation Algorithms", IEEE Transactions on Computers, vol. C-32, no. 12, December 1983, pp. 1137-1144. [42] J. B. Fussell and W. E. Vesely, "A New Methodology for Obtaining Cut Sets for Fault Trees," Trans, of the American Nuclear Society, vol. 15, June 1972, pp. 262-263. [43] M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979. [44] P. Goel, "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits," IEEE Transactions on Computers, vol. C-30, no. 3, March 1981, pp. 215-222. [45] L. H. Goldstein, "Controllability/Observability Analysis of Digital Circuits," IEEE Transactions on Circuits and Systems, vol. CAS-26, no. 9, September 1979, pp. 685-693. [46] A. Goyal, W.C. Carter, E. de Souza e Silva, S.S. Lavenberg, and K.S. Trivedi, "The System Availability Estimator," Proc. of the 16th Int. Symp on Fault-Tolerant Computing FTCS-16', 1986, pp. 84-89. [47] A. Goyal, P. Heidelberger and P. Shahabuddin, "Measure Specific Dynamic Importance Sampling for Availability Simulations," in Proc. 1987 Winter Simulation Conference, A. Thesen, H. Grant and W. D. Kelton (eds.), 1987, pp. 351-357. [48] A. Goyal, P. Shahabuddin, P. Heidelberger, V. F. Nicola, and P. W. Glynn, "A Unified Framework for Simulating Markovian Models of Highly Dependable Systems," IEEE Trans, on Computers, vol. 42, no. 1, January 1992, pp. 36-51. [49] D. Gross and D. Miller, "The randomization technique as a modeling tool and solution procedure for transient Markov processes", Operations Research, vol. 38, no. 2, 1984, pp 334- 361 [50] U. Gunneflo, J. Karlsson and J. Torin, "Evaluation of Error Detection Schemes Using Fault Injection by Heavy-Ion Radiation," in Proc. 19th Int'l Symp. on Fault-Tolerant Computing (FTCS-19), June 1989, pp. 340-347. [51] S. Han, K. G. Shin and H. A. Rosenberg, "DOCTOR: An IntegrateD SOftware Fault InjeCTiOn Environment for Distributed Real-Time Systems," in Proc. 1st Int'l Computer Performance and Dependability Symp., April 1995, pp. 204-213.