检索结果-内蒙古大学图书馆

The distributed program reliability analysis on star topologies

COMPUTERS & OPERATIONS RESEARCH 2000年第2期27卷 129-142页

作者： Chang, MS Chen, DJ Lin, MS Ku, KL Natl Chiao Tung Univ Inst Comp Sci & Informat Engn Hsinchu 30050 Taiwan Tamsui Oxford Univ Coll Dept Informat Management Taipei Taiwan Chung Shan Inst Sci & Technol Tao Yuan Taiwan

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 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 the star distributed computing systems is NP-hard. We also develop an efficiently solvable case to compute distributed program reliability when some additional file distribution is restricted on the star topology.

关键词： distributed program reliability distributed computing system algorithms

来源：评论

学校读者我要写书评

暂无评论

The distributed program reliability analysis on ring-type topologies

引用

COMPUTERS & OPERATIONS RESEARCH 2001年第7期28卷 625-635页

作者： Lin, MS Chang, MS Chen, DJ Ku, KL Aletheia Univ Dept Informat Management Taipei 25103 Taiwan Chunghwa Telecommun Training Inst Dept Informat Technol Taipei 22077 Taiwan Natl Chiao Tung Univ Inst Comp Sci & Informat Engn Hsinchu 30050 Taiwan Chung San Inst Sci & Technol Tao Yuan Taiwan

distributed computing system (DCS) has become very popular for its high fault-tolerance, potential for parallel processing, and better reliability performance. One of the important issues in the design of the DCS is the reliability performance. distributed program reliability (DPR) is addressed to obtain this reliability measure, In this paper, we propose a polynomial-time algorithm for computing the DPR of ring topology and show that solving the DPR problem on a ring of trees topology is NP-hard. (C) 2001 Elsevier Science Ltd. All rights reserved.

关键词： distributed program reliability minimal file spanning tree algorithm ring of tree

来源：评论

学校读者我要写书评

暂无评论

Time-constrained distributed program reliability analysis

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 1998年第4期14卷 891-911页

作者： Chen, DJ Chang, MS Sheng, MC Horng, MS Natl Chiao Tung Univ Inst Comp Sci & Informat Engn Hsinchu 300 Taiwan Natl Ping Tung Inst Commerce Dept Informat Management Ping Tung 912 Taiwan Natl Taipei Teachers Coll Dept Math & Sci Educ Taipei 106 Taiwan

In this paper, we propose an approach to the reliability analysis of distributed programs that addresses real-time constraints. Our approach is based on a model for evaluating transmission time, which allows us to find the time needed to complete execution of the program, task, or mission under evaluation. With information on time-constraints, the corresponding Markov state space can then be defined for reliability computation. To speed up the evaluation process and reduce the size of the Markov state space, several dynamic reliability-preserving reductions are developed. A simple distributed real-time system is used as an example to illustrate the feasibility and uniqueness of the proposed approach.

关键词： distributed program reliability distribute system reliability file spanning tree file spanning forest reliability

来源：评论

学校读者我要写书评

暂无评论

The distributed program reliability analysis on a star topology: Efficient algorithms and approximate solution

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 1999年第6期E82D卷 1020-1029页

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 star topology has no the additional file distribution.

关键词： distributed program reliability distributed computing system algorithms

来源：评论

学校读者我要写书评

暂无评论

A GENERALIZED ALGORITHM FOR EVALUATING distributed-program reliability

引用

IEEE TRANSACTIONS ON reliability 1993年第3期42卷 416-426页

作者： KUMAR, A AGRAWAL, DP N CAROLINA STATE UNIV DEPT ELECT & COMP ENGNRALEIGHNC 27695

Algorithm GEAR (Generalized Evaluation Algorithm for reliability) computes the reliability of a distributed computing system (DCS) which usually consists of processing element, memory unit, input/output devices, data-files, and pr as its shared resources. The probability that a task or an application can be computed successfully by sharing the required resources on the DCS is termed as the system reliability. Some of the important reliabilities defined using the above concept are terminal-pair, computer- network, distributed-program, and distributed-system. GEAR is general enough to compute all 4 of these parameters. GEAR is a 1-step algorithm and does not require any prior knowledge about multiterminal connections for computing reliability expression. Many examples are included to illustrate the usefulness of GEAR for computing reliability measures of a DCS.

关键词： distributed program reliability distributed SYSTEM reliability MULTIPROCESSOR TRANSACTION-BASED SYSTEM

