Tree-based termination detection associates weights with individual work pieces. When its work is partitioned, retains half the weight, and gives half to processor receiving work. When a processor completes the work, its weight is returned to the parent. When processor becomes one, and has completed its work, algorithm terminates. Given p processors, use a centralized strategy so that each processor can work on current best nodes in open list.
Parallel formulation expands the first p nodes in the open list.
Each processor has a local open list. Initially search space is statically divided among processors and expanding some nodes and distributing them to local open lists of various processors. All processors then select and expand nodes simulatenously. A communication strategy allows state-space nodes to be exchanged between open lists of different processors. In parallel search algorithms, speedup can greatly vary from one execution to another because the portion of search space examined by processors is determined dynamically.