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:
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.