Task allocation algorithms for maximizing reliability of heterogeneous distributed computing systems

The rapid progress of microprocessor and communication technologies has mad e the distributed computing system economically attractive for many compute r applications. One of the first problems encountered in the operation of a distributed system is the problem of allocating the tasks among the proces sing nodes. The task allocation problem is known to be computationally intr actable for large task sets. In this paper, we consider the task allocation problem with the goal of maximizing reliability of heterogeneous distribut ed systems. After presenting a quantitative task allocation model, we prese nt a least-cost branch-and-bound algorithm to find optimal task allocations . We also present two heuristic algorithms to obtain suboptimal allocations for realistic size large problems in a reasonable amount of computational time. Simulation was used to study the performance of the proposed algorith ms for a large number of problems. Also, performance of the proposed algori thms has been compared with a well-known heuristics available in the litera ture.