Younes Mechqrane
email: ymechqrane@gmail.com

Mohamed Wahbi
email: mohamed.wahbi@insight-centre.org

Christian Bessiere
email: bessiere@lirmm.fr

Kenneth N Brown
email: ken.brown@insight-centre.org

Reordering All Agents in Asynchronous Backtracking for Distributed Constraint Satisfaction Problems

Keywords: Distributed Constraint Reasoning, Asynchronous Backtracking, Dynamic Variable Ordering

Distributed constraint satisfaction problems (DisCSPs) can express decision problems where physically distributed agents control different decision variables, but must coordinate with each other to agree on a global solution. Asynchronous Backtracking (ABT) is a pivotal search procedure for DisCSPs. ABT requires a static total ordering on the agents. However, reordering agents during search is an essential component for efficiently solving a DisCSP. All polynomial space algorithms proposed so far to improve ABT by reordering agents during search only allow a limited amount of reordering. In this paper, we propose AgileABT, a general framework for reordering agents asynchronously that is able to change the ordering of all agents. This is done via the original notion of termination value, a label attached to the orders exchanged by agents during search. We prove that AgileABT is sound and complete. We show that, thanks to termination values, our framework allows us to implement the main variable ordering heuristics from centralized CSPs, which until now could not be applied to the distributed setting. We prove that AgileABT terminates and has a polynomial space complexity in all these cases. Our empirical study shows the significance of our framework compared to state-of-the-art asynchronous dynamic ordering algorithms for solving distributed CSP.

Introduction

Distributed artificial intelligence involves numerous combinatorial problems where multiple physically distributed entities, called agents, need to cooperate in order to find a consistent combination of actions. Examples of such problems are: traffic light synchronization [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF], truck task coordination [START_REF] Ottens | Coordination Agent Plans Trough Distributed Constraint Optimization[END_REF], target tracking in distributed sensor networks [START_REF] Jung | Argumentation As Distributed Constraint Satisfaction: Applications and Results[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Modi | Adopt: Asynchronous Distributed Constraint Optimization with Quality Guarantees[END_REF], distributed scheduling [START_REF] Maheswaran | Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling[END_REF], distributed planning [START_REF] Bonnet-Torrés | Multiply-Constrained DCOP for Distributed Planning and Scheduling[END_REF], nurse shift assignment problem [START_REF] Kaplansky | Distributed Personnel Scheduling-Negotiation Among Scheduling Agents[END_REF], distributed resource allocation [START_REF] Petcu | A Value Ordering Heuristic for Distributed Resource Allocation[END_REF], distributed vehicle routing [START_REF] Léauté | Coordinating Logistics Operations with Privacy Guarantees[END_REF], etc. In these problems agents have to achieve the combination in a distributed way and without centralization. In general, this condition is mainly motivated by privacy and/or security requirements: constraints or possible values may be strategic information that should not be revealed to other agents that can be seen as competitors. In addition, in many distributed settings, gathering the whole knowledge into a centralized agent may be impractical or its cost may be intolerable. In the field of multiagent coordination, the above-mentioned problems were formalized using the distributed constraint satisfaction problem (DisCSP) paradigm that allows a distributed solving process.

A DisCSP is composed of multiple agents, each owning its local constraint network. Variables in different agents are connected by constraints. The agent community must assign a value to each variable so that all constraints are satisfied. To achieve this, agents assign values to their own variables that satisfy their own constraints; to satisfy constraints involving variables with other agents, they must exchange messages about their decisions and revise those decisions accordingly.

During the last two decades, many distributed algorithms have been designed

for solving DisCSPs, among which Asynchronous Backtracking (ABT) is the central one [START_REF] Yokoo | The Distributed Constraint Satisfaction Problem: Formalization and Algorithms[END_REF][START_REF] Bessière | Asynchronous Backtracking Without Adding Links: A New Member in the ABT Family[END_REF]. ABT is an asynchronous algorithm executed concurrently and autonomously by all agents in the distributed problem. Agents are not required to wait for the decisions of other agents. ABT assumes a single static total priority order on the agents. For a given agent, those agents that appear before it in the order are higher priority, while those that appear after it are lower priority. When an agent performs an assignment, it sends out messages to lower priority neighbors informing them about its new assignment. Each agent tries to find an assignment satisfying the constraints with what is currently known from higher priority neighbors, and whenever an agent detects a dead end, it determines a conflict set of assignments (called a no-good) that is responsible for the inconsistency. Because a superset of a no-good cannot be a solution, the generator of the no-good sends a message to the lowest priority agent involved in the conflict set (i.e., the backtracking target) in order to revise its current assignment.

A strong weakness in ABT is the static order on the agents. It is known from centralized CSPs that reordering variables dynamically during search dramatically improves the efficiency of the search procedure [START_REF] Haralick | Increasing Tree Search Efficiency for Constraint Satisfaction Problems[END_REF][START_REF] Bessière | MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems[END_REF][START_REF] Boussemart | Boosting Systematic Search by Weighting Constraints[END_REF]. Hence, several extensions of ABT have been proposed to dynamically reorder variables during search, leading to a more flexible exploration of the search space. Silaghi et al. [START_REF] Silaghi | Hybridizing ABT and AWC into a polynomial space, complete protocol with reordering[END_REF] proposed asynchronous backtracking with reordering (ABTR). ABTR is an asynchronous complete algorithm with polynomial space requirements where abstract agents fulfill the reordering operation. Zivan and Meisels [START_REF] Zivan | Dynamic Ordering for Asynchronous Backtracking on DisCSPs[END_REF] proposed dynamic ordering for asynchronous backtracking (ABT DO). Three different ordering heuristics were proposed to reorder lower priority agents in ABT DO: random, min-domain [START_REF] Brito | Synchronous, Asynchronous and Hybrid Algorithms for DisCSP[END_REF] and no-good-triggered. The experimental results in [START_REF] Zivan | Dynamic Ordering for Asynchronous Backtracking on DisCSPs[END_REF] show that no-good-triggered, where the generator of the no-good is placed just after the target of the backtrack, is the best. Silaghi [START_REF] Silaghi | Framework for Modeling Reordering Heuristics for Asynchronous Backtracking[END_REF] has shown that ABT DO, when used with no-good-triggered, is equivalent to ABTR when used with the ABTR-db dynamic-backtracking self redelegation heuristic.

While the above-mentioned algorithms have led to great improvement in performance compared to ABT, they all share the same weakness. Whenever a no-good is discovered, the agent that must change its assignment is that with the lowest priority among the conflicting set, and no lower agent can be moved to a position higher than this target of the backtrack. This restriction is a major source of inefficiency for these algorithms. If a bad variable assignment is made high in the agents order, an exhaustive search of lower priority agents must be performed before being able to reach back to the culprit variable.

A new kind of ordering heuristics for ABT DO is presented in [START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF][START_REF] Mechqrane | Corrigendum to "Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF]. These heuristics enable the reordering of agents that are higher than the backtracking target. The resulting algorithm is called ABT DO Retro. The degree of flexibility of the heuristics ABT DO Retro can implement depends on the value of a predefined parameter K that determines the no-good storage capacity. Agents are limited to store no-goods with a size equal to or smaller than K. The space complexity of ABT DO Retro agents is thus exponential in K.

Finally, asynchronous weak commitment (AWC), proposed by Yokoo [START_REF] Yokoo | Asynchronous Weak-commitment Search for solving Distributed Constraint Satisfaction Problems[END_REF], is the algorithm that has the highest degree of flexibility to reorder agents during search. AWC dynamically reorders agents by moving the sender of a no-good higher in the order than the other agents in the no-good. Thus, when a dead end occurs, AWC is not committed to the current partial assignment of agents.

It starts constructing a new partial assignment from scratch. AWC stores all the abandoned partial assignments in order to ensure termination. AWC can be seen as the special case of ABT DO Retro when K = n. AWC was shown to outperform ABT on small problems [START_REF] Hirayama | An Approach to Over-constrained Distributed Constraint Satisfaction Problems: Distributed Hierarchical Constraint Satisfaction[END_REF]. However, AWC requires an exponential space for storing all generated no-goods. This high space complexity prevents its use on larger problems.

All algorithms we discussed have shown empirically the benefit of reordering agents during distributed asynchronous search. However, we observe that those that allow the greatest flexibility (i.e., AWC and ABT DO Retro) pay it at the cost of an exponential space complexity for storing no-goods.

In this paper, we propose agile asynchronous backtracking, AgileABT, a distributed constraint satisfaction framework that allows reordering of all agents during search without requiring exponential space. Agents operate asynchronously, and at any stage an agent may propose a reordering. Each proposal must be associated with some auxiliary information, which we call a termination value. Agents accept or reject the suggested reordering using a priority relation over termination values. The termination values are mathematical objects that could be simple scalar values, or could be more complex structures based on the intrinsic properties of the proposed reordering. The general framework AgileABT is instantiated by specifying a function used to compute new orders and their associated termination values together with the priority relation over the computed termination values. If the priority relation is a well ordering, then AgileABT is guaranteed to terminate; if the function used to compute new orders and their associated termination values has polynomial space complexity, then AgileABT has polynomial space complexity as well.

The general framework AgileABT can be instantiated in several possible ways. We only present some examples in this paper. In our examples, any agent can propose a reordering of all other agents, including those appearing before the backtrack target, provided that the termination value is improved w.r.t. the priority relation over the termination values. As a consequence of this agile reordering capability, an agent is able to propose any other conflicting agent as a backtracking target, provided that the target agent is the last among the conflicting ones in the new ordering. These features are unique for a DisCSP algorithm with polynomial space complexity. Our motivation was to study in a distributed setting some of the most effective DVOs heuristics from centralized CSP. We show how to implement the most common DVOs from CSP, and we evaluate their performance on DisCSP benchmarks. Our empirical results show that the DVOs implemented in AgileABT can offer orders of magnitude improvement in both computation and messaging costs compared to the original static ABT, and that they consistently outperform previous proposals for dynamic ordering in ABT.

The reminder of the paper is organized as follows. We give the necessary background on distributed CSP and dynamic reordering materials in Section 2. Section 3 introduces the general framework of Agile Asynchronous Backtracking, AgileABT and analyses its theoretical properties. Section 4 presents some instantiation examples of AgileABT and their proof of correctness. We report our empirical results in Section 6. Finally, we conclude in Section 7.

Background

Constraint programming is one of the main fields in artificial intelligence for studying combinatorial problems. Constraint Programming is based on approaches to solving a generic problem definition (constraint satisfaction problem) over a constraint network.

A constraint network is defined by a set of decision variables, their domain of possible values, and a set of constraints. Constraints represent restrictions on value combinations allowed for constrained variables. A solution is an assignment of values to decision variables that satisfies all the constraints. CSP is a general framework that can formalize many real world combinatorial problems whenever the knowledge about the whole problem is available for a (centralized) solver.

Basic definitions and notations

The distributed constraint satisfaction problem (DisCSP) consists in looking for solutions to a distributed constraint network. A distributed constraint network has been defined in [START_REF] Yokoo | The Distributed Constraint Satisfaction Problem: Formalization and Algorithms[END_REF] as a tuple (A, X , D, C), where A is a set of m agents {a 1 , . . . , a m }, X is a set of n variables {x 1 , . . . , x n }, where each variable

x i is controlled by one agent in A. D = {D 1 , . . . , D n } is a set of n domains,
where D i is the initial set of possible values to which variable x i may be assigned. During search, values may be pruned from the domain. At any node, the set of possible values for variable x i is denoted by D c i and is called the current domain of x i . Only the agent which controls a variable has knowledge of its current domain and can assign it a value. C is a set of constraints that specify the combinations of values which may be assigned simultaneously for the variables they involve. A constraint may involve variables from several agents. For this paper, we restrict our attention to binary constraints (i. e., constraints that involve two variables). A constraint c ij ∈ C between two variables x i and x j is a subset of the Cartesian product of their domains (c ij ⊆ D i × D j ). Each agent a i only knows constraints involving its variables, denoted by C i . When there exists a constraint between two variables x i and x j , these variables are called neighbors. The set of neighbors of a variable x i is denoted by Γ i . The connectivity between the variables can be represented with a constraint graph, where vertices represent the variables and edges represent the constraints [START_REF] Dechter | Constraint Networks (Survey)[END_REF].

A solution is an assignment to each variable of a value from its domain, satisfying all constraints. In order to propagate constraints locally, we assume that each agent in the system knows the initial domain of each neighbor and keeps a local copy of that domain.

For simplicity purposes, we assume each agent controls exactly one variable (m = n), so we use the terms agent and variable interchangeably and do not distinguish between a i and x i . For the rest of the paper we consider a generic agent a i ∈ A. Agent a i stores a unique total order on agents, i.e. a vector of n agents IDs, denoted by λ i . λ i is called the current order of a i . We denote by λ i [k] (∀k ∈ 1..n) the ID of the agent located at position k in λ i . Agents appearing before agent a i in λ i are the higher priority agents denoted by λ - i and conversely the lower priority agents λ + i are agents appearing after a i in λ i . The order λ i divides the set Γ i of neighbors of a i into higher priority neighbors Γ - i , and lower priority neighbors Γ + i . Figure 1 presents an example of a DisCSP instance. This problem consists of 5 agents with the following domains ∀i ∈ 1..5, D i = {1, 2, 3, 4} and 6 constraints among these agents c 12 : To solve a DisCSP, agents assign values to their variables and exchange messages to satisfy constraints with variables owned by other agents. Each agent maintains a counter, and increments it whenever it changes its value. The current value of the counter tags each generated assignment.

x 1 = x 2 , c 13 : x 1 = x 3 , c 15 : x 1 = |x 5 -2|,
Definition 1. Given a DisCSP defined by the network (A, X , D, C), an assignment for an agent a i ∈ A is a tuple (x i , v i , t i ), where v i ∈ D i is the value to which variable x i is assigned, and t i ∈ N is the timestamp tagging the assignement. Given two assignments (x i , v i , t i ) and

(x i , v i , t i ), if v i = v i then t i = t i by construction. If t i > t i , (x i , v i , t i
) is said to be more up to date than (x i , v i , t i ). Two sets of assignments are compatible if every common variable is assigned the same value in both sets.

Definition 2. The agent-view of an agent a i , AV , stores the most up to date assignments received from other agents. It is initialized to the set of empty assignments. AV -denotes the locally stored assignments of higher agents w.r.t. the current order λ i stored by agent a i .

During search agents can infer inconsistent sets of assignments called nogoods. Agents use these no-goods to justify value removals. Definition 3. A no-good ruling out value v i from the initial domain of a variable

x i , ngd[x i =v i ], is a clause of the form [x j = v j ∧ . . . ∧ x k = v k ] → x i =v i ,
meaning that the assignment x i = v i is inconsistent with the assignments

x j = v j ∧ . . . ∧ x k = v k .
The left hand side (lhs) and the right hand side (rhs) are defined from the position of →. We say that a no-good is compatible with an agent-view AV if its lhs is compatible with AV . Each value removal from D i is justified by a no-good. The current domain D c i of a variable x i contains all values from the initial domain D i that are not ruled out by a no-good. The initial domain size of a i is denoted by d i while its current domain size is denoted by

d c i (i. e., d c i = |D c i | and d i = |D i |)
. Let Λ i be the conjunction of the left-hand sides of all no-goods ruling out values from D i , i.e.

Λ i = vi∈{Di\D c i } lhs(ngd[x i =v i ])
. When all values of a variable x i are ruled out by no-goods (D c i = ∅), these no-goods are resolved, producing a new no-good from the conjunction of their left-hand sides (Λ i ) meaning that at least one of the variables in Λ i needs to change its value. There are clearly many different ways of representing Λ i as a no-good. In standard backtracking search algorithms (like ABT), the variable that has the lowest priority in the current order among the conflicting variables must change its value. We will see later how our framework relaxes this restriction. be that variable that must change its value, i.e. to be put in the rhs of the new no-good. The variable x t is called the backtracking target.

Λ i \ (x t = v t )] → x t =v t .
The new generated no-good will be used as justification for removing the value v t of the variable x t once sent to agent a t . The variables in the lhs of a no-good must precede the variable on its rhs in the current order because the assignments of these variables have been used to filter the domain of the variable in its rhs. These ordering constraints induced by a no-good are called safety conditions in [START_REF] Ginsberg | GSAT and Dynamic Backtracking[END_REF]. Definition 4. A safety condition is an assertion x j ≺ x k meaning that x j must precede x k in the ordering. We say that a no-good is coherent with an order λ i if all agents in its lhs appear before its rhs in λ i .

