Browsing by Author "Olthof, Ian"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
- ItemOpen AccessTHE DESIGN OF AN OPTIMISTIC AND PARALLEL PROLOG(1992-05-01) Cleary, John G.; Olthof, Ian(This paper has been submitted to the Journal of Logic Programming) A distributed AND parallel Prolog implementation is described. The system can correctly handle all pure Prolog program. In particular, it deals with the problem of distributed backtracking. Conflicts in variable bindings are resolved by assigning a time value to every unification. Bindings with smaller time values are given precedence over those with larger time values. The algorithm is based on the optimistic Time Warp system, with Prolog-specific specializations. The result is a system which can fully exploit both dependent and independent AND parallelism.
- ItemOpen AccessORDER-INDEPENDENT UNIFICATION AND BACKTRACKING(1992-07-01) Olthof, Ian; Cleary, John G.Two algorithms for order-independent unification are presented. Both assume that unifications are timestamped, giving a natural ordering on unifications from lowest timestamp to highest. The first algorithm permits lower-timestamped unifications to be performed after higher-timestamped unifications have already been done, without requiring previous unifications to be backtracked and later redone. The binding state that results is indistinguishable from that produced by a lowest-to-highest execution. The second algorithm extends the first by allowing intermediate unifications to be undone, again avoiding work in undoing and redoing unifications with higher timestamps. These algorithms are designed for distributed, fully AND-parallel Prolog execution; asynchronous events occurring on different CPSs can be reconciled without too much overhead.