Considering dependent components in the terminal pair reliability problem

Minh Lê, Max WalterLehrstuhl für Rechnertechnik und Rechnerorganisation

Technischen Universität MünchenMunich, Germany

Email: lem@in.tum.de, walterm@in.tum.de

Abstract—The determination of the reliability value fortechnical systems whose components are subjected to randomfailure possesses a wide range of applicability, e.g. in datacommunication networks, computer architectures and electri-cal power networks. The inherent redundancy structures canbe described by reliability block diagrams (RBDs) and bysolving those RBDs the reliability of the respective systemcan be computed. The problem of solving the RBD in orderto compute the reliability is well-known as the terminal pairreliability problem. If it is assumed that system components failindependently, pure combinatorial methods can be applied todetermine the required probability. However, as soon as thereare some dependencies concerning the failure of componentswe cannot utilize pure combinatorial methods unless we dosome suitable modifications which take the dependencies intoaccount. For this purpose we present a hybrid method basedon the idea of factoring in combination with series and parallelreductions for systems with dependent component failures. Themethod is hybrid in the sense that dependent probability termsarisen from our proposed algorithm can be obtained by thehelp of a stochastic solver. The algorithm comprises clausesfor carrying out series and parallel reductions in parallel withfactoring. In addition to that we propose how to deal withmultiple occurring components.

Keywords-terminal pair, interdependent components, factor-ing, series parallel reductions, Binary Decision Diagram

A. Abbreviations

CTMC Continuous Time Markov ChainsPr ProbabilitySIC set of interdependent componentsROBDD Reduced Ordered Binary Decision DiagramMuBDD Multiple Binary Decision DiagramRBD Reliability Block Diagram

I. INTRODUCTION

The idea of analyzing the network reliability for technicalsystems lies in representing its redundancy structure bya graph where each system component - depicted by anedge - is regarded as a random variable with two states:working or failed. The literature generally assumes inde-pendent edges respectively components. Unfortunately, thissimplified assumption does not suffice the requirements inreality where we might have dependencies among somecomponents which have to be considered. Among others,those dependencies come up due to common cause failures,

fault propagation, cold/warm standby redundancy, imperfectfault detection and recovery, non-zero failover times andlimited repair capacity (See [1]). Thus, our problem ofcalculating the terminal pair reliability is extended with theadditional difficulty of interdependent components. To bemore precise, the components can be grouped into sets ofinterdependent components whereas two components fromdifferent SICs are independent to each other. In general,dependencies can be considered using finite, continuous timeMarkov chains (CTMCs) (see [2]). For this purpose a statespace is generated to account for all possible system states.Unfortunately there is an exponential growth in the amountof states with the increasing number of components. Forall nontrivial examples - starting with graphs comprisingtwenty edges - this might lead to a state space explosion. Away out is to find independent submodules in the stochasticmodel and create CTMCs with respect to those submodules.Following this fact, a good constellation of a system con-taining dependencies would be that the system comprisesmany SICs and each in turn possessing as few elements aspossible. Probability terms describing dependencies whichoccur during the calculation can be inquired by the help of astochastic solver which is nothing else than a state automatongenerating all possible combinations of states with respect toa group of components as described before. The objective ofthis work is to extend established algorithms to our claimedpurpose. We decided to use the factorization method inalternation with the series and parallel reductions.Our paper is structured as follows: After giving the formalstatement of the problem in section II, we will explain therespective data structure BDD used in the algorithm (seesection II-A). Then we will demonstrate how the algorithmworks if all components are independent on the basis ofan example graph (see section II-B). After establishing therules for the choice of edges to be factored, we will justifythe heuristics for conducting series and parallel reductionsif we allow the occurrence of interdependent components(see section II-D1). Because redundant computations haveto be accounted, we will consider all cases where the reuseof a BDD node is possible in section II-D2. In the last partwe will illustrate the appropriate approach for the factoringtheorem in combination with series and parallel reductionson the basis of a case study (see section II-E). Finally, we

2011 Sixth International Conference on Availability, Reliability and Security

978-0-7695-4485-4/11 $26.00 © 2011 IEEE

DOI 10.1109/ARES.2011.91

415

will briefly conclude our work and an outlook for our futurework will be given.

A. Related Work

