# Qualitative Analysis of Commercial Services in MEC as Phased-Mission Systems

Authors: Yuhuan Gong; Yuchang Mo
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Currently, mobile edge computing (MEC) is one of the most popular techniques used to respond to real-time services from a wide range of mobile terminals. Compared with single-phase systems, commercial services in MEC can be modeled as phased-mission systems (PMS) and are much more complex, because of the dependencies across the phases. Over the past decade, researchers have proposed a set of new algorithms based on BDD for fault tree analysis of a wide range of PMS with various mission requirements and failure behaviors. The analysis to be performed on a fault tree can be either qualitative or quantitative. For the quantitative fault tree analysis of PMS by means of BDD, much work has been conducted. However, for the qualitative fault tree analysis of PMS by means of BDD, no much related work can be found. In this paper, we have presented some efficient methods to calculate the MCS encoding by a PMS BDD. Firstly, three kinds of redundancy relations-inclusive relation, internal-implication relation, and external-implication relation-within the cut set are identified, which prevent the cut set from being minimal cut set. Then, three BDD operations, IncRed, InImpRed, and ExImpRed, are developed, respectively, for the elimination of these redundancy relations. Using some proper combinations of these operations, MCS can be calculated correctly. As an illustration, some experimental results on a benchmark MEC system are given.


---

## Body

## 1. Introduction

Currently, mobile edge computing (MEC) is one of the most popular techniques used to respond to real-time services from a wide range of mobile terminals [1–4]. Edge computing is a distributed computing topology where information processing is placed closer to the things or people that produce and/or consume that information. It means that MEC provides cloud-computing capabilities at the edge of the mobile network in close proximity to mobile subscribers; it is also considered as one of the key pillars for meeting the demanding KPIs of 5G.Mobile edge computing integrates cloud computing (CC) into mobile networks, prolonging the battery life of mobile users (MUs). However, this mode may cause significant mission complexity. Compared with single-phase systems, commercial services in MEC can be modeled as phased-mission systems (PMS). A MEC PMS is defined as a commercial service, which is subject to multiple, consecutive, nonoverlapping phases of operation. During each phase, it has to accomplish a specified task. Thus, the MEC configuration, failure criterion, and/or failure behavior can change from phase to phase [5–8].Much early work has been conducted on the fault tree analysis of PMS. Qualitative analysis of commercial services in MEC as phased-mission systems is much more complex, because of the dependencies across the phases. For instance, the state of a MEC node at the beginning of a new phase is identical to its state at the end of the previous phase [9–11]. Over the past decade, researchers have proposed a set of new algorithms based on the binary decision diagram (BDD) for fault tree analysis of a wide range of PMS with various mission requirements and failure behaviors [12–15]. Due to the nature of the BDD, cancellation of common components among the phases can be combined with the BDD generation, without additional operations, and the sum of disjoint products (SDP) can be implicitly represented by the final PMS BDD. Several experiments show that BDD-based algorithm is more efficient than the algorithm based on SDP, in both computation time and storage space; this efficiency allows the study of some practical, large MEC PMS [16–18].The analysis to be performed on a fault tree can be either qualitative or quantitative. Qualitative analysis involves calculating the minimal cut set (MCS), that is, listing all possible smallest combinations of basic events, which cause the top event. Quantitative analysis, on the other hand, involves calculating the probability of the top event occurring from the probabilities of the basic events. For the qualitative fault tree analysis of MEC PMS by means of BDD, no much related work can be found. In this paper, we focus on this line of research, that is, calculating the MCS encoding by a PMS BDD. The major contributions of our work are the following ones:(1)
Different kinds of redundancy relations within the cut set encoding by a PMS BDD are identified, and it is these relations that prevent the cut set from being minimal cut set.(2)
Two BDD operations are proposed to eliminate these redundancy relations from a PMS BDD. One operation can only eliminate the external-implication relations relating to one component, and the other operation eliminates all the inclusive relations from the cut set.(3)
MCS calculation method is developed by combining the proposed two BDD operations for a PMS BDD with forward ordering.The remainder of the paper is organized as follows. Section2 introduces the fundamentals of fault tree and BDD for the qualitative analysis of MEC PMS. Section 3 proposes three kinds of redundancy relations within a PMS BDD, several BDD operations eliminating these redundancy relations, and MCS calculation methods based on these BDD operations. Section 4 gives some experimental results on a benchmark MEC PMS. Last, conclusions are given in Section 5.


## 2. Preliminaries

### 2.1. Fault Tree

Fault tree analysis is an important technique for reliability and safety analysis. Bell Telephone Laboratories developed the concept in 1962 for the US Air Force for use with the Minuteman system. It was later adopted and extensively applied by the Boeing Company.Fault tree diagrams are logic block diagrams that display the state of a system (top event) in terms of the states of its components (basic events). It uses a graphic “model” of the pathways within a system that can lead to a foreseeable, undesirable loss event (or a failure). Fault trees are built using gates and events. The two most commonly used gates in a fault tree are the AND and OR gates. If both events need to occur to cause the top event to occur, they are connected by an AND gate. Alternatively, if the occurrence of either event causes the top event to occur, then these events are connected using an OR gate. Notice that NOT gate is not considered in this paper. Thus, the fault trees analyzed in the following sections are coherent fault trees.For MEC PMS, there are two kinds of fault tree models: phase-level fault tree, which represents the causal chain between component failure and phase failure, and system-level fault tree, which represents the causal chain between phase failure and service failure. As an illustration example, Figure1 depicts a small MEC PMS fault tree.Figure 1
An example MEC PMS fault tree.For the purpose of this paper, MEC PMS fault trees are essentially considered as Boolean functions, that is, terms inductively built over the two constants 0 and 1, a set of variablesX, and usual logical connectives ∧ (AND) ∨ (OR). The Boolean function F associated with the fault tree in Figure 1 is F=A1∨B1∨C1∨A2∨B2∧C2∨A3∧B3∧C3.


