标题: The computational complexity of the reliability problem on distributed systems
作者: Lin, MS
Chen, DJ
资讯科学与工程研究所
Institute of Computer Science and Engineering
关键字: distributed systems;distributed program reliability;computational complexity;graph theory
公开日期: 14-十一月-1997
摘要: 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.
URI: http://hdl.handle.net/11536/190
ISSN: 0020-0190
期刊: INFORMATION PROCESSING LETTERS
Volume: 64
Issue: 3
起始页: 143
结束页: 147
显示于类别:Articles


文件中的档案:

  1. A1997YJ57400006.pdf

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.