Title: Efficient algorithms for reliability analysis of distributed computing systems
Authors: Lin, MS
Chang, MS
Chen, DJ
資訊工程學系
Department of Computer Science
Keywords: distributed computing systems;distributed program reliability;computational complexity;algorithms
Issue Date: 1-Jul-1999
Abstract: 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.
URI: http://dx.doi.org/10.1016/S0020-0255(99)00003-1
http://hdl.handle.net/11536/31250
ISSN: 0020-0255
DOI: 10.1016/S0020-0255(99)00003-1
Journal: INFORMATION SCIENCES
Volume: 117
Issue: 1-2
Begin Page: 89
End Page: 106
Appears in Collections:Articles


Files in This Item:

  1. 000081471700004.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.