Nowadays, many real problems can be modelled as constraint
satisfaction problems (CSPs) and solved using specific constraint
satisfaction techniques. These include problems from fields such
as artificial intelligence, operational research, information
systems, databases, etc. Most of these problems can be naturally
modelled using CSPs. However, some of these problems are of a
distributed nature either for reasons of security, for privacy
requirements, or for spatial constraints; this requires that
problems of this kind must be modelled as distributed constraint
satisfaction problems (DCSPs), where the set of variables and
constraints of the problem are distributed among a set of agents
who are in charge of solving their own sub-problem and must
coordinate themselves with the rest of the agents in order to
reach a solution to the global problem.

In the Literature of constraint satisfaction, the need to handle
DCSP emerged at the beginning of the 90s. However, most
researchers who work in this field focus their attention on
algorithms in which each agent handles a single variable. Even
though  these algorithms can be transformed so that each agent
handles multiple variables, none of the resulting algorithms
scales up well as the size of the problems increases due to space
requirements and/or computacional cost. Therefore, the resolution
of real problems with algorithms of this type, in practice, is not
viable.

In this thesis, we present new algorithms for the resolution of
distributed constraint satisfaction problems that are able to
handle multiple variables by agent. These algorithms handle the
data obtained by means of communication between the agents in
order to obtain greater efficiency during the resolution process.
In addition, their space requirements are minimum which is why
they are able to handle large, local sub-problems. Several
algorithms and heuristic techniques are presented in this thesis
so that each agent carries out effectively the search of partial
solutions of his sub-problem.

In addition, constraint satisfaction problems can also model large
real problems, they generally  imply models with a great number of
variables and constraints.These problems often have clear, smaller
sub-problems. These problems can be handled as a whole only at
overwhelming computational cost. This leads to one more
contribution of this thesis: it is based on the problem partition
so that, they can subsequently be solved more effectively by means
of the proposed algorithms that solve DCSPs. In this thesis we
propose three ways to divide a problem: first one is based on
techniques of  graph partitioning, the second  is based on the
identification of tree structures and third is based on the
identification of problem common entities. Both the partitioning
methodologies and the algorithms to solve DCSPs represent the
heart of this thesis. Finally, we evaluate the proposed method,
make a review and think about the future work.