NASA Contractor Report 178008

NASA-CR-178008

19860005577

;J.

SYNTHETIC BOUNDS' FOR SEMI-MARKOV

RELIABILITY MODELS

Allan L. White

PRC Kentron, Inc.

Aerospace Technologies Division

Hampton, Virginia 23666

Contract NASl-18000

November 1985

,

j.

NI\S/\

National Aeronautics and

Space Administration

Langley Research Genter

Hampton,Virginia 23665

",o.MPTON, VIRGINIA

INTRODUCTION

We derive upper and lower bounds for the probabilityof failure for

systems that achieve high reliabilitywith architecturesthat use redundancy

and reconfiguration. The engineeringassumptionsare that individual

componentsfail independentlyat a low constant rate and that the system

quickly recoversfrom all faults. The mathematicalassumptionis that the

process of componentfailure and system recoverycan be representedby a

semi-Markovmodel where competingevents are stochasticallyindependent. The

bounds are syntheticin the sense that descriptionsof componentfailure and

system recoveryare obtainedfrom differentsources. The reliabilitymodel is

constructed(synthesized)under the assumptionthat the processesare

independent.

UPPER AND LOWER BOUNDS

Figure 1 displaysa general path in a reliabilitymodel that begins at an

initial fault-freestate and ends at an absorbingsystem-failurestate. The

global time-independenceof a semi-Markovmodel permits the rearrangementof

states on the path for notationaland computationalconvenience. In the first

line of figure 1, successfulfault transitionsthat have rate xk compete

I with fault transitionsthat have rate Yk- In the second line, successful

recoverytransitionsthat have generalizeddensity dFi,_ compete with other

t

recoverytransitionsdFi,z,...,dFi,biand fault occurrences€i. In

the third line, successfulfault occurrencesaj competewith recovery

transitionsdGj,l,...,dGj,cjand other fault occurrencesBj. For

notation

A/7-/ oy7
D(T) = Probabilityof traversingthe path in figure 1 by time T

p(Fi) = Probabilitythe transitiondFi,I is successfulwhen competing

against other recovery transitions

= 0f [I - Fi,z(t)]...[l- Fi,bi(t)]dFi,i(t)

m1(Fi) = First conditionalmoment of dFi,I

