JUCS - Journal of Universal Computer Science 10(2): 106-119, doi: 10.3217/jucs-010-02-0106
A Message-Optimal Distributed Graph Algorithm: Partial Precedence Constrained Scheduling
expand article infoPranay Chaudhuri‡, Hussein Thompson‡
‡ University of the West Indies, Cave Hill Campus, Barbados

Corresponding author: Pranay Chaudhuri ( pchaudhuri@uwichill.edu.bb )

© Pranay Chaudhuri, Hussein Thompson.
This article is freely available under the J.UCS Open Content License.
Citation: Chaudhuri P, Thompson H (2004) A Message-Optimal Distributed Graph Algorithm: Partial Precedence Constrained Scheduling. JUCS - Journal of Universal Computer Science 10(2): 106-119. https://doi.org/10.3217/jucs-010-02-0106
Open Access
Abstract
This paper presents a distributed algorithm for the partial precedence constrained scheduling problem. In the classical precedence constrained scheduling problem all the dependent tasks must be scheduled before the task itself can be scheduled. The partial precedence constrained scheduling problem is a generalized version of the original precedence constrained problem in the sense that the number of dependent tasks to be scheduled before the task itself can be scheduled is considered a variable. Using a directed graph to model the partial precedence constrained scheduling problem in which n nodes represent the tasks and e edges represent the precedence constraints, it is shown that the distributed algorithm requires O(e) messages and O(n) units of time and is optimal in communication complexity to within a constant factor.
Keywords
distributed algorithm, directed graph, scheduling, task, precedence constraints