The computational complexity of the reliability problem on distributed systems

被引：35

作者：

Lin, MS ^{[1
]}

Chen, DJ ^{[1
]}

机构：

[1] NATL CHIAO TUNG UNIV,INST COMP SCI & INFORMAT ENGN,HSINCHU 30050,TAIWAN

来源：

INFORMATION PROCESSING LETTERS | 1997年 / 64卷 / 03期

关键词：

distributed systems; distributed program reliability; computational complexity; graph theory;

D O I：

10.1016/S0020-0190(97)00150-6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The reliability of a distributed program in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to communicate with other processing elements for remote data files will be executed successfully. This reliability varies according to (1) the topology of the distributed computing system, (2) the reliability of the communication links, (3) the data files and program distribution among processing elements, and (4) the data files required to execute a program. This paper shows that solving this reliability problem is NP-hard even when the distributed computing system is restricted to a series-parallel, a 2-tree, a tree, or a star structure. (C) 1997 Elsevier Science B.V.

引用

页码：143 / 147

页数：5

共 20 条

[1]

AGGRAWAL KK, 1981, IEEE T RELIAB, V30, P32

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3] RELIABILITY COVERING PROBLEMS [J].

BALL, MO ;

PROVAN, JS ;

SHIER, DR .

NETWORKS, 1991, 21 (03) :345-357

[4]

Chen D.J., 1993, IEEE T COMPUT, V15

[5] RELIABILITY-ANALYSIS OF DISTRIBUTED SYSTEMS BASED ON A FAST RELIABILITY ALGORITHM [J].

CHEN, DJ ;

HUANG, TH .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1992, 3 (02) :139-154

[6]

ENSLOW P, 1978, COMPUTER, V11

[7]

GARCIAMOLINA J, 1982, IEEE COMPUT, V16, P34

[8]

GRNAROV A, 1981, 1981 P INT C PAR PRO, P79

[9] ON COMPUTER-COMMUNICATION NETWORK RELIABILITY UNDER PROGRAM EXECUTION CONSTRAINTS [J].

KUMAR, A ;

RAI, S ;

AGRAWAL, DP .

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 1988, 6 (08) :1393-1400

[10] DISTRIBUTED PROGRAM RELIABILITY-ANALYSIS [J].

KUMAR, VKP ;

HARIRI, S ;

RAGHAVENDRA, CS .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1986, 12 (01) :42-50

← 1 2 →