Efficient backtracking in and-parallel implementations of non-deterministic languages

We consider the problem of efficiently supporting backtracking in independent and-parallel non-deterministic systems. We consider this problem in the context of logic programming, although the solution proposed is sufficiently general to be applicable to any non-deterministic language or system. Our model employs various optimizations, as well as a novel memory organization scheme in which processors are allowed to traverse each others´ stacks to achieve this efficiency. The solution developed has been implemented in the ACE Prolog system. The performance of the system is analyzed on a variety of non-deterministic benchmarks.