### 2.2. BDD

BDD is a compact encoding of the truth tables of Boolean function [19]. The BDD representation is based on the Shannon decomposition. Let F be a Boolean function that depends on the variable x; then the following equality holds:(1)F=x∧Fx←1∨¬x∧Fx←0=itex,Fx←1,Fx←0.BDD has two sink nodes, labeled 0 and 1, representing the two corresponding constants 0 and 1. Each nonsink node is labeled with a Boolean variablex and has two outgoing edges that represent the two corresponding expressions in the Shannon decomposition. These two edges are called E-edge (or 0-edge) and T-edge (or 1-edge), respectively. The node linked by the T-edge represents the Boolean expression Fx←1; E-edge represents the Boolean expression Fx←0. Thus, each nonsink node in a BDD encodes an ite format.An ordered BDD is a BDD with the constraint that the variables are ordered and every source-to-sink path in the ordered BDD visits the variables in ascending order. A reduced ordered BDD is an ordered BDD where each node represents a distinct Boolean expression.


### 2.3. Variable Ordering

A variable in a PMS BDD indicates the component that the variable belongs to and the phase in which the component exists. For example,Ci is the state indicator variable of component C at phase i. Variable ordering can be generated in the following steps: component-level ordering and ordering variables on phases.(1)
Component-level ordering: the components in PMS ares-independent from each other. Therefore, the ordering heuristics for ordinary BDD can be applied to component-level ordering for PMS BDD.(2)
Phase ordering: there are two classes of phase ordering: forward ordering and backward ordering. In forward ordering, the variable order is the same as the phase order. In backward ordering, the variable order is the reverse of the phase order.To illustrate the above ordering method, the PMS in Figure1 can be used. Applying DFLM to the fault tree in “do not care” form shown in Figure 2, where phase indexes are unconsidered, the component-level ordering is A < B < C. Extending this component-level ordering over different phase indexes, the forward DFLM ordering is A1 < A2 < A3 < B1 < B2 < B3< C1 < C2 <C3, and the backward DFLM ordering is A3 < A2 < A1 < B3 < B2 < B1 < C3 < C2 < C1.Figure 2
The “do not care” form of the tree in Figure1.


### 2.4. BDD Generation

In order to compute the BDD associated with a Boolean functionF, the following principle is applied:(1)
IfF is a constant, then one associates with F the corresponding sink node 0 or 1.(2)
IfF = x, where x is a variable, then one associates with F the BDD ite (x, 1, 0).(3)
Finally, ifF=G<>H, where <> is the binary connective ∧ or ∨ and G and H are functions, then one computes the BDDs associated with G and H and then performs the operation <> on these two BDDs.Given two Boolean functionsG and H encoded by the BDDs G = ite (x, G1, G0) and H = ite (y, H1, H0), it is possible to compute directly on G and H any logical operation between G and H by means of the following calculation:(2)G⋄H=itex,G1,G0⋄itey,H1,H0=itex,G1⋄H1,G0⋄H0,x=y,itex,G1⋄H,G0⋄H,x<y,itey,G⋄H1,G⋄H0,x>y.Compared with the single-phase system, BDD generation of PMS is much more complex because of the dependencies of component states across the phases. UseG and H to represent phase BDD of phase i and phase j, respectively i<j. When expanded with regard to xi and xj, they, respectively, can be written as G = ite (xi, G1, G0); H = ite (xj, H1, H0).Following special BDD operation, to deal with the cross-phase dependencies associated with the operation <> onG and H,(3)G⋄H=itexi,G1,G0⋄itexj,H1,H0=itexi,G1⋄H1,G0⋄H0,xi=xj,itexj,G⋄H1,G0⋄H0,xj<xi,itexi,G1⋄H1,G0⋄H,xi<xj.With the help of BDD operations (2) and (3), PMS BDD can be generated from PMS fault tree. When different orderings are used, the sizes of PMS BDD are different. As shown in Figure 3, the size of BDD with forward DFLM ordering is 15.Figure 3
PMS BDD with forward DFLM ordering.


## 2.1. Fault Tree