来源：评论

学校读者我要写书评

暂无评论

A genetic algorithm for reliability-oriented task assignment with (k)over-tilde-$ duplications in distributed systems

引用

IEEE TRANSACTIONS ON reliability 2006年第1期55卷 105-117页

作者： Chiu, CC Hsu, CH Yeh, YS Private Takming Coll Dept Management Informat Syst Taipei Taiwan Natl Chiao Tung Univ Inst Comp Sci & Informat Engn Hsinchu 30050 Taiwan

A distributed system is a collection of processor-memory pairs connected by communication links. The reliability of a distributed system can be expressed using the distributed program reliability, and distributed system reliability analysis. The computing reliability of a distributed system is an NP-hard problem. The distribution of programs & data-files can affect the system reliability. The reliability-oriented task assignment problem, which is NP-hard, is to find a task distribution such that the program reliability or system reliability is maximized. For example, efficient allocation of channels to the different cells can greatly improve the overall network throughput, in terms of the number of calls successfully supported. This paper presents a genetic algorithm-based reliability-oriented task assignment methodology (GAROTA) for computing the (k) over tilde -DTA reliability problem. The proposed algorithm uses a genetic algorithm to select a program & file assignment set that is maximal, or nearly maximal, with respect to system reliability. Our numerical results show that the proposed algorithm may obtain the exact solution in most cases, and the computation time seems to be significantly shorter than that needed for the exhaustive method. When the proposed method fails to give an exact solution, the deviation from the exact solution is very small. The technique presented in this paper would be helpful for readers to understand the correlation between task assignment reliability, and distributed system topology.

关键词： distributed program reliability distributed system reliability genetic algorithm task assignment

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for reliability analysis of distributed computing systems

引用

INFORMATION SCIENCES 1999年第1-2期117卷 89-106页

作者： 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

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.

关键词： distributed computing systems distributed program reliability computational complexity algorithms

来源：评论

学校读者我要写书评

暂无评论

The computational complexity of the reliability problem on distributed systems

引用

INFORMATION PROCESSING LETTERS 1997年第3期64卷 143-147页

作者： Lin, MS Chen, DJ NATL CHIAO TUNG UNIV INST COMP SCI & INFORMAT ENGNHSINCHU 30050TAIWAN

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.

关键词： distributed systems distributed program reliability computational complexity graph theory

来源：评论

学校读者我要写书评

暂无评论

reliability analysis of distributed computing systems in ring networks

引用

Journal of Communications and Networks 1999年第1期1卷 68-77页

作者： Chang, Ming-Sang Chen, Deng-Jyi Lin, Min-Sheng Ku, Kuo-Lung Instiute Comp. Sci. and Info. Eng. National Chiao Tung University Hsin Chu Taiwan Department of Information Management Tamsui Oxford Univetsity College Tamsui Taipei Taiwan Chung-San Inst. of Sci. and Technol. Tao-Yuan Taiwan

distributed Computing System (DCS) has become very popular for its high fault-tolerance, potential for parallel processing, and better reliability performance. One of the important issues in the design of the DCS is the reliability performance. distributed program reliability (DPR) has to be addressed to obtain this reliability measure. An efficient network topology is quite important for the distributed computing system. For example, the ring network has been widely used in current distributed system design. In this paper, we focus on DCS with ring topologies. We propose polynomialtime algorithms to analyze the DPR of the dual ring topology and show that solving the DPR problem on a ring of trees topology is NP-hard.

关键词： Algorithms Computational Complexity distributed program reliability Minimal File Spanning Tree Ring of Tree

来源：评论

学校读者我要写书评

暂无评论

A genetic algorithm for reliability-oriented task assignment in a distributed system

引用

Journal of Information & Optimization Sciences 2004年第2期25卷 385页

作者： Hsu, Chung-Hsien Chin-Ching, Chiu

The reliability-oriented task assignment problem, which is NP-hard, is to find a task distribution such that the program reliability or systom reliability is maximized. In this paper, we have developed a reliability oriented task allocation scheme, based on a genetic algorithm, for distributed systems to find an appproximate solution. The simulation shows that, in most test cases, the algorithm finds sub-optimal solutions efficiently; therefore, it is a desirable approach to solve these problems. [PUBLICATION ABSTRACT]

关键词： distributed system reliability task assignment distributed program reliability genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：