CompAPO: A Complete Version of the APO Algorithm

Asynchronous partial overlay (APO) is a search algorithm that uses cooperative mediation to solve distributed constraint satisfaction problems (DisCSPs). The algorithm partitions the search into different subproblems of the DisCSP. The proof of completeness of the APO algorithm is based on the growth of the size of the subproblems. We have discovered that this expected growth of groups does not occur in some situations, leading to a termination problem of the algorithm. The present paper identifies the problematic parts in the algorithm that interfere with its completeness. Some necessary modifications are given to the algorithm to fix these problematic parts. The resulting version of the algorithm, complete asynchronous partial overlay (CompAPO), ensures its completeness. Formal proofs for the soundness and completeness of CompAPO are given.