A HEURISTIC TASK ASSIGNMENT ALGORITHM TO MAXIMIZE RELIABILITY OF A DISTRIBUTED SYSTEM

Abstract

Distributed systems potentially provide high reliability owing to the program and data-file redundancy possible. In many applications, high reliability is the major consideration for system design. Some work by Kumar, Hariri, Raghavendra shows that the distribution of programs and data-files can affect the system reliability appreciably, and that redundancy in resources such as computers, programs, and data-files can improve the reliability of distributed system. This paper first formulates a practical application for a reliability-oriented distributed task assignment problem which is NP-hard. Then, to cope with this challenging problem, we propose a greedy algorithm, based upon some heuristics, to find an approximate solution. The simulation shows that, in most cases tested, the algorithm finds suboptimal solutions efficiently; therefore, it is a desirable approach to solve these problems.