Distributed Constraint Satisfaction

The Distributed Constraint Satisfaction is a general formalism for modeling naturally distributed problems [Yokoo&Durfee&Ishida&Kuwabara'98].

Workshops
Distributed Constraint Satisfaction - CP-2000, Singapore
Distributed Constraint Reasoning - IJCAI-2001, Seattle
Distributed Constraint Reasoning - AAMAS-2002, Bologna
Distributed Constraint Reasoning - IJCAI-2003, Acapulco
Distributed Constraint Reasoning - CP-2004, Toronto
Distributed Constraint Reasoning - IJCAI-2005, Edinburg
Distributed Constraint Reasoning - AAMAS-2006, Hakodate
Distributed Constraint Reasoning - ECAI-2006, Italy
Distributed Constraint Reasoning - CP-2007, Providence
Distributed Constraint Reasoning - IJCAI-2007, Hyderabad
Distributed Constraint Reasoning - AAMAS-2008, Estoril
Distributed Constraint Reasoning - IJCAI-2009, Pasadena
Distributed Constraint Reasoning - AAMAS-2010, Toronto
Distributed Constraint Reasoning - IJCAI-2011, Barcelona
Distributed Constraint Reasoning - ECAI-2012, Montpellier
 

Previously, many related publications have appeared in the Series of International Workshops on Distributed Artificial Intelligence.

History
History of Complete Asynchronous Techniques For Natural DisCSPs
History of Other Ideas
History for DisCSP allowing for problem redistribution

DisCSP Formalism

1998 (IEEE TKDE) - Yokoo&Durfee&Ishida&Kuwabara
DisCSP acronym - proposed by Christian Bessiere at CP DCS Workshop, 2000

References

2000 (made available at the CP DCS Workshop) Yokoo (some references on DisCSPs before 2000)


History of Complete Asynchronous Techniques For Naturally Distributed CSPs
 

Asynchronous Backtracking

1990 (10th DAI Workshop) - Yokoo&Durfee&Ishida&Kuwabara (Basic Asynchronous Backtracking, 1 agent has1 distinct variable, storing all nogoods)
1998 (ICMAS) - Yokoo&Hirayama (Complex Local Problems)
2000 (AAAI) - Silaghi&Haroud&Faltings (Minimal Space&Complete+Allows shared variables+Cartesian Product Representation of proposals)
2001 (IJCAI DCR Workshop&CP) - Bessiere&Maestre&Meseguer (Getting rid of Add Link Messages)
2001 (IJCAI DCR Workshop) - Silaghi&Haroud&Faltings (Asynchronous Dichotomous Splitting For Numerical CSPs)
Asynchronous Reordering
1991 (IJCAI) - Zeev&Dechter&Katz  (Need For Static Total Ordering)
1993 (12th DAI Workshop)  - Yokoo (For Nogood-Based Heuristics - Constrained Agents First)
2001 (IJCAI DCR Workshop) - Silaghi&Haroud&Faltings (For General Heuristics & Polynomial Space Requirements)
2001 (EPFL-TR-364) - Silaghi&Haroud&Faltings  (Reordering Heuristics for Asynchronous Distributed Search)
Strategies for Nogood Selection
1997 (AAAI Workshop) - Havens (Strategies for nogood selection and discarding nogoods)
2000 (AA) - Turner (efficiency for classes of nogoods)
2000 (ICDCS) - Hirayama&Yokoo (efficient nogoods)
2000 (Springer) - Yokoo (Space Complexity with Dynamic Backtracking-like nogood storing)
Relaxation
1993 (ICTAI) - Yokoo  (for overconstrained problems-based on tuple value)
1997 (CP) - Hirayama&Yokoo (for overconstrained problems-based on number of conflicting constraints)
2000 (ICMAS) - Hirayama&Yokoo (for overconstrained problems-based on number of conflicting constraints and tuple value)
2000 (DCS Workshop CP) - Silaghi&Haroud&Faltings  (based on constraint references)
Asynchronous Consistency Achievement
1990 (IJCAI) - Mackworth&Zhang (General Distribution of Constraints)
1997 (UCL-TR) - Deville&.. (AC4-like)
1999 (CP) - Hamadi (Optimal Distribution of Constraints)
2000 (ACM Symp. on Applied Computing) - Monfroy (General Propagation Algorithm for an Abstract Notion of Consistency)
Asynchronous Consistency Maintenance
2000 (CP DCS Workshop) - Silaghi&Haroud&Faltings (Without Strength Guarantees)
2001 (IJCAI DCR Workshop) - Silaghi&Haroud&Faltings (offers guarantees&allows to use backtrack nogoods in consistency)
Distributed Optimization
2003 (AAMAS) - Modi&Tambe&Shen&Yokoo (asynchronous A* behaviour)
2003 (IAT) - Silaghi (asynchronous PFCMRDAC-like consistency based bound estimation behavior)
Privacy Tradeoffs
2000 (CP DCS Workshop) - Meseguer&Jimenez (tradeoffs against efficiency)
2001 (IJCAI Workshop) - Freuder&Minca&Wallace (privacy measure)
Asynchronous Use Of Hierarchical Abstractions (IJCAI Workshop)
2001 (IJCAI DCR Workshop) - Silaghi&Haroud&Faltings
Applications
2000 (CP DCS Workshop) - Jung&Tambe&Zhang&Shen  (negotiation among Helicopters)
2000 (CP DCS Workshop) - Idrissi&Bouyakhf (Airplanes - traffic control)
2000 (CP DCS Workshop) - Eisenberg (task scheduling)
2001 (IJCAI DCR Workshop) - Silaghi&Haroud&Calisti&Faltings (General English Auctions)
2001 (IJCAI DCR Workshop) - Freuder&Minca&Wallace (meeting scheduling)
2001 (IJCAI DCR Workshop) - Modi&Jung&Tambe&Zhang&Shen and Gomes (multi-sensor target tracking)
History of Other Ideas

    1996 (ICMAS) - Yokoo&Hirayama (Local Search)
    1997 (IJCAI) - Armstrong&Durfee (Reordering heuristics with synchronization)
    2000 (CP DCS Workshop) Hirayama&Yokoo (Phase Transition in DisCSPs)
    2000 (CP DCS Workshop) Hannebauer (Proof with Petri Nets for DisCSPs)
    2000 (ICMAS) Willmott&Faltings&Macho&Calisti (XML-CSP)
    2001 (IJCAI DCR Workshop) - Razgon&Meisels (Value/Variable reordering in synchronous search)

History for DisCSP allowing for problem redistribution

Tutorial on distributed approaches to problem solving

2001 (IJCAI) J.Denzinger (more about distributed genetic algorithms)
Efficient Synchronous Search
1990 (IJCAI) Zeev&Dechter&Katz (Exploiting independent subproblems)
Canonic Model For Constraints that can be Redistributed
1995 (CP Workshop) Solotorevski&Meisels
Redistribution for SAT problems
2001 (IJCAI Workshop) Amir&McIllraith
Send comments to Marius-Calin Silaghi