Fault tree analysis is an important technique for reliability and safety analysis. Bell Telephone Laboratories developed the concept in 1962 for the US Air Force for use with the Minuteman system. It was later adopted and extensively applied by the Boeing Company.Fault tree diagrams are logic block diagrams that display the state of a system (top event) in terms of the states of its components (basic events). It uses a graphic “model” of the pathways within a system that can lead to a foreseeable, undesirable loss event (or a failure). Fault trees are built using gates and events. The two most commonly used gates in a fault tree are the AND and OR gates. If both events need to occur to cause the top event to occur, they are connected by an AND gate. Alternatively, if the occurrence of either event causes the top event to occur, then these events are connected using an OR gate. Notice that NOT gate is not considered in this paper. Thus, the fault trees analyzed in the following sections are coherent fault trees.For MEC PMS, there are two kinds of fault tree models: phase-level fault tree, which represents the causal chain between component failure and phase failure, and system-level fault tree, which represents the causal chain between phase failure and service failure. As an illustration example, Figure1 depicts a small MEC PMS fault tree.Figure 1
An example MEC PMS fault tree.For the purpose of this paper, MEC PMS fault trees are essentially considered as Boolean functions, that is, terms inductively built over the two constants 0 and 1, a set of variablesX, and usual logical connectives ∧ (AND) ∨ (OR). The Boolean function F associated with the fault tree in Figure 1 is F=A1∨B1∨C1∨A2∨B2∧C2∨A3∧B3∧C3.


## 2.2. BDD

BDD is a compact encoding of the truth tables of Boolean function [19]. The BDD representation is based on the Shannon decomposition. Let F be a Boolean function that depends on the variable x; then the following equality holds:(1)F=x∧Fx←1∨¬x∧Fx←0=itex,Fx←1,Fx←0.BDD has two sink nodes, labeled 0 and 1, representing the two corresponding constants 0 and 1. Each nonsink node is labeled with a Boolean variablex and has two outgoing edges that represent the two corresponding expressions in the Shannon decomposition. These two edges are called E-edge (or 0-edge) and T-edge (or 1-edge), respectively. The node linked by the T-edge represents the Boolean expression Fx←1; E-edge represents the Boolean expression Fx←0. Thus, each nonsink node in a BDD encodes an ite format.An ordered BDD is a BDD with the constraint that the variables are ordered and every source-to-sink path in the ordered BDD visits the variables in ascending order. A reduced ordered BDD is an ordered BDD where each node represents a distinct Boolean expression.


## 2.3. Variable Ordering

A variable in a PMS BDD indicates the component that the variable belongs to and the phase in which the component exists. For example,Ci is the state indicator variable of component C at phase i. Variable ordering can be generated in the following steps: component-level ordering and ordering variables on phases.(1)
Component-level ordering: the components in PMS ares-independent from each other. Therefore, the ordering heuristics for ordinary BDD can be applied to component-level ordering for PMS BDD.(2)
Phase ordering: there are two classes of phase ordering: forward ordering and backward ordering. In forward ordering, the variable order is the same as the phase order. In backward ordering, the variable order is the reverse of the phase order.To illustrate the above ordering method, the PMS in Figure1 can be used. Applying DFLM to the fault tree in “do not care” form shown in Figure 2, where phase indexes are unconsidered, the component-level ordering is A < B < C. Extending this component-level ordering over different phase indexes, the forward DFLM ordering is A1 < A2 < A3 < B1 < B2 < B3< C1 < C2 <C3, and the backward DFLM ordering is A3 < A2 < A1 < B3 < B2 < B1 < C3 < C2 < C1.Figure 2
The “do not care” form of the tree in Figure1.


## 2.4. BDD Generation

In order to compute the BDD associated with a Boolean functionF, the following principle is applied:(1)
IfF is a constant, then one associates with F the corresponding sink node 0 or 1.(2)
IfF = x, where x is a variable, then one associates with F the BDD ite (x, 1, 0).(3)
Finally, ifF=G<>H, where <> is the binary connective ∧ or ∨ and G and H are functions, then one computes the BDDs associated with G and H and then performs the operation <> on these two BDDs.Given two Boolean functionsG and H encoded by the BDDs G = ite (x, G1, G0) and H = ite (y, H1, H0), it is possible to compute directly on G and H any logical operation between G and H by means of the following calculation:(2)G⋄H=itex,G1,G0⋄itey,H1,H0=itex,G1⋄H1,G0⋄H0,x=y,itex,G1⋄H,G0⋄H,x<y,itey,G⋄H1,G⋄H0,x>y.Compared with the single-phase system, BDD generation of PMS is much more complex because of the dependencies of component states across the phases. UseG and H to represent phase BDD of phase i and phase j, respectively i<j. When expanded with regard to xi and xj, they, respectively, can be written as G = ite (xi, G1, G0); H = ite (xj, H1, H0).Following special BDD operation, to deal with the cross-phase dependencies associated with the operation <> onG and H,(3)G⋄H=itexi,G1,G0⋄itexj,H1,H0=itexi,G1⋄H1,G0⋄H0,xi=xj,itexj,G⋄H1,G0⋄H0,xj<xi,itexi,G1⋄H1,G0⋄H,xi<xj.With the help of BDD operations (2) and (3), PMS BDD can be generated from PMS fault tree. When different orderings are used, the sizes of PMS BDD are different. As shown in Figure 3, the size of BDD with forward DFLM ordering is 15.Figure 3
PMS BDD with forward DFLM ordering.


## 3. Qualitative Analysis

### 3.1. Cut Set and Minimal Cut Set

