DISTRIBUTED TASK ASSIGNMENT USING CRITICAL PATH ESTIMATE

A very general task assignment scheme for a distributed computing syst em 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 th e tree to a node represents a partial or total task assignment. We pro pose 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 clo se approximation to the actual cost and saving a high percentage of no de generations.