Load balanced allocation of multiple tasks in a Distributed Computing System

Abstract

A Distributed Computing Systems (DCS) calls for proper partitioning of tasks into modules and allocating them to various nodes so as to enable parallel execution of their modules by individual different processors of the system. A number of algorithms have been proposed for allocation of tasks in a Distributed Computing System. Most of the models proposed in literature consider modules of a single task for static allocation, for the purpose of allocation onto a DCS. Moreover, they did not consider the architectural capability of the processing nodes and the way of connectivity among them. This work considers allocation of disjoint multiple tasks with their corresponding modules and proposes a parallel algorithm for a realistic situation wherein multiple disjoint tasks with their modules compete for execution on an arbitrarily connected DCS based on well-known A* technique. The proposed algorithm also considers a load balanced allocation for the purpose. The paper justifies the effectiveness of the algorithm with the experimental results by comparing with previously reported works. © IFIP International Federation for Information Processing 2005.