Analysis of Or-Parallel Execution Models

We discuss fundamental limitations of or-parallel execution models of nondeterministic programming languages. Or-parallelism corresponds to the execution of different nondeterministic computational paths in parallel. A natural way to represent the state of 1993 execution of a nondeterministic program is by means of an or-parallel tree. We identify three important criteria that underlie the design of or-parallel implementations based on the or-parallel tree: constant-time access to variables, constant-time task creation, and constant-time task switching, where the term constant-time means that the time for these operations is independent of the number of nodes in the or-parallel tree, as well as the size of each node. We prove that all three criteria cannot be simultaneously satisfied by any or-parallel execution model based on a finite number of processors but unbounded memory. We discuss in detail the application of our result to the class of logic programming languages and show how our result can serve as a useful way to categorize the various or-parallel methods proposed in this field. We also discuss the suitability of different or-parallel implemenation strategies for different parallel architectures.