A Sequential View of AND-Parallelism Through Partial AND-Processes

Abstract

Most implementations of AND-parallelism tackle the shared variable problem by running literals in parallel only if they have no variables in common and thus are independent from each other. But even in its independent form, AND-parallel clause execution remains an intricate matter with numerous problems to be solved. First to mention, a carefully worked out synchronization mechanism is required to control process activities like dependency checking, literal ordering, message passing and intelligent backtracking. Due to the complex nature of these problems, implementation of AND-parallelism often results in a rather opaque interplay of processes. Therefore, based on a new kind of process, this paper presents a sequential - Prolog like - view of AND-parallelism for making it more understandable on one hand and easier to implement on the other. Processes of the new type will be called partial AND-processes.