Scheduling tasks and communications on a virtual distributed system

A set of tasks has to be scheduled on identical parallel processors subject to precedence constraints and small communication delays. A polynomial algorithm is known to exist if task duplication is allowed and the number of available processors is not limited. However the problem of communications scheduling is not taken into account. In this paper, we prove that this algorithm also never saturates communication channels and always delivers messages on time, if slightly stronger constraints are imposed on the tasks.