The state of the art algorithms for the efficient and exactdetermination of the terminal pair reliability apply the fac-torization method in combination with reductions (see [3]).Apart from cut-based methods like [4], there are also path-based methods for partitioning the state space into disjointsets, e.g. Gobien-Dotson algorithm with reductions (see [5]).But none of those methods considers the occurrence ofinterdependent components within a system’s redundancystructure. To our knowledge there is only one article treatingthis issue (see [6]) whereas a different technique has beenused in comparison to the proposed technique of this work.In [6] the whole Boolean structure of the input graph isextracted first, thereupon the Shannon expansion is appliedwith respect to each SIC. Our approach works directly on thegraph and considers possible reductions. In addition to thatonly involved states with respect to each SIC are consideredin our calculation whereas by the Shannon expansion allpossible states have to be treated. With regard to dynamicfault trees (see [7], [8]) where dependencies can also beconsidered, our approach can handle the arbitrary arrange-ment of SICs, whereas a DFT can only be decomposed inindependent subtrees if the leafs (basic events) which have acommon AND/OR-gate are belonging to the same SIC. Sothe exploitation of independent subtrees is only possible fora certain configuration of SICs. The same issue holds whenapplying GSPNs (Generelized stochastic petri nets, see [2])to the SICs of a DFT.

II. FORMAL DESCRIPTION

We have a multigraph G := (V,E) with no loops andwhere V stands for a set of vertices or nodes and E amultiset of unordered pairs of vertices, called edges (SeeFig.1). Given the redundancy structure of a system modelledby a network graph G := (V,E), we specify two nodes s andt which characterize the terminal nodes (In Fig.1 those nodesare colored in black). We define a not necessarily injectivemap f for assigning the edges to the system components:

f : E → C

where C = S ∪ T is the finite set of system components,T is the set of independent components - where eachcomponent in T can be regarded as a SIC on its own -and S = SIC1 ∪ SIC2 ∪ . . . ∪ SICn, n ∈ N represents thedisjoint union of sets of interdependent components (SICs).The mapping of several edges to one component c infersthat c is a multiple component whereas component c canbe from any SIC or from set T . The dependency relationbetween two components infers that they must belong to thesame SIC. Because the dependency property is transitive,a SIC can be regarded as a transitive closure where each

element depends on the others whether directly or indirectly.So two components which are dependent must belong tothe same SIC and if they are from different SICs theyare independent. In other words, for all i, j with i 6= jit holds that SICi ∩ SICj = ∅. Moreover it holds that|SICk| ≥ 2 ∀k ∈ I. So if there are two components x1, x2

from different SICs, then their conjoint probability of failurewould be: Pr(x1∧x2) = Pr(x1) ·Pr(x2). If they would be inthe same SIC we have to query the stochastic solver to obtainthe conjoint probability. Note that the effort for generatingthe state space probabilities in terms of the stochastic solvergrows exponentially by the quantity of components in oneSIC. In an ideal situation the complexity can be kept downif the components are spread over several SICs and each oneconsist of only few components. In our example graph offigure 1 there are two SICs: SIC1 contains three componentsand SIC2 two. All remaining independent components areassigned to T .Because f is not necessarily injective we can assign severaledges to one component. Attention, this does not inferthat f is surjective because there might be componentswhich are not represented by any edge. For example twocomponents x, y fail due to a common cause failure comingfrom component z, but z plays no role in the system’sredundancy structure. This means that we allow the multipleoccurrence of one component in any system’s redundancystructure. This fact is implied by saying that there exist amultiple component in the redundancy structure. The men-tioned example graph contains three multiple componentsa, b and c which represent a two out of three redundancysubstructure. After introducing the notations we can nowformulate the problem as follows:Given a graph G := (V,E), its terminal nodes s, t, a setof system components C = S ∪ T and a not necessarilyinjective map f : E → C. Each component e ∈ E representsa random variable with two states: failed and working. Thesystem’s terminal pair reliability R is the probability that thetwo specified terminal nodes can be connected by at leastone path consisting of only edges associated with workingcomponents.

A. Detection of isomorphic subgraphs

This approach uses the technique of factoring, hencewe want to illustrate the associated data structure in thefollowing. By factoring on one edge of our input graphwe state that the respective component is working or isfailed. The input graph would split up into two subgraphs,one where the edge has been contracted and the other onewhere the edge has been deleted. Each of those subgraphsrepresent a node in a factoring tree. If we would go onfactoring until the terminal nodes are merged, the number ofthe leafs in the tree would grow exponentially with the sizeof the edges. We have to take into account that isomorphicsubstructures might occur in the course of the algorithm.

