DisCSP

DisCSP

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:" [http://liawww.epfl.ch/frodo/ 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.

ee also

* Distributed constraint optimization (DCOP)


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • DisCSP — est l acronyme anglais pour DIStributed Constraint Satisfaction Probem. Il s agit de la résolution de problème de satisfaction de contraintes distribué sur un réseau de machines. Cette approche de résolution de problèmes est associée aux systèmes …   Wikipédia en Français

  • Constraint satisfaction problem — Constraint satisfaction problems (CSP)s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite… …   Wikipedia

  • Cooperative distributed problem solving — is a network of semi autonomous processing nodes working together to solve a problem, typically in a multi agent system. That is concerned with the investigation of problem subdivision, sub problem distribution, results synthesis, optimisation of …   Wikipedia

  • Secure multi-party computation — (also known as secure computation or multi party computation (MPC)) is a sub field of cryptography. The goal of methods for secure multi party computation is to enable parties to jointly compute a function over their inputs, while at the same… …   Wikipedia

  • Distributed constraint optimization — (DCOP or DisCOP) is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is… …   Wikipedia

  • Problème de satisfaction de contrainte — Problème de satisfaction de contraintes Les problèmes de satisfaction de contrainte ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou …   Wikipédia en Français

  • Problème de satisfaction de contraintes — Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l objet de… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”