: p--_;O_ t [I - Fi •z(t)].. ""[1 - Fi 'bi(t)] dFi, l(t)

mz(Fi) = Second conditionalmoment of dFi,i

: _1 of tz [I - Fi,z(t)]...[1- Fi,bi(t)ldFi,l(t)

m1(Cj) = First moment of the holdingtime in state Cj consideringonly the

recoverytransitions

: 0f [1 - Gj,1(t)]...[1- Gj,cj(t)]dt

mz(Cj) = Second moment of the holding time in state Cj consideringonly

the recovery transitions

_ o

: 2 oft [1 - Gj,1(t)]...[1- Gj,c.(t)] J dt.

2
There is a relationship between the moments of a holding time for a state and

the conditional moments of the transition functions given by

, mi(Cj) : _J p ) mi

{:1 (Gj,_ (Gj,{)

where p(Gj,_) and mi(Gj,{) are defined just as the probabilitiesand

moments for the F's are.

Continuingto developingthe notation,figure 2 displaysthe constant

rate part of the path in figure 1. Let

E(T) = Probabilityof traversingthe path in figure 2 by time T.

Let V = T - r_ - ... - rm - s_ - ... - sn where

ri = [mi(Fi)jI/2

s i = [m,(Cj)jl/2

We assume r_ +...+ rm + s_ +,,,+ sn < T.
The proof of the assertionsbelow uses the elementaryfacts that if H is

a distributionsuch that H(O-) = 0 then

w

I [Z-H(t)dt] = mz(H)

0

" mz(H)

I tLZ-H(t)dt]=T 0

GO

mz(H)

1-H(c) = f dH(t) < _ for c > 0 (Markov'sinequality)

C _ c z

Theorem With the notation and assumptionsas above

m mz(Fi)j

E(V)i=1II P(Fi) [I - cimz(F) -

n + Bj)mz(Cj) )

H aj _(cj)L1- (_j) mz(Cj

j=l 2m1(Cj [m_(Cj)] '3/2J

< D(T)

m n

< E(T)II P(Fi) II _j mz(Cj)

-- i=1 j=1
proposition

- -_ixi

(i) IO e [l"Fi,z(xi)J'"[l"Fi,bi(XidF)Ji_ L (x. i)< P(Fi)

W

' (Ii)01_j e-_jyje'Bjyj[1 - Gj,i(yj)]...[1- Gj,cj(yj)]dyj<__jm1(Cj)

J

• -€.X i

(iii)_I e

0 [1 - Fi•z(xi)]...[1- Fi,bi(xi)] dFi 1(xi)

mz(Fi)

>p(F i) [1 - €i mi(Fi) ----_zj

ri

._i/ (iv)_J _j e"_jyje-Bjyj[1 - Gj,1(yj)]...[1- Gj,cj(yj)]dyj

aJm1(CJ)L1 (aj+Bj)mz(Cj) mz(Cj)

_-- 2mi(Cj) sjm_(Cj)"j

Proof of the proposition

Assertions(i)and (ii)followfromthe inequalitye-a < 1 for a > O.
Assertions (iii) and (iv) require more work and use the equation

f = f - _ and the inequalities1-a < e-a < 1 for a > O.

0 0 c

|

To prove (iii) note that the integralis bigger than or equal to

(1 - cixi)ll - Fi,z(xi)J...ll- Fi,bi(xi)JdFi 1(xi) 0 '

- _ [1 - Fi,z(xi)]...[1- Fi,bi(Xi)]dFi,1(xi)

r i

which is biggerthanor equalto

mz(Fi)

p(Fi) - ciP(Fi) m1(Fi) - P(Fi)

ri

when the last integral is replacedby Markov'sinequality.

To prove (iv) note that the integralis bigger than or equal to

(1-(_j+ Bj)yj)[1- Gj,I(yj)J...[1- Gj,cj(Yj)Jdyj ,
w

• - aj _j[1 _ Gj,i(yj)]...[1- Gj,cj(Yj)]dyj.

The integrandin the last integralis equal to one minus the probabilityof

being in state Cj at time yj and by Markov's inequalityis less than or

(cj)

equal to 2

Yj

Hence (iv) is bigger than or equal to

_j(_j + Bj) mz(Cj) _jm_(Cj)

_jm_(Cj)- 2 sj

Proof of the theorem

Let q(t) be the density function for traversingthe path in figure 2 by

time t.

The probabilityof reachingstateD in figure1 beforetimeT is

T

D(T) = S q(t)

0

T-t -clx_

• f e [I - Fx,z(x,)J...[-zFx,b1(Xl)]

0 _

T-t-x1-. -xm. -

.0/. " x eCmXmL1- Fm'z(Xm)] "'"L1" Fm,bm(Xm)]
T-t-xI-.•--xm "(aL+131)YI

0I e [I - G_,_(yl)]...[l. G1,c,(y,)]

i

T-t-x, "( an+Bn)Yn

i """Yn-i a e [1 )1 [1 -

0 n " Gn,i(Yn "'" Gn,cn(Yn)]

dYn...dY_ dFm,l(Xm)...dFl,l(x l) dt

Working with just the limits of integration

Vi_ I ...... _m) I )n _<D(T)_<Ti=i-.. --i i ..- ®i •

O0 0 0 0 O0 O0 0

The theorem is proved by applyingthe inequalitiesin the propositionto the

integralsin the above inequalityfor D(T).

CONCLUDINGREMARKS

A new method for bounding the probabilityof enteringan absorbing

state of a semi-Markovmodel has been presented. The method is based on

a path analysis of the model, and reduces the calculationof an absorbing

state probabilityto a single algebraiccomputation. The bounds are typically

close and consequentlyrepresenta practicalsolutionto the analysisof a

class of semi-Markovreliabilitymodels.

8
dFmml

_l dFl'l _ dF2, !

i !

! !

,b ,b2

FigureI: GeneralPathin a Semi-MarkovModel

9
Figure 2: ConstantRate Part of the Path

10



Standard Bibliographic Page

1. Report No. 12. Government Accession No. 3. Recipient's Catalog No.

NASA CR-178008

4. Title and Subtitle 5. Report Date

Synthetic Bounds for Semi-Markov Reliability Models November 1985

6. Performing Organization Code

7. Author(s) 8. Performing Organization Report No.

All an L. White

9. Performing Organization Name and Address 10. Work Unit No.

PRC Kentron, Inc.

Aerospace Technologies Division 11. Contract or Grant No.

3221 N. Armistead Avenue NASl-180DO Hampton, VA 23666

13. Type of Report and Period Covered 12. Sponsoring Agency Name and Address Contractor Report National Aeronautics and Space Administration 14. Sponsoring Agency Code Washington, DC 20546 505-34-13-33

15. Supplementary Notes

Langley Technical Monitor: Charles W. Meissner, Jr.

16. Abstract

Upper and lower bounds are derived for the probability of failure for a class of

highly reliable process control computers. The bounds are synthetic in the sense

that the descriptions of component failure and system recovery are assumed to be

obtained from different sources. The reliability model is constructed under the

assumption that the processes are independent.

17. Key Words (Suggested by Authors(s» 18. Distribution Statement

Reliability estimation Unclassified - Unlimited

Fault-tolerant computers Subject Category 66

19. Security Classif.(of this report) 120. Security Classif.(of this page) 21. N

1

0

i

of Pages 122. ~~2

Unclassified Unclassified .

For sale by the National Technical Information Service, Springfield, Virginia 22161

NASA Lanllley Form 63 (June 1985)

•

&

t'