In order to introduce formally the notion of minimal cut set, we need the following definitions.Definition 1.
LetX=x1,x2,…,xn be a set of Boolean variables. An assignment of X is a mapping from X into {0, 1}.
Assignment and subset ofX are equivalent objects. A unique assignment σ corresponds to a subset of X, Xσ, where(4)σx=1iffx∈Xσ.Definition 2.
Letσ be an assignment of X and F be a monotonic Boolean function on X.Xσ is a cut if Fσ=1.
The set of cuts ofF is denoted by CSF.Definition 3.
For anyρ∈CSF, ρ is a minimal cut if for any assignment σ,(5)Xσ′⊂ρimplies thatFσ′=0.
The set of minimal cuts ofF is denoted by MCSF.
According to Definition3, the following property holds.Property 1.
LetMCSF be the minimal cut set of F; then(6)MCSF⊆CSF∧∀ρ∈CSF−MCSF,∃δ∈MCSF,δ⊂ρ.Here, set CSF-MCSF includes all the elements in CSF, but not in MCSF.
Let F be the BDD associated withF. Each path from the root of F to sink node 1 corresponds to an assignment σ and defines a cut of F, ρ, as follows: x∈ρ iff the path goes through a node labeled by x and goes out of this node on the T-edge.
The set of cuts encoded byF is denoted by CSF. Due to the fact that F compactly encodes the truth table of F in Shannon’s form by means of subtree sharing, CSF is a cut set of F.
What is more, PMS BDDF is minimal if for any path from the root of F to sink node 1, the cut identified by it is minimal. The set of cuts encoded by minimal F, denoted by MCSF, is still a minimal cut set of F.
Consider the PMS BDD with forward DFLM ordering shown in Figure3. The cut set encoded by this BDD is(7)A1,A2,A3,B1,A3,B2,C1,A3,B3,C2,A3,B2,C3,A3,B3,C1,A3,B3,C3,A3,C1,B1,B2,C1,B2,C2,C1.
According to forward ordering, the following property holds.Property 2.
LetF be a PMS BDD with forward ordering. Then,(8)∀C∈CSF,C∩X=1,where X=x1,x2,…,xn includes all variables relating to component X and n is the maximum of phase number.Proof.
Due to the fact that PMS considered in this paper is not maintained, a component remains down for the remaining phases if it is down in one phase; that is,xj will never appear at the T-edge of node xi.
In the following section, we try to show how to calculate theMCSF from PMS BDD F or CSF.


### 3.2. Inclusive Relation Elimination

LetF = ite (x, F1, F0) be a BDD. If ω is a cut of F0, then ω does not contain x and ω is also a cut of F. If δ is a cut of F1, δ augmented of x, ρ=δUx, is a cut of F. If ρ includes ω, we say that F has inclusive relation between ω and ρ. Notice that ω will never include ρ. More formally, we have the following definition.Definition 4.
LetF be a PMS BDD; F has inclusive relation across different cuts within CSF if ∃ρ1,ρ2∈CSF,ρ1⊂ρ2.
From the point of view of MCS, inclusive relation is one kind of redundancy relation. That is to say, in order to makeCSF be MCS, ρ11 should be dropped.
It is obvious that the cut sets encoded by PMS BDD shown in Figures4 and 5 have inclusive relations across different cuts. For example, A3,C1 is a cut, but its subset C1 is still a cut.
The following theorem gives an inductive principle to eliminate the inclusive relations across cuts.Figure 4
Results of IncRed operation for the PMS BDD in Figure3.Figure 5
Results of ExImpRed operation for the PMS BDD in Figure4.Theorem 1.
LetF = ite (x, F1, F0) be a PMS BDD. Then,(9)IncRedF=ρρ=δ∪x∧δ∈IncRedF1\CSF0∪IncRedF0,where IncRed (F) is the cut set of F which has no inclusive relation across different cuts.Proof.
(10)CSF=ρρ=δ∪x∧δ∈CSF1∪CSF0.
ForCSF0, by eliminating the inclusive relations within it, we obtain IncRed (F0).
ForCSF1, by eliminating the inclusive relations within it, we obtain IncRed (F1).
In order to eliminate the inclusive relations betweenρρ=δ∪x∧δ∈IncRedF1 and CSF0, IncRedF1\CSF0 should be calculated. The without operation “\” is defined in [9] and can remove from IncRed (F1) all those cuts that include a cut of CSF0. For example, if A,B,B,C∈IncRedF1 and A∈CSF0, then A,B∉IncRedF1\CSF0.
According to Theorem1, the following property holds.Property 3.
LetF be a PMS BDD. Then,(11)IncRedFCSF∧∀ρ∈IncRedF−CSF,∃δ∈IncRedF,δ⊂ρ.
Using Theorem1, an operation (IncRed) can be derived to eliminate all the inclusive relations within CSF. Reference [20] has implemented a similar operation called “Minsol” under the context of fault tree analysis of single-phase system. Thus, the operation implementation would not be given here.
As an illustration, IncRed operation is used to transform BDD in Figure3 into the one as shown in Figure 4. The cut set encoded by the PMS BDD shown in Figure 4 is A1,A2,A3,B2,C3,A3,B3,C3,B1,B2,C2,C1.


### 3.3. External-Implication Relation Elimination