For example, the no-good [x j = v j ∧ x k = v k ] → x i =v i implies that x j ≺ x i and x k ≺ x i , that is x j and x k must precede x i in the variable ordering (i. e., x j , x k ∈ λ - i ).

Asynchronous Backtracking -ABT

The first complete asynchronous search algorithm for solving DisCSPs is asynchronous backtracking (ABT) [START_REF] Yokoo | Distributed constraint satisfaction for formalizing distributed problem solving[END_REF][START_REF] Bessière | Asynchronous Backtracking Without Adding Links: A New Member in the ABT Family[END_REF]. In ABT, agents act concurrently and asynchronously, and do not have to wait for decisions of others. However, to be complete, ABT requires a total priority ordering on agents (λ i ). The priority order of agents is static and uniform across the agents. The required total ordering on agents in ABT induces a directed acyclic constraint graph where constraints are represented by directed links according to the total order among agents. Hence, a directed link between each two constrained agents is established. ABT performs asynchronous search based on this structure. The agent to which the direct link arrives is the agent evaluating the constraint represented by that link. Consider the instance of Figure 1 and a lexicographic ordering on agents λ = [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF][START_REF] Ottens | Coordination Agent Plans Trough Distributed Constraint Optimization[END_REF][START_REF] Jung | Argumentation As Distributed Constraint Satisfaction: Applications and Results[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Modi | Adopt: Asynchronous Distributed Constraint Optimization with Quality Guarantees[END_REF]. The ordering λ induces the acyclic constraint graph shown in Figure 2. Constraints are represented by directed links from higher to lower priority neighbors. Agent a 2 evaluates constraint c 12 because it has a lower priority than a 1 in λ, a 3 evaluates c 13 , a 4 evaluates c 34 , and a 5 evaluates constraints c 15 , c 25 , and c 45 .

In ABT, each agent a i tries to find an assignment satisfying the constraints with what is currently known from higher priority neighbors Γ - i . When an agent a i assigns a value to its variable, it sends out messages to lower priority neighbors Γ + i informing them about its assignment. When no value is possible for a variable x i , a i resolves its no-goods producing a new no-good ngd[x t =v t ] from Λ i . Next, agent a i reports the resolved no-good ngd[x t =v t ] to agent a t .

ABT computes a solution (or detects that no solution exists) in a finite time.

Furthermore, in ABT, each agent a i , stores in its agent-view, AV , the most up to date assignments that it believes are assigned to higher priority neighbors. To stay polynomial in space, agent a i only keeps one no-good per removed value. When two no-goods eliminating the same value are possible, the no-good with the highest possible lowest variable involved is selected (HPLV heuristic) [START_REF] Hirayama | The Effect of Nogood Learning in Distributed Constraint Satisfaction[END_REF]. By doing so, when an empty domain is found, the resolved no-good contains variables as high as possible in the ordering, so that the backtrack message is sent as high as possible, thus saving unnecessary search effort [START_REF] Bessière | Asynchronous Backtracking Without Adding Links: A New Member in the ABT Family[END_REF]. In the following, v i will represent the current value assigned to x i and t i the counter tagging v i . t i is used for the timestamp mechanism of generated assignments. ABT agents exchange the following types of messages:

• ok? message used to notify its recipients of a new assignment of the sender.

• ngd message used to report a no-good to its receiver agent, requesting the removal of its value.

• adl message used to request the addition of a link to the receiver.

• stp message used to inform all agents to stop the search meaning that the problem is unsolvable because an empty no-good has been generated.

The pseudo-code of ABT executed by every agent a i ∈ A is presented in Figure 3. In the main procedure ABT(), each agent assigns a value to its variable and informs its lower priority neighbors Γ + i (assignVariable() call, line 2). Then, it loops for processing the received messages (lines 3 to 9).

Procedure assignVariable is used by agent a i to select a consistent value for x i from its current domain D c i (chooseValue call, line 15). During this process, some values from D c i may appear as inconsistent. Thus, a i removes inconsistent values from D c i and stores the no-goods justifying their removals (line 18). To ensure a polynomial space complexity, agents keep only one nogood per removed value. If chooseValue finds a consistent value, it is assigned to x i and agent a i notifies all its lower priority neighbors (Γ + i ) about its new assignment through ok? messages (line 22) after incrementing the tag counter t i . Otherwise, agent a i must identify the subset of higher agents' assignments responsible for the failure, i.e. its domain wipe-out (procedure backtrack() call, line 23). Whenever agent a i receives an ok? message from a higher agent a s , it processes it by calling procedure processOk( x s , v s , t s ), line 6. The agent-view of a i is updated (updateAgentView call, lines 28 and 30) only if the received message contains an assignment more up to date than that already stored for the sender a s (lines 27 to 28). Next, all no-goods that become incompatible with the agent-view of a i are removed (line 29). Then, a consistent value for a i is searched if necessary after the change in the agent-view (checkAgentView call, line 31). In procedure checkAgentView(), agent a i checks whether its current assignment (v i ) is consistent with assignments of higher priority neighbors, i.e. AV -. If it is not the case, agent a i seeks a new consistent value (assignVariable call, line 25).

When every value of variable x i is forbidden by a stored no-good, procedure backtrack() is called. The first step of this procedure is to determine the set Λ i of variable assignments responsible for the failure. If Λ i is empty, then the DisCSP has no solution. Agent a i sends stp messages to all agents and terminates its execution (lines 33 to 35). Otherwise, agent a i selects the variable x t that has the lowest priority among the variables in the conflicting set Λ i to be the backtracking target, generating a new no-good, ngd[x t =v t ] (lines 37 to 38). The generated no-good is sent in a ngd message to the agent a t owning the variable x t , line 39. Then, the assignment of x t is deleted from the agent-view (updateAgentView call, line 40). Finally, a new consistent value is selected (checkAgentView call, line 41).

Whenever agent a i receives a ngd message, procedure processNgd is called, line 7. In this procedure, agent a i calls procedure checkAddLink (line 42) in order to update its agent-view with the newer assignments contained in the left hand side of the received no-good (updateAgentView call, line 52) and to request the establishment of new links with non-neighbors agents owning variables on the the left hand side of the received no-good (lines 53 to 56). Then, agent a i checks if the received no-good is compatible with its agent-view (Definition 3). The no-good is accepted only if it is compatible with the assignments of higher priority agents, i.e. AV -(line 43). An accepted no-good is stored in order to justify the removal of the value on its rhs (line 44). If the current value of a i is the same as the rhs of the accepted no-good then a new consistent value for a i is searched (checkAgentView call, line 46). If the no-good is not accepted, it is discarded, but if the value in its rhs was correct, a i re-sends its assignment to the no-good sender (a s ) through an ok? message (lines 47 and 48).

When a link request is received, agent a i calls procedure processAdl in order to include the sender in Γ i (line 49). Afterwards, agent a i sends its assignment through an ok? message to the sender of the request if its value is different from that included in the received adl message (lines 50 and 51).

It has been proven in [START_REF] Yokoo | Distributed Constraint Satisfaction: Foundations of Cooperation in Multi-Agent Systems[END_REF][START_REF] Bessière | Asynchronous Backtracking Without Adding Links: A New Member in the ABT Family[END_REF] that ABT is sound, complete and terminates.

Set Theory

Let S be a set and ≺ be a relation on S. (S, ≺) is a total ordering if and only if for all a, b in S, either a ≺ b or b ≺ a or a = b. Definition 5. We say that ≺ well-orders S, or (S, ≺) is a well-ordering, iff (S, ≺) is a total ordering and every non-empty subset of S has a ≺-least element, i.e. for every B ⊆ S, B = ∅, there exists a ∈ B such that for every b ∈ B we have a b.

Well-orders have the following interesting property.

Proposition 1 ([29]

). An ordered set is well ordered if and only if it does not include an infinite decreasing sequence.

The General Framework AgileABT

In this section, we propose agile asynchronous backtracking (AgileABT), a general framework for reordering agents asynchronously. In AgileABT, all agents start with the same order. Then, agents are allowed to change the order asynchronously. There is one major issue to be solved for allowing agents to asynchronously propose new orders. The agents must be able to coherently decide which among different orders to select. We propose to establish a priority relation between orders via their termination value, a label attached to the orders exchanged by agents during search. Termination values are auxiliary information associated with each suggested reordering. New orders and their termination values are computed by a function, denoted by f() in the rest of the paper. Agents accept or reject a suggested reordering using the priority relation over termination values. Termination values can be simple scalar values, or more complex structures based on some features of the agents. As in AgileABT every agent can change the order without any global control, whenever changing the order, agent a i informs other agents of the new order by sending them its new order λ i and its associated termination value, denoted by τ i . When an agent compares two pairs order/termination value, the strongest pair is chosen. Definition 6. Let λ i and λ j be two total agent orderings and τ i and τ j their associated termination values. The pair (λ i , τ i ) is stronger than the pair (λ j , τ j ) if and only if the termination value τ i is smaller than τ j w.r.t. the priority relation ≺ τ over the range of termination values, or τ i = τ j and the vector of agents IDs in λ i is smaller than the vector of agents IDs in λ j w.r.t. the lexicographic order < lex .

Consider for instance the three orders on five agents λ i = [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF][START_REF] Ottens | Coordination Agent Plans Trough Distributed Constraint Optimization[END_REF][START_REF] Jung | Argumentation As Distributed Constraint Satisfaction: Applications and Results[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Modi | Adopt: Asynchronous Distributed Constraint Optimization with Quality Guarantees[END_REF], [START_REF] Ottens | Coordination Agent Plans Trough Distributed Constraint Optimization[END_REF][START_REF] Modi | Adopt: Asynchronous Distributed Constraint Optimization with Quality Guarantees[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Jung | Argumentation As Distributed Constraint Satisfaction: Applications and Results[END_REF] and λ i = [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF][START_REF] Ottens | Coordination Agent Plans Trough Distributed Constraint Optimization[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Modi | Adopt: Asynchronous Distributed Constraint Optimization with Quality Guarantees[END_REF][START_REF] Jung | Argumentation As Distributed Constraint Satisfaction: Applications and Results[END_REF]. If the termination value τ i associated with λ i is smaller than the termination value τ i associated with λ i , the pair (λ i , τ i ) is stronger than the pair (λ i , τ i ). If the termination value τ i associated with λ i is equal to the termination value associated with λ i , the pair (λ i , τ i ) is stronger than the pair (λ i , τ i ) because the vector [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF][START_REF] Ottens | Coordination Agent Plans Trough Distributed Constraint Optimization[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Modi | Adopt: Asynchronous Distributed Constraint Optimization with Quality Guarantees[END_REF][START_REF] Jung | Argumentation As Distributed Constraint Satisfaction: Applications and Results[END_REF] of IDs in λ i is lexicographically smaller than the vector [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF][START_REF] Ottens | Coordination Agent Plans Trough Distributed Constraint Optimization[END_REF][START_REF] Modi | Adopt: Asynchronous Distributed Constraint Optimization with Quality Guarantees[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Jung | Argumentation As Distributed Constraint Satisfaction: Applications and Results[END_REF] of IDs in λ i .

λ i = [1,

The algorithm AgileABT

In AgileABT, agents exchange the following types of messages:

• ok? message used to notify its recipients of a new assignment of the sender.

• ngd message used to report a no-good to its receiver agent, requesting the removal of its value.

• adl message used to request the addition of a link to the receiver.

• order message is sent to propose a new order. This message includes the proposed order together with its associated termination value λ, τ .

• stp message used to inform all agents to stop the search meaning that the problem is unsolvable because an empty no-good has been generated.

The pseudo-code of AgileABT executed by every agent a i ∈ A is presented in Figure 4. In the following, v i will represent the current value assigned to x i and t i the counter tagging v i . t i is used for the timestamp mechanism of generated assignments. In the main procedure AgileABT, after initialization of the data structures (line 1) each agent assigns a value to its variable and informs its lower priority neighbors Γ + i through ok? messages (assignVariable call, line 2). Then, it loops for processing the received messages (lines 3 to 10).

Procedures initialize, chooseValue, assignVariable, checkAgentView, updateAgentView, processOk, processAdl, and checkAddLink are exactly the same as in ABT. We reproduce them in Figure 4 but we do not repeat the description.

The procedure backtrack() is called when a dead end occurs (i.e., when every value of variable x i is forbidden by a stored no-good). The first step of this procedure is to determine the set Λ i of variable assignments responsible for the failure (resolveNogoods() call, line 37). If Λ i is empty, then the DisCSP has no solution. Agent a i sends stp messages to all agents and terminates its execution (lines 38 to 40). Otherwise, agent a i is allowed to propose a new order (proposeOrder() call, line 43). After the reordering, agent a i selects the variable x t that has the lowest priority among the variables in the conflicting set Λ i to be the backtracking target, generating a new no-good, ngd[x t =v t ] (lines 44 to 45). The generated no-good is sent in a ngd message to agent a t owning the variable x t , line 46. It is important to note that as a consequence of changing ordering, x t was not necessarily the lowest variable in ngd[x t =v t ] on the agent ordering when calling procedure backtrack(). The assignment of x t is deleted from the agent-view (updateAgentView call, line 47). Finally, agent a i checks if its current assignment is consistent with assignments of higher agents AV -. If it is the case, agent a i has to send its assignment through ok? messages to its lower neighbors who did not receive it beforehand because they had a higher priority in previous agent ordering, line 49. If v i is inconsistent with AV -, agent a i tries to select a new consistent value (assignVariable() call, line 50).

The procedure proposeOrder() calls function f() to generate a new order λ and a new termination value τ , line 31. If the termination value τ associated with the newly generated order λ is smaller (w.r.t. ≺ τ ) than the termination value τ i associated to the current order λ i , agent a i sends λ , τ to all other agents through order messages, line 33, and calls procedure changeOrder, line 34, to update its current order, termination value, according to the newly generated ones. Otherwise, a i keeps its current order and termination value unchanged. In procedure changeOrder(), agent a i replaces its current order λ i and its associated termination value τ i by the new ones (line 29). Then, a i removes all no-goods that become incoherent with the new order (line 30).

Whenever agent a i receives an order message (procedure processOrder, line 9), it checks if the pair (λ s , τ s ) included in the received message is stronger than its current pair (λ i , τ i ) (line 51). If it is the case, a i calls procedure stp : end ← true;

procedure initialize() 11. vi ← nil; ti ← 0; end ← false; 12. Γ - i ← Γi ∩ λ - i ; 13. Γ + i ← Γi ∩ λ + i ; function chooseValue() 14. foreach ( v i ∈ D c i ) do 15. if ( isConsistent(v i , AV -) ) then 16. xi ← v i ; 17.
return(true);

if ( vi = v i ) then checkAgentView(); 61. else if ( vi = v i ) then 62.
sendMsg:ok? xi, vi, ti to as;

procedure processAdl(as, v i ) 63. Γi ← Γi ∪ {as}; 64. if ( vi = v i ) then 65.
sendMsg:ok? xi, vi, ti to as; changeOrder to change its current order and its associated termination value to the newly received ones λ s , τ s (line 53). Next, agent a i checks if v i is consistent with assignments of higher agents AV -. If it is the case, agent a i has to send x i 's assignment through ok? messages to its lower neighbors who did not receive it beforehand because they had a higher priority in previous agent ordering, line 55. If v i is inconsistent with AV -, agent a i tries to select a new consistent value (assignVariable() call, line 56).

procedure checkAddLink(S) 66. updateAgentView(S); 67. ∆ ← j | xj, vj, tj ∈ S ∧ j / ∈ Γi ; 68. Γi ← Γi ∪ ∆; 69. foreach ( xj, vj, tj ∈ S s.t. j ∈ ∆ ) do
The procedure processNgd() is called whenever agent a i receives a ngd message, line 7. In this procedure, agent a i calls procedure checkAddLink (line 57) in order to update its agent-view with the newer assignments contained in the left hand side of the received no-good (updateAgentView call, line 66) and to request the establishment of new links with non-neighbors agents owning variables on the left hand side of the received no-good (lines 67 to 70). Then, the compatibility (Definition 3) and coherence (Definition 4) of the received nogood are checked (line 58) and the no-good is accepted only if it is compatible with the assignments of higher priority agents, i.e. AV -and coherent with the current order λ i of agent a i . An accepted no-good is stored in order to justify the removal of the value on its rhs (line 59). If the current value of a i is the same as the rhs of the accepted no-good then a new consistent value for a i is searched (checkAgentView call, line 60). If the no-good is not accepted, it is discarded, but if the value in its rhs was correct, a i re-sends its assignment to the no-good sender (a s ) through an ok? message (lines 61 and 62).

There are several ways to instantiate the general framework AgileABT. The instantiation is made by defining the termination values and the priority relation over those termination values and by specifying the function f() that computes new orders associated with those termination values.

Correctness and complexity

In this section we prove that AgileABT is sound, complete and terminates provided that (T , ≺ τ ) is a well-ordering, where T denotes the range of termination values computed by function f() and ≺ τ is the priority relation on T . In addition, if the function f() has polynomial space complexity, then AgileABT has polynomial space complexity.

AgileABT always stops its execution in one of the two cases: when an empty no-good has been generated, meaning that there is no solution, or when the network reaches a quiescence state reporting a solution. To prove that AgileABT is sound, one needs to prove that the reported solution is a correct one and to prove that it is complete one needs to prove that it cannot infer an empty no-good if a solution exists.

Proposition 2. The AgileABT algorithm is sound.

Proof. Let us assume that the state of quiescence is reached. The order (say λ * ) known by all agents is the same because when an agent proposes a new order, it sends it to all other agents. Obviously, (λ * , τ * i ) is the strongest pair that has ever been calculated by agents. Also, the state of quiescence implies that every pair of constrained agents satisfies the constraint between them. To prove this, assume that there exists two agents a i and a k that do not satisfy the constraint between them (i. e., c ik ). Let a i be the agent which has the highest priority between the two agents according to λ * (a k is the agent evaluating c ik ). Let v i be the current value of a i when the state of quiescence is reached (i. e., x i , v i , t i is the most up to date assignment of a i ). Let msg be the last ok? message sent by a i to a k before the state of quiescence is reached. Clearly, msg contains v i , otherwise, a i would have sent another ok? message when it chose v i , i.e. msg = ok? i→k : x i , v i , t i . If v i was assigned after a i changed its current order to λ * , agent a i sent msg to all its lower priority neighbors according to λ * (including a k , procedure assignVariable()). If v i was assigned before a i changed its previous order λ i to λ * , agent a k received msg if a k ∈ λ + i when v i was assigned to a i , otherwise (a k ∈ λ - i ), a k receives a copy of msg when a i changed λ i to λ * ( line 49 or line 55). The only case where a k can forget v i after receiving it is the case where a k derives a no-good proving that v i is not feasible. In this case, a k should send a no-good message to a i . If the nogood message is accepted by a i , a i must send an ok? message to its lower neighbors (and therefore msg is not the last one). Similarly, if the no-good message is discarded, a i has to re-send an ok? message to a k , lines 61 and 62 (and therefore msg is not the last one). So the state of quiescence implies that a k knows both λ * and v i . Upon receiving an ok? message, agents in AgileABT call procedure checkAgentView() to ensure their current value is consistent with the assignments of higher neighbors. Therefore, the state of quiescence implies that the current value of a k is consistent with value v i . Proposition 3. If the function f() has a polynomial space complexity, Ag-ileABT has also a polynomial space complexity.

Proof. In addition to the termination values, each agent in AgileABT stores one no-good per removed value and one current order that is bounded by n, the total number of agents. Thus, the space complexity of those data structures is in O(nd + n) = O(nd) on each agent. Hence, the space complexity of AgileABT is polynomial.

We now show that if the function f() always returns the same order, then AgileABT reduces to ABT. Lemma 1. If all agents hold the same order λ at the start of the solving process and the function f() always returns λ, then AgileABT behaves like ABT called with the order λ on all the agents. Proof. Agents in AgileABT exchange ok?, ngd, adl, order, and stp messages.

When an AgileABT agent a i assigns a value to its variable it sends ok? messages to its lower neighbors (Line 22) w.r.t. λ, exactly like ABT. When the AgileABT agent a i detects a dead-end, it is allowed to propose a new order through order messages (Line 43). But this step has no effect because by assumption the function f() used to compute new orders always returns λ. Hence, when a dead-end is detected, the agent a i resolves its no-goods and reports the resolved no-good ngd[x t =v t ] to the lowest agent a t w.r.t. λ through a ngd message (Line 46), exactly like ABT. Since λ is static, lhs(ngd[x t =v t ]) exclusively contains assignments of agents higher than a t in λ. Thus, the add-link requests in line 70 can only be sent to higher agents, again exactly as in ABT. Finally, an stp message is sent by an AgileABT agent a i when an empty no-good is detected (Line 40), which is the same condition as in ABT. Therefore, AgileABT behaves exactly like ABT if all agents hold the same order λ at the start of the solving process and the function f() always returns λ.

Proposition 4. AgileABT terminates if (T , ≺ τ ) is a well-ordering.
Proof. By the assumption that messages are delivered in finite time, a pair (λ, τ ) sent by an agent is known by all other agents after a finite amount of time. After this time, an agent can no longer generate and send a new order that has a termination value equal to τ , even if the new order is lexicographically smaller than the one to which τ was attached (Figure 4, line 32). Hence, if no agent improves the termination value τ , all agents will know the same pair (λ , τ ) after a finite amount time, where λ is the lexicographically smallest order generated with termination value τ during the time (λ, τ ) was traveling through the system. Furthermore, by Proposition 1, the termination values cannot decrease indefinitely w.r.t. ≺ τ if (T , ≺ τ ) is a well-ordering. Thus, AgileABT cannot change the pairs (λ, τ ) indefinitely. As a result, after a finite amount of time, either a quiescent state has been reached, or all agents own the strongest pair computed in the system and follow the same static order. In that last case, AgileABT then behaves exactly like ABT (Lemma 1), which terminates. Proposition 5. The AgileABT algorithm is complete.

Proof. Suppose a solution to the DisCSP exists. By Proposition 4, AgileABT must terminate. As noted previously, AgileABT can only terminate if it generates an empty no-good, or reaches a quiescent state. All no-goods used as justification of removing inconsistent values are induced by the constraints of the problem (Line 18, Figure 4). Thus, these no-goods are redundant regarding the problem to solve. All additional no-goods produced when dead-ends occur are generated by logical inference from existing ones (Line 37, Figure 4). As a result, an empty no-good cannot be inferred if a solution exists. Therefore Ag-ileABT must reach a quiescent state, and by Proposition 2, this must represent a solution.

Geometric interpretation of the termination of AgileABT

In this Section we present a geometric interpretation of the termination proof of Proposition 4. Given the set T of termination values that can be computed by function f(), Proposition 4 uses the assumption that (T , ≺ τ ) is a well ordering, that is, T = (τ * , . . . , τ t , . . . , τ 0 , . . . ) has a least element τ * = min ≺τ (T ). In AgileABT, the initial termination value is the same for all agents and is denoted by τ 0 . A final state is a state where a solution is found or the inconsistency is proved.

The function τ (x) returning the best termination value computed by all agents until time x is a function of time that has the shape of a decreasing sequence of horizontal segments (Figure 5). Given a termination value τ p computed at time p, the segment where τ (x) = τ p is an interval of time that starts at the time p where the best termination value in the system was improved to τ p and ends at the time p where an agent has succeeded to propose a new termination value τ p smaller than τ p , or the final state was reached. The key points of the proof are that the length of each segment is finite as well as the number of segments.

Regarding the length of each segment, assume a i has proposed a new order λ p that improves the current best termination value of the system to value τ p . Once another agent a j knows τ p , it can no longer propose an order with the same termination value even if the proposed order is lexicographically smaller than λ p (Figure 4, line 32). Hence, the time during which an agent a j can change the order without improving τ p is bounded by the finite time it takes to receive the order message sent by a i and containing (λ p , τ p ). Thus, after a finite time, τ p is known by all agents and no order lexicographically smaller than λ p can be generated. Again because messages are delivered in finite time, the lexicographically smallest order that could be generated with termination value equal to τ p is known by all agents after a finite time. At this point, the order is the same for all agents and AgileABT starts behaving like ABT (Lemma 1). ABT is correct and terminates. As a result, either a new smaller termination value is discovered or a final state is reached after a finite time. Therefore, the length of each segment is finite.

As for the number of segments, τ (x) can only decrease or remain unchanged because agents reject termination values that are greater than their current termination value. Hence, as long as agents can improve the termination value, τ (x) will continue to fall down along the y-axis. The fact that (T , ≺ τ ) is a well ordering (assumption in Proposition 4) implies that the number of times τ (x) can fall down along the y-axis is finite (Proposition 1). As every segment corresponds to a best termination value over an interval of time (Figure 5), we conclude that the number of segments that make the shape of τ (x) is finite.

To summarize, AgileABT has two main features that guarantee termination. When the best termination value stops changing, AgileABT ends up behaving like ABT and this ensures that the segments have a finite size. And if the best termination value continues to be improved, we are sure that it cannot indefinitely decrease because (T , ≺ τ ) is a well ordering. So the number of segments is bounded.

Example of Running AgileABT with a trivial function f

We now give a simple example of running AgileABT with a trivial function f(). Given that T is the range of termination values computed by f(), we have seen in Section 3.2 that the only restriction on f() to ensure that AgileABT terminates is that (T , ≺ τ ) is a well-ordering (Proposition 4). We thus choose a trivial function f() that simply returns a random reordering of agents associated with a termination value that is a random integer in the range T = {0, . . . , 100} (Figure 6b). 1 The relation ≺ τ is the standard < ordering of the integers. Clearly (T , ≺ τ ) is a well ordering.

We give a sketch of a possible execution of AgileABT on a small problem with four variables and five constraints (Figure 6a). The initial order is λ 0 = [1, 2, 3, 4] and the initial termination value τ 0 is 100.

• t 0 : All agents assign value 1 to their variables and send ok? messages to their lower priority neighbors. Observe that apart from the message sent by agent a 1 to agent a 2 , no other message will cause a conflict with the current value of the recipient.

• t 1 : Agent a 2 receives the assignment of a 1 (x 1 = 1) and removes value 1 from its domain because of the constraint (x 1 + x 2 ) div 3 = 0. This removal is justified by the no-good ngd 1 (Figure 6c). a 2 replaces its current assignment by x 2 = 2 and sends ok? messages to its lower priority neighbors (i. e., a 3 and a 4 (Figure 6a).

• t 2 : Agent a 3 receives the new assignment of a 2 (x 2 = 2) and removes value 1 from its domain because of the constraint x 2 ≤ x 3 . This removal is justified by the no-good ngd 2 (Figure 6c). Next, a 3 replaces its current assignment by x 3 = 2 and sends an ok? message to a 4 .

• t 3 : Agent a 4 has received the ok? messages sent by a 2 and a 3 ((x 2 = 2) and (x 3 = 2)). All of the values in its domain are now eliminated because Step Orders / Nogoods Decisions

t0 λ 0 = [1, 2, 3, 4], τ 0 = 100 xi = 1, ∀i t1 ngd1: x1 = 1 → x2 = 1 x2 = 2 t2 ngd2: x2 = 2 → x3 = 1 x3 = 2 t3 ngd3: x2 = 2 → x4 = 1 ngd4: x3 = 2 → x4 = 2 ngd5: x3 = 2 → x4 = 3 ngd6: ¬[x2 = 2 ∧ x3 = 2] x4 = 1 t4 λ 1 = [3, 2, 4, 1], τ 1 = 50
(c) Agent a 4 facing a dead-end.

Step Orders / Nogoods Decisions t5 ok? messages sent to new of the constraints x 2 + x 4 = 3 and x 3 • x 4 ≤ 3. These deletions are justified by the no-goods ngd 3 , ngd 4 and ngd 5 (Figure 6c). Then, agent a 4 proceeds to the resolution of its no-goods and derives the new nogood ngd 6 : ¬[(x 2 = 2) ∧ (x 3 = 2)] (Figure 6c). Agent a 4 calls function f() to see whether it can propose a new order. Suppose f() returns λ 1 = [3, 2, 4, 1], τ 1 = 50 . Because τ 1 = 50 is smaller than τ 0 = 100, the new order λ 1 is accepted by a 4 and sent to all other agents. The conclusion of the no-good ngd 6 is selected such that the ordering constraints induced by ngd 6 are coherent with the new order λ 1 . That is, x 2 is moved down to the conclusion of ngd 6 (ngd 6 : x 3 = 2 → x 2 = 2) and a ngd message is sent to the owner of x 2 (i. e., a 2 ). Afterwards, the no-good ngd 3 is removed from the set of no-goods stored by agent a 4 because it becomes incompatible. After that, agent a 4 assigns its variable to value 1, the unique value left in its domain. Agent a 4 does not have any lower priority neighbor to inform, so it does not send any ok? message.

Γ + i t6 ngd6: x3 = 2 → x2 = 2 x2 = 3 t7 ngd7: x2 = 3 → x1 = 1 ngd8: x2 = 3 → x1 = 2 ngd9: x3 = 2 → x1 = 3 ngd10: ¬[x2 = 3 ∧ x3 = 2] x1 = 1 t8 ngd10: x3 = 2 → x2 = 3 x2 = 1 t9 ngd11: x2 = 1 → x1 = 1 x1 = 2 (
• t 4 : Agents a 1 , a 2 and a 3 receive the new order sent by a 4 . All of them accept the new order because it is associated with a termination value smaller than τ 0 . Agents a 2 and a 3 remove respectively the no-goods ngd 1 and ngd 2 because they become incoherent with the new order.

• t 5 : After accepting the new order, agents a 1 , a 2 and a 3 check their current values. Because their current values are still consistent, each of them has to send ok? messages to its new lower priority neighbors that had higher priority than its own before the order changed. That is, agent a 2 sends an ok? (x 2 = 2) message to a 1 and agent a 3 sends an ok? (x 3 = 2) message to a 2 and a 1 . These messages do not cause any conflict with the current assignments of their recipients a 2 and a 1 . Agent a 1 will not send any ok? message because it is now the last agent in the order.

• t 6 : Agent a 2 receives the no-good sent by a 4 and replaces its assignment by x 2 = 3. Next, it sends ok? (x 2 = 3) messages to a 1 and a 4 .

• t 7 : The ok? message sent by a 2 is received by a 4 and a 1 . This message causes agent a 1 to face a dead end because of the constraints (x 1 +x 2 ) div 3 = 0 and x 1 +x 3 = 5. Therefore, a 1 resolves its no-goods and derives the new no-good ngd 10 : ¬[(x 2 = 3) ∧ (x 3 = 2)] (Figure 6d). Then, agent a 1 calls function f() in the hope of proposing a new order. Suppose f() returns λ 2 = [4, 1, 2, 3], τ 2 = 90 . The new order λ 2 is not accepted by a 1 and is not sent to the other agents because τ 2 = 90 ≥ τ 1 = 50. The no-good ngd 10 is sent to a 2 and the no-goods ngd 7 and ngd 8 are removed by a 1 because they become incompatible. Agent a 1 reassigns its variable to value 1.

• t 8 : Agent a 2 receives the no-good sent by a 1 , instantiates x 2 to 1 and informs its lower priority neighbors.

• t 9 : Agents a 1 and a 4 receive the ok? (x 2 = 1) message sent by a 2 . a 1 removes its value 1, stores the no-good ngd 11 : x 2 = 1 → x 1 = 1 and assigns its variable to value 2. The current value 1 of agent a 4 is not in conflict with the new assignment of a 2 . A solution has been found.

Instantiation of the General Framework

In this section, we propose AgileABT([α], ≺ α ), an instance of AgileABT in which the role of the termination values is not only to establish priority between the different orders proposed by agents but also to simulate a dynamic variable ordering (DVO) heuristic, since DVOs significantly speed up search in CSPs. To be able to simulate a given DVO, we first need to define a measure α that together with a preference relation ≺ α over the range of measure α (i. e., α, ≺ α ) capture the DVO heuristic. In other words, α needs to be smaller w.r.t. ≺ α when a variable is better for the DVO. For example to represent the min-domain heuristic, α is defined by the domain size and ≺ α is defined by the standard ordering < on numbers. Furthermore, to be able to properly reorder all agents in AgileABT([α], ≺ α ), a termination value needs to express information about every agent. Thus, in AgileABT([α], ≺ α ), termination values are vectors of size n, where each element in the vector represents a measure α used to implement a DVO of the agent in that position in the order. More formally, given an ordering λ, its associated termination value τ is built in such a way that the k th element τ [k] of τ depends on the agent at position k in λ. Specifically, we have τ

[k] = α(λ[k]
), where α is a generic measure that uses information about agents in the system.

In the general framework of AgileABT, we proposed to establish priority between orders using the priority relation ≺ τ over termination values. Thus, in AgileABT( [α], ≺ α ) we first need to define the priority relation over termination values in the form of a vector of measures α. AgileABT([α], ≺ α ) uses termination values to implement the DVO and, as a side effect, to provide more flexibility in the choice of the backtracking target. We will show later how to simulate different DVO heuristics by specifying the generic measure α together with the preference relation ≺ α . We then need to specify the function f() that computes new orders associated with their termination values in form of vector of measures α. We will do it in such a way that the smaller the value returned by α (w.r.t. , ≺ α ), the more preferred the corresponding variable for the DVO heuristic represented by α. In the following we discuss theses points together with necessary materials before formally presenting AgileABT([α], ≺ α ) algorithm.

Priority between orders

In AgileABT, agents accept or reject the suggested reordering using a priority relation over termination values. Thus, we need to specify a priority relation on termination values defined by vector of measures α. Let α and ≺ α be a measure on agents and a total preference order that together capture the DVO to simulate and let R α be the range of measure α. We propose that the priority between the different orders is based on the lexicographic comparison of termination values (vector of measure α) using ≺ α as preference order on the elements of the vector: Definition 7 (≺ lex α ). Let λ i and λ j be two total agent orderings and τ i and τ j their associated termination values. The termination value τ i is smaller than τ j (τ i ≺ lex α τ j ) if and only if τ i is lexicographically smaller than τ j w.r.t. ≺ α . In other words, The pair (λ , τ ) is stronger than the pair (λ, τ ) because the termination value associated with λ is smaller than the termination value associated with λ (i. e., τ ≺ lex α τ ). However, the pair (λ , τ ) is stronger than the pair (λ , τ ) because termination values associated with λ and λ are equal, but we broke the tie by comparing lexicographically the vector of IDs as stated in Definition 6 (i. e., the vector [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF][START_REF] Ottens | Coordination Agent Plans Trough Distributed Constraint Optimization[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Modi | Adopt: Asynchronous Distributed Constraint Optimization with Quality Guarantees[END_REF][START_REF] Jung | Argumentation As Distributed Constraint Satisfaction: Applications and Results[END_REF] of IDs in λ is lexicographically smaller than (< lex ) the vector [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF][START_REF] Ottens | Coordination Agent Plans Trough Distributed Constraint Optimization[END_REF][START_REF] Modi | Adopt: Asynchronous Distributed Constraint Optimization with Quality Guarantees[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Jung | Argumentation As Distributed Constraint Satisfaction: Applications and Results[END_REF] of IDs in λ ).

τ i ≺ lex α τ j if and only if ∃ k ∈ 1..n such that ∀p ∈ 1..k -1, τ i [p] = τ j [p] and τ i [k] ≺ α τ j [k].
The termination of the general framework of AgileABT is based on Proposition 4 that requires that the priority relation on termination values ≺ lex α wellorders the range T of terminations values. In the following, we define a simple condition on the total preference order ≺ α which guarantees that (T , ≺ lex α ) is a well-ordering and therefore AgileABT([α], ≺ α ) terminates.

Proposition 6. If ≺ α well-orders the range R α of measure α then the lexicographic comparison ≺ lex α well-orders the range T of termination values.

Proof. We proceed by contradiction. Suppose (T , ≺ lex α ) is not a well-ordering, that is, we can obtain an infinite decreasing sequence of termination values using a lexicographic comparison w.r.t. ≺ α . We thus must have an infinite decreasing sequence of τ [k] = α(λ[k]) measures, for some k ∈ 1..n. But, following Proposition 1, it would mean that ≺ α does not well-order R α , which contradicts the assumption that ≺ α well-orders R α . Therefore, the lexicographic comparison w.r.t. ≺ α well-orders T if the priority ordering ≺ α well-orders R α .

Corollary 1. AgileABT([α], ≺ α ) terminates if ≺ α well-orders R α .
Proof. Direct from Proposition 4 and Proposition 6.

Implementing DVO heuristics

The termination values defined by vector of measures α allow us to mimic a wide variety of DVOs. To mimic them in AgileABT([α], ≺ α ), it is sufficient to define the measure α in such a way that the smaller (w.r.t. ≺ α ) α(k), the better variable x k for the heuristic. Once we have decided which DVO we want AgileABT( [α], ≺ α ) to mimic, the only thing to do is to design the right measure α and the right total preference relation ≺ α over the range of α. The only condition required for AgileABT( [α], ≺ α ) to terminate is that the total preference relation ≺ α well-orders R α (see Corollary 1). In the following, we show how AgileABT([α], ≺ α ) is able to capture a number of different DVO heuristics that are known to be effective in reducing search in centralized CSP.

The DVO heuristics we consider in this work can be divided in three categories: (i) min-domain size [START_REF] Haralick | Increasing Tree Search Efficiency for Constraint Satisfaction Problems[END_REF] (i. e., dom), (ii) neighborhood based DVOs [START_REF] Bessière | MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems[END_REF] (i. e., dom/deg, dom/f deg, and dom/pdeg), and (iii) conflict-directed DVO (i. e., dom/wdeg) [START_REF] Lecoutre | Backjump-Based Techniques versus Conflict-Directed Heuristics[END_REF]. Domain size is ubiquitous in all those DVOs. As AgileABT([α], ≺ α ) is used in a distributed environment, agents must be able to recognize the domain size of other agents. To this end, agents exchange explanations of the domain sizes. Definition 8. An explanation e i is an expression e i : Λ i → d c i , where Λ i is the conjunction of the left hand sides of all no-goods stored by a i as justifications of value removals for x i , and d c i is the size of the current domain of x i . (That is, Λ i explains the removal of

|D i \ D c i | values.)
Each time an agent communicates its assignment to other agents (by sending them an ok? message) it inserts its explanation in the ok? message for allowing other agents to be able to infer its domain size. For an explanation e i to be correct, the variables in the left hand side Λ i of e i must precede the variable x i in the agent order because the assignments of these variables have been used to remove values from the current domain of x i . Hence, every explanation induces some ordering constraints, called safety conditions in [START_REF] Ginsberg | GSAT and Dynamic Backtracking[END_REF] (see Definition 4).

Definition 9. An explanation e k : Λ k → d c k is coherent with an order λ if all variables in Λ k appear before x k in λ. Given an explanation e k , S(e k ) is the set of safety conditions induced by e k , that is,

S(e k ) = {x j ≺ x k | x j ∈ Λ k }. Given a set E i of explanations, S(E i ) = e k ∈Ei S(e k ).
Each agent a i stores a set E i of explanations sent by other agents. During search, a i updates E i to store newly received explanations. Furthermore, each time an agent computes a new order, E i is updated to remove explanations that are no longer valid.

Definition 10. An explanation e

k : Λ k → d c k in E i is valid on agent a i if it is
coherent with the current order λ i and Λ k is compatible with the agent-view of agent a i .

When E i contains a valid explanation e k associated with agent a k , agent a i can infer the size of the current domain of x k . Otherwise, a i can assume that the size of the current domain of x k is equal to its initial domain size d k . 2 This gives the following function:

dom(k) = d c k if (e k : Λ k → d c k ) ∈ E i , d k otherwise (i.e., e k : ∅ → d k ) (1)

Simulating Min-Domain DVO Heuristic

The most well-known DVO heuristic from the centralized CSP is the ubiquitous min-domain [START_REF] Haralick | Increasing Tree Search Efficiency for Constraint Satisfaction Problems[END_REF]. This heuristic selects first the variable with smallest current domain. To mimic min-domain in AgileABT([α], ≺ α ), an agent a i simply needs to select an order λ that minimizes the termination value τ = [α(λ [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF]), . . . , α(λ[n])] w.r.t. ≺ lex α , where α(k) = dom(k) and ≺ α is the standard ordering < on integers.

procedure propagate(cij) 01. foreach ( vi ∈ D c i ) do 02.
if ( ¬hasSupport(cij, xi), vi ) then 03.

D c i ← D c i \ {vi}; 04. foreach ( vj ∈ D c j ) do 05. if ( ¬hasSupport(cij, xj), vj ) then 06. D c j ← D c j \ {vj}; 07. if ( D c i = ∅ ∨ D c j = ∅ ) then wj ← wj + 1 ; procedure computeWeight() 08. wdegi ← 1; 09. foreach ( cij ∈ Ci ) do 10. if ( xj ∈ Γ + i ∨ xj, nil, tj ∈ AV -) then 11.
wdegi ← wdegi + wj;

12. wdegi ← min(wdegi, W );

Simulating Neighborhood Based Variable Ordering Heuristics

In the second category we simulate three DVO heuristics from centralized CSP that take into account the neighborhood of each agent ( [START_REF] Bessière | MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems[END_REF][START_REF] Smith | Trying Harder to Fail First[END_REF]): dom/deg, dom/pdeg and dom/f deg. Each of these DVOs prefers the variable minimizing a ratio where the numerator is the size of the domain of that variable and the denominator is some information about its neighborhood. To obtain measures that mimic these DVOs, agents use Equation ( 1) for the numerator, but they require information about the neighborhood of other agents to infer the denominator. For dom/deg, each agent a i requires to know the degree deg(k) of each agent a k in the problem (i. e., the number of neighbors of a k ). 3 Agent

a i computes τ = [α(λ[1]), . . . , α(λ[n])] using α(k) = dom(k) 1 + deg(k)
. For dom/pdeg (resp. dom/f deg) each agent a i requires to know the set of neighbors of each other agent a k because it will need to compute the incoming degree pdeg(k) (resp. the outgoing degree f deg(k)) of a k for any proposed order. 4 Agent a i computes τ using α(k) = dom(k)

1 + pdeg(k) (resp. α(k) = dom(k) 1 + f deg(k)
) where the incoming degree pdeg(k) in λ is the number of neighbors of a k that appear before k in λ and the outgoing degree f deg(k) in λ is the number of neighbors of a k that appear after k in λ. As these DVO heuristics prefer the variable minimizing the measure, they are simulated by calling AgileABT([dom/deg], <), AgileABT([dom/pdeg], <), and AgileABT([dom/f deg], <), respectively.

Simulating Conflict-Directed Variable Ordering Heuristic

The third category covers the popular conflict-directed variable ordering heuristic dom/wdeg from the centralized CSP [START_REF] Boussemart | Boosting Systematic Search by Weighting Constraints[END_REF]. The conflict-driven heuristic dom/wdeg associates a weight with each constraint to record conflicts during search. The weight of a constraint is increased each time the constraint fails. This heuristic selects the variable that minimizes the ratio dom/wdeg, where dom denotes the current size of the domain of the variable and wdeg the weighted degree of the variable defined as the sum of the weights of the constraints involving that variable and at least another uninstantiated variable.

AgileABT([dom/wdeg], <) is the algorithm that simulates the conflict-driven heuristic in AgileABT( [α], ≺ α ). Agents in AgileABT([dom/wdeg], <) store and exploit information about failures in the form of constraint weights to compute measure α(k). Each agent a i maintains the weight of each constraint c ij in C i , denoted by w j , and the weighted degree of each agent a k denoted by wdeg k .

Each agent a i in AgileABT([dom/wdeg], <) computes τ using α(k) = dom(k) wdeg k .

In order to check consistency (isConsistent() calls, Figure 4), agents perform successive revisions of their constraints using a procedure propagate().

A general description of procedure propagate(c ij ) called to revise a constraint c ij ∈ C i is presented in Figure 7. Whenever a constraint c ij fails (i.e., D c i or D c j is wiped out, D c i = ∅ ∨ D c j = ∅) when calling procedure propagate, w j is incremented (line 7, Figure 7). Each time a i assigns a new value to its variable (procedure assignVariable(), Figure 4), a i computes its own counter wdeg i using procedure computeWeight(), Figure 7. The weighted degree wdeg i is the sum of the weights (w j ) of all constraints (c ij ) in C i involving a variable having a lower priority (x j ∈ Γ + i ) or not assigned in AV -(lines 8 to 11, Figure 7). However, to guarantee that AgileABT([dom/wdeg], <) terminates (see Section 4.4), we require that the new computed weighted degree does not exceed a limit W (line 12, Figure 7). Next, agent a i attaches its counter wdeg i to each ok? message it sends out. Upon receiving an ok? message from an other agent a s , agent a i updates wdeg s to the weight included in the received ok? message.

AgileABT([α], ≺ α ) algorithm

Once we have decided which DVO we want to mimic and designed the right measure α with the right total preference relation ≺ α over the range of α, if we want to mimic the given DVO as closely as possible, AgileABT( [α], ≺ α ) should compute orders with the smallest possible termination values (w.r.t. , ≺ lex α ). Each time an agent faces a dead-end, it resolves its no-goods and then it is allowed to propose a new order. Unlike previous polynomial reordering approaches, AgileABT([α], ≺ α ) relaxes the restriction of selecting the variable that has the lowest priority in the current order among conflicting variables as backtracking target. AgileABT( [α], ≺ α ) allows agent a i to select the backtracking target among conflicting variables Λ i . The only restriction for selecting x t as a backtracking target is to find an order λ associated with a termination value τ = [α(λ [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF]), . . . , α(λ[n])] that is smaller (w.r.t. ≺ lex α ) than the termination value associated with the current order λ i of agent a i and x t is the lowest among variables in Λ i w.r.t. the freshly computed order λ .

To deal with explanations, an AgileABT([α], ≺ α ) agent a i keeps a set of explanations E i , and some of AgileABT procedures in (Figure 4) are slightly modified. The new lines/procedures of AgileABT([α], ≺ α ) with respect to Ag-ileABT are presented in Figure 8. Agents in AgileABT( [α], ≺ α ) exchange the same types of messages as AgileABT, however, each agent sends an explanation of its new size in each of its ok? messages.

As in AgileABT, whenever agent a i receives an ok? message from an agent a s , it processes it by calling procedure processOk( x s , v s , t s , e s ). Agent a i procedure AgileABT( [α]

E i ← E i \ ek ; 18. if ( et / ∈ E i ) then 19.
add updates its set of explanations E i by storing the newly received explanation e s (line 11, Figure 8). As usual the agent-view of a i is updated, but in addition to the assignment of the sender (a s ), agent a i takes newer assignments contained in the left hand side of the explanation (i.e., Λ s ) included in the received ok? message to update its agent-view (line 12, Figure 8). Then, procedure checkAgentView is called (line 13) to search a new consistent value for a i if necessary.

(E i , et : ∅ → dt); 20. add(E i , et ← [Λt ∪ Λi \ (xt = vt)] → d c t -
To compute a new reordering, an AgileABT([α], ≺ α ) agent a i makes use of the function f() presented in Figure 8. First, a i updates its set of explanations E i to remove all explanations that are no longer valid (lines 34 to 36, Figure 8). As a result, all explanations in E i are coherent with λ i . Therefore, the set of safety conditions S(E i ) does not contain cycles. Next, agent a i iterates through all variables x t in Λ i , considering x t as a potential backtracking target, (i. e., the directed no-good is ngd[

x t =v t ] : [Λ i \ (x t = v t ) → x t =v t ]) line 38.
Agent a i then predicts the set of explanations E i after backtracking (function simulateExplanations call, line 39). E i is updated to remove all explanations containing x t (after backtracking x t assignment will be changed), lines 14 to 17. Next, agent a i updates the explanation of x t by considering the new generated no-good ngd[x t =v t ] (lines 19 to 20). Finally, agent a i calls computeOrder to compute a new order with small termination value (line 40). Once all the potential backtracking targets have been tried, the function f() returns the computed order associated with the smallest computed termination value (line 44). Unfortunately, given a backtracking target, computing a total order λ that respects the ordering constraints induced by the set S(E i ) while minimizing [α(λ(1)), . . . , α(λ(n))] is NP-hard (see Proposition 9 in Section 4.4).

As it is NP-hard to compute an order λ satisfying a set of safety conditions and minimizing termination value w.r.t. ≺ lex α (Definition 7), AgileABT([α], ≺ α ) uses a greedy function computeOrder to find a small termination value for ≺ lex α while respecting the safety conditions. The basic idea of the function computeOrder is to perform a topological sort of the acyclic graph representing the ordering constraints with the objective of minimizing τ . The function computeOrder performs n iterations ranging from 1 to n (lines 25 to 32). At the p th iteration, a variable x r is selected such that α(r) is minimal among the set of variables R that have no predecessors, lines 26 to 27. Ties are broken lexicographically. The selected variable x r is put in p th position in the order, and τ [p] is assigned value α(r), lines 28 to 29. Next, x r is removed from the acyclic graph, lines 31 to 32. Then, the next iteration is executed.

Correctness of function computeOrder is based on the fact that the set R computed at line 26 is never empty. This is true if computeOrder is called with a set E i of explanations such that S(E i ) does not contain cycles. This is what Lemma 2 tells us.

Lemma 2. When calling function computeOrder(E i ), S(E i ) does not contain cycles.

Proof. Function computeOrder(E i ) is called on function f(). In function f(), all explanations in E i that are no longer valid are removed (lines 34 to 36, Figure 8). As a result, all explanations in E i are coherent with λ i . Therefore, the set of safety conditions S(E i ) does not contain cycles. We need now to prove that function simulateExplanations does not create cycles in the set of safety conditions S(E i ) if S(E i ) is acyclic. The first step is to copy E i into E i (line 14, Figure 8). Then all explanations containing x t are removed from E i (lines 15 to 17, Figure 8). By removing these explanations, all safety conditions of the form x t ≺ x j are removed from S(E i ). Until this point, if

S(E i ) is acyclic, then S(E i ) is acyclic because S(E i ) ⊆ S(E i ).
Then, the explanation of e t is updated by taking the generated no-good into account (lines 19 and 20). All the safety conditions added to S(E t ) after this step are of the form x l ≺ x t . Suppose that once e t is updated S(E i ) becomes cyclic. Hence, if S(E i ) contains cycles, all these cycles should contain x t and there is a sequence of safety conditions in

S(E i ) such that x t ≺ x j ≺ • • • ≺ x l ≺ x t .
However, all safety conditions of the form x t ≺ x j were removed, and all the safety conditions in S(e t ) are of the form x l ≺ x t . Therefore, S(E i ) cannot be cyclic.

Theoretical Analysis

We first show that all measures presented in Section 4.2 satisfy the condition in Corollary 1. This is sufficient to ensure termination of AgileABT([α], ≺ α ). Proposition 7. For all measures α in {dom, dom/deg, dom/pdeg, dom/fdeg, dom/wdeg}, (R α , <) is a well-ordering.

Proof. We proceed by contradiction. Suppose there is an infinite decreasing sequence of values of α(k). In all measures above, α(k) = dom(k) ρ(k) , for some ρ(k). dom(k) is the expected domain size of the agent a k . It is obvious that domain size cannot be negative, that is, ∀k ∈ 1..n, 0 ≤ dom(k) ≤ d k . So dom(k) cannot decrease indefinitely. Therefore, ρ(k ) must increase infinitely. ρ(k ) is a positive integer whose value depends on the measure used. Three cases were explored in this paper. The first case concerns min-domain (dom) where ρ(k ) equals 1. The second case concerns the family of degree-based heuristics (dom/deg, dom/pdeg, dom/fdeg). In this case, all of the ρ(k ) are greater than or equal to 1 and smaller than or equal to n the number of agents in the system because an agent is at most constrained to n -1 other agents. Thus, 1 ≤ ρ(k ) ≤ n. The third case is related to the heuristic dom/wdeg. We have outlined that an agent is not allowed to increment its weight when it has reached the limit W set beforehand (Figure 7, line 12). Thus, 1 ≤ ρ(k ) ≤ W . In all three cases ρ(k ) is an integer that cannot increase infinitely. Therefore, for all measures presented above,

) cannot decrease infinitely, and so < well-orders R α the range of measure α.

Corollary 2. AgileABT([α], ≺ α ) is guaranteed to terminate if α ∈
{dom, dom/deg, dom/pdeg, dom/fdeg, dom/wdeg}.

Proof. From Corollary 1 and Proposition 7.

Hence, AgileABT([α], ≺ α ) has all the good properties we can expect from an algorithm for solving DisCSPs. We demonstrate that the space complexity of AgileABT(

[α], ≺ α ) is polyno- mially bounded. Proposition 8. The spatial complexity of AgileABT([α], ≺ α ) is polynomial.
Proof. The size of no-goods, explanations, termination values, and orderings, is bounded by n, the total number of variables. Now, on each agent, AgileABT([α], ≺ α ) only stores one no-good per value, one explanation per agent, one termination value and one ordering. Thus, the space complexity of AgileABT(

[α], ≺ α ) is in O(nd + n 2 + n + n) = O(nd + n 2 ) on each agent.
We prove that it is difficult for an agent a i to compute an order with the smallest possible termination value.

of [α(λ[1]), . . . , α(λ[n])]. By construction, any lexicographically smaller prefix would put a w ij before u i or u j in λ , which would break the safety conditions. Suppose now that we have an order λ such that 22121 2 21 3 ...21 k-1 is a prefix of We have proved that the existence of a clique of size k is equivalent to the existence of the prefix 22121

2 21 3 ...21 k-1 in [α(λ[1]), . . . , α(λ[n])].
Checking this prefix is polynomial, therefore we have a polynomial-time reduction, and our problem is NP-hard.

Example of Running AgileABT([dom], <)

Figure 9 presents an example of a possible execution of AgileABT([dom], <) on the simple problem presented in Figure 1. Assume all 5 agents start with the same initial ordering λ i = [1, 2, 3, 4, 5] associated with the termination value τ i = [START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF] and values are chosen lexicographically. Consider the situation in a 5 after receiving ok? messages from other agents (Figure 9a). On receipt, explanations e 1 , e 2 , e 3 , and e 4 are stored in E 5 , and assignments x 1 = 1, x 2 = 2, x 3 = 2, and x 4 = 3 are stored in a 5 agent-view. After checking its constraints with higher neighbors (c 15 , c 25 , and c 45 ), a 5 detects a dead end (Λ 5 → 0) where

Λ 5 : {x 1 = 1 ∧ x 2 = 2 ∧ x 4 = 3}.
All explanations stored in E 5 are valid: They are compatible with the agent-view of a 5 and coherent with λ 5 . Agent a 5 iterates through all variables x t ∈ Λ 5 , considering x t as the target of the backtracking. Figure 9b shows the updates on the explanations stored in a 5 (E 5 ) when it considers x 1 as the target of the backtracking (i. e., x t = x 1 ). Agent a 5 updates E 5 to remove all explanations containing x 1 (i. e., e 2 and e 3 ) and considering the new generated no-good ngd[x 1 =1] : [x 2 = 2 ∧ x 4 = 3] → x 1 =1 in the explanation of x 1 , i.e. e 1 (Figure 9b, left). Finally, a 5 computes a new order (λ ) and its associated termination value (τ ) from the updated explanations E 5 . λ is obtained by performing a topological sort on the directed acyclic graph formed by safety conditions induced by the updated explanations E 5 (Figure 9b, right). Figure 9c presents the computed orderings and their associated termination values (by topological sort) when considering each x t ∈ Λ 5 as backtracking target. The strongest computed order (i.e., λ = [3, 4, 2, 5, 1], τ = [4, 2, 4, 2, 3]) is that computed when considering x 1 as backtracking target. Since τ is smaller than τ 5 (i.e., τ ≺ lex α τ 5 ) agent a 5 changes its current order to λ and proposes this ordering to all other agents through order messages (i. e., order: λ , τ ). Then, a 5 sends the no-good ngd[

x 1 =1] : [x 4 = 3 ∧ x 2 = 2] → x 1 =v 1 to agent x 1 .

AgileABT versus retroactive ABT DO

As mentioned in the introduction, several algorithms have been proposed for reordering agents dynamically during search. AgileABT and retroactive ABT DO (i. e., ABT DO Retro [START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF]) are the only ones which are able to reorder Data structures maintained by A 5 ∀i ∈ 1..5, directed nogood agent ordering termination value the agents with priority higher than the no-good receiver. 5 Therefore the main differences between these two algorithms deserve to be explored in more depth 5.1. Reordering

λ i = [1, 2, 3, 4, 5], τ i = [4, 4, 4, 4, 4] Λ 5 : x 1 = 1 ∧ x 2 = 2 ∧ x 4 = 3
ngd[x 1 =1]: [x 4 = 3 ∧ x 2 = 2] → x 1 =1 λ = [3, 4, 2, 5, 1] τ = [4, 2, 4, 2, 3] ngd[x 2 =2]: [x 1 = 1 ∧ x 4 = 3] → x 2 =2 λ = [1, 3, 4, 5, 2] τ = [4, 3, 2, 1, 2] ngd[x 4 =3]: [x 1 = 1 ∧ x 2 = 2] → x 4 =3 λ = [1, 2, 5, 3, 4] τ = [4, 3 , 1, 3, 1]

ABT DO Retro

The algorithm ABT DO was first introduced in [START_REF] Zivan | Dynamic Ordering for Asynchronous Backtracking on DisCSPs[END_REF]. When an ABT DO agent assigns a value to its variable, it can only change the order of agents that have a lower priority than its own. ABT DO Retro, presented in [START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF], is a slightly modified version of ABT DO where the reordering operation is generated by the no-good generator instead of the no-good receiver. Furthermore, ABT DO Retro allows for retroactive heuristics. A retroactive heuristic enables moving the no-good sender to a higher position than the no-good receiver. The more the no-good sender is moved higher in the order, the more the heuristic is flexible.

However, the flexibility of the retroactive heuristics enabled by ABT DO Retro comes at the price of keeping no-goods in memory. To monitor the storage of the no-goods, ABT DO Retro uses a parameter K and only allows the storage of no-goods that are smaller than or equal to K in size. Hence, ABT DO Retro has a space complexity exponential in K.

When K is equal to the number of agents in the system, the no-good sender can always be moved to be before all the participants in the no-good. The resulting algorithm is a generalization of AWC [START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF]. However, agents must store all the no-goods until the end of the search, which gives a space complexity exponential in the number of agents.

When K equals 0, the spatial complexity of the algorithm becomes polynomial, but the flexibility becomes limited because the sender of the no-good, can no longer be moved to a position higher than the second last in the no-good [START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF].

An intermediate version between these two extremes consists in setting the parameter K to a value between 0 and the number of agents in the system. In this case, if the no-good created has size larger than K, the sender of the nogood cannot be moved to a position higher than the second last in the no-good. If the no-good has size smaller than or equal to K, the sending agent can be moved to be higher than all the participants in the no-good and the no-good is sent to and stored by all of them.

Despite allowing this space consumption, the extra flexibility given to ABT DO Retro had no positive effects on its performance. Indeed, "The fact that a larger storage, which enables more flexibility of the heuristic, actually causes a deterioration of the performance might come as a surprise. " [quoted from [20, p.193 ]]. Furthermore, "Larger storage for Nogoods (even exponential in the extreme case) was found to produce worse efficiency for search on random problems." [quoted from [20, p.197 ]]. The only heuristic that performed well was the min-domain retroactive heuristic that works with K set to 0: "In our best performing heuristic, agents are moved higher in the priority order as long as their domain size is smaller than the domains of the agents before them and as long as they do not pass the second last in the no-good." [quoted from Zivan et al. [20,p.197 ]].

AgileABT

To increase flexibility, AgileABT uses a totally different and innovative strategy based on termination values. To be able to reorder agents that are before the receiver of the no-good, agents in AgileABT do not need to keep no-goods in memory. They only need to improve the termination value. An agent that can improve the termination value can propose a new order where the positions of all agents are changed, including the agents before the receiver of the no-good.

Selection of the Backtracking target

ABT DO Retro

In all previous asynchronous backtracking algorithms, including ABT DO [START_REF] Zivan | Dynamic Ordering for Asynchronous Backtracking on DisCSPs[END_REF] and ABT DO Retro [START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF], whenever a dead end occurs, the backtracking target is determined by the order known by the generator of the no-good before the dead end. That is, the backtracking target always corresponds to the agent with the lowest priority among those participating in the no-good.

AgileABT

In order to ensure greater flexibility in exploring the search space, the restriction of selecting the lowest agent in the current order as backtracking target has been relaxed in AgileABT. Instead of being determined by the order known by the generator of the no-good before the dead end, the backtracking target is determined by the order newly proposed by this agent. By proposing an appropriate new order, any variable participating in the generated no-good can be moved down to the lowest position in that generated no-good and then be selected as the backtracking target (Figure 4, lines 43 to 46). The example of Section 4.5 illustrates this feature. When the no-good ngd 6 : ¬[(x 2 = 2) ∧ (x 3 = 2)] was generated by a 4 , the current order that was known by this agent was [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF][START_REF] Ottens | Coordination Agent Plans Trough Distributed Constraint Optimization[END_REF][START_REF] Jung | Argumentation As Distributed Constraint Satisfaction: Applications and Results[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF]. In all previous asynchronous backtracking algorithms, including ABT DO [START_REF] Zivan | Dynamic Ordering for Asynchronous Backtracking on DisCSPs[END_REF] and ABT DO Retro [START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF], the conclusion of the no-good ngd 6 must be x 3 because it is owned by the agent that has the lowest priority according to the current order. In AgileABT, this restriction can be relaxed. Indeed, by choosing the new order [3, 2, 4, 1], the variable x 2 was dragged down to the lowest position among the variables participating in ngd 6 and the no-good x 3 = 2 → x 2 =2 was sent to a 2 instead of a 3 .

Timestamps versus termination values

ABT DO Retro

The method of timestamping for defining the most updated order in ABT DO Retro is the same as that used in [START_REF] Zivan | Dynamic Ordering for Asynchronous Backtracking on DisCSPs[END_REF]. In these algorithms, an order is an ordered list of pairs where every pair includes the ID of one of the agents and a counter attached to it. Initially, all counters are set to zero, and each agent a i that proposes a new order, updates the counters as follows:

• The counters of agents with priority higher than a i are not changed.

• The counter of a i is incremented by one.

• The counters of agents with priority lower than a i are set to zero.

The counters attached to the agents ID form a timestamp. Agents decide which order is more up-to-date by comparing the timestamps lexicographically [START_REF] Mechqrane | Corrigendum to "Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF]. Therefore, the timestamps used by ABT DO Retro are arrays of integers whose sole purpose is to indicate that a given order is more up-to-date than another one.

AgileABT

Termination values used by AgileABT are fundamentally different from the timestamps of ABT DO Retro. First, termination values do not need to be arrays of integers. They may be numbers, arrays or any other mathematical object. The only requirement is that (T , ≺ τ ) is a well ordering (Proposition 4). The example of Section 4.5 illustrates a case where termination values are positive integers, and the heuristics introduced in Section 4.2 illustrate cases where termination values are arrays of integers and arrays of rational numbers.

Second, termination values can be used to mimic a wide variety of DVOs.

The termination values used by the instantiations of AgileABT presented in Section 4 are arrays of measures α defined such that the smaller the value returned by α w.r.t. ≺ α , the more preferred the corresponding variable for the DVO heuristic represented by α. We showed in Section 4.2 how AgileABT( [α], ≺ α ) is able, thanks to the termination values, to capture a number of different DVO heuristics (dom, dom/deg and dom/wdeg) that are known to be effective in reducing search in centralized CSP.

Empirical Analysis

In this section we experimentally compare AgileABT([α], ≺ α )6 using different DVO heuristics to three other algorithms: ABT, ABT DO with nogoodtriggered heuristic (ABT DO-ng) [START_REF] Zivan | Dynamic Ordering for Asynchronous Backtracking on DisCSPs[END_REF] and ABT DO with min-domain retroactive heuristic (ABT DO Retro(mindom)) [START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF][START_REF] Mechqrane | Corrigendum to "Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF]. All experiments were performed on the DisChoco 2.0 platform [START_REF] Wahbi | Dischoco 2: A platform for distributed constraint reasoning[END_REF]. 7 Uniform binary random DisCSPs are characterized by n, d, p 1 , p 2 , where n is the number of agents/variables, d is the number of values in each domain, p 1 is the network connectivity defined as the ratio of existing binary constraints to possible binary constraints, and p 2 is the constraint tightness defined as the ratio of forbidden value pairs to all possible pairs. We solved instances of two 1175 classes of random DisCSPs: sparse problems 20, 10, 0.2, p 2 and dense problems 20, 10, 0.7, p 2 . We varied the tightness from 0.1 to 0.9 by steps of 0.05. For each pair of fixed density and tightness (p 1 , p 2 ), we generated 20 instances, solved 5 times each. We report average over the 100 executions.

Figures 10 and11 show the results on sparse respectively dense uniform binary random DisCSPs. In sparse problems (Figure 10

Composed random instances

We also evaluate all algorithms on two sets of unsatisfiable composed random instances used to evaluate the conflict-directed variable ordering heuristic 1220 in centralized CSP [START_REF] Roussel | XML Representation of Constraint Networks: Format XCSP 2[END_REF][START_REF] Boussemart | Boosting Systematic Search by Weighting Constraints[END_REF]. 8 Each set contains 10 different instances where each instance is composed of a main (under-constrained) fragment and some auxiliary fragments, each of which being grafted to the main one by introducing some binary constraints. Each instance contains 33 variables and 10 values per variable, and as before, each variable is controlled by a different agent. We solved 1225 each instance 5 times and present the average over 50 executions in Table 2.

The results ( ] is a benchmark based on a real distributed problem. This problem consists of a set of n stationary sensors, and a set of m mobile targets, moving through their sensing range. The objective is to track each target by sensors. Thus, sensors have to cooperate for tracking all targets. In order for a target to be tracked accurately, at least three sensors must concurrently turn on overlapping sectors. This allows the target's position to be triangulated. However, each sensor can track at most one target. Hence, a solution is an assignment of three distinct sensors to each target. A solution must satisfy visibility and compatibility constraints. The visibility constraint defines the set of sensors to which a mobile is visible. The compatibility constraint defines a compatibility relation among sensors regarding the physical limitations of the sensors and the properties of the terrain on which the sensors are located.

We encode SensorDisCSP in DisCSP as follows. Each agent represents one mobile. There are three variables per agent, one for each sensor that we need to allocate to the corresponding mobile. The domain of each variable is the set of sensors that can detect the corresponding mobile. The intra-agent constraints between the variables of one agent (mobile) specify that the three sensors assigned to the mobile must be distinct and pairwise compatible. The inter-agent constraints between the variables of different agents specify that a given sensor can be selected by at most one agent. In our implementation of the DisCSP algorithms, this encoding is translated into an equivalent formulation where we have three virtual agents for each real agent. Each virtual agent handles a single variable but #msg does not take into account messages exchanged between virtual agents belonging to the same real agent. Problems are characterized by n, m, p c , p v , where n is the number of sensors, m is the number of mobiles. Each sensor can communicate with a fraction p c of the sensors that are in its sensing range, and each mobile can be tracked by a fraction p v of the sensors having the mobile in their sensing range. We solved instances of class 25, 6, 0.15, p v ∈ {.1, . . . , .65} , where we vary p v by steps of 0.05. Again, for each pair (p c , p v ) we generated 20 instances, solved 5 times each, and averaged over the 100 runs. The results are shown in Figure 12.

When comparing the speed-up of algorithms (top of Figure 12), AgileABT([dom/wdeg], <) is the fastest algorithm and it shows more than an order of magnitude improvement compared to ABT that shows very ABT is the algorithm that requires the most messages to solve SensorDisCSP instances. ABT DO-ng and ABT DO Retro(mindom) require almost half the #msg of ABT. All smaller longest messages for all compared algorithms. The size of largest message size is 105 and it is exchanged by AgileABT([dom/wdeg], <). In ABT the size of longest message size is smaller than in all asynchronous dynamic ordering algorithms. AgileABT( [α], ≺ α ) requires larger longest messages compared to other algorithms. However, among all our experiments, the size of the longest message sent by AgileABT([α], ≺ α ) was of size 253 bytes. We are able to send a single datagram of up to 568 bytes (IPv4) or 1, 272 bytes (IPv6) without fragmentation (i. e., send in one single physical message) in either TCP or UDP. Thus, counting the number of exchanged messages is equivalent to counting the number of physical messages. Therefore, in all our experiments assessing the communication load by #msg is not biased.

Figure 14 presents the total number of bytes exchanged on the uniform binary random DisCSPs and the target tracking in distributed sensor network benchmark. The obtained results for distributed sensor network instances (Figure 14a) show that ABT DO Retro(mindom) is the algorithm requiring the largest number of exchanged bytes to solve these problems followed by ABT. All AgileABT([α], ≺ α ) heuristics require fewer exchanged bytes than all other algorithms. They show an improvement factor of almost 3 over ABT DO Retro(mindom) and of almost 2.5 over ABT. The improvement factor is almost 2 over ABT DO. For sparse binary random DisCSPs (Figure 14b), the obtained results show that ABT DO-ng and ABT DO Retro(mindom) are the algorithm that require the largest amount of data. Except for AgileABT([dom/wdeg], <) that shows a similar performance compared to ABT, all other AgileABT([α], ≺ α ) heuristics outperform all other algorithms by a large scale. They show an improvement factor of almost 3 over ABT and an almost order of magnitude improvement over ABT DO-ng and ABT DO Retro. For dense binary random DisCSPs (Figure 14c), ABT DO Retro(mindom) is again the algorithm requiring the largest amount of exchanged bytes. ABT DO-ng shows better performance compared to sparse instances and it outperforms AgileABT([dom/wdeg], <). In these instances, ABT and AgileABT([α], ≺ α ) with neighbourhood based heuristics are the algorithms that require the minimum amount of exchanged bytes with a slight improvement for ABT over AgileABT( [α], ≺ α ).

Discussion

Looking at all results together, we come to the straightforward conclusion that AgileABT([α], ≺ α ) with neighbourhood-based heuristics, namely dom/deg, dom/f deg and dom/pdeg perform very well compared to other techniques. We think that neighbourhood-based heuristics perform well thanks to their ability to take into account the structure of the problem [START_REF] Bessière | MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems[END_REF]. Distinctly, among these three heuristics dom/pdeg seems to be the best one.

In distributed dynamic ordering algorithms, each change on the agents ordering invokes a series of coordination messages, and affects the search effort by wasting all incoherent no-goods computed so far. Therefore, too many changes of agents ordering will have a negative impact on the communication load and on the computational effort. In all our experiments, we counted the number of order messages exchanged by each distributed dynamic ordering algorithm. The results (presented in Table 3) show that ABT DOng and ABT DO Retro(mindom) exchange a large number of order messages compared to AgileABT([α], ≺ α ). Among AgileABT([α], ≺ α ) algorithms, AgileABT([dom/pdeg], <) is the algorithm that exchanges the smallest number of order messages while AgileABT([dom/wdeg], <) is the one that exchanges the largest number of order messages. These empirical results suggest that to be efficient a distributed dynamic ordering algorithm needs to be able to revise the ordering of all agents. However, the fewer times the ordering is changed, the better the performance. On the other hand, AgileABT([α], ≺ α ) with the conflict-directed variable ordering heuristic dom/wdeg shows a relatively poor performance on some instances. This fact can be explained by the limited amount of constraint propagation performed by DisCSP algorithms. Furthermore, asynchrony affects reception and treatment of ok? and ngd messages and has a direct impact on the computation of weights and new orders for the dom/wdeg heuristic.

Conclusion

We proposed agile asynchronous backtracking (AgileABT), a distributed asynchronous constraint satisfaction framework which allows total reordering of agents during search without requiring exponential space. This is done via the original notion of termination values, labels attached to the orders exchanged by agents during search. Agents accept or reject the suggested reordering using a priority relation over termination values that can be simple scalar values, or could be more complex structures based on the intrinsic properties of the proposed reordering. We proved that AgileABT is guaranteed to terminate if the priority relation over the termination values is a well ordering and has a polynomial space complexity when the computation of the termination values has polynomial space complexity.

We then proposed AgileABT( [α], ≺ α ) an instance of AgileABT where arbitrary dynamic variable ordering heuristics defined by an order relation over a measure, α, applied to each variable in the problem can be implemented using termination values in the form of vector of measures α. We proved that AgileABT( [α], ≺ α ) is guaranteed to terminate if the order relation over the measure α is a well ordering. Thanks to this original concept of termination values, any agent is now able to propose any other conflicting agent as a target to backtrack to, and can propose a reordering of all other agents, including those appearing before that backtrack target. These interesting features are totally new for a DisCSP algorithm with polynomial space complexity. AgileABT( [α], ≺ α ) allowed us to implement for the first time in DisCSPs a wide variety of the DVOs studied in centralized CSP research. Our experiments confirm the significance of these DVOs on a distributed setting. These experiments showed that AgileABT( [α], ≺ α ) offers orders of magnitude improvement in both computation and messaging costs compared to the original static ABT, and consistently outperforms previous proposals for dynamic ordering in ABT.

A 12 : x 1 =x 2 c 13 : x 1 =x 3 c 15 : x 1 =c 25 : x 2 =x 5 c 34 : x 3 < x 4 c 45 : x 4 ≥ x 5 Figure 1 :

 12213315125534451 Figure 1: The constraint graph of a DisCSP instance of 5 agents/variables and 6 constraints.

c 25 :

 25 x 2 = x 5 , c 34 : x 3 < x 4 , and c 45 : x 4 ≥ x 5 . Figure 1(left) shows the constraint graph representation of this instance. Agent a 1 knows three constraints C 1 = {c 12 , c 13 , c 15 } and ignores the other constraints.

Figure 2 :

 2 Figure 2: The directed acyclic constraint graph of the DisCSP instance in Figure 1 induced by λ = [1, 2, 3, 4, 5].

Figure 3 :

 3 Figure 3: The ABT algorithm running by agent ai.

  xj, vj, tj to aj;

Figure 4 :

 4 Figure 4: The AgileABT algorithm run by agent ai.

Figure 5 :

 5 Figure 5: The variation of the best termination value of the system over time.

A 3 c34 : x3 • x4 ≤ 3 ( a )

 33a = {a1, . . . , a4} X = {x1, . . . , x4} D = {D1, . . . , D4}, where Di = {1, 2, 3} C = {c12, c13, c23, c24, c34} c12 : (x1 + x2) div 3 = 0 c13 : x1 + x3 = 5 c23 : x2 ≤ x3 c24 : x2 + x4 = The constraint graph of a DisCSP instance of 4 agents/variables and 4 constraints. function f() 01. λ ← random permutation of [1, . . . , n]; 02. τ ← random integer in [0, . . . , 100]; 03. return( λ, τ ); (b) A trivial function f() used by agents to propose new orders.

  d) Agent a 1 facing a dead-end.

Figure 6 :

 6 Figure 6: An example of AgileABT running with a trivial function f()

  Now we shall give a small example to illustrate how ≺ lex α is used to compare termination values and orders. Consider for instance three orders on five agents λ = [1, 2, 3, 4, 5], λ = [1, 2, 5, 4, 3], and λ = [1, 2, 4, 5, 3], associated respectively with termination values τ = [2, 2, 3, 4, 2], τ = [1, 2, 2, 2, 2], and τ = [1, 2, 2, 2, 2].

Figure 7 :

 7 Figure 7: Compute wdeg(i), the weighted degree of agent ai.

Figure 8 :

 8 Figure 8: New lines/procedures of AgileABT([α], ≺α) with respect to AgileABT in Figure 4.

Corollary 3 .

 3 AgileABT([α], ≺ α ) is sound, complete, and terminates if α ∈ {dom, dom/deg, dom/pdeg, dom/fdeg, dom/wdeg}. Proof. From Proposition 2, Proposition 5, and Corollary 2.

  [α(λ[1]), . . . , α(λ[n])]. By construction, this means that there are k nodes in G that are linked by [1 + 2 + • • • + (k -1)] = k(k -1)/2 edges. In other words, these nodes form a clique in G.

: 4 e 2 : [x 1 = 1 ] → d 2 = 3 e 3 : [x 1 = 1 ] → d 3 = 3 e 4 : [x 3 = 2 ] → d 4 = 2 explanations (E 5 ) 5 A 5 : 5 Updated explanations (E 5 ) e 1 : [x 2 = 2 ∧ x 4 = 3 ] → d 1 → d 4 = 2 e 5 : [x 2 = 2 ∧ x 4 = 3 ] → d 5 a 5 :

 42113311343225555512243125224355 (x 1 = 1), e 1 : [] → 4 ok? 2→5 : (x 2 = 2), e 2 : [x 1 = 1] → 3 ok? 3→5 : (x 3 = 2), e 3 : [x 1 = 1] → 3 ok? 4→5 : (x 4 = 3), e 4 : [x 3 = 2] → 2 e 1 : [] → d 1 = ngd(x 5 =1): [x 1 = 1] → x 5 =1 ngd(x 5 =2): [x 2 = 2] → x 5 =2 ngd(x 5 =3): [x 1 = 1] → x 5 =3 ngd(x 5 =4): [x 4 = 3] → x 5 =4no-goods (D 5 = ∅) (a) Explanations and no-goods maintained by a when choosing x 1 as backtracking target for Λ updated explanations with x 1 as target.

A 5 :

 5 target selection Selected no-good: ngd[x 1 =1]: [x 4 = 3 ∧ x 2 = 2] → x 1 =1 λ 5 = [1, 2, 3, 4, 5] τ 5 = [[START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF]

(c) a 5 :

 5 selection of target (x 1 ).

Figure 9 :

 9 Figure 9: An example of a possible execution of AgileABT([dom], <) on the problem of Figure 1.

Figure 11 :

 11 Figure 11: Dense uniform binary random DisCSPs

Figure 12 :

 12 Figure 12: Distributed sensor networks

( c )

 c The total number of bytes exchanged on dense random DisCSP instances.

Figure 14 :

 14 Figure 14: The total number of bytes exchanges to solve random DisCSP and Sen-sorDisCSP instances.

  Let x t

			c 13		c 15	c 25
	c 12				c 34		c 45
	x 1		x 2		x 3	x 4		x 5
	a 1	a 2	c 12	a 3	c 13	c 34	a 4	c 15 c 25	a 5
								c 45

  : processNgd(as, ngd[xi =v i ]);

	procedure AgileABT()
	01. initialize();
	02. assignVariable();
	03. while ( ¬end ) do 04. msg ← getMsg(); 05. switch ( msg.type ) do
	06.	ok? : processOk(xs, vs, ts);
	07.
	08.
	09.

ngd adl : processAdl(as, v i ); order : processOrder(λs, τs); 10.

  ) 29. λi, τi ← λ , τ ; 30. remove incoherent no-goods; procedure proposeOrder() 31. λ , τ ← f(); 32. if ( τ ≺τ τi ) then procedure processOk( xs, v s , t s ) 35. updateAgentView( xs, v s , t s ); 36. checkAgentView();

		procedure backtrack()
		37. Λi ← resolveNogoods(); 38. if ( Λi = ∅ ) then 39. end ← true; 40. sendMsg:stp to {A \ ai}; 41. else
		42. 43.	i ; LN ← Γ + proposeOrder() ;
		44.
		46.
		48.
	18.
	21. 22.	ti ← ti +1;
	33.

else store ngd[xi =v i ] from constraints; 19. return(f alse); procedure assignVariable() 20. if ( chooseValue() ) then sendMsg:ok? xi, vi, ti to Γ + i ; 23. else backtrack(); procedure checkAgentView() 24. if ( ¬isConsistent(vi, AV -) ) then 25. assignVariable(); procedure updateAgentView(S) 26. foreach ( xj, v j , t j ∈ S ) do 27. if ( t j ≥ tj ) then AV [j] ← xj, v j , t j ; 28. remove incompatible no-goods; procedure changeOrder(λ , τ sendMsg:order λ , τ to {A \ ai}; 34. changeOrder(λ , τ ); Let xt be the lowest agent in Λi; 45. ngd[xt =vt] ← ({Λi \ xt} → xt =vt); sendMsg:ngd ngd[xt =vt] to at; 47. updateAgentView( xt, nil, tt ); if ( isConsistent(vi, AV -) ) then 49. sendMsg:ok? xi, vi, ti to {Γ + i \ LN }; 50. else assignVariable(); procedure processOrder(λs, τs) 51. if ( (λs, τs) is stronger than (λi, τi) ) then 52. LN ← Γ + i ; 53. changeOrder(λs, τs); 54. if ( isConsistent(vi, AV -) ) then 55. sendMsg:ok? xi, vi, ti to {Γ + i \ LN }; 56. else assignVariable(); procedure processNgd(as, ngd[xi =v i ]) 57. checkAddLink(lhs(ngd[xi =v i ])); 58. if (compatible(ngd[xi =v i ], AV -)∧ coherent(ngd[xi =vi], λi)) then 59. store ngd[xi =v i ]; 60.

  1); 21. return(E i ); function computeOrder(E i ) 22. λ and τ are arrays of length n; 23. p ← 1; 24. G ← {(j, k) | xj ∈ Λk, ek ∈ E i }; 25. while ( p ≤ n ) do

	26. 27.	R ← {r | (s, r) ∈ G}; r ← arg min k∈R {α(k)}; /* using ≺α */
	28. 29. 30. 31. 32. 33. return( λ, τ ); λ[p] ← r; τ [p] ← α(r); p ← p + 1; foreach ( (r, s) ∈ G ) do G ← G \ (r, s);
	function f()
	34. foreach ( ek ∈ Ei ) do 35. if ( ¬valid(ek) ) then 36. Ei ← Ei \ ek ; 37. λ ← nil; τ ← nil; 38. foreach ( xt ∈ Λi ) do 39. E i ← simulateExplanations(xt); 40.
	41. 42. 43.	α τ ) then if ( τ ≺ lex λ ← λ ;

λ , τ ← computeOrder(E i ); τ ← τ ; 44. return( λ, τ );

  DisChoco implements a model to solve Distributed Constraint Reasoning problems. Communication is performed via the Simple Agent Communication Infrastructure (SACI) if agents are implemented on different Java Virtual Machine (JVM). Otherwise, if agents are Sparse uniform binary random DisCSPs simulated by Java threads on a single JVM, the communication is performed only through message passing via a local communication simulator. This is this second option that we have used in our experiments.

				#ncccs 〈n=20, d=10, p 1 =0.2〉 #ncccs 〈n=20, d=10, p 1 =0.7〉
	5e+6
	4e+6 2.5e+5		ABT_DO-ng ABT 1e+6				ABT_DO-ng ABT
	2.0e+5		Agile(dom) ABT_DO-Retro(dom) 9e+5		Agile(dom) 2.5e+4 ABT_DO-Retro(dom)
	1.5e+5 3e+6		Agile(dom/deg) 8e+5				Agile(dom/deg)
			Agile(dom/fdeg) 7e+5				5.0e+3 Agile(dom/fdeg)
	1.0e+5 2e+6	0.3	Agile(dom/pdeg)				0.65 Agile(dom/pdeg)
			Agile(dom/wdeg)				Agile(dom/wdeg)
	5.0e+4 1e+6
	0.45 0.15	0.5 0.2	0.55 0.25	0.6 0.3	0.65 0.35	0.7 0.4	0.75 0.45	0.8 0.5	0.85 0.55
						p 2 p 2
				#msg 〈n=20, d=10, p 1 =0.2〉 #msg 〈n=20, d=10, p 1 =0.7〉
	4e+6 1.0e+5		ABT_DO-ng ABT 7e+5				ABT_DO-ng 1.5e+4 ABT
	8.0e+4 3e+6		ABT_DO-Retro(dom)		ABT_DO-Retro(dom)
			Agile(dom) 6e+5				1.0e+4 Agile(dom)
	6.0e+4		Agile(dom/deg)				Agile(dom/deg)
	2e+6		Agile(dom/fdeg) 5e+5				5.0e+3 Agile(dom/fdeg)
	4.0e+4	0.3	Agile(dom/pdeg)				0.65 Agile(dom/pdeg)
	1e+6		Agile(dom/wdeg)				Agile(dom/wdeg)
	2.0e+4
	0.45 0.15	0.5 0.2	0.55 0.25	0.6 0.3	0.65 0.35	0.7 0.4	0.75 0.45	0.8 0.5	0.85 0.55
						p 2 p 2
	Figure 10: When comparing distributed algorithms, the performance is evaluated using
	two common metrics: the communication load and computation effort. Com-
	munication load is measured by the total number of exchanged messages among
	agents during algorithm execution (#msg) [34]. Computation effort is measured
	by the number of non-concurrent constraint checks (#ncccs) [35]. #ncccs is the
	metric used in distributed constraint solving to simulate computation time, but

Table 1 :

 1 ), ABT is significantly the slowest algorithm but it requires fewer messages than ABT DOng. AgileABT([α], ≺ α ) outperforms all other algorithms on both #msg and #ncccs. AgileABT([dom/wdeg], <) is slower and requires more messages compared to other heuristics of AgileABT([α], ≺ α ). Regarding the messaging, the neighborhood based heuristics (i. e., dom/deg, dom/pdeg and dom/f deg) perform well. They show more than an order of magnitude improvement compared to ABT, ABT DO-ng and ABT DO Retro(mindom) and an almost twofold improvement over dom/wdeg. Regarding the speedup, AgileABT([α], ≺ α ) shows at least an order of magnitude improvement compared to ABT. The Distributed graph coloring problems

	Algorithm	15, 5, 0.65	25, 5, 0.45
		#msg #ncccs	#msg	#ncccs
	AgileABT([dom/wdeg], <)	64,587 184,641 1,155,373 2,068,677
	AgileABT([dom/f deg], <)	42,305 109,348	453,888	821,397
	AgileABT([dom/pdeg], <)	24,174	67,829	197,877	396,320
	AgileABT([dom/deg], <)	29,688	78,200	255,434	504,600
	AgileABT([dom], <)	48,095 166,564 1,054,793 2,386,179
	ABT DO Retro(mindom)	76,228	87,480 1,208,224	678,424
	ABT DO-ng	139,866 239,424 4,110,364 3,131,566
	ABT	77,536 133,354 1,531,776 3,413,261

Table 2 :

 2 Composed random instances

	Instances	25-1-25	25-1-40
	Algorithm	#msg	#ncccs	#msg	#ncccs
	AgileABT([dom/wdeg], <)	19,133	22,205	23,313	23,728
	AgileABT([dom/f deg], <)	56,158	139,106	112,389	316,381
	AgileABT([dom/pdeg], <)	9,511	10,786	10,911	11,512
	AgileABT([dom/deg], <)	38,026	150,880	156,164	763,136
	AgileABT([dom], <)	9,871	14,328	10,920	14,286
	ABT DO Retro(mindom)	53,566	27,507	69,627	37,049
	ABT DO-ng	1,045,077 1,166,210 14,400,090 13,017,189
	ABT	1,327,065 7,883,914 10,219,262 64,570,955

Table 2

 2 <) shows 3 orders of magnitude improvement compared to ABT and ABT DO-ng. Regarding AgileABT([α], ≺ α ) DVOs, dom/wdeg pays off on these instances compared to dom/deg and dom/f deg.6.4. Target tracking in distributed sensor networksThe Target Tracking in Distributed Sensor Network (SensorDisCSP)[START_REF] Béjar | Sensor Networks and Distributed CSP: Communication, Computation and Complexity[END_REF][START_REF] Wahbi | CSPLib problem 072: Target tracking in distributed sensor network[END_REF]

	) show that AgileABT([dom/pdeg], <) outperforms

  The total number of bytes exchanged on SensorDisCSP instances. The total number of bytes exchanged on sparse random DisCSP instances.

				dataTX(bytes) 〈n=25, m=6, p c =0.15〉
	1.4e+6									ABT
									ABT_DO-ng
	1.2e+6							ABT_DO-Retro(dom)
	1.0e+6								Agile(dom)
									Agile(dom/deg)
	8.0e+5								Agile(dom/fdeg)
	6.0e+5								Agile(dom/pdeg)
									Agile(dom/wdeg)
	4.0e+5
	2.0e+5
	0.1	0.15	0.2	0.25	0.3	0.35	0.4	0.45	0.5	0.55	0.6	0.65
						p v
	2e+6 3e+6 4e+6 (a) 1e+6	dataTX(bytes) 〈n=20, d=10, p 1 =0.2〉 Agile(dom/wdeg) Agile(dom/pdeg) Agile(dom/fdeg) Agile(dom/deg) Agile(dom) ABT_DO-Retro(dom) ABT_DO-ng ABT
	0.45	0.5	0.55	0.6	0.65		0.7	0.75	0.8	0.85
						p 2
	5.0e+7 1.0e+8 1.5e+8 2.0e+8 2.5e+8 (b) 0.0e+0			dataTX(bytes) 〈n=20, d=10, p 1 =0.7〉 Agile(dom/wdeg) Agile(dom/pdeg) Agile(dom/fdeg) Agile(dom/deg) Agile(dom) ABT_DO-Retro(dom) ABT_DO-ng ABT
	0.15	0.2		0.25	0.3	0.35	0.4	0.45	0.5	0.55
						p 2

Table 3 :

 3 The number of order messages exchanged by each algorithm

		Composed	Composed	Graph	Graph	Sensor	Randon	Randon
	Benchmark	Random:	Random:	Coloring:	Coloring:	DisCSP:	DisCSP:	DisCSP:
		25-1-25	25-1-40	15, 5, .65	25, 5, .45	25, 6, .15, .3	20, 10, .2, .65	20, 10, .7, .3
	ABT DO	84,709	842,538	24,962	708,482	2,710	19,331	392,376
	ABT DO Retro(mindom)	30,357	35,550	27,450	423,198	5,470	24,795	1,559,112
	AgileABT([dom], <)	5,095	5,182	7,935	20,315	1,022	2,206	171,374
	AgileABT([dom/deg], <)	6,170	10,101	7,447	17,260	968	1,994	155,031
	AgileABT([dom/f deg], <)	10,175	10,428	10,171	30,746	837	2,622	174,801
	AgileABT([dom/pdeg], <)	4,600	4,813	5,081	16,925	688	1,496	173,826
	AgileABT([dom/wdeg], <)	6,591	7,104	13,285	67,197	1,265	5,187	240,000

In practice it is of course desirable to choose a function f() such that the smaller the termination value, the better the associated ordering.

The initial domain size of each agent can be known in a preprocessing step before search starts.

deg(k) can be known before the search starts as is the case for the d k of each agent.

Again this information can be known in a preprocessing step.

AWC also allows retroactive reordering, but ABT DO Retro is a generalization of AWC[START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF].

For AgileABT([dom/wdeg], <), we fixed W = 10 3 . But, varying W (to 10 4 or 10 5 ) made negligible difference to the results.

http://dischoco.sourceforge.net/

for dynamic reordering algorithms its variant generic #ncccs is used[START_REF] Zivan | Message delay and DisCSP search algorithms[END_REF]. Al-

http://www.cril.univ-artois.fr/∼lecoutre/benchmarks.html

AgileABT([α], ≺ α ) heuristics require almost the same #msg to solve Sensor-

Acknowledgements

This material is based in part on work supported by Science Foundation Ireland under Grant No. 12/RC/2289 P2 which is co-funded under the European Regional Development Fund.

Proposition 9. Given a DisCSP defined by the network (A, X , D, C), with X = {x 1 , . . . , x n }, given an agent a i , and given a measure α from [1..n] to Q, it is NP-hard to compute a total order λ on X that satisfies the safety conditions in S(E i ) and such that [α(λ [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF]), . . . , α(λ[n])] is lexicographically minimum, even if S(E i ) is acyclic.

Proof. Our proof is inspired from a proof of hardness of finding minimal topological sorts of a graph [START_REF] Eppstein | Lexicographically Minimal Topological Sort of a Labeled DAG[END_REF]. We reduce the Clique problem (one of Karp's 21 NP-complete problems), to our problem of finding a total order λ on X that satisfies the safety conditions in S(E i ) and such that [α(λ [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF]), . . . , α(λ[n])] is lexicographically minimum. Let G = (X, H) be an undirected graph in which we want to decide if there exists a clique of size k. We build a DisCSP with network (A, X , D, C). X contains |X| + |H| + 1 variables, where each node i in X is associated with a variable u i , each edge (i, j) is associated with a variable w ij , plus a variable z. A contains an agent per variable of X . The variables u i have two values {i, i + 1} in their domain. The variables w ij have three values {i, j, i + j • |X|} in their domain, so that value i + j • |X| only belongs to one w ij variable. The variable z has domain {i + j • |X| | (i, j) ∈ H} that contains |H| values, each value corresponding to an edge (i, j) ∈ H. C is composed of 3 • |H| constraints: u i = w ij , u j = w ij , and w ij = z, for each edge (i, j) ∈ H. The measure α is defined by α(x) = dom(x), for any variable x in X . The initial order among agents is such that all u i appear before all w ij , and z is the last. Finally suppose all agents instantiate their variables in lexicographic order of their values. Once a variable w ij has received ok? messages from its two predecessors u i and u j , it eliminates values i and j from its domain and assigns value i + j • |X| to its variable. Afterwards, it sends a new ok? message to the variable z. In addition to the new value of the variable w ij , this ok? message contains the explanation u i = i ∧ u j = j → 1. Once the variable z has received all the ok? messages from variables w ij , it has to backtrack because all values in its domain become forbidden. It has to compute a new order minimizing the termination value, that is, an order λ such that [α(λ [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF]), . . . , α(λ[n])] is lexicographically minimum. For each w ij ∈ X , there are two safety conditions (u i ≺ w ij ) and (u j ≺ w ij ) in S(E z ) induced by the explanation sent by w ij . Observe that S(E z ) is thus acyclic. In addition, for each i ∈ X, α(u i ) = 2, and for each (i, j) ∈ H, α(w ij ) = 1 (because no-goods have removed values i and j from the domain of w ij ). As a result, G contains a clique of size k if and only if the lexicographically minimum vector [α(λ [START_REF] Junges | Evaluating the Performance of DCOP Algorithms in a Real World, Dynamic Problem[END_REF]), . . . , α(λ[n])] satisfying the acyclic safety conditions accepts the word 22121 2 21 3 ...21 k-1 as prefix, where 2 i denotes the sequence of i consecutive 2.

To prove this claim we first observe that an order λ satisfying the safety conditions cannot put a variable w ij before u i and u j . We now analyze the two directions of this claim. If G contains a clique of size k, we generate a sequence of variables the following way. Start from the empty sequence. Select each node j in turn in the clique of size k. Add u j to the sequence, followed by all w ij such that u i is already in the sequence. At the end of this process we have built a prefix of an order λ such that 22121 2 21 3 ...21 k-1 is a prefix DisCSP instances. They show an improvement factor of 3.5 over ABT DO-ng and ABT DO Retro(mindom) and an improvement factor of 7 over ABT.

Evaluation of messages size

In order to assess the communication load we measured #msg, the total number of exchanged messages among agents during algorithm execution [START_REF] Lynch | Distributed Algorithms[END_REF]. 13 presents the size of the longest message sent by each algorithm on all our experiments. The results show that in all the compared algorithms the size of the longest message sent is larger when solving composed random instances (it is between 147 bytes for ABT and 253 bytes for AgileABT([dom/pdeg], <)). Solving graph coloring instances requires the