Dependability & Maintainability
Theory and Methods
4. State Enumeration
Andrea Bobbio
Dipartimento di Informatica
Università del Piemonte Orientale, “A. Avogadro”
15100 Alessandria (Italy)
[email protected] http://www.mfn.unipmn.it/~bobbio/IFOA/
A. Bobbio
IFOA, Reggio
Emilia,
June 2003
17-18, 2003
Reggio Emilia,
June 17-18,
1
State space
Consider a system with n binary components.
We introduce an indicator variable x i :
1 component i up
x i=
0 component i down
The state of the system can be identified as a
vector x = (x 1, x 2, . . . . , x n ) .
The state space  (of cardinality 2 n ) is the set of
all the possible values of x.
A. Bobbio
Reggio Emilia, June 17-18, 2003
2
2-component system
A. Bobbio
Reggio Emilia, June 17-18, 2003
3
3-component system
A. Bobbio
Reggio Emilia, June 17-18, 2003
4
Characterization of system states
The system has a binary behavior.
We introduce an indicator variable for the system y:
1 system up
y = 0 system down
For each state s   corresponding to a single
value of the vector x = (x 1, x 2, . . . . , x n ) .
1 system up
y =  (x)= 0 system down
y =  (x) is the structure function
Characterization of system states
The structure function y =  (x) depends on the
system configuration
The state space  can be partitioned in 2 subsets:
A1
A2
2-component system
A1
A2
A. Bobbio
Reggio Emilia, June 17-18, 2003
7
3-component system
a)
A1
A3
A2
b)
A1
A2
A3
A. Bobbio
Reggio Emilia, June 17-18, 2003
8
State probability
Define:
Pr{x i(t) = 1} = R i (t)
Pr{x i(t) = 0} = 1 - R i (t)
Suppose components are statistically independent;
The probability of the system to be in a given state
x = (x 1, x 2, . . . . , x n ) at time t is given by the
product of the probability of each individual
component of being up or down.
P {x(t)} = Pr{x 1(t)} · Pr{x 2(t)} · … ·Pr{x n(t)}
A. Bobbio
Reggio Emilia, June 17-18, 2003
9
A1
2-component system
A1
A2
A2
A. Bobbio
Reggio Emilia, June 17-18, 2003
10
3-component system
A. Bobbio
Reggio Emilia, June 17-18, 2003
11
Dependability measures
A. Bobbio
Reggio Emilia, June 17-18, 2003
12
Dependability measures
A. Bobbio
Reggio Emilia, June 17-18, 2003
13
2-component series system
A1
A. Bobbio
Reggio Emilia, June 17-18, 2003
A2
14
2-component parallel system
A1
A2
A. Bobbio
Reggio Emilia, June 17-18, 2003
15
3-component system
a)
A1
A3
A2
b)
A1
A2
A3
A. Bobbio
Reggio Emilia, June 17-18, 2003
16
A1
Voter
A2
A3
3-component system
2:3A. majority
voting
Bobbio
Reggio Emilia, June 17-18, 2003
17
5
component
systems
A. Bobbio
Reggio Emilia, June 17-18, 2003
18
Non series-parallel systems
with 5 components
A1
Independent identically
distributed components
A. Bobbio
Reggio Emilia, June 17-18, 2003
A4
A2
A3
A5
19