LetF=itexi,F1,F0=itexj,G1,G2,i<j, be a PMS BDD with forward ordering. If ρ1 is a cut of G1, ρ1 contains xj and ρ1Uxj is also a cut of F. If ρ2 is a cut of F1, ρ2Uxi is a cut of F. If ρ1 includes ρ2, we say that F has external-implication relation between cut ρ1Uxj and cut ρ2Uxi. More formally, we have the following definition.Definition 5.
LetF be a PMS BDD with forward ordering. F has external-implication relation across different cuts within CSFif∃ρ1,ρ2∈CSF:(12)ρ1∩xi,xj=xi∧ρ2∩xi,xj=xj∧ρ1<=ρ2<∧ρ1<⊇ρ2<,where ρ<=yy∈ρ∧ordery<orderxi. Notice that ρ1,ρ2 will never contain variables within X−xi,xj according to Property 2.
From the point of view of MCS, external-implication relation is one kind of redundancy relation. Notice thatxi implies xj, and xi,xj and xi are equivalent objects. In order to make CSF be MCS, ρ2 should be dropped. Consider the PMS BDD shown in Figure 5. The cut set encoded by this BDD is A1,A2,A3,B2,C3,A3,B3,C3,B1,B2,C2,C1. Due to the external-implication relation, A1 should be eliminated from the cut set, and so does A2,B2,C3.
The following theorem gives an inductive principle to eliminate the external-implication relation across different cuts.Theorem 2.
LetF = ite (xi, F1, F0 = ite (yj, G1, G0)), i < j, be a PMS BDD with forward ordering. Then,(13)ExImpRedF=ρρ=δ∪xi∧δ∈ExImpRedF1∪ExImpRedF0,x≠y,ρρ=δ∪xi∧δ∈ExImpRedF1\CSG1∪ExImpRedF0,x=y,where ExImpRed (F) is the cut set of F which has no external-implication relation across different cuts.Proof.
Two cases are possible:(1)
x≠y. F0 does not contain variables relating to component X.Ifρ is a cut of F, ρ is either a cut of F0 (ρ does not contain xi) or a cut of F1 augmented of xi (ρ only contains one variable xi relating to component X). Thus, there is no external-implication relation relating to xi within the cut set, and we obtain that(14)ρρ=δ∪xi∧δ∈ExImpRedF1∪ExImpRedF0.(2)
x = y. There might be some cuts that have external-implication relation relating to xi.
Ifρ is a cut of F0 and ρ contains xj, ρ is also a cut of F. If δ is a cut of F1, δ augmented of xi is a cut of F. If δ⊇ρ/xj, ρ and δUxi have external-implication relation. That is to say, δ should be eliminated. According to the fact that ρ contains xj, ρ/xj is a cut of G1. Thus, we obtain that(15)ρρ=δ∪xi∧δ∈∈ExImpRedF1\CSG1∪ExImpRedF0.
According to Theorem2, the following property holds.Property 4.
LetF be a PMS BDD with forward ordering. Then,(16)ExImpRedF⊆CSF∧∀ρ∈ExImpRedF−CSF,∃δ∈ExImpRedF,δ⊂Extendρ,where extend operation means adding variables with higher index to a cut. For example, extend A2,B2,C3=A3,A2,B3,B2,C3.
As an illustration, the ExImpRed operation is used to transform BDD in Figure4 into the BDD shown in Figure 5. The cut set encoded by this BDD is A2,A3,B3,C3,B1,B2,C2,C1. This cut set has no external-implication relation across different cuts.


### 3.4. MCS Calculation

