Technical Reports

The ICICS/CS Reading Room

UBC CS TR-92-30 Summary

Parallel and Distributed Finite Constraint Satisfaction: Complexity, Algorithms and Experiments, November 1992 Ying Zhang and Alan K. Mackworth, 36 pages

This paper explores the parallel complexity of finite constraint satisfaction problems (FCSPs) by developing three algorithms for deriving minimal constraint networks in parallel. The first is a parallel algorithm for the EREW PRAM model, the second is a distributed algorithm for fine-grain interconnected networks, and the third is a distributed algorithm for coarse-grain interconnected networks. Our major results are: given an FCSP represented by an acyclic constraint network (or a join tree) of size n with treewidth bounded by a constant, then (1) the parallel algorithm takes O(log n) time using O(n) processors, (2) there is an equivalent network, of size poly(n) with treewidth also bounded by a constant, which can be solved by the fine-grain distributed algorithm in O(\log n) time using poly(n) processors and (3) the distributed algorithm for coarse-grain interconnected networks has linear speedup and linear scaleup. In addition, we have simulated the fine-grain distributed algorithm based on the logical time assumption, experimented with the coarse-grain distributed algorithm on a network of transputers, and evaluated the results against the theory.

If you have any questions or comments regarding this page please send mail to