标题: | RELIABILITY-ANALYSIS OF DISTRIBUTED SYSTEMS BASED ON A FAST RELIABILITY ALGORITHM |
作者: | CHEN, DJ HUANG, TH 交大名義發表 資訊工程學系 National Chiao Tung University Department of Computer Science |
关键字: | DISTRIBUTED PROGRAM RELIABILITY (DPR);DISTRIBUTED SYSTEM RELIABILITY (DSR);GRAPH THEORY;FILE SPANNING TREE (FST);SPANNING TREE;RELIABILITY |
公开日期: | 1-三月-1992 |
摘要: | The reliability of distributed processing system (DPS) can be expressed by the analysis of distributed program reliability (DPR) and distributed system reliability (DSR). One of the good approaches to formulate these reliability performance indexes is to generate all disjoint File Spanning Trees (FST's) in the DPS graph such that the DPR and DSR can be expressed by the probability that at least one of these FST's is working. In this paper, we present a unified algorithm to efficiently generate disjoint FST's by cutting different links and compute the DPR and DSR based on a simple and consistent union operation on the probability space of the FST's. The DPS reliability related problems are also discussed in this paper. These include 1) the reliability of more than one copy of programs running on a given DPS starting from different sites, 2) the reliability of a specified program running on a given DPS starting from different sites, 3) the reliability of more than one different programs running on a given DPS, and so on. For speeding up the reliability evaluation, nodes merged, series, and parallel reduction concepts are incorporated in the algorithm. Based on the comparison of number of subgraphs (or FST's) generated by the proposed algorithm and by existing evaluation algorithms, we conclude that the proposed algorithm is much more economic in terms of time and space than the existing algorithms. |
URI: | http://dx.doi.org/10.1109/71.127256 http://hdl.handle.net/11536/3500 |
ISSN: | 1045-9219 |
DOI: | 10.1109/71.127256 |
期刊: | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS |
Volume: | 3 |
Issue: | 2 |
起始页: | 139 |
结束页: | 154 |
显示于类别: | Articles |
文件中的档案:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.