Task Allocation for Maximizing Reliability of Distributed Computing Systems using Dynamic Greedy Heuristic

Abstract: This paper deals with the problem of task allocation (i.e., to which processor should each task of an application be assigned) in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The task assignment problem for more than three processors is known to be NP-hard, and therefore satisfactory suboptimal solutions obtainable in an acceptable amount of time are generally sought. We propose a new intelligent technique based on dynamic task allocation which uses greedy search algorithm for this problem. Performance of the algorithm depends on number of tasks, number of processors, the ratio of average communication time to average computation time and task interaction density of application. The effectiveness and efficiency of our algorithm is compared with recently proposed task allocation algorithms for maximizing system reliability available in literature.

Keywords: Task assignment, Distributed computing, Reliability, Dynamic Greedy heuristic, Task interaction graph.