Welcome to the Distributed Constraints Reasoning homepage, at the Computer Science Dept. at Ben-Gurion University of the Negev, Israel. This is also the home of our research group — however, we strive to make it useful to the general DCR community, so your comments are welcome. If you object to your paper appearing here (perhaps because it is preliminary), please tell me about that.
Distributed CSPs, are composed of a set of variables which are distributed among agents. The variables are connected by constraints which define the constraints network among the agents. As a result, the search algorithm for solving these problems is a distributed algorithm. The algorithm is run by agents that communicate by sending and receiving messages. In general, messages contain information about assignments of values to variables and refutations of assignments, by agents that have no compatible assignment, to their own variables. The first to propose this family of problems was Makoto Yokoo, who published two distributed search algorithms for solving DCSPs —
The Asynchronous Backtracking algorithm was the base for later and clearer versions published by Yokoo (1998, 2000). Versions of the asynchronous backtracking algorithm, which include Dynamic Backtracking methods and do not change the initial constraints network, were published by Bessière et. al in 2005. The up to date version of Asynchronous BackTracking includes Dynamic variable ordering and was published by Zivan and Meisels in 2006.
Because of the distributed nature of DCSPs, the solving algorithm must run on all agents and perform a complete and correct search, by exchanging messages among the agents. This generates multiple research questions:
All of the above issues have been tackled in the last decade of intensive research on DCSPs and on distributed search algorithms for DCSPs. However, many of the above issues relate also to Distributed Constraints Optimization Problems (DCOPs), which are described below.
A natural extension to distributed constraints satisfaction problems are distributed constraints Optimization problems (DCOPs). DCOPs have a set of Agents, each with its variables and finite domains of values, that are connected by valued constraints. Any compound assignment of constrained agents is associated with a finite cost (or gain). As a result, constraints are represented by tables whose values are not in {0,1} (as in DCSPs) but rather finite positive (say) numbers. The goal of a search algorithm for DCOPs is to find the optimal solution. Most commonly, DCOPs are assumed to use the Utilitarian objective function which is the sum of all costs of all agents. The cost of each agent is usually taken to be the sum of all the costs of the constraints in which the agent participates. Finding an optimal solution in this case means finding the minimal-cost (or the maximal-cost) global assignment.
Search and optimization algorithms for DCOPs are different in nature than search algorithms for DCSPs. For DCOPs one needs to go over the whole search space and find the optimal solution. This is many times done by distributed and asynchronous Branch and Bound algorithms. But, some algorithms use forms of dynamic programming. Both DCOPs and DCSPs are hard problems and for a large number of agents (or values), when the search space becomes too large to handle, one usually uses a local search algorithm. This family of algorithms searches in local neighbourhoods of agents and arrives at good solutions that are not in general globally optimal.
The simplest form of a distributed search algorithm for DCSPs could be described as follows:
The above algorithm is usually called Synchronous Backtracking (SBT). It is clear that no two agents are performing computations at the same time in SBT. It is also a correct algorithm, by a clear analogy to (centralized) chronological backtrack. This naive algorithm is a base point for all distributed DCSP algorithms. The main drawback Yokoo was seeking to improve was the idleness of agents through most of the search. He has done so by allowing agents to perform computations asynchronously. But idleness of agents is not the major flaw in SBT. By using BackJumping one can improve the performance of SBT by a large factor, even though the algorithm stays synchronous. SBT defines a base line from which algorithms which exploit the asynchronous nature of the problems are developed. One approach, asynchronous search, was designed by (Yokoo) and later made more elegant by Bessière, Brito, Meseguer and Maestre. Other approaches, which use some coordination among agents in order to propagate constraints asynchronously, or to explore different parts of the search space concurrently, or to use a distributed variable ordering according to a selected heuristic, were designed. All improved algorithms try to avoid computation against inconsistent partial assignments. When tested for performance these algorithms were found very effective, by members of our group.
Evaluating performance of solving algorithms for DCSPs and DCOPs is a major issue which was extensively investigated by our group. The asynchronous, multi-machine environment in which the algorithms run, makes it difficult to measure the efficiency of the algorithm in terms of CPU time. Furthermore, time is not the only relevant measure for distributed algorithms. The amount of messages the network is loaded with and the concurrent computational effort are just as relevant. Our algorithmic papers reflect on proper experimental evaluation methods for comparing distributed search algorithms on DCSPs and on DCOPs, and the results include several measures and behavior under message delays.
A decade of intensive research into search algorithms for DCSPs and DCOPs has produced several algorithms in each domain and some extensive experimental evaluation results, comparing performance of these algorithms. A more detailed description of these results is in the introduction page. The last few years have seen additional research directions for DCR. One such direction relates to privacy and self-interests and has generated several new approaches - adversarial, asymmetric, partially-known, and the design of a truth enforcing mechanism. Each of these approaches is described in detail as one of the Research Sub-Fields and will potentially lead to further advances in the coming years.