Common Cost Bound: Each processor is given the same cost bound. Processors use parallel DFS on the tree within the cost bound. The drawback of this scheme is that there might not be enough concurrency.
Variable Cost Bound: Each processor works on a different cost bound. The major drawback here is that a solution is not guaranteed to be optimal until all lower cost bounds have been exhausted.
In each case, parallel DFS is the search kernel.
Parallel Best-First Search
The core data structure is the Open list (typically implemented as a priority queue).
Each processor locks this queue, extracts the best node, unlocks it.
Successors of the node are generated, their heuristic functions estimated, and the nodes inserted into the open list as necessary after appropriate locking.
