CAREL - COMPUTER-AIDED RELIABILITY EVALUATOR FOR DISTRIBUTED COMPUTING NETWORKS

This paper presents an efficient method to compute the terminal reliability (the probability of communication between a pair of nodes) of a distributed computing system (DCS). We assume that the graph model G(V, E) for DCS is given. Also, it is assumed that we have path and/or cut information for the network G(V, E). Boolean algebraic concepts are used to define four operators namely, COMpare, REDuce, CoMBine, and GENerate. The proposed method, henceforth called CAREL (Computer Aided RELiability evaluator), uses these four operators to generate exclusive and mutually disjoint (e.m.d.) events, and hence the terminal reliability expression. Examples illustrating the technique are given in the text. We have implemented CAREL using bit vector representation [11] on Encore MULTIMAX 320 system. CAREL solves large DCS networks (having pathset of the order of 780 and cutset of the order of 7300 or more) with reasonable memory requirement. A comparison with existing algorithms reveals the computational efficiency of the proposed method. The proof of correctness of CAREL is included in the Appendix.