A failure-distance based method to bound the reliability of non-repairablefault-tolerant systems without the knowledge of minimal cuts

CTMC (continuous-time Markov chains) are a commonly used formalism for mode ling fault-tolerant systems. One of the major drawbacks of CTMC is the well -known state-space explosion problem. This paper develops and analyzes a me thod (SC-BM) to compute bounds for the reliability of nonrepairable fault-t olerant systems in which only a portion of the state space of the CTMC is g enerated. SC-BM uses the failure distance concept as the method described i n [1] but, unlike that method, which is based on the computation of exact f ailure distances, SC-BM uses lower bounds for failure distances, which are computed on the system fault-tree, avoiding the computation and holding of all minimal cuts as required in [1], This is important because computation of all minimal cuts is NP-hard and the number of minimal cuts can be very l arge. In some cases SC-BM gives exactly the same bounds as the method in [1 ]; in other cases it gives less tight bounds. SC-BM computes tight bounds f or the reliability of quite complex systems with an affordable number of ge nerated states for short to quite large mission times. The analysis of seve ral examples seems to show that the bounds obtained by SC-BM appreciably ou tperform those obtained by simpler methods, e.g,, [2], and, when they are n ot equal, are only slightly worse than the bounds obtained by the method in [1], In addition, the overhead in CPU time due to computing lower bounds f or failure distances seems to be reasonable.