Min-Sheng Lin and Deng-Jyi Chen
Institute of Computer Science and Information Engineering
National Chiao-Tung University
Hsin Chu, Taiwan, R.O.C. 30050
This paper proposes two algorithms for computing the reliability of a Distributed Computing System (DCS). The first algorithm, called MFST-NRT (Minimal File Spanning Trees with No Replicated Trees), guarantees that no replicated file spanning trees are generated during the tree (or subgraph) expansion process. The second algorithm, called FREA (Fast Reliability Evaluation Algorithm), is based on the extended gactoring theorem with several incorporated reliability-preserving reductions to speedup reliabilty evaluation. Based on a comparison of the number of trees (subgraphs) generated as the algorithm proceeds, our algorithms are more economic in both time and space than are existing algorithms.
Keywords: distributed program, distributed system, graph theory, reliability, spanning tree, factoring theorem, reliability-preserving reduction
Received October 15, 1991; revised Juy 20, 1992.
Communicated by Jhing-Fa Wang.
* This research work is supported in part by the National Science Council, Taiwan, R.O.C. under the contract # NSC-80-0408-E009-39 and in part by the Chung-Shan Institute of Science and Technology under contract #CS80-0210-D009-33.