A distributed Prolog system with AND-parallelism

A description is given of the design and implementation of a distributed version of a Prolog interpreter running on a network of Sun workstations. The system easily takes advantage of AND-parallelism using fork and join primitives implemented by message passing. The design decisions and tradeoffs are explained in detail. The design is simple and yet powerful enough to achieve practical speedups on large existing Prolog programs. It is proved that deadlock is not possible provided a weak condition is met. The principles of programming using the new primitives are explained with simple examples. It is concluded that implementing AND-parallelism can give a significant performance gain despite the message overhead, and that the design complexity is less than that needed to incorporate other types of parallelism in Prolog.<>