What is an effective schedule?

Parallel algorithms are more difficult to analyze than sequential algorithms, in part because one has to account for communication between the processors in addition to the usual measures of time and space. To find meaningful lower bounds on communication, one has to restrict the kinds of schedules that are examined. The authors show that the traditional equal work restriction is insufficient, but they use it as a starting point, and, by successively refining their intuitive notions of what good and bad schedules are, they come up with the concept of an effective schedule. They then show that a communication/time tradeoff result which has been shown by Papadimitriou and Ullman for the diamond directed acyclic graph (DAG) (SIAM J. of Comput. vol.16, no.4, p.639-46, 1987) and Jayasimha and Loui for the triangular solver DAG (Tech. Rep.629, CSRD, Illinois Univ., Mar.1988) occurs with ineffective schedules