Parallel computation has the potential for accelerating the solution of combinatorial search problems. Universal randomized methods, with provably effective speed-up, have already been developed for parallel backtrack search and parallel branch-and-bound computation. Also previously developed was a paradigm for parallelizing the sequential alpha-beta pruning algorithm and its variants for evaluating game trees. This project continues work on the theory of parallel search algorithms, with the following objectives. First, the performance of the randomized methods will be analyzed for hypercube and butterfly networks. This analysis will demonstrate the effectiveness of the algorithms in practice. Second, network routing methods in which messages are issued periodically and asynchronously will be studied, since these methods provide a mechanism for implementing backtrack search on networks. Third, a new type of probabilistic performance analysis, competitive analysis, will be applied to parallel algorithms. Finally, experimental work on the proposed algorithms will provide insight for the theoretical investigations.
