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. Serial search can expand a set of nodes to reach a goal node. Parallel search can expand more or less nodes to reach same goal node. Acceleration anomalies, superlinear speedups Deceleration anomalies, sublinear speedups.