The design of an optimistic AND-parallel Prolog

A distributed AND-parallel Prolog implementation is described. The system can correctly handle all pure Prolog programs. In particular, it deals with the problem of distributed backtracking. Conflicts in variable bindings are resolved by assigning a time value to every unification. Bindings with smaller time values are given precedence over those with larger time values. The algorithm is based on the optimistic Time Warp system, with Prolog-specific optimizations. The optimizations include two new unification algorithms that permit unification and backtracking in any order. The result is a system which can fully exploit the parallelism available in both dependent and independent AND-parallelism