DISTRIBUTED TASK ASSIGNMENT USING CRITICAL PATH ESTIMATE

Abstract

A very general task assignment scheme for a distributed computing system is presented in this paper. It takes execution time, communication time, and idle time into consideration. All possible task assignments are formed as a state space tree where a path from the root node of the tree to a node represents a partial or total task assignment. We propose an approach called the critical path overestimate for achieving a suboptimal task assignment and pruning most of the nodes of the tree. Combining the above approach with a divide-and-conquer method, we can further reduce the complexity of the problem, and therefore attain a satisfactory solution. Results from a wide range of experiments reveal that the proposed approaches perform well because of their giving close approximation to the actual cost and saving a high percentage of node generations.