Asynchronous Partial Overlay: A New Algorithm for Solving Distributed
  Constraint Satisfaction Problems
  Distributed Constraint Satisfaction (DCSP) has long been considered an
important problem in multi-agent systems research. This is because many
real-world problems can be represented as constraint satisfaction and these
problems often present themselves in a distributed form. In this article, we
present a new complete, distributed algorithm called Asynchronous Partial
Overlay (APO) for solving DCSPs that is based on a cooperative mediation
process. The primary ideas behind this algorithm are that agents, when acting
as a mediator, centralize small, relevant portions of the DCSP, that these
centralized subproblems overlap, and that agents increase the size of their
subproblems along critical paths within the DCSP as the problem solving
unfolds. We present empirical evidence that shows that APO outperforms other
known, complete DCSP techniques.
