IJCAI-2005 Slides /AAMAS-2004 Slides / IJCAI-2003 Slides

Tutorial on Distributed Constraint Reasoning

Presenters: Jörg Denzinger, Marius Silaghi, Makoto Yokoo

Description

Due to the unprecedented expansion of the Internet, a major change occurs in
our life and habits. We can expect that some software agents would work on
our behalf, representing our interests and defending our privacy. A
principled approach to the achievement of this dream is proposed by the
Distributed Constraint Reasoning community which offers a general framework
and powerful competitive techniques to approach these important applications.
Distributed Constraint Satisfaction is the outcome of intensive research
performed in the 80ies and tries to offer equal opportunities to participants
in cooperative or semi-cooperative distributed resource allocation problems.
The field got a clear contour in the beginning of the 90ies when researchers
proved the main theoretical limitations of distributed computations. This was
followed by a decade of research that continuously increases its intensity
studying trade-offs between efficiency, privacy, security, and openness.

This tutorial will provide an unified view on Distributed Constraint
Reasoning, introducing distributed constraint reasoning systems as
semi-cooperative multi-agent systems and concentrating on the privacy,
communication and organization requirements of such systems. The general
ideas behind the known distributed constraint reasoning systems are presented
within this multi-agent framework. For each approach, the requirements,
limitations, advantages and disadvantages of the different categories will be
discussed.

Prerequisite knowledge:

The tutorial is targeted at the general AI audience, both academic and industrial, working in AI fields that employ search at the core of their systems. It requires only a basic knowledge in standard algorithm schemes, like branch-and-bound or local optimization techniques.

Table of Content:

1. Introduction: Distributed Search and Distributed Constraint Reasoning
   distribution concepts and their motivation, peculiarities and motivations for distributing or maintaining problems distributed.
2. Frameworks for Distributed Constraint Reasoning
   frameworks for artificially distributed versus frameworks for naturally distributed problems. Frameworks for privacy requirements.
3. Properties and Applications
   
1. Samples of Applications:
   (open systems for tracking targets, coordinating emitors, scheduling, auctions)
   
2. Privacy and openness
   (alternative techniques for maintaining privacy, classification of approaches to open and dynamic systems)
   
4. Secure Multi-party Computations
   
1. Simple Secure Multi-party Computations
   (computing summations)
   
2. Shamir's Secret Sharing
   (representing secrets in ways that enable distributed processing)
   
3. Secure Function Evaluation
   (basic distributed processing of secrets, simulating arithmetic circuit evaluation)
4. Homomorphic Encryption for Distributed Secure Computations
   (distributed processing of secrets based on encryption)
   
5. Secure techniques for Solving Distributed Constraint Satisfaction Problems
   
1. Solvers based on Homomorphic Encryption
   (trusted pasrty approaches, distributing trust, encoding distributed constraints)
   
2. Solvers based on Secure Function Evaluation
   (secure distributed solvers for satisfaction and optimization problems)
   
3. Distributed Constraint Reasoning Frameworks for secure computations
   (frameworks for modeling team-making problems and auctions)
   
6. Centralized Search and its Distribution
   
1. Centralized backtracking and straightforward operational distributions
   (introduce centralized search, look-ahead, reordering, and consistency maintenance, the synchronization as simple way of distributing algorithms)
   
2. Improved Distributions
   (idle processors and parallelism, improved problem distribution as means of improving the communication)
3. Unhindered parallelism in distributed search
   (real impediments to parallelism, theoretical results for distribution techniques as solution to lack of parallelism)
7. Asynchronous techniques
   
1. Asynchronism
   (what is asynchronism and why bother, framework and explaining results, need and drawbacks of ordering)
2. Analysis of equivalences to centralized backtracking
   (phenomenal analysis versus operational analysis, enumeration, phenomenal extensions of other centralized search techniques)
3. Sources of parallelism in asynchronous solving
   (parallelism and commitment, the roots of committment)
   
8. Incomplete Search for DisCSPs
1. Why (not) completeness
   (impossibility results and natural approaches to resource allocation)
   
2. Efficient Algorithms with(without) structure
   (structure and synchronisation as slowing factors in distributed processes, how far are we from completeness)
9. Overview of State of The Art
   

Last Change: 02/20/2005