DSCP'05 is the first edition of this international workshop, on Distributed and Speculative Constraint Processing. It will be held on October 1st, 2005, in conjunction with the Eleventh International Conference on Principles and Practice of Constraint Programming (CP'2005), in Sitges (Barcelona) Spain.

Overview:

DSCP'05 addresses constraint processing techniques in distributed environments, with a special interest on speculative computations.

A distributed constraint satisfaction problem (usually referred to as DisCSP) is a constraint satisfaction problem (CSP) in which multiple agents are involved. DisCSPs arise when pieces of the whole problem can be discharged / allocated to agents. These agents are generally independent (autonomous), but able to communicate, basically to let the others know (depending on the communication protocol) the result of their inner solving process. Pieces of the global problem may be, depending on the problem, variables, or constraints, or both.

Many problems in Multi-Agent Systems (MAS) can be formalized as DisCSPs. Therefore, we expect this workshop to impact a wide range of people, more specifically a lot of people involved in both CSP and MAS, or in either of these. Multi-agent systems are indeed very fashionable and convenient, for they make it possible, for instance, to take advantage of multi-processor machines, and for they also make it possible to design human-like efficient organizations of agents.

In addition to work on plain DisCSP, our workshop aims at emphasizing the process of speculative computations among agents. Indeed, even if multi-agent systems are very fashionable and convenient, their main limitation is that, as arises in human organizations, communication may be an issue: delayed or broken, it leads to incompleteness of the information in the reasoning structure. This is a concrete concern when we consider distributed systems such as the Internet, in which communication is indeed not guaranteed, and even if we could guarantee it, communication may either take time, or agents themselves may delay their sending information. In the case of such not ideal but practical situations, when problem-solving is at stake, frameworks for speculative computations can constitute a solution. Some work was already carried out on speculative constraint processing, but only in master-slave systems.

Scope of DSCP:

In this workshop, we would be pleased to gather together researchers interested in all aspects of distributed and/or speculative constraint solving, such as:

frameworks for DisCSPs

algorithms

communication protocols in DisCSPs

theoretical issues, such as space complexity

handling over-constrained DisCSPs, as well as performing optimization using DisCSPs

applications of DisCSPs

frameworks for speculative computations in MAS

theoretical work on communication protocols for speculative computation in MAS

algorithms for DisCSP solving with speculative computation

applications

...
We encourage in particular the submission of work in progress, of work on very specialized aspects of distributed and/or speculative constraint processing, and of work emphasizing real applications of DSCP.

Program:

Invited speaker: Ken Satoh, from the National Institute of Informatics in Tokyo (Japan)
Presentation on: Speculative Constraint Processing

Interactive Distributed Configuration,
by Tarik Hadzic, Thomas Stuart Henney, and Henrik Reif Andersen

Experimental results for solving job-shop scheduling problems with multiple SAT solvers,
by Takehide Soh, Katsumi Inoue, Mutsunori Banbara, and Naoyuki Tamura

Collaboration Model Based on Interval Constraints,
by Vitaly Telerman, Sergey Preis, Nikolay Snytnikov, and Dmitry Ushakov

Distributed Lagragean Relaxation Protocol for the Generalized Mutual Assignment,
by Katsutoshi Hirayama

Asynchronous Forward-Bounding for Distributed Constraints Optimization,
by Amir Gershman, Amnon Meisels, and Roie Zivan

Approximations in Distributed Optimization,
by Adrian Petcu and Boi Faltings

Registration:

Details about registration to this workshop are available here.
Registration is possible here.

Organizing committee:

Martine Ceberio (Primary contact)
University of Texas at El Paso - USA
e-mail: mceberio@utep.edu
url: http://www.cs.utep.edu/mceberio

Makoto Yokoo
Kyushu University -- Fukuoka -- Japan
e-mail: yokoo@is.kyushu-u.ac.jp

Enrico Pontelli
New Mexico State University -- USA
e-mail: epontell@cs.nmsu.edu

Boi Faltings
EPFL -- Swiss Federal Institute of Technology -- Switzerland
e-mail: Boi.Faltings@epfl.ch

Weixiong Zhang
Washington University -- St. Louis -- USA
e-mail: zhang@cse.wustl.edu

Hiroshi Hosobe
National Institute of Informatics -- Tokyo -- Japan
e-mail: hosobe@nii.ac.jp

Jay Modi
Carnegie Mellon University -- Pittsburg -- USA
e-mail: pmodi@cs.cmu.edu


Back to top of the page