A significant problem in Logic Programming is how to execute Prolog on
multiprocessor and distributed systems. For and-parallel Prolog
correctly co-ordinating backtracking across many processors is
difficult. An algorithm which fully supports such backtracking is
described. The algorithm is based on the Virtual Time technique first
described by Jefferson and Sowizral in their Time Warp system for
concurrent discrete event simulation. The algorithm preserves the
standard semantics of Prolog and does not require additional program
control other than directives as to where goals should be run.
Because of the logical semantics of Prolog optimizations of the basic
Time Warp algorithm are possible. These reduce the number of rollbacks
necessary and the amount of recomputation necessary after a rollback.