The intrinsic parallelism present in logic programs, and more generally in nondeterministic programs, has over the years spurred the design and implementation of a wealth of execution models. Even if one limits oneself to OR parallelism, more than a dozen models have been suggested. Gupta and  Jayaraman  suggest a three-criterion classification scheme that lays the groundwork for an objective comparison between them. These three criteria are the respective costs of creating a binding environment for procedure calls; accessing and binding variables for assignments and parameter transmissions; and switching tasks, which accounts for backtracking. An optimal evaluation model would have these three costs as small as possible, which ideally means all costs would be constant for any program. For a realistic resource-bound parallel machine, however, the authors show that this goal cannot be achieved; at least one of these criteria must be dependent upon the program size. In the second part of the paper, the currently proposed OR-parallel models are grouped according to the costs they assign to these three fundamental operations.

This paper is a delight to read, not only because of its research value, but also for its presentation, self-containedness, and clarity. While it is mainly targeted to architecture designers for parallel logic languages, it will nonetheless be useful reading to anyone wishing to keep abreast of fundamental issues in parallel logic programming, or looking for a rational survey of current parallel execution models.