Title: A genetic algorithm for reliability-oriented task assignment with (k)over-tilde-$ duplications in distributed systems
Authors: Chiu, CC
Hsu, CH
Yeh, YS
資訊科學與工程研究所
Institute of Computer Science and Engineering
Keywords: distributed program reliability;distributed system reliability;genetic algorithm;task assignment
Issue Date: 1-Mar-2006
Abstract: 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
Journal: IEEE TRANSACTIONS ON RELIABILITY
Volume: 55
Issue: 1
Begin Page: 105
End Page: 117
Appears in Collections:Articles


Files in This Item:

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