標題: A genetic algorithm for reliability-oriented task assignment with (k)over-tilde-$ duplications in distributed systems
作者: Chiu, CC
Hsu, CH
Yeh, YS
資訊科學與工程研究所
Institute of Computer Science and Engineering
關鍵字: distributed program reliability;distributed system reliability;genetic algorithm;task assignment
公開日期: 1-Mar-2006
摘要: 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.
URI: http://dx.doi.org/10.1109/TR.2005.863797
http://hdl.handle.net/11536/12522
ISSN: 0018-9529
DOI: 10.1109/TR.2005.863797
期刊: IEEE TRANSACTIONS ON RELIABILITY
Volume: 55
Issue: 1
起始頁: 105
結束頁: 117
Appears in Collections:Articles


Files in This Item:

  1. 000236037600013.pdf