416

Those recurring substructures need to be detected in order tosave computational costs and decrease runtime. This can bedone by making use of the ROBDDs (see [9]) which accountfor isomorphic graph structures so that no node containingthe same subgraphs occur twice in the just described tree. Inorder to find out whether two subgraphs are isomorphic wetake those two graphs as input parameters for a functionthat determines whether two graphs are isomorphic. Ourproblem of detecting isomorphism can be solved in lineartime effort since the position of the edges can be determinedunambiguously by their labels and the terminal nodes. Note,that this problem cannot be classified as the known problemof graph isomorphism where the edges don’t bear any labels.Indeed, the longer the path length from the OBDD node -representing an isomorphic subgraph - to the leaf of theOBDD tree, the more the effort spent for the detection paysoff.

B. Case of independency

Even if all components are independent and there are nomultiple components, it has been shown in [10] that thisproblem is NP hard. However, it was shown in [11] thatfactoring in combination with reductions is one of the mosteffective approach to compute the terminal pair reliability,i.e. this algorithm works well for many practical scenariosexemplified in the literature. Hence we modify this approachfor our purpose.For determining the network reliability we first carry out allpossible reductions on the graph until no further reductionsare possible. Afterwards we choose an edge to factorizewhich gives us two subgraphs: One resulting from thecontraction and the other one from the deletion of the chosenedge. The computation again continues on the two sub-graphs. In doing so reductions should be applied if possibleotherwise we have to choose an edge for factorization. Thisprocedure is conducted until the terminal nodes are meltedor disconnected from each other.First we want to apply this algorithm to the case thatall components in Fig.1 are independent. After we haveconducted one series and one parallel reduction (See Fig.2),we start factoring on edge a to obtain G2′ and G3′ (see Fig.3left side) where in G3′ we have conducted twice the seriesreduction to obtain the edge r3 = r2 ∧ d. If we factor onthe multiple edge b in G2′ we will obtain the subgraphs G4′

and G5′ and another edge resulting from a series reductionr4 = c∧d. By factoring on r3 in G3′, d in G4′ and r4 in G5′

(see Fig.3 right side) we obtain two new subgraphs G6′ andG7′. Because isomophism occurs in those two BDD nodes,they are highlighted in grey color. By series and parallelreductions G6′ and G7′ can be reduced to one edge whichhas the label r7 in G6′ and r10 in G7′ (see Fig.5 right side).After those two edges were contracted, the algorithm ends.We must now address the important question, namely howwe have to proceed if the graph contains interdependent

a

b

f

i j

g

e

ab

cc

d

hG0:= SIC1

f

g

SIC2

e

d

h

Figure 1. initial graph

a

b

r1

R1

e

ab

cc

d

hG1:=

G0reduce

Figure 2. reduced initial graph

components. So in the next steps we will give the answersto the appropriate adjustments for the factoring algorithmwith series and parallel reductions. First we explain how werestrict the utilization of series and parallel reductions in thepresence of interdependent components.

C. Reductions

For speeding up the calculation, reduction techniquesshould be applied to the graph whenever it is possible. Withnegligible expense certain substructures can be identified andsimplified so that the graph size decreases under preservationof the probability for the reliability of the original graph.Typical well known reduction methods are those of seriesand parallel reductions. Under the consideration of depen-dencies among certain system components and the claimedconvention that no reductions with multiple components areallowed, we want to establish certain rules and heuristicsfor the factoring algorithm in combination with series andparallel reductions.

1) Rules for series and parallel reductions: We denotethe initially reducible components as e1 and e2 (both areeither edges in a series or in a parallel structure). In thefollowing, we allow the existence of multiple componentsbut at the same time we prohibit reductions involved withmultiple components. This is based on the fact that if areduction with a multiple component has taken place no

b

eb

cc

d

h

r1

R1

er3

h

G1a !a

G2' G3'r1

R1

ed

h

b

r1

R1

r1

R1

e

h

!b

r4

G4' G5'

h h

G3'

e

d

r1

R1

r4

G4' G5'

e

r1

