Efficient algorithms for reliability analysis of distributed computing systems

作     者：Lin, MS Chang, MS Chen, DJ 

作者机构：Tamsui Oxford Univ Coll Dept Informat Management Taipei 25103 Taiwan Natl Chiao Tung Univ Dept Comp Sci & Informat Engn Hsinchu 30050 Taiwan 

出 版 物：《INFORMATION SCIENCES》 (信息科学)

年 卷 期：1999年第117卷第1-2期

页      面：89-106页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：distributed computing systems distributed program reliability computational complexity algorithms 

摘      要：A distributed computing system is modeled as a collection of resources (e.g. processing elements, data tiles and programs) interconnected via an arbitrary communication network and controlled by a distributed operating system, The distributed program reliability in a distributed computing system is the probability of successful execution of a program running on multiple processing elements and needs to retrieve data files from other processing elements. This reliability varies according to (1) the topology of the distributed computing system, (2) the reliability of the communication edges, (3) the data files and programs distribution among processing elements and (4) the data files required to execute a program. In addition, computing the reliability of distributed computing systems is #P-complete even when the distributed computing system is restricted to a series-parallel, a 2-tree, a tree, or a star structure. This paper presents efficient algorithms for computing the reliability of a distributed program running on other restricted classes of networks. (C) 1999 Elsevier Science Inc. All rights reserved.