Precedence-constrained task allocation in distributed computing systems

Abstract

A distributed computing system (DCS) provides a platform for concurrent execution of tasks consisting of various modules. The problem of task allocation becomes quite difficult to solve when the precedence constraint is considered along with other constraints such as memory, network topology, etc. Various solutions have been proposed, considering one or the other constraint, in the literature. The present work discusses .a comprehensive task allocation policy that can promise to provide an optimal solution to the problem. An algorithm, considering the precedence relation among the modules of a task, is proposed for allocation. The algorithm is used to show the allocation for some interconnection topologies and task graphs.