A distributed and parallel backtracking algorithm using virtual time

Journal Title
Journal ISSN
Volume Title
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.
Computer Science