Theorem 3.
LetF be a PMS BDD with forward ordering. Then,(17)IncRedF∩ExImpRedF=MCSF.Proof.
We have known thatCSF might have inclusive relations and external-implication relations across the included cuts. According to Property 2, we know that xi and xj will not be simultaneously included by a cut. Thus, there is no internal-implication relation.
According to Theorem2, we know that ExImpRed operation can only eliminate the external-implication relations relating to one component. However, CSF might have external-implication relations relating to more than one component. For example, consider a CSF has two cuts (one is A2,B2 and the other is A1,B1. Notice that xi implies xj and A1,B1,A2,B2 and A1,B1 are equivalent objects. Thus, A1,B1 should be dropped. However, our ExImpRed operation cannot use A2,B2 to eliminate A1,B1. Now, we show that the ExImpRed operation can do this elimination indirectly. If both A2,B2 and A1,B1 belong to CSF, then F must have a structure as shown in Figure 6. There are two points: (1) according to the BDD generation process, B1 will appear at the T-edge of node A2 under the condition that the T-edge of node A1 has a B1 and the T-subBDD of node A2 has a B2; (2) the T-edge of this B1 is 1 due to the fact that A2,B2 is a cut. Thus, A2,B1 must be included by CSF. Now, the ExImpRed operation can use A2,B1 to eliminate A1,B1 and then use A2,B2 to eliminate A2,B1. Thus, our ExImpRed operation can eliminate all kinds of external-implication relations within CSF.
ExImpRed operation eliminates all the external-implication relations from the cut setCSF. However, it will disturb some inclusive relations. For example, consider the PMS BDD F shown in Figure 7, where cut set CSF=A1,A2,B1,C1,A2,B2,C1,B1,C1. After the ExImpRed operation, we get ExImpRedF=A1,A2,B2,C1,B1,C1. Here, the inclusive relation between cut B1,C1 and cut A2,B1,C1 is destroyed. Thus, after another IncRed operation, we get IncRed ExImpRedF=A1,A2,B2,C1,B1,C1 instead of A1,B1,C1, the MCSF.
On the other hand, IncRed operation eliminates all the inclusive relations from the cut setCSF. However, it will disturb some external-implication relations. For the PMS BDD F shown in Figure 7, after the IncRed operation, we get IncRedF=A1,A2,B2,C1,B1,C1. Here, the external-implication relation between cut A2,B1,C1 and cut A2,B2,C1 is destroyed. Thus, after another ExImpRed operation, we get ExImpRed IncRedF=A1,A2,B2,C1,B1,C1 instead of A1,B1,C1, the MCSF.Figure 6
The PMS BDD encodingA2,B2 and A1,B1.Figure 7
An example PMS BDD with forward ordering.


## 3.1. Cut Set and Minimal Cut Set

In order to introduce formally the notion of minimal cut set, we need the following definitions.Definition 1.
LetX=x1,x2,…,xn be a set of Boolean variables. An assignment of X is a mapping from X into {0, 1}.
Assignment and subset ofX are equivalent objects. A unique assignment σ corresponds to a subset of X, Xσ, where(4)σx=1iffx∈Xσ.Definition 2.
Letσ be an assignment of X and F be a monotonic Boolean function on X.Xσ is a cut if Fσ=1.
The set of cuts ofF is denoted by CSF.Definition 3.
For anyρ∈CSF, ρ is a minimal cut if for any assignment σ,(5)Xσ′⊂ρimplies thatFσ′=0.
The set of minimal cuts ofF is denoted by MCSF.
According to Definition3, the following property holds.Property 1.
LetMCSF be the minimal cut set of F; then(6)MCSF⊆CSF∧∀ρ∈CSF−MCSF,∃δ∈MCSF,δ⊂ρ.Here, set CSF-MCSF includes all the elements in CSF, but not in MCSF.
Let F be the BDD associated withF. Each path from the root of F to sink node 1 corresponds to an assignment σ and defines a cut of F, ρ, as follows: x∈ρ iff the path goes through a node labeled by x and goes out of this node on the T-edge.
The set of cuts encoded byF is denoted by CSF. Due to the fact that F compactly encodes the truth table of F in Shannon’s form by means of subtree sharing, CSF is a cut set of F.
What is more, PMS BDDF is minimal if for any path from the root of F to sink node 1, the cut identified by it is minimal. The set of cuts encoded by minimal F, denoted by MCSF, is still a minimal cut set of F.
Consider the PMS BDD with forward DFLM ordering shown in Figure3. The cut set encoded by this BDD is(7)A1,A2,A3,B1,A3,B2,C1,A3,B3,C2,A3,B2,C3,A3,B3,C1,A3,B3,C3,A3,C1,B1,B2,C1,B2,C2,C1.
According to forward ordering, the following property holds.Property 2.
LetF be a PMS BDD with forward ordering. Then,(8)∀C∈CSF,C∩X=1,where X=x1,x2,…,xn includes all variables relating to component X and n is the maximum of phase number.Proof.
Due to the fact that PMS considered in this paper is not maintained, a component remains down for the remaining phases if it is down in one phase; that is,xj will never appear at the T-edge of node xi.
In the following section, we try to show how to calculate theMCSF from PMS BDD F or CSF.


## 3.2. Inclusive Relation Elimination

LetF = ite (x, F1, F0) be a BDD. If ω is a cut of F0, then ω does not contain x and ω is also a cut of F. If δ is a cut of F1, δ augmented of x, ρ=δUx, is a cut of F. If ρ includes ω, we say that F has inclusive relation between ω and ρ. Notice that ω will never include ρ. More formally, we have the following definition.Definition 4.
LetF be a PMS BDD; F has inclusive relation across different cuts within CSF if ∃ρ1,ρ2∈CSF,ρ1⊂ρ2.
From the point of view of MCS, inclusive relation is one kind of redundancy relation. That is to say, in order to makeCSF be MCS, ρ11 should be dropped.
It is obvious that the cut sets encoded by PMS BDD shown in Figures4 and 5 have inclusive relations across different cuts. For example, A3,C1 is a cut, but its subset C1 is still a cut.
The following theorem gives an inductive principle to eliminate the inclusive relations across cuts.Figure 4
Results of IncRed operation for the PMS BDD in Figure3.Figure 5
Results of ExImpRed operation for the PMS BDD in Figure4.Theorem 1.
LetF = ite (x, F1, F0) be a PMS BDD. Then,(9)IncRedF=ρρ=δ∪x∧δ∈IncRedF1\CSF0∪IncRedF0,where IncRed (F) is the cut set of F which has no inclusive relation across different cuts.Proof.
(10)CSF=ρρ=δ∪x∧δ∈CSF1∪CSF0.
ForCSF0, by eliminating the inclusive relations within it, we obtain IncRed (F0).
ForCSF1, by eliminating the inclusive relations within it, we obtain IncRed (F1).
In order to eliminate the inclusive relations betweenρρ=δ∪x∧δ∈IncRedF1 and CSF0, IncRedF1\CSF0 should be calculated. The without operation “\” is defined in [9] and can remove from IncRed (F1) all those cuts that include a cut of CSF0. For example, if A,B,B,C∈IncRedF1 and A∈CSF0, then A,B∉IncRedF1\CSF0.
According to Theorem1, the following property holds.Property 3.
LetF be a PMS BDD. Then,(11)IncRedFCSF∧∀ρ∈IncRedF−CSF,∃δ∈IncRedF,δ⊂ρ.
Using Theorem1, an operation (IncRed) can be derived to eliminate all the inclusive relations within CSF. Reference [20] has implemented a similar operation called “Minsol” under the context of fault tree analysis of single-phase system. Thus, the operation implementation would not be given here.
As an illustration, IncRed operation is used to transform BDD in Figure3 into the one as shown in Figure 4. The cut set encoded by the PMS BDD shown in Figure 4 is A1,A2,A3,B2,C3,A3,B3,C3,B1,B2,C2,C1.


## 3.3. External-Implication Relation Elimination

LetF=itexi,F1,F0=itexj,G1,G2,i<j, be a PMS BDD with forward ordering. If ρ1 is a cut of G1, ρ1 contains xj and ρ1Uxj is also a cut of F. If ρ2 is a cut of F1, ρ2Uxi is a cut of F. If ρ1 includes ρ2, we say that F has external-implication relation between cut ρ1Uxj and cut ρ2Uxi. More formally, we have the following definition.Definition 5.
LetF be a PMS BDD with forward ordering. F has external-implication relation across different cuts within CSFif∃ρ1,ρ2∈CSF:(12)ρ1∩xi,xj=xi∧ρ2∩xi,xj=xj∧ρ1<=ρ2<∧ρ1<⊇ρ2<,where ρ<=yy∈ρ∧ordery<orderxi. Notice that ρ1,ρ2 will never contain variables within X−xi,xj according to Property 2.
From the point of view of MCS, external-implication relation is one kind of redundancy relation. Notice thatxi implies xj, and xi,xj and xi are equivalent objects. In order to make CSF be MCS, ρ2 should be dropped. Consider the PMS BDD shown in Figure 5. The cut set encoded by this BDD is A1,A2,A3,B2,C3,A3,B3,C3,B1,B2,C2,C1. Due to the external-implication relation, A1 should be eliminated from the cut set, and so does A2,B2,C3.
The following theorem gives an inductive principle to eliminate the external-implication relation across different cuts.Theorem 2.
LetF = ite (xi, F1, F0 = ite (yj, G1, G0)), i < j, be a PMS BDD with forward ordering. Then,(13)ExImpRedF=ρρ=δ∪xi∧δ∈ExImpRedF1∪ExImpRedF0,x≠y,ρρ=δ∪xi∧δ∈ExImpRedF1\CSG1∪ExImpRedF0,x=y,where ExImpRed (F) is the cut set of F which has no external-implication relation across different cuts.Proof.
Two cases are possible:(1)
x≠y. F0 does not contain variables relating to component X.Ifρ is a cut of F, ρ is either a cut of F0 (ρ does not contain xi) or a cut of F1 augmented of xi (ρ only contains one variable xi relating to component X). Thus, there is no external-implication relation relating to xi within the cut set, and we obtain that(14)ρρ=δ∪xi∧δ∈ExImpRedF1∪ExImpRedF0.(2)
x = y. There might be some cuts that have external-implication relation relating to xi.
Ifρ is a cut of F0 and ρ contains xj, ρ is also a cut of F. If δ is a cut of F1, δ augmented of xi is a cut of F. If δ⊇ρ/xj, ρ and δUxi have external-implication relation. That is to say, δ should be eliminated. According to the fact that ρ contains xj, ρ/xj is a cut of G1. Thus, we obtain that(15)ρρ=δ∪xi∧δ∈∈ExImpRedF1\CSG1∪ExImpRedF0.
According to Theorem2, the following property holds.Property 4.
LetF be a PMS BDD with forward ordering. Then,(16)ExImpRedF⊆CSF∧∀ρ∈ExImpRedF−CSF,∃δ∈ExImpRedF,δ⊂Extendρ,where extend operation means adding variables with higher index to a cut. For example, extend A2,B2,C3=A3,A2,B3,B2,C3.
As an illustration, the ExImpRed operation is used to transform BDD in Figure4 into the BDD shown in Figure 5. The cut set encoded by this BDD is A2,A3,B3,C3,B1,B2,C2,C1. This cut set has no external-implication relation across different cuts.


## 3.4. MCS Calculation

Theorem 3.
LetF be a PMS BDD with forward ordering. Then,(17)IncRedF∩ExImpRedF=MCSF.Proof.
We have known thatCSF might have inclusive relations and external-implication relations across the included cuts. According to Property 2, we know that xi and xj will not be simultaneously included by a cut. Thus, there is no internal-implication relation.
According to Theorem2, we know that ExImpRed operation can only eliminate the external-implication relations relating to one component. However, CSF might have external-implication relations relating to more than one component. For example, consider a CSF has two cuts (one is A2,B2 and the other is A1,B1. Notice that xi implies xj and A1,B1,A2,B2 and A1,B1 are equivalent objects. Thus, A1,B1 should be dropped. However, our ExImpRed operation cannot use A2,B2 to eliminate A1,B1. Now, we show that the ExImpRed operation can do this elimination indirectly. If both A2,B2 and A1,B1 belong to CSF, then F must have a structure as shown in Figure 6. There are two points: (1) according to the BDD generation process, B1 will appear at the T-edge of node A2 under the condition that the T-edge of node A1 has a B1 and the T-subBDD of node A2 has a B2; (2) the T-edge of this B1 is 1 due to the fact that A2,B2 is a cut. Thus, A2,B1 must be included by CSF. Now, the ExImpRed operation can use A2,B1 to eliminate A1,B1 and then use A2,B2 to eliminate A2,B1. Thus, our ExImpRed operation can eliminate all kinds of external-implication relations within CSF.
ExImpRed operation eliminates all the external-implication relations from the cut setCSF. However, it will disturb some inclusive relations. For example, consider the PMS BDD F shown in Figure 7, where cut set CSF=A1,A2,B1,C1,A2,B2,C1,B1,C1. After the ExImpRed operation, we get ExImpRedF=A1,A2,B2,C1,B1,C1. Here, the inclusive relation between cut B1,C1 and cut A2,B1,C1 is destroyed. Thus, after another IncRed operation, we get IncRed ExImpRedF=A1,A2,B2,C1,B1,C1 instead of A1,B1,C1, the MCSF.
On the other hand, IncRed operation eliminates all the inclusive relations from the cut setCSF. However, it will disturb some external-implication relations. For the PMS BDD F shown in Figure 7, after the IncRed operation, we get IncRedF=A1,A2,B2,C1,B1,C1. Here, the external-implication relation between cut A2,B1,C1 and cut A2,B2,C1 is destroyed. Thus, after another ExImpRed operation, we get ExImpRed IncRedF=A1,A2,B2,C1,B1,C1 instead of A1,B1,C1, the MCSF.Figure 6
The PMS BDD encodingA2,B2 and A1,B1.Figure 7
An example PMS BDD with forward ordering.


## 4. Application

With edge, compute and storage systems reside at the edge as well, as close as possible to the component, device, application, or human that produces the data being processed. The purpose is to remove processing latency, because the data need not be sent from the edge of the network to a central processing system and then back to the edge.The applications for edge make sense: Internet of things-connected devices are a clear use for edge computing architecture. With remote sensors installed on a machine, component, or device, they generate massive amounts of data. If that data is sent back across a long network link to be analyzed, logged, and tracked, that takes much more time than if the data is processed at the edge, close to the source of the data.There are patterns of failure. (1) If you place too much at the edge, it is easy to overwhelm the smaller processor and storage platforms that exist there. In some cases, storage could be limited to a few gigabytes and processing using a single CPU. Power and size restrictions are really what set the limits. (2) Another pattern is failure to integrate security from concept to production. Security is systemic to edge computing architectures and centralized processing. Security needs to span both and use mechanisms such as identity and access management. Encryption is not a nice-to-have, but rather a requirement for device safety.Consider a benchmark MEC PMS borrowed from [21]. This MEC PMS has the following:(1)
It has 7 groups of components.(2)
Each group has 5 components.(3)
Five MEC node configurations are shown in Figure8.(4)
Four MEC service configurations are listed in Table1.Figure 8
Five MEC node configurations.
(a)(b)(c)(d)(e)Table 1
Four MEC service configurations.
NamePhase numberConfigurationM12A, EM23A, B, EM34A, B, C, EM45A, B, C, D, EUsing Theorem 4, MCS is calculated with forward ordering. The results are shown in Table2. Here, we only present the numbers of cuts in the set CS [Mi], IncRed (Mi), ExImpRed (Mi), and IncRed (Mi) ∩ ExImpRed (Mi). From the results in Table 2, the following conclusions can be derived: (1) Different phase combination will result in different sizes of cut sets. Some more complex combination may have smaller cut sets as illustrated by M3 and M4. (2) For the MCS calculation IncRed ∩ ExImpRed of this PMS, forward ordering can generate extremely smaller cut sets for the intermediate BDD operations compared with the original CS.Table 2
Results of MCS calculation for PMS BDD with forward ordering.
MissionCSMiExImpRedMiIncRedMiIncRedMi∩ExImpRedMiM1339966110449227994378132M21095740345802547194429578307M3161672467060025676822289081432M412246650261213743021795344281682


## 5. Conclusion

Based on the mobile edge computing techniques, commercial service providers, such as video content providers, can benefit from low-latency edge resources to provide their users with more efficient service acquisition, thereby improving the quality of experience [22–24]. Compared with single-phase systems, fault tree analysis of MEC PMS is much more complex, because of the dependencies across the phases.The analysis to be performed on a fault tree can be either qualitative or quantitative. For the qualitative fault tree analysis of PMS by means of BDD, no much related work can be found. In this paper, we have presented some efficient methods to calculate the MCS encoding by a PMS BDD. The basic idea is to eliminate different kinds of redundancy relations from a cut set encoding by a PMS BDD. These methods are based on several BDD operations, such as IncRed and ExImpRed. The IncRed can eliminate all inclusive relations. The ExImpRed can eliminate all external-implication relations. Using some proper combinations of these operations, MCS can be calculated correctly.Smart city is a fast-developing system enabled by the Internet of things (IoT) with massive collaborative services (e.g., intelligent transportation and collaborative diagnosis) [25, 26]. Therefore, one direction of our future work is to consider the qualitative analysis of commercial services in MEC smart city. As an extension of this research work, we will also improve the presented BDD-based analysis methodology for more generalized MEC service systems [27].



---

*Source: 8823952-2020-10-12.xml*