Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45827
Title: A distributed and parallel backtracking algorithm using virtual time
Authors: Cleary, John
Unger, Brian W
Li, Xining
Keywords: Computer Science
Issue Date: 1-Oct-1987
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.
URI: http://hdl.handle.net/1880/45827
Appears in Collections:Cleary, John
Unger, Brian W

Files in This Item:
File Description SizeFormat 
1987-281-29.pdf1.11 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.