R1

!dr3!r3 !r4

G6' G7'

Figure 3. independent case

417

more factorization on the multiple component can be donewithout any further efforts. In the course of the algorithmit might occur that multiple components become unique. Inthat case we allow reductions on them. This case can beobserved in our example later on. Furthermore we imposethat series and parallel reductions can only be performedamong independent components and among componentswhich are from the same SIC. In other words, series orparallel reductions are possible if e1, e2 ∈ T or e1, e2 ∈ SICi,i ∈ N. We also have investigated the idea to reduce edgesfrom different SICs but came to the conclusion that thespent overhead would far exceed the advantage of thereductions. Each time we do a reduction, we record theBoolean term in a global Boolean table (see Table I). Welabel the new resulting edge with a capital letter Ri - wherei stands for the i-th reduction - if there is a reductionamong interdependent components and otherwise we labelthe new edge with a small letter ri if e1, e2 ∈ T , i.e. theyare independent. Because there are only series and parallelreductions, the operator is limited to OR and AND. We namethe operands according to the labels of the edges e1, e2.In addition to that we have to enter the probability of thenew resulting edge in a separate global probability table. Weonly store the probability for reductions among independentcomponents. The probability of the edge evolving from theseries independent reduction would be:

pr1 = pe1pe2

and from the parallel reduction

pr1 = pe1 ⊕ pe2 := pe1 + pe2 − pe1pe2 .

For the parallel reduction we have introduced the operator ⊕which implies the above formula. The probabilities for thedependent reductions are not registered in the table becauselater on those reduced edges will be factored and by the endof the algorithm aggregated to one boolean term which thenwill be added to a global list ToSolver in order to querythe dependent probabilities. There are also other establishedreduction methods such as the polygon-to-chain (see [12]) ortriangle base method (see [13]) but we restrict to the seriesparallel reductions. The reason therefore is that if we wouldcomprise the mentioned reduction techniques we wouldspend too much effort on modifying the probability terms ofthe reductions’ resulting edges and in turn the dependencieswithin those edges have to be considered during runtime ofthe calculation.

D. Rules for Factoring

In the presence of SICs the order of factorization plays animportant role. The rule can be formulated as follows: Thefirst time a component from any SIC had been chosen tobe factored, components or edges from this respective SICmust be chosen in the following factorization steps. This isdone until no more edges or components from this respective

SIC are left over in the subgraph. From this moment onany arbitrary remaining edge can be chosen to be factored.Between the factoring steps we can conduct series andparallel reductions with respect to the rules described above.The factoring scheme can be depicted as an alternation ofdifferent SIC layers (See the small dotted box in Fig.5). Bythe use of this rule we even keep the set of factored edgesindependent from the remaining components or edges of thesubgraph.

1) Heuristics for the variable ordering: We want toestablish some heuristics for the variable ordering because itplays an important role for the runtime of the algorithm. Ifwe have to choose the first edge to be factored, any arbitraryedge can be taken as long as there are no multiple edges,otherwise we prioritize multiple edges (With respect to [6]multiple edges can be factorized at the same time. Either alledges are factorized or deleted). Assume that we would haveseveral SICs of different sizes and no independent edges inour input graph, then we suggest to factor on the SIC havingthe least number of edges remaining in the subgraph. Onthe one hand this way leads to less subproblems becausewe have to factor on fewer edges in series and on the otherhand we hope that by factoring on those components somepossible reductions between interdependent edges of otherSICs might arise in the respective subgraphs. In general wesuggest the following edge choice priority for factoring:• Multiple independent edges• Multiple interdependent edges (with regard to the least

number of edges for each SIC remaining)• Independent edges• Interdependent edges (with regard to the least number

of edges for each SIC remaining)Note, that it is possible to factor on some independent edgesfollowed by factoring on any SIC though there are stillindependent edges remaining in the subgraph. That is, not allthe independent components have to be factored in sequence.In the case study we adhere to the priority suggested above.Thereby we consider that each depth-level of the OBDD treecontains the same variables that have been factored. This isdistinguished by the dotted box in Fig.5. The reason whythe depicted OBDD is in fact a ROBDD is that there doesnot exist any two nodes which stand for the same subgraph.This directs us to the following issue.

