  Goal-level Independent and-parallelism (IAP) is exploited by scheduling for
simultaneous execution two or more goals which will not interfere with each
other at run time. This can be done safely even if such goals can produce
multiple answers. The most successful IAP implementations to date have used
recomputation of answers and sequentially ordered backtracking. While in
principle simplifying the implementation, recomputation can be very inefficient
if the granularity of the parallel goals is large enough and they produce
several answers, while sequentially ordered backtracking limits parallelism.
And, despite the expected simplification, the implementation of the classic
schemes has proved to involve complex engineering, with the consequent
difficulty for system maintenance and extension, while still frequently running
into the well-known trapped goal and garbage slot problems. This work presents
an alternative parallel backtracking model for IAP and its implementation. The
model features parallel out-of-order (i.e., non-chronological) backtracking and
relies on answer memoization to reuse and combine answers. We show that this
approach can bring significant performance advantages. Also, it can bring some
simplification to the important engineering task involved in implementing the
backtracking mechanism of previous approaches.
