DisCSP

From Wikipedia, the free encyclopedia

You have new messages (last change).

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help Wikipedia by improving the introduction according to the guidelines laid out at Wikipedia:Guide to layout. You can discuss the issue on the talk page.

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 1980's. 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
  • 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 multy-party secure computations. Some of them are based on semi-trusted servers, while others are based on threshold cryptography.

Retrieved from "http://en.wikipedia.org../../../d/i/s/DisCSP_c7a3.html"