With the weak synchronization scheme between the iterations, special provision must be taken to ensure that the returned solution is optimal in the `first-solution-case'. When a goal node is found in iteration , all processors working on iterations must complete their search to prove that no better solution exists.

In the `all-solutions-case' (subject of this paper)
the last iteration is searched to completion until
all processors examined all their assigned subtrees.
Due to the varying branching degree, the subtree sizes
can hardly be estimated in advance.
This results in different termination times for the parallel processors.
As shown in Figures 2 and 3
(compare the two bottom graphs
and ) the time spent in the finishing phase is appreciable.
Note however, that this will usually not occur
in the search for *one*solution, a case, that is more important in practice.

Mon Dec 19 17:27:56 MET 1994