- A limited and local view: every entity has a partial and local knowledge of its environment. - A set of simple rules: each entity follows a set of simple rules. - The interactions are manifold: each individual entity has a relationship with one or more other individuals in the group. •The emerging structure is useful to the community: different entities are a benefit to work (sometimes instinctively) and their performance is better than if they had been alone.

From these points of view, the paradigm of multi-agent systems seek to simulate the coordination of autonomous entities called agents that represent individuals in their community. An agent is an entity that can be viewed as perceiving and acting independently in its environment. According to J. Ferber [10] "One agent called a physical or virtual:
1) which can act in an environment, 2) that can communicate directly with other agents, 3) which is driven by a set of trends (in the form of individual objectives or function of satisfaction and even survival, it seeks to optimize), 4) which has its own resources, 5) which is able to collect (but limited) its environment, 6) which has only a partial representation of this environment (and possibly none), 7) has expertise and provides services, 8) which may be repeated, 9) whose behavior tends to meet its objectives, taking into account the resources and skills available to it and according to its perception, its representations and the communications it receives. "
Given such definition of the agent, we can define a multiagent system as a set of agents located in a certain environment. 

They share some common resources, and they interact with each other either directly or indirectly (via their effects on the environment). They seek to achieve the goals of individual agents in the interest of all. The multi-agent systems have applications in the field of artificial intelligence, where they reduce the complexity of solving a problem by dividing the necessary knowledge into sub-units, involving an intelligent agent independent at each of these sub - sets and coordinating the activity of these agents [10].

Because general definitions of inter-agent interaction are too vague we need to apply more strict and formal conventions to express allowable methods of communication between agents. Paradigm of constraints satisfaction, particularly distributed constraints satisfactions, offers flexible and convenient foundations to do this.

The paradigm of constraints satisfaction provides a generic method for declarative description of complex constrained or optimization problems in terms of variables and constraints [12, 13]. Formally, a Constraint Satisfaction Problem (CSP) is a triple (V, D, C) where: 
There is V = {v1, …, vn} is a set of n variables, a corresponding set D = {D(v1), …, D(vn)} of n domains from which each variable can take its values from, and C = {c1, …, cm} is a set of m constraints over the values of the variables in V. Each constraint ci = C(Vi) is a logical predicate over subset of variables Vi ⊆ V with an arbitrary arity k : ci(va, …, vk) that maps the Cartesian product D(va) × … × D(vk) to {0, 1}. As usual the value 1 means that the value combination for va, …, vkis allowed, and 0 otherwise. 

Constraints involving only two variables are called *binary* constraints [14]. A binary constraint between xi and xj can be denoted as cij. Although most of real world problems are represented by non-binary constraints, most of them can be transformed into binary ones using some techniques such as the dual graph method and hidden variable method [15]. Translating non-binary constraints into binary ones allows processing the CSP using efficient techniques adapted only for binary constraints. However, this translation implies normally an increase in number of constraints.

A solution for a CSP is an assignment of values for each variable in V such that all the constraints in C are satisfied. A single solver supports the tasks of collecting all data of the problem: variables, domains and constraints. It treats all such information in a centralized manner. 

A Distributed Constraint Satisfaction Problem (DCSP) is a CSP where the variables are distributed among agents in a MultiAgent System and the agents are connected by relationships that represent constraints. DCSP is a suitable abstraction to solve constrained problems without global control during per—to-peer agent communication and cooperation [16]. A DCSP can be formalized as a combination of (V, D, C, A, ∂) described as follows: V, D, C are the same as explained for an original CSP,
A = {a1, …, ap} is a set of p agents, and ∂ : V → A is a function used to map each variable vjto its owner agent ai.

Each variable belongs to only one agent, i.e. 

∀ v1, …, vk ∈ Vi ⇔ ∂ (v1) = … = ∂ (vk) where Vi ⊂ V represents the subset of variables that belong to agent ai. These subsets are distinct, i.e. V1 ∩ … ∩ Vp = ∅ and the union of all subsets represents the set of all variables, i.e. V1 ∪ … ∪ Vp = V. The distribution of variables among agents divides the set of constraints C into two subsets according to the variables involved within the constraint. The first set is the one of intraagent constraints C*intra* that represent the constraints over the variables owned by the same agent Cintra = {C(Vi) | ∂ (v1) = … = ∂ (vk), v1, …, vk ∈ Vi}.

The second set is the one of inter-agent constraints C*inter* that represents the constraints over the variables owned by two or more agents. Obviously, these two subsets are distinct Cintra ∩ C*inter* = ∅ and complementary Cintra ∪ C*inter* = C.

The variables involved within inter-agent constraints C*inter* are denoted as interface variables V*interface*. Assigning values to a variable in a constraint that belongs to C*inter* has a direct effect on all the agents which have variables involved in the same constraint. The interface variables should take values before the rest of the variables in the system in order to satisfy the constraints inside C*inter* firstly. Then, the satisfaction of internal constraints in C*intra* becomes an internal problem that can be treated separately inside each agent independently of other agents. If the agent cannot find a solution for its intra-agent constraints, it fails and requests another value proposition for its interface variables. To simplify things, we will assume that there are no intra-agent constraints, i.e. C*intra* = ∅. Therefore, all variables in V are interface variables V = V*interface*.

Many techniques are used to solve DCSPs. In general the technique proposes a distributed algorithm which is executed by 