Completeness and Performance 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 original proof of completeness of the APO algorithm is based on
the growth of the size of the subproblems. The present paper demonstrates that
this expected growth of subproblems does not occur in some situations, leading
to a termination problem of the algorithm. The problematic parts in the APO
algorithm that interfere with its completeness are identified and necessary
modifications to the algorithm that fix these problematic parts are given. 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. A detailed performance evaluation of CompAPO
comparing it to other DisCSP algorithms is presented, along with an extensive
experimental evaluation of the algorithm's unique behavior. Additionally, an
optimization version of the algorithm, CompOptAPO, is presented, discussed, and
evaluated.
