Dependability Analysis of Distributed Computer Systems with Imperfect Coverage

In this paper, a new algorithm based on Binary Decision Diagram (BDD) for dependability analysis of distributed computer systems (DCS) with imperfect coverage is proposed. Minimum file spanning trees (MFST) are generated and stored via BDD maniplution. By using the multistate concepts, the algorithms for BDD generation and evaluation that can deal with imperfect coverage are given. Due to the nature of BDD, the sum of disjoint products (SDP) can be implicitly represented by BDD, which avoids huge storage and high computation complexity for large system. Several examples are given to show the efficiency of this algorithm. Index Terms: Distributed Computer System (DCS), Minimum File Spanning Tree (MFST), Imperfect Coverage, Multistate Component, Reliability Evaluation, Binary Decision Diagram (BDD) This research was supported in part by the National Science Foundation under Grant No. EEC9418765, and by the Department of Defense as an enhancement project to the Center for Advanced Comp..