2) Rules for BDD node reuse: When dealing with depen-dent components it is not always possible to link to an exist-ing node in case of isomorphism: For instance, at a certaindepth of our tree we would factor on a component x ∈ SICi

and would detect an existing BDD node representing anisomorphic subgraph (see Fig.4). We are not allowed to linkto that node if there are still components in the subgraphwhich belong to SICi and the factored edge outgoing fromthis node would be from a different SICj, namely i 6= j (Seecase 3). If we would have factored on an independent edgeit would be always possible to link to an existing node in

418

x independent

!yyy arbitrary x in SICi

!yyy independent

allowed, only if x is the lastfactored component in SICi

x in SICi

!yyy in SICj

allowed, only if i = j or if i != j then x must be the last factored component in SICi

(1)

(2)

(3)

Figure 4. Rules for BDD node reuse

case of isomorphism (See case 1), otherwise if the edge tobe factored is not independent then it should be the last onefrom its respective SIC in order to allow the exploitation ofold BDD nodes (See case 2).

3) Structure charts and remarks to the algorithm: Ouralgorithm is illustrated by the structure charts at the end ofthis paper. The top down arrangement for the structure chartfunctions is according to their position in the hierarchy.All important aspects that we have treated in the previoussections are integrated in their designated functions. Forthe series reduction we assume the following node-edgesequence: [v0, e1, v, e2, v1] whereas e1 and e2 are thetwo neighbored edges. Analogously this convention holdsfor the parallel reduction except that we have a parallelarrangement for e1, e2 with v0, v1 as border nodes. We omitthe structure chart for the parallel reduction since it workssimilarly.

Graph G Reduce(Graph G)G = SeriesRed(G)

G = ParallelRed(G)

int a = NumberOfSeriesRed + NumberOfParallelRedhhhhhhhhhhhhh

(((((((((((((a == 0y n

return G��@@

@@��

G = Reduce(G)

Graph G SeriesRed(Graph G)for each Node v ∈ G \ {s, t} ∧ deg(v) == 2 with edges e1 and e2

i1 = e1.SICIndex

i2 = e2.SICIndexhhhhhhhhhhhh

((((((((((((i1!= i2y n

continueString EdgeLabel = BT.add(’AND’,e1,e2)

hhhhhhhhhhhh

((((((((((((i1, i2==0y n

Prob.add(EdgeLabel,’Mult’,e1,e2)//0 corresponds to the independent case

∅G.delete(v)

G.addEdge(EdgeLabel, v0, v1)

Table IBOOLEAN TERM TABLE

Label Operator O1 O2r1 OR i jR1 AND f gr1 AND b cR2 AND h R1

R3 AND d e

Table IIPROBABILITY TABLE

Label Operator O1 O2r1 ⊕ i jr2 · b c

MuBDDNode root BDD2MuBDD(BDDNode root0)MuBDDNode root1 = new MuBDDNode.addNode()//Initialization of MuBDD root node

replicate(root0,root1,1) //Call of recursive transformation function

return root1��@@

@@��

double R fetch(MuBDDNode node)hhhhhhhhhhhhh

(((((((((((((node.val==1y n

return node.val��@@

@@��

double R = 0for each node.incidentEdge e

R = R + p(e.Label) ·fetch(e.getEndNode())

∅

return R��@@

@@��

Based on the described rules and heuristics we assume thatwe have finalized our factoring algorithm for an arbitraryexample graph (this is equivalent to the finalization of theRel(G) routine in the Main() procedure). To that moment thetwo global tables Booleanterm (see Table I) and Probability(see Table II) have been filled. Additionally, we obtain afactoring tree respectively a BDD with nodes representingthe subgraphs, edges representing the factored componentsand leafs which possesses values in {0, 1}. Hereby we haveall elementary events for the system state (zero for failed andone for available) represented by a tree. Zero corresponds tothe cuts and one to the paths. The union of all those elemen-tary probabilities for the path yields the network reliabilityR and all cuts the network unreliability 1−R. To obtain thereliability we normally have to compute all path probabilitiesand sum them up. To avoid searching all possible paths fromthe root to the leafs of the BDD, we have to transform theBDD to a MuBDD1. We do this by calling the functionBDD2MuBDD in the Main() procedure - all auxiliary func-tions except the replicate function are listed on this page.In BDD2MuBDD the root nodes for the BDD and MuBDDare initialized as parameters for the recursive transformation

1MuBDD were introduced in [6]. The name MuBDD is justified by thefact that any parent node in a MuBDD might have more than two outgoingedges to the child nodes whereas in the BDD there are at most two outgoingedges to the child nodes.

419

1

a !a

b !b r2 !r2

c !c

r1 !r1

R2 !R2

r1 !r1

h

R3

R1!R1

h !h

!R1R1

R3ed

G1

G2 G3

G4G5

G6 G7

G8

G9

R3

1

a !a

b !br2

!r2

c !c

r1 !r1

R2 !R2

r1!r1

R3 R3

hR1h!R1

!h!R1!hR1

R3e

d

G1

G2 G3

G4G5

G6 G7

G8

e

!R1 R1

a

b,c

i,j

SIC1

SIC2

BDD MuBDD

independent

SIC2

SIC1

L1

L2

L3

BDD 1

a !a

b !b

r7 r10

r3!r3

d

!d!r4

r4

G1

G2' G3'

G4'G5' G6' G7'

Figure 5. Transformation of BDD to MuBDD, BDD for independent case

function replicate. Recall that any parent node in a MuBDDmight have more than two outgoing edges to the child nodes.This is due to the fact that as soon as we are on an edgelabeled with a component from a SIC, we have to traversethe whole SIC layer (i.e. possibly several levels of edgesfactored) until a MuBDD node can be created. The functionMuBDDNode.addNode(StringEdgeLabel, StringNodeLabel)returns the node created which again will be passed as aparameter for the next recursive call. It should be notedthat isomorphic nodes are only permitted in the independentlayer of factorization within the MuBDD tree. In our exam-ple the two isomorphic nodes from the independent layerof the BDD would remain in the MuBDD (See Fig.5). Thisfact is incorporated by naming the newly created MuBDDnodes after the node labels of the BDD.In the course of the transformation new dependent probabil-ity terms are added to the ToSolver list. After those termsare queried from the solver, we have enough informationto compute the reliability R. This is done by conducting adepth-first search in the MuBDD by the help of the recursivefunction fetch. Note, that the probabilities for each edge -labeled with Boolean terms - in the MuBDD tree can beobtained by inquiring the Probability table or ToSolver list.At the end the requested result R will be returned.

E. Case study

In the following we will apply our proposed algorithmto the example graph G0 from Fig.1. This graph containssome series parallel structures and a two out of threesystem implying three multiple edges. The two black nodesrepresent the terminal nodes. As mentioned before thereare two SICs, one containing three components and theother two. We start our algorithm by conducting a parallelindependent reduction for i and j which results in r1 anda series dependent reduction for f and g labeled with R1.We call the reduced graph G1 and add the new terms to theBooleanterm table and Probability table. We continue thecalculation on G1 (see Fig.2). Because no further reductionsare possible we have to factorize. As proposed in section 1.4we choose one of the multiple edges (e.g. a) to factor on.

b

eb

cc

d

h

r1

R1

er2

d

h

G1a !a

G2:= =:G3r1

R1

ed

h

b G2

r1

R1

r1

R1

ec

d

h

!b

=:G5G4:=

eh

r1

R1G8:=

c

!c

G3

!r2

ed

h

G4

R1

r1

R1

ed

h=:G7

G6:=

G8

!r1

R2

R3

e

R1

d

R1

e

d ed

h !h

R1 !R1

e

!R1

R3

R3

!R2

1

e

R1

hh R1

R1

e dR3

R2

R3h

r1 !r1

R3

G9:=

R3

1)

2)

3)

r2

Figure 6. dependent case

Thus we get two new BDD nodes represented by subgraphsG2 and G3 whereby in G3 we have reduced b and c tor1 since b and c became unique. Though G3 still containsa series structure, we are not allowed to reduce becauser2 ∈ T and d ∈ SIC2 (see Fig.6 first part). We move onelevel lower in the BDD tree by factoring on b and r2 forG2 and G3. Thereupon we obtain three new BDD nodesinstead of four: As we can see in Fig.6 second part, G3merged with r2 and G2 merged with a lead to the sameisomorphic subgraph node G4. The same holds for nodeG8. We carry on the approach for G4,G5 and G8 andobtain the respective subgraphs in the lower level of theBDD tree (see Fig.6 third part). Note that we have factoredon all leftover independent components before we startedto factor on all components for each SIC. The left part ofFig.5 shows the sequential factoring order from layer one tolayer three. Instead we could have chosen another factoringorder by interchanging the layers. It can also be taken fromthe picture that G9 is another already existent BDD node inthe tree. Altogether we have three of these nodes which arehighlighted in grey color. Nodes G9 and G8 possess indegreetwo, whereby node G4 has even three edges entering. Eachleaf of the tree with value one or true represents the lastedge for each possible path. Just as the tree has beencompleted and the two global tables were filled, we have totransform our BDD to a MuBDD (see Fig.5) by calling thefunction BDD2MuBDD(BDDNode node). After completingthe creation of the MuBDD the ToSolver list would containthe following entries: pe, pd, ped grouped with regard to SIC1

and phfg, phfg, phf g, phf g, pfg, pf g grouped according to SIC2.Now the stochastic solver can be inquired in order to obtainthe values for the requested probability terms. Afterwards wehave all probablity terms needed for traversing the MuBDDwith the fetch function. As a result the reliability will be re-turned. Our approach works as an usual factoring algorithmwith series and parallel reductions if all components fromgraph G would be independent (as carried out in section1.2). In comparison with the independent case, let us referto the right lower part of Fig.5. As expected, this BDD hasgot a lower depth. It has got only seven nodes and two leafs

420

double R Main()

Graph G = Input(V,E) //Input of the redundancy structure

Map Mappings = ReadMapping() //Input of the assignments for SICs and multiple components

Table ←↩ List ToSolver = 0, Map Prob = 0, Map BT = 0 //Initialization of necessary data structures

BDDNode root = new BDDNode.addNode(G) //BDDNode.val = -1 if node already existent

Rel(G, root) //Call of Rel function

MuBDDNode rootMuBDD = BDD2MuBDD(root) //Transform ROBDD to MuROBDD

querySolver(ToSolver)

R = fetch(rootMuBDD)

return R��@@

@@��

Rel(Graph G,BDDNode node)hhhhhhhhhhhhhhhhhhhhhhhhh

(((((((((((((((((((((((((

G.IsConnected

y n

return 0��@@

@@��

∅

Graph G = Reduce(G)hhhhhhhhhhhhhhhhhhhhhhhhh

(((((((((((((((((((((((((

G.NumberOfEdges > 1

y n

Edge e = chooseEdge(G)//Choose one Edge e for Factoring in compliance with the imposedheuristics

BDDNode a = node.addNode(G ∗ e,e)BDDNode b = node.addNode(G− e,e)

hhhhhhhhhhhhh

(((((((((((((a.val != -1y n

Rel(G ∗ e, a)hhhhhhhhhhhhh

(((((((((((((b.val != -1y n

Rel(G− e, b)

int n =G.NumberOfEdgeshhhhhhhhhhhhh

(((((((((((((n == 1y n

node.addLeaf(lastEdge) node.addLeaf()

∅

return

replicate(BDDNode end1,MuBDDNode end2,String akk)

for each edge e starting at end1 leading to end1tailhhhhhhhhhhhhhhhhhhhhhhhhh

(((((((((((((((((((((((((

e.SICIndex == 0

y //SICIndex=0→ independent n //traverse SIC layerhhhhhhhhhhhhh

(((((((((((((end1tail.val == 1y n

end2.addLeaf(e.Label)

continue∅

end2 = end2.addNode(e.Label,end1tail.Label)

replicate(end1tail,end2,1)

akk = akk ∧ e.Labelint i = e.SICIndexhhhhhhhhhhhhh

(((((((((((((end1tail.val == 1y n

end2.addLeaf(akk)

continue∅

int j = end1tail.incidentEdge.SICIndex//Preview whether creation of MuBDDNode is possible

hhhhhhhhhhhhh

(((((((((((((j !=iy n

end2 = end2.addNode(akk)ToSolver.add(akk)//Create MuBDDNode and addBoolean term to ToSolver list

replicate(end1tail,end2,1)

replicate(end1tail,end2,akk)

∅

∅

421

whereas the other BDD has got 16 nodes and seven leafs.The low depth of the tree can be affiliated to the elaboratechoice of the factoring order.

III. CONCLUSION

In the paper we have proposed a hybrid method to accountfor component dependencies within a system’s redundancystructure. The method is based on the idea of factoring incombination with series and parallel reductions. To acquiredependent probability terms, we have integrated the possibil-ity to query a stochastic solver into our proposed approach.In addition we suggested rules for factoring and for reduc-tions in the presence of dependent components. Moreover weproposed heuristics for the choice of the variable ordering.Our algorithm finds all possible pathways of the inputgraph and stores them in a ROBDD where isomorphicnodes can be recognized and redundant computations cantherefore be avoided. Finally we proposed how to obtain thereliability in an efficient way by transforming the BDD toan MuBDD and extracting information out of the MuBDDby conducting a depth-first search. The whole approach wasapplied to an example graph where the independent casewas compared with the dependent case containing two SICsof different sizes. For the next steps we plan to work onapproximation methods for determining the reliability ofgraphs of large sizes which for example exist as internetgraphs. The proposed ideas could be applied to the Gobien-Dotson algorithm (see [14]) to obtain approximation bounds.One of our future research interest is to determine the k-terminal reliability according to our problem of dependentcomponents. Altogether this work is a contribution in theframework of LARES (see [15] and [16]).

IV. ACKNOWLEDGMENTS

The authours would like to express their thanks to M.Siegle, A. Gouberman, M. Riedl and J. Schuster fromUniversität der Bundeswehr. We really have appreciatedthe lively and thoughtful discussions we have had in thelimited time available to us. This work is partly fundedby the Deutsche Forschungsgemeinschaft within the projectBO 818/8-1: "Modellbasierte Analyse der Verlässlichkeitkomplexer fehlertoleranter Systeme".

REFERENCES

[1] M.Walter and W.Schneeweiss, The Modeling World of Relia-bility/Safety Engineering, 2005.

[2] R.Sahner, K.Trivedi, and A.Puliafito, Performance and Reli-ability Analysis of Computer Systems, 1996.

[3] N.Deo and M.Medidi, “Parallel algorithms for terminal pairreliability,” in IEEE Trans. Reliability, vol 41, no.2, pp.201-209, 1992.

[4] C. Y.G. and Y. M.C., “A cut-based method for terminal-pairreliability,” in GLOBECOM 95, IEEE, 1995.

[5] Y.B.Yoo and N. Deo, “A comparison of algorithms for termi-nal pair reliability,” in IEEE Trans. Reliability R-37 (1988),pp. 210–215, 1988.

[6] M.Pock and M.Walter, “Efficient extraction of the structureformula from reliability block diagrams with dependent ba-sic events,” in Professional Engineering Publishing 2008,München, Germany, 2009.

[7] S. K. G. Coppit D, “Galileo: A tool built from mass-market applications,” in Proceedings of the 22nd internationalconference on software engineering, IEEE, 2000.

[8] V. B. G. R. Dugan J, “Diftree: a software package for theanalysis of dynamic fault tree models,” in Proceedings of thereliability and maintainability symposium (RAMS), 1997.

[9] F.-M. Yeh, S. K. Lu, and S. Y. Kuo, “Obdd based evaluationof k terminal network reliability,” in IEEE Trans. Reliability,vol. 51, no. 4, pp. 443-451, 2002.

[10] L. Valiant, “The complexity of enumeration and reliabilityproblems,” in SIAM Journal on Computing, 1979.

[11] A. Satyanarayana and K. Wood, “A linear time algorithm forcomputing k-terminal reliability in series parallel networks,”in SIAM Journal on Computing 14, 818, 1985.

[12] R. K. Wood, “A factoring algorithm using polygon-to-chainreductions for computing k-terminal network reliability,” inNetworks 15, pp. 173–190, 1985.

[13] S.J.Hsu and M.C.Yuang, “Efficient computation of terminal-pair reliability using triangle reduction in network manage-ment,” 1998.

[14] W.P.Dotson and J.Gobein, “A new analysis technique forprobabilistic graphs,” in IEEE Trum. Circuit Theory, vol. CT-20, pp. 335-340, 1979.

[15] M.Walter and M.Le, “Clear and concise models for fault-tolerant systems with limited repair using the modelingparadigm LARES+,” in 19th AR2TS, München, Germany,2011.

[16] M.Walter, “Stepwise refinement of complex dependabilitymodels with LARES,” in DYADEM-FTS 2011, 2011.

422