The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Un système informatique distribué se compose d'éléments de traitement, de liaisons de communication, d'unités de mémoire, de fichiers de données et de programmes. Ces ressources sont interconnectées via un réseau de communication et contrôlées par un système d'exploitation distribué. La fiabilité des programmes distribués (DPR) dans un système informatique distribué est la probabilité qu'un programme qui s'exécute sur plusieurs éléments de traitement et doit récupérer des fichiers de données à partir d'autres éléments de traitement soit exécuté avec succès. Cette fiabilité varie en fonction 1) de la topologie du système informatique distribué, 2) de la fiabilité des bords de communication, 3) de la répartition des fichiers de données et des programmes entre les éléments de traitement, et 4) des fichiers de données nécessaires à l'exécution d'un programme. Dans cet article, nous montrons que le calcul de la fiabilité d’un programme distribué sur un système informatique distribué en étoile est #P-complet. Un cas polynomial résoluble est développé pour calculer la fiabilité d'un programme distribué lorsqu'une distribution de fichiers supplémentaires est restreinte sur la topologie en étoile. Nous proposons également un algorithme en temps polynomial pour calculer la fiabilité d'un programme distribué avec des solutions approximatives lorsque la topologie en étoile n'a pas de distribution de fichiers supplémentaire.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Ming-Sang CHANG, Deng-Jyi CHEN, Min-Sheng LIN, Kuo-Lung KU, "The Distributed Program Reliability Analysis on a Star Topology: Efficient Algorithms and Approximate Solution" in IEICE TRANSACTIONS on Information,
vol. E82-D, no. 6, pp. 1020-1029, June 1999, doi: .
Abstract: A distributed computing system consists of processing elements, communication links, memory units, data files, and programs. These resources are interconnected via a communication network and controlled by a distributed operating system. The distributed program reliability (DPR) in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to retrieve data files from other processing elements will be executed successfully. 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 this paper, we show that computing the distributed program reliability on a star distributed computing system is #P-complete. A polynomially solvable case is developed for computing the distributed program reliability when some additional file distribution is restricted on the star topology. We also propose a polynomial time algorithm for computing the distributed program reliability with approximate solutions when the star topology has no the additional file distribution.
URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_6_1020/_p
Copier
@ARTICLE{e82-d_6_1020,
author={Ming-Sang CHANG, Deng-Jyi CHEN, Min-Sheng LIN, Kuo-Lung KU, },
journal={IEICE TRANSACTIONS on Information},
title={The Distributed Program Reliability Analysis on a Star Topology: Efficient Algorithms and Approximate Solution},
year={1999},
volume={E82-D},
number={6},
pages={1020-1029},
abstract={A distributed computing system consists of processing elements, communication links, memory units, data files, and programs. These resources are interconnected via a communication network and controlled by a distributed operating system. The distributed program reliability (DPR) in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to retrieve data files from other processing elements will be executed successfully. 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 this paper, we show that computing the distributed program reliability on a star distributed computing system is #P-complete. A polynomially solvable case is developed for computing the distributed program reliability when some additional file distribution is restricted on the star topology. We also propose a polynomial time algorithm for computing the distributed program reliability with approximate solutions when the star topology has no the additional file distribution.},
keywords={},
doi={},
ISSN={},
month={June},}
Copier
TY - JOUR
TI - The Distributed Program Reliability Analysis on a Star Topology: Efficient Algorithms and Approximate Solution
T2 - IEICE TRANSACTIONS on Information
SP - 1020
EP - 1029
AU - Ming-Sang CHANG
AU - Deng-Jyi CHEN
AU - Min-Sheng LIN
AU - Kuo-Lung KU
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E82-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 1999
AB - A distributed computing system consists of processing elements, communication links, memory units, data files, and programs. These resources are interconnected via a communication network and controlled by a distributed operating system. The distributed program reliability (DPR) in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to retrieve data files from other processing elements will be executed successfully. 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 this paper, we show that computing the distributed program reliability on a star distributed computing system is #P-complete. A polynomially solvable case is developed for computing the distributed program reliability when some additional file distribution is restricted on the star topology. We also propose a polynomial time algorithm for computing the distributed program reliability with approximate solutions when the star topology has no the additional file distribution.
ER -