A distributed and parallel backtracking algorithm using virtual time
Date
1987-10-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Keywords
Computer Science