DisCSP

From Wikipedia, the free encyclopedia

Merge arrows
 It has been suggested that this article or section be merged with Distributed constraint optimization. (Discuss)
The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.

Distributed Constraint Satisfaction Problems (DisCSPs) are a form of constraint satisfaction problems.

Distributed Constraint Satisfaction is a framework for describing a problem in terms of constraints that are known and enforced by distinct participants (agents). The constraints are described on some variables with predefined domains, and have to be assigned to the same values by the different agents.

Problems defined with this framework can be solved by any of the algorithms that are proposed for it.

The framework was used under different names in the 1980s. The first known usage with the current name is in 1990.

The currently most well known paper is the one which introduced in 1992 an asynchronous complete algorithm (ABT) for solving such problems. A large number of such techniques are now available.

  • 1992 -- Asynchronous Backtracking (ABT), -static ordering, complete
  • 1994 -- Asynchronous Weak-Commitment (AWC), -reordering, fast, complete (only with exponential space)
  • 1995 -- Distributed Breakout Algorithm (DBA), -incomplete but fast (Reference Implementation: FRODO)
  • 2000 -- Distributed Forward Chaining (DFC), -slow, comparable to ABT
  • 2000 -- Asynchronous Aggregation Search (AAS), -aggregation of values in ABT
  • 2001 -- Maintaining Asynchronously Consistencies (DMAC), -the fastest algorithm
  • 2001 -- Asynchronous Backtracking with Reordering (ABTR), -reordering in ABT with bounded nogoods
  • 2002 -- Secure Computation with Semi-Trusted Servers, -security increases with the number of trustworthy servers
  • 2003 -- Secure Multiparty Computation For Solving DisCSPs (MPC-DisCSP1-MPC-DisCSP4), secure if 1/2 of the participants are trustworthy

Another major type of solvers are based on multi-party secure computations. Some of them are based on semi-trusted servers, while others are based on threshold cryptography.

[edit] See also