Sébastien Mosser

Gabriel Hermosillo

Anne-Françoise Le Meur

Lionel Seinturier

Laurence Duchien

Undoing Event-Driven Adaptation of Business Processes

Keywords: Event Driven Approach, Business Process, Adaptation

As business processes continue to gain relevance in different domains, dynamicity is becoming a great concern. Static processes no longer cover the actual needs of constantly changing environments, and process adaptation is a must in order to maintain competitive levels. While creating dynamically adaptable business processes can be a challenging task, undoing these adaptations is a natural functionality that has not been studied in depth. Straight forward approaches for unadaptation can easily end up with corrupted processes, bringing uncertainty to the whole business logic. In this paper we bring forward a solution for efficiently undoing a business process adaptation in event-driven environments, considering also the correlated adaptations that happened afterwards.

I. INTRODUCTION

There is a huge amount of variable conditions surrounding today's business environments. The context in which our business processes (BPs) are executed is an important factor that directly affects the way they are executed. We can no longer rely on static processes, since we need to consider these conditions and adapt our processes accordingly in order to obtain better results and maintain a competitive level. Several efforts have been made towards adding dynamicity to BPs, showing how much this problematic matters [START_REF] Rahman | An Adaptive ECA-centric Architecture for Agile Service-based Business Processes with Compliant Aspectual[END_REF]- [START_REF] Hermosillo | Creating Context-Adaptive Business Processes[END_REF].

By monitoring the context in which business processes are being executed, it is possible to efficiently respond to any changes in the environment and continue the process in an optimal way. Changes in the context can be seen as events that arrive at a specific moment in time and have a different meaning depending on several conditions, e.g., timing, origin, sequence. The meaning of each event can help us determine a specific situation to which we can react by adapting the process. However, sometimes it is not a single event, but a combination of events that should trigger the adaptation, and this is where Complex Event Processing (CEP) can be used. CEP is an emerging technology from which organizations can benefit, since it allows them to find real-time relationships between different events, using elements such as timing, causality, and membership in a stream of data to extract relevant information [START_REF] Luckham | The Power of Events: An Introduction to Event Processing in Distributed Enterprise Systems[END_REF].

Using CEP approaches, the reception of an event ǫ (e.g., a CPU overload) meet a certain condition and the system is then adapted [START_REF] Hermosillo | Using Complex Event Processing for Dynamic Business Process Adaptation[END_REF]. But, what happens when we receive ¬ǫ? The condition is no longer true (i.e., the CPU load is back to normality) and we would like to go back to our original process. Undoing of adaptations is a topic that has been left aside, but it cannot be obviated, since, as we will explain in this paper, a straight forward approach can easily lead to corrupted processes.

The objective of this paper is to present an effective solution to event-driven BP unadaptation, by considering not only the event that caused the adaptation, but also the correlated adaptations that came afterwards, leaving all the unrelated adaptations untouched, in order to obtain a BP "as it would be if this adaptation had never happened" (similarly to transactional systems [START_REF] Bernstein | Concurrency Control and Recovery in Database Systems[END_REF] where the rollback operation is used to restore a system). Using this generic and automated approach, users are relieved from handling the unadaptation logic.

The rest of this paper is organized as follows. In Section II, we use a scenario to illustrate the motivation and challenges of our proposal. Section III presents our approach for doing and undoing BP adaptations. Section IV describes how the actual undoing of BP adaptation is achieved. In Section V, we show an implementation to validate our proposal. Section VI gives some related work. Finally, Section VII concludes and discusses future work.

II. MOTIVATION AND CHALLENGES

In this section we will use a simple example to illustrate how a business process can be adapted and why undoing this adaptation is needed, but is not a simple and transparent task.

A. Example Description

We consider here a simple process, part of an online catalog software. It contains five activities, which respectively: (i) logs the user in, (ii) asks for user's request, (iii) performs the search in the internal database, (iv) displays the results to the user and finally (v) logs the user out. This process is depicted in FIG. 1. We want to adapt this process according to the context, using an event-driven approach. Process adaptations are driven by the reception of explicit events (triggered by associated conditions). For example, if the search service becomes unavailable, a fail event will be triggered, and an adaptation will be executed to fix the problem. Precisely, it will connect the process to a remote backup service, to ensure continuity for customers. We summarize in TAB. I the different adaptation rules associated to our running example. Accordingly, if the fail event is received, the business process will be adapted to tackle this issue, and we will obtain after the adaptation the process depicted in FIG. 2. In this figure (and the upcoming ones), we represent deleted elements with dashed lines . If we then receive a performance alert by the event perf (identifying a CPU abnormal usage), we want to start monitoring the CPU consumption for all the activities in the process. To achieve this, we will add a monitoring activity after each existing activity. The resulting process is depicted in FIG. 3. As the backup server is a remote entity, we depend on the quality of the network connection to search the catalog. Considering a bandwidth drop (identified with a slow event), the cache event will also be recognized (as it is defined as a fail followed by a slow) and we will need to adapt the process by adding a cache mechanism to help diminish the response time of the requests. The adapted process is depicted in FIG. 4.

B. Need for Adaptation Undo

When an adaptation condition is no longer true, we would like to get our process "as it would be if this adaptation had never happened". Retaking our previous example, let's say we receive an event ¬fail1 , which means that we recovered our internal search server. In this case, we no longer need the external backup nor the associated cache mechanism and we can remove them. Naively, undoing an adaptation does not seem so complicated. It can be seen as removing all the changes made to the business process that were caused by the fail event. In order to achieve this, the intuitive undoing action would be to use the exact "opposite" of the used adaptation. In our case, it would remove the backup server and re-introduce the internal search one. The associated process is depicted in FIG. 5(a). Unfortunately this process does not make sense in terms of business logic, as it holds the two following issues2 : (i) the search activity is not monitored and (ii) the cache mechanisms are irrelevant since the vanishing of the backup server.

C. Challenge: Automating Adaptation Undoing

As seen in the previous example, a straight forward undoing of the adaptation can result in a corrupted process. To obtain a correct undoing of an adaptation, we could add an adaptation rule that changes the process to its original state. However, this approach will only work if we consider all the possible states of the process, given all the possible adaptations that could happen, providing the correct process for each and every one of them. This, far from being user friendly, is virtually impossible to accomplish.

The ideal case would be to provide the user with an automated unadaptation of the process, whenever adaptation conditions are no longer met. Using this approach, we could automatically produce a system "as it would be if this adaptation had never happened". Going back to the previous example, it results in the synthesis of the process depicted in FIG. 5 mechanism is not present (since its trigger event depends on the fail one). As a consequence, to support this automated unadaptation, we highlight the following mechanisms M i , which are required to properly undo an adaptation triggered by an event ǫ:

• M 1 : Identify the undoing trigger. Based on the description of events, the system must be able to recognize their opposite, and trigger the automated undoing mechanisms when relevant. • M 2 : Restore the process. The current process must be restored to what it was before the reception of ǫ. • M 3 : Forget the correlated adaptations. Adaptations triggered by any event which depends (immediately or transitively) on ǫ (e.g., the cache event depends on the fail event) must be forgotten. • M 4 : Re-execute the unrelated adaptations. All adaptations that are independent of ǫ must be re-executed, to yield a system equivalent to the one obtained after their on-the-fly execution.

III. ADAPTATION: FROM "do" TO "undo"

To tackle the issues identified in the previous section, we propose to automate the support of BP unadaptation. The key idea is to formalize the adaptation, and to rely on this formal model to define and then operationalize the unadaptation. We consider here an event-driven adaptation engine based on state-of-the-art mechanisms [START_REF] Sharon | Event-processing Network Model and Implementation[END_REF], represented in FIG. 6. At a coarse-grained level, the engine receives a continous flow of events from deployed sensors. According to the received events, the CEP engine will trigger associated adaptations, stored in an adaptation repository. The obtained (adapted) process is then sequentially used as input for the upcoming adaptations.

Complex Event Processing Engine event flow

Adaptation rules Repository

A. Business Processes & Actions

We define a business process p ∈ P as a set of activities acts, which implement elementary tasks, and a set of causal relations rels to schedule the activity set according to a partial order. This formalization is based on the ADORE meta-model [START_REF] Mosser | Behavioral Compositions in Service-Oriented Architecture[END_REF] and models a subset of the BPEL industrial standard [START_REF]Web Services Business Process Execution Language Version 2.0[END_REF]. For simplification purpose, we assimilate an activity to its name, without further knowledge of its internal contents. A (binary) causal relation is defined as an ordered pair of activities (i.e., lef t and right). We denote as lef t ≺ right ∈ R the fact that a relation exists between lef t and right. We depict in FIG. 7 a business process and its associated formal representation. To manipulate BPs, we use an action-based approach, since these approaches are known to efficiently support the manipulation of models [START_REF] Blanc | Detecting Model Inconsistency through Operation-Based Model Construction[END_REF]. An elementary action is defined as the addition or deletion of a model element in a given business process. In itself, an action α is simply a ground term that reifies the associated intention (e.g., adding an activity, deleting a relation). TAB. II lists the existing actions available to modify a given business process. The execution of an action α on a process p is handled by a call to the exec function: exec(α, p) = p ′ , where p ′ is a process effectively modified. Actions can be sequenced to implement complex modifications. Let A = [α 1 , . . . , α n ] be a sequence3 of actions. The execution of A on a given process p is formally defined as follows:

exec + (L, p) = L = ∅ ⇒ p L = [α|A] ⇒ exec + (A, exec(α, p))
Using this representation, the process p depicted in FIG. 7 can be built as the result of the execution of its associated action sequence A p on the empty process.

A p = [add a (a 1 ), add a (a 2 ), add r (a 1 , a 2 ), add a (a 3 ), add r (a 2 , a 3 )] p = exec + (A p , (∅, ∅))

B. Events & Complex Events

An event ǫ is reified as a value associated to a sensor, e.g., the CPU load is equal to 80%. We use a tuple of terms ǫ = (sensor, value) to represent this information. Events are continuously sent to a complex event processor engine, in our case Esper 4 . Based on this continuous flow, this engine identifies complex events (CEs), defined as (i) a boolean formula applied to an (elementary) event to process it or (ii) a combination of other complex events. We represent in TAB. III the expressiveness associated to usual complex events definitions. CEs can be conjucted (∧) or disjuncted (∨) using elementary boolean logic. A sequence operator is used to introduce causality between two events (ǫ 1 ; ǫ 2 means that ǫ 2 foolows ǫ 1 eventually, even if not immediately). Finally, a time window operator supports the wait for a given complex event for a given duration (e.g., ǫ ′ = within(ǫ, 200ms) will be recognized if the CE ǫ is received by the engine within 200ms).

C. Event-driven BP Adaptation

Based on these definitions of BPs and CEs, one can add adaptability into existing business processes. To perform such a task, a user would define adaptation rules, and store them into a shared rule repository. This repository is connected to the complex event processing engine, which triggers the adaptation application at runtime.

An adaptation rule r ∈ A R is defined as a tuple (ǫ, ϕ), where ǫ is the CE used to trigger the adaptation 5 , and ϕ is a function used to compute the action sequence to be executed to perform the adaptation. This action sequence is executed on the BP, to modify its structure and then implement the adaptation:

Let a = (ǫ, ϕ) ∈ A, p ∈ P, ǫ ⇒ exec + (ϕ(p), p)
We illustrate such an adaptation in FIG. 8. The goal of this adaptation is to replace an activity by another one when the ǫ complex event is processed (e.g., the replacement of the internal search by the backup server in the running example, FIG. 2). The application of ϕ the process p produces a sequence of actions A, which aims to replace the activity a 2 by a new activity a ′ 2 . To implement this adaptation, the engine executes A on p, and computes as output p ′ , the adapted process. To properly support unadaptation of BPs, we need to keep track of the adaptation history. This concept is expressed as a list of tuples (ǫ, A ǫ ), where ǫ is the processed CE and A ǫ = [α 1 , . . . , α n ] the sequence of actions computed according to this event. The list is maintained in reversed order, i.e., the head of the history corresponds to the last adaptation. Considering the final adapted process (FIG. 4) associated to the adaptation scenario depicted in SEC. II, the history is defined as follows:

H ex = [(perf, A perf ), (slow, A slow ), (fail , A fail )]

D. Automating Adaptation Undoing

We consider here the situation depicted in FIG. 9. This situation is a formal representation of the adaptation scenario textually described in SEC. II: p is the initial scenario (FIG. 1), and p 123 is the resulting adapted process (FIG. 4).

p ǫ 1 -→ p 1 ǫ 2 -→ p 12 ǫ 3 -→ p 123
Defined complex events: {ǫ 1 , ǫ 2 , ǫ 3 } Complex events combination: ǫ 3 = ǫ 1 ; ǫ 2 Rule repository: {(ǫ 1 , ϕǫ 1 ), (ǫ 2 , ϕǫ 2 ), (ǫ 3 , ϕǫ 3 )} Adaptation steps:

p 1 = exec + (Aǫ 1 , p), Aǫ Doing adaptation. The adaptation rule repository holds three rules, defined with respect to three complex events: {ǫ 1 , ǫ 2 , ǫ 3 }. Complex events ǫ 1 and ǫ 2 are elementary event processing, and ǫ 3 is defined as the detection of ǫ 2 after the detection of ǫ 1 . Based on the analysis of the incoming elementary events, adaptations are triggered by the complex event processing engine to adapt a given process p. We consider here the following sequence of events: ǫ 1 , ǫ 2 , and consequently ǫ 3 (according to its definition). After these three adaptations, we obtain a process p 123 . This process is handled through the previously defined mechanisms.

Undoing adaptation. We consider now the detection of a complex event opposed to ǫ 1 (denoted as ¬ǫ 1 ). In this new context, adaptations that had been triggered based on ǫ 1 do not make sense anymore, and must be undone. Considering that our objective is "to produce the system as it would be if this adaptation had never happened", we also need to undo all adaptations depending on ǫ 1 (i.e., triggered by a complex event which combines ǫ 1 with others, here ǫ 3 ). According to this goal, and with respect to the mechanisms M i identified in SEC. II, the system needs to (i) recognize the opposite event and then trigger the undoing mechanisms (M 1 ), (ii) rewind the historic to retrieve the process as it was before the reception of the incriminated event (M 2 ), (iii) prune from the historic the adaptations that depend (immediately or transitively) on this event (M 3 ), and finally (iv) replay the remaining adaptations to obtain the expected process (M 4 ).

Considering the example depicted in FIG. 9, the undo mechanism associated to ǫ 1 is expected to automate the following steps:

• recognize: Assuming that ǫ 1 is an arithmetic comparison (e.g., bandwidth < 100kbps), its opposite can be automatically computed (i.e., ¬ǫ 1 = bandwidth ≥ 100kbps). An adaptation needs to be undone since the complex event processor engine detects the event and its opposite in sequence, i.e., ǫ -1 1 = ǫ 1 ; ¬ǫ 1 . • rewind: On the detection of ǫ -1 1 , the system will restore the process as it was before the detection of ǫ 1 . In our case, this rewind restores the process as p.

• prune: Considering the contents of the history, the engine knows that the process p was adapted according to the following sequence of events: [ǫ 1 , ǫ 2 , ǫ 3 ]. The pruning step removes from this sequence the incriminated event, and all its (transitive) dependencies (here, ǫ 3 ). In our case, the pruned sequence is [ǫ 2 ]. • replay: The adaptations triggered by the events contained in the pruned sequence need to be replayed on the process. In our case, it means to adapt p according to the rule associated to ǫ 2 . We obtain as a result of this adaptation undoing the process p 2 , as represented in FIG. 10.

p ǫ 1 -→ p 1 ǫ 2 -→ p 12 ǫ 3 -→ do p 123 ¬ǫ 1 -→ (p ǫ 2 -→) undo p 2 p 2 = exec + (ϕǫ 2 (p), p)

IV. "UNDO" OPERATIONALIZATION

In this section, we formally describe how the undaptation can be operationalized. We present the different operations used to support the undo process using a functional style, being consequently language independent.

A. M 1 : Recognition of an Undo Trigger (ǫ -1 )

We denote as ǫ -1 the CE that triggers an undo. This event is defined as the sequence composed by the event ǫ and its associated opposite event ¬ǫ. Using this definition, an undo will always be triggered when the engine recognizes an opposite event (e.g., ¬fail ) eventually preceded by an event (e.g., fail).

fail -1 = fail ; ¬fail
We represent in TAB. IV the way an oposite event ¬ǫ is computed with respect to an event ǫ.

Complex Event (ǫ)

Opposite Event (¬ǫ)

(sensor ∼ value) (sensor ∼ value) ǫ 1 ∧ ǫ 2 ¬ǫ 1 ∨ ¬ǫ 2 ǫ 1 ∨ ǫ 2 ¬ǫ 1 ∧ ¬ǫ 2 ǫ 1 ; ǫ 2 ¬ǫ 1 ∧ ¬ǫ 2 within(n, ǫ 1 ) ¬ǫ 1

Table IV COMPLEX EVENTS (ǫ) & OPPOSITES (¬ǫ)

B. M 2 : Rewinding a Business Process

The objective of this function is to restore a process as it was before the reception of the initial event ǫ. It intensively relies on the history model previously defined, identifying the actions to be undone and the encountered events.

Undoing actions. For each kind of action α, we present in TAB. II its inverse α -1 . Executing α -1 after α annihilates the introduced modification: exec(α -1 , exec(α, p)) = p. Considering a sequence of actions A, its inverse (denoted as A -1 ) is defined as the inverse of all actions contained by A, in reversed order. This approach is inspired by aspect unweaving techniques [START_REF] Klein | Aspect Model Unweaving[END_REF].

α α -1 adda(a)
dela(a) addr(a, a ′ ) delr(a, a ′ ) dela(a) adda(a) delr(a, a ′ ) addr(a, a ′ )

A = [α 1 , . . . , αn] A -1 = [α -1 n , . . . , α -1 1 ] Table V ACTIONS (α) & INVERSE (α -1 )
Function description. This operation is implemented in a rewind function. Based on a given process p, the associated history H and the intended event ǫ, this function computes a process p ′ (representing the business process p as it was before the reception of ǫ) and a list of complex events [ǫ i , . . . , ǫ j ] (representing all the events recognized between the receptions of ¬ǫ and ǫ). For clarity reasons, we decouple the computation of p ′ (using a restore function) from the identification of the encountered events (using an extract function). The definition of these functions, based on the formalization described in SEC. III is presented in FIG. 11. The objective of this operation is to identify in a sequence of events the ones related to the to-be-removed event (immediately or transitively), and consequently reject them all (as they are now irrelevant). We define a prune function to support this operation. Using as inputs the sequence of events computed by rewind (named History) and a sequence of events to be rejected (named Removed, and initially containing the to-be-removed event), this function produces a P runed sequence of events. According to our objectives, the P runed sequence contains events that are not related to the ones defined in Removed. Its definition is represented in FIG. 12 prune The objective of this operation is to perform process readaptation, i.e., to re-execute on the rewinded process the adaptations that still need to be present in the expected result (i.e., the adaptations triggered by the events identified by the prune function). This operation is described in a function named replay, presented in FIG. 13. Using a given process p ′ and a sequence of events [ǫ i , . . . , ǫ j ] as inputs, the function produces a process p r that implements the expected result of the undo process. The unadaptation function takes as inputs the business process p, the associated history H and the event to unadapt ǫ. Let (p ′ , E) be the result of rewind(p, H, ǫ), and pruned the result of prune(E, [ǫ]). The unadapted process p u is obtained as the result of replay(p, reverse(pruned)). We implemented the complete approach using the PRO-LOG language, to support its application on large examples 6 . Events are sent to the adaptation engine through the send_events([[sensor, value],...]) command. We consider here the scenario described in SEC. II, i.e., the reception of an errorneous status for the search service, followed by a CPU overload and a network slowdown.

rewind : P × History × CE → P × [CE] (p, H, ǫ) → (p ′ , [ǫ i , . . . , ǫ j ]) restore : P × History × CE → P (p, H, ǫ) → p ′ extract : History × CE → [CE] (H, ǫ) → [ǫ i , . . . , ǫ j ] restore(p, H, ǫ) =          H = ∅ ⇒ p H = [(ǫ, Aǫ)|H ′ ] ⇒ exec + (A -1 ǫ , p) H = [(ǫ ′ , A ǫ ′ )|H ′ ], ǫ), ǫ ′ = ǫ ⇒ restore(exec + (A -1 ǫ ′ , p), H ′ , ǫ) extract(H, ǫ) =      H = ∅ ∨ H = [(ǫ, Aǫ)|H ′ ] ⇒ ∅ H = [(ǫ ′ , A ǫ ′ )|H ′ ], ǫ), ǫ ′ = ǫ ⇒ [ǫ ′ |extract(H ′ , ǫ)] rewind(p, H, ǫ) = ( restore(p, H, ǫ), extract(H, ǫ) )
: [CE] × [CE] → [CE] (Hist, Removed) → P runed prune(H, R) =          H = ∅ ⇒ ∅ H = [ǫ|H ′ ] ∧ ∃ǫ ′ ∈ R, ǫ ∈ ǫ ′ ⇒ prune(H ′ , [ǫ|R]) H = [ǫ|H ′ ] ∧ ∄ǫ ′ ∈ R, ǫ ∈ ǫ ′ ⇒ [ǫ|prune(H ′ , R)]

?-send_events([[search_status, error], ...]).

The immediate advantage of our approach is to relieve the user from handling the unadaptation logic. In this example, the recognition of the ¬fail CE is fully automated, based on the value received through the associated sensor. The proposed unadaptation function properly handles this situation, and yields the expected business process.

VI. RELATED WORK

As stated before, dynamic adaptation has been a widely studied topic [START_REF] Cheng | Engineering for Self-Adaptive Systems[END_REF]. For instance, the MUSIC middleware [START_REF] Rouvoy | MUSIC: Middleware Support for Self-Adaptation in Ubiquitous and Service-Oriented Environments[END_REF] is defined to support component assembly self-adaptation. Event-based AOP (EAOP) is a framework that intends to express aspects in terms of events that arrive during execution [START_REF] Douence | A Formal Definition of Crosscuts[END_REF]. They even detect sequences of events, and relate them using event patterns at run-time. However, these approaches for adaptation are only one way, and they never consider undoing their changes.

In [START_REF] Tigli | WComp Middleware for Ubiquitous Computing: Aspects and Composite Event-based Web Services[END_REF], the authors present an aspect-oriented approach called WComp, a lightweight component-based middleware to design composite Web services. They propose an aspectoriented approach called Aspect of Assembly (AA) to create a composition for adaptation. When a change in the context is detected, they create a simulation by applying all the AAs (implementing remaining adaptation rules) to the initial state and compare it to the actual state. Then they apply the differences by using pure elementary modifications (add, remove, link, unlink). Our approach is semantically different as they focus on one kind of event (i.e., service apparition or vanishing) where we use the definition of CE to drive the (un)adaptation process.

In [START_REF] Da Silva | Towards Automated Inconsistency Handling in Design Models[END_REF], the authors propose to automate the handling of model inconsistencies through the discovery of repair plans, implemented as action sequences. They demonstrate that action-based approaches support an efficient implementation of model manipulation. FScript [START_REF] Léger | Reliable Dynamic Reconfigurations in a Reflective Component Model[END_REF] uses actions to support automated rollback (i.e., only for reconfiguration failure). In [START_REF] Klein | Aspect Model Unweaving[END_REF], the authors propose an action-based approach to support the unweaving of model aspects. The underlying principles are close to the ones used in this proposal, i.e., the execution of inverted action sequences and the replay of remaining adaptations (in this case, aspect application). However, our approach is different as we aim to automatically support the undoing of adaptations (without human intervention) where aspect model unweaving is a humandriven process. Moreover, the reification of relations between CEs helps us to smartly prune the encountered events and then implement an accurate replay.

In [START_REF] Bernal | Dynamic Context-aware Business Process: a Rule-based Approach Supported by Pattern Identification[END_REF], the authors present their approach for creating dynamic business processes using ECA (Event-Condition-Action) rules. They decompose the original business process structure in a set of rules. This rules are then used to create a Control Flow Checking table, where the flow of the process is defined. To adapt the process they create a new modified Control Flow Checking table, which they compare to the original. The differences between both tables are then used to create new rules that will allow the new modifications to be considered during the BP execution. To undo the adaptation, the new rules could just be removed, or restored to their previous state. However, even though the goal of adaptation is accomplished, the introduction and removal of rules require external interaction, (i.e. somehow the rules need to be created and fed into the system).

VII. CONCLUSIONS AND FUTURE WORK

In this paper we have argued that BP unadaptation is an important issue that should not be obviated, since naive approaches could end up with corrupted processes. We presented our approach to solve this issue with a fourstep procedure: recognize, rewind, prune and replay. The proposed approach is generic since the detection of the undo trigger event is defined in terms of state-of-the-art CEP engines, and uses boolean logic to associate an event to its non-event. Furthermore, our approach is also automated. Indeed the way BPs are unadapted is fully delegated to an automatic engine. Thanks to these two advantages, we set the user free from having to deal with the unadaptation logic. Moreover, our four-step approach warranties that the final process will be as expected: the approach considers not only the original adaptation, but also the subsequent adaptations that were related to it, and unadapts them as well, while leaving the unrelated adaptations untouched. The obtained result is a cleanly unadapted process, "as if the original adaptation had never happened". We validated our approach by formalizing each step of the unadaptation procedure and implemented the logic approach with PROLOG.

As for future work, we are currently enhancing the proposed approach to support user-driven customization of the automatically generated unadaptation trigger events: these generated events could indeed be optimized according to business knowledge. We are also working in developing an instance level process (un)adaptation method. Since each process instance has a context of its own, adapting or unadapting cannot always be performed. To correctly achieve (un)adaptation at the instance level, we need to consider also the step of the process that the instance is running and then adapt its process only when referring to future steps. Also, a particular attention must be paid when loops are involved in the instance, since in this case a previous step is also a future step, and these adaptations need to be managed carefully.

Figure 1 .

 1 Figure 1. Illustrative business process (initial)

Figure 2 .

 2 Figure 2. Consulting a backup when the search service is unavailable

Figure 3 .

 3 Figure 3. Monitoring the process to identify abnormal CPU consumption

Figure 4 .

 4 Figure 4. Introducing a cache to deal with lower bandwidth

Figure 5 .

 5 Figure 5. Undoing adaptation (¬fail): a not-so-easy task

Figure 6 .

 6 Figure 6. Overview of the adaptation process

Figure 7 .

 7 Figure 7. A simple business process, p ∈ P.

Figure 8 .

 8 Figure 8. Applying an adaptation (ǫ, ϕ) to p

1 =Figure 9 .

 19 Figure 9. Doing adaptation: p becomes p 123 .

Figure 10 .

 10 Figure 10. Undoing adaptation: p 123 becomes p 2

Figure 11 .

 11 Figure 11. Description of the rewind function

Figure 12 .

 12 Figure 12. Description of the prune function

Figure 13 .

 13 Figure 13. Description of the replay function

Table I

 I EVENT-DRIVEN ADAPTATION DECISIONS

Intuitively, if fail is defined as search_status = ok, ¬fail is defined as search_status = ok

Syntactically talking, the removal of the backup activity also creates a hole between the cache validity test and the cache writing activity, leading to a corrupted process.

We assimilate a sequence to a totally ordered set (i.e., a list), and use the notation and functions associated to lists usually encountered in the logic programming literature[START_REF] O'keefe | The craft of Prolog[END_REF]. A list is defined as a head h followed by a tail list T , and is denoted as l = [h|T ]. The empty list is ∅.

http://esper.codehaus.org/

We assume that a given complex event ǫ will trigger only one adaptation: ∀(ǫ, ϕ) ∈ A, ∄(ǫ ′ , ϕ ′ ), ǫ = ǫ ′ . According to state-of-the-art engines, we also assume that an adaptation is only triggered once.

ACKNOWLEDGEMENTS

This work was supported by the French Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the Contrat de Projets Etat Region (CPER) 2007-2013.

The undoing is triggered with the recognition of a ¬fail event, i.e., the reception of a (search_status, ok) event. It first triggers the rewind of the process to its original state. Then, the pruning function removes the cache event as it depends on fail. Finally, the replay is triggered, and the expected result (depicted in FIG. 5(b)) is obtained as output.


Alexis Benichoux

Prasad Sudhakar

Rémi Gribonval

Well-posedness of the frequency permutation problem in sparse filter estimation with ℓ p minimization

A well-known issue in blind convolutive source separation is that the sources and filters are at best identifiable up to an arbitrary scaling and permutation at each frequency bin. We propose to exploit the sparsity of the filters as a consistency measure for correcting such permutations. We show that the permutation is well-posed, up to a global permutation, under appropriate sparsity hypotheses on the filters. A greedy combinatorial algorithm is proposed for permutation recovery. Its empirical performance shows that the time-domain sparsity of the filters allows to recover permutations much beyond theoretical predictions.

I. CONTEXT

Let xi[t] be M mixtures of N source signals sj [t], resulting from the convolution with a filter aij[t] of length L such that:

xi[t] = N j=1 (aij ⋆ sj)[t], 1 ≤ i ≤ M.
(

) 1
We consider the problem of estimating the matrix of filters A = (ai,j) from the mixtures, without knowledge about the sources. A standard approach is to formulate the problem in the Fourier domain: one needs to estimate aij [ω]. This suffers from a well known ambiguity : without further assumption on either aij [t] or sj[t], one can at best hope to find an estimation à = (ãi,j) where for every frequency ω ≤ L we have

ãi,j[ω] = λj[ω]a iσω (j) [ω], (2)
with λj a scaling ambiguity and σω a permutation ambiguity. Several methods [START_REF] Pedersen | A survey of convolutive blind source separation methods[END_REF] to exploit properties of either S or A solve these. Our focus here is on the use of the sparsity of A in the time domain to find σ1 . . . σL ∈ SN , assuming the scaling λ ∈ C L is solved.

Of course we can at best hope to obtain uniqueness up to a global permutation of the columns of A. We exploit [2, Th.6.2a] the ℓp quasi-norm

A p p := ijt |aij[t]| p , 0 ≤ p ≤ 1
, as a consistency measure to solve the permutations.

II. THEORETICAL GUARANTEES

If the filters aij have disjoint supports, without further sparsity hypothesis, we show that permutations can only increase the lp norm.

Theorem 1 ( [START_REF] Sudhakar | Well-posedness of the frequency permutation problem in sparse filter estimation with ℓp minimization[END_REF]): Let Γij ⊂ {1, . . . , L} be the time domain support of aij. Suppose that for all i and j1 = j2 we have Γi,j 1 ∩ Γi,j 2 = ∅. Then for 0 ≤ p ≤ 1 we have A p p ≤ Ã p p . To obtain uniqueness guarantees, we now introduce assumptions on the sparsity k := maxi,j ai,j 0. We measure the permutation error for 0 ≤ p ≤ 1 with

∆p := min π∈S N max i,j a iπ(j) [ω] -ãij[ω] 1≤ω≤L p . (3)
For sparse filters, the true filters are the sparsest among all filters incurring sufficiently few permutations. The skilled reader will rightly sense the role of the ℓ0 Fourier-Dirac uncertainty principle [START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of bases[END_REF] in the following result.

This work was supported by the EU FET-Open project FP7-ICT-225913-SMALL Theorem 2 ( [START_REF] Sudhakar | Well-posedness of the frequency permutation problem in sparse filter estimation with ℓp minimization[END_REF]):

(i) If 1 ≤ ∆0 ≤ L/2k, then A 0 ≤ Ã 0. (ii) If A 0 ≥ Ã 0, then ∆0 ≥ L 2k .
For prime L, the results hold with L + 1 -2k instead of L 2k . The equality case implies that the filters are pathologically related to Dirac combs of step L 2k .

III. A COMBINATORIAL ALGORITHM

We perform minimisation iteratively by considering one frequency bin 1 ≤ ω ≤ L 2 at a time and choosing a permutation (in a combinatorial fashion) that minimises the ℓ p norm locally, while keeping the other bins fixed. To preserve aij = āij , the same permutation is applied on the corresponding mirror frequency L + 1ω. This iterative procedure is repeated over all frequency bins till the ℓ p norms of the filters converges.

We conservatively consider the filters as successfully recovered when the SNR of the permutation corrected time-domain filters exceeds 200dB. The guarantees of Theorem 2 are delimited by the black line in general, and the white line if L is prime. We observe a phase transition close to the prime length case.

Fig. 1

 1 shows the phase transition diagram for filter recovery using the proposed algorithm for the number of sources N = 4, number of channels M = 3, length of individual filters L = 1024 and p = 1. White indicates guaranteed success, black is guaranteed failure.

Fig. 1 .

 1 Fig. 1. Phase transition diagram for filter recovery by ℓ 1 minimisation.


A Carneiro Viana

N Mitton

L Schmidt

M Vecchio

A k-layer self-organizing structure for product management in stock-based networks

Traditional Distributed Hash Tables (DHT) abstraction distributes data items among peer nodes on a structured overlay network in storage-intensive applications. The question is whether DHT-based systems can provide reliable and scalable storage services also in stock-oriented applications, where logistics, traceability and fault-tolerance are the main requirements. In this paper a novel approach to self-organizing stock management networks, based on a two-level DHT mechanism is proposed and analyzed. Some preliminary results suggest that our method can reduce network traffic and achieve high data availability also in such storage and management networks.

I. INTRODUCTION

Nowadays, trade industries are growing up and need more and more the support of technology for managing their goods, for logistic, inventories and traceability concerns. Such ordinary applications need the support of new technologies to fit the scalability of companies. More and more servers and databases are deployed to store information and connected in networks to become accessible from every place. These databases are now supplied through the reading of bar-codes or RFID tags hold by objects. Shelves equipped by readers even consist in database themselves and can be connected to database network. Even mobile RFID readers can be directly connected to the network and transfers useful data.

Although the networking architecture might be general, it is desirable that the communication infrastructure takes application requirements into account. Here, we narrow our focus to applications of stock management with a large amount of products to be controlled and managed, a general communication pattern with entities in different geographic sites communicating, and a need for limited communication overhead and reliable data. The network should be standard compliant 1 able to be connected to an EPC 2 network (e.g. which respects the EPC standards) and support requests issued from an EPC ALE 3 engine in order to fit most of companies' applications.

The kind of networks we are dealing with is composed of heterogeneous entities. In order to identify products to be controlled, they are equipped with unique identifiers labels (RFID, bar code, etc.). To perform the identification, traceability and inventory actions, the network is composed of database servers, routers, and two kinds of readers: either fixed (as a This work has been partially supported by the FP7 European project ASPIRE (http://fp7-aspire.eu) and the regional project ICOM. 1 RFID relative standards are established by EPC Global. 2 http://www.epcglobalinc.org/ 3 http://www.epcglobalinc.org/standards/ale smart shelf) or mobile. Mobile readers can read and store data without being connected to the network, and so transfer data when connected. In this case, routers or fixed readers act as gateways towards databases. The first motivation is the scalability and reliability of such a network. Indeed, the number of entities can increase heavily and sets the need of large scale communications without overloading the network. Data have to be duplicated for ensuring reliability but in a smart way in order to avoid memory overhead and facilitate at the same time the query routing when information needs to be retrieved from them. Secondly, the different characteristics of stock management requests, coupled with the need of scalability, require a specific network infrastructure management. Different granularities for the different diffusion primitives are needed, such as broadcast ("Count number of this specific product"), k-cast ("Is there a quantity x of this product") or anycast ("Give me the price of this product"). At last, due to the mobility of some readers, the structure of the network has to organize itself and adapt at every modification in a transparent and local way. Wireless readers may appear/disappear, generating topology changes. The network must be able to self-organize and self-configure.

In this paper, we propose SENSATIONa reliable k-level structure for distributed redundant memory placement. This structure allows to smartly store data and fast request to be processed by limiting bandwidth overhead. One level is dedicated to each single object kind (e.g. sportswear, shoes, etc) or location according to the application needs and granularities (e.g. Paris, France or Europe). This unique structure allows performing different operations: (i) distributed storing to allow scalability by reducing memory overhead, (ii) data replication to ensure data reliability and (iii) efficient request management for answering requests in a smart scalable way which limits traffic and flooding overhead. This is achieved through the use of two distributed hash tables. The first one allows to reach the correct level, i.e. the level corresponding to the specific object or location targeted by the request while the second one allows to reach the proper correspondent in this layer. For instance, if the request is "What is the price of a blue trouser ?", the first DHT directs the request towards the layer responsible for trousers while the second one then directs the request towards a node aware of the price of blue trousers. Results show that for a low replication level (3), only 25% of data are lost when more than 70% of servers fail. The remaining of this paper is organized as follows. Section II describes the case studies we are focusing on in order to illustrate more easily the behavior of SENSATION. Section III sets background works useful for the understanding of SENSATION. Section IV describes the relative works useful in the construction of SENSATIONwhile Section V explains in details SENSATION. Section VI presents SENSATIONperformance results. At last Section VII concludes that work by prospecting some future works.

II. CASE STUDY

Our case study is represented by a wide area stock management application. It can be, for instance, a distributor with several warehouses spread all over one or more countries; in each warehouse the servers and the databases are supposed to be connected, thus forming a network. Such an organization may need several tools at different levels.

In order to have a glimpse on these different tools, let us firstly consider an user located in one warehouse: he may need to draw an inventory (i) of the whole set of all warehouses, or (ii) of a particular warehouse located in a specific area, or evenly (iii) of products laying in a small area of a specific warehouse. Moreover, the inventory may target either (i) a kind of product (e.g. "inventory of every trouser"), or (ii) products in a specific place (e.g. "inventory of everything located in Paris"), or (iii) even both (e.g. "inventory of every trouser located in Paris"). On its side, the application has to handle different granularity requests. Finally, requests can be of different natures, possibly requiring different mechanisms for their diffusion: consider, for instance, (i) broadcast queries ("how many items of the specific product do I have?"), (ii) kcast queries ("do I have at least k items of this product?"), and (iii) anycast queries ("give me the price of this product").

With a plain database network infrastructure, in all the abovementioned situations, every reader and/or database has to be queried (i.e. the network is flooded). Upon answers, some filters may be applied and/or data are aggregated. This normally introduces a non-negligible latency and causes a network overload, which actually is not necessary. Indeed, (i) for broadcast queries, only databases storing information about the articles being enumerated should be contacted; (ii) a k-cast query should be delivered as soon as k products have been found; finally, (iii) an unicast query may be answered after having contacted only one server. Essentially, these are the features we are to give SENSATION, in order to ensure scalability and high quality of service.

A second, equally important, concern in this case study is enabling a tunable fault-tolerance level. In order to add some reliability to data, it is necessary to include a degree of redundancy (i.e. provide one or more alternate servers in which to store the same data). The main issues here are to decide where, how and how many times to replicate data. Indeed, in most cases, data are simply replicated in one or more backup servers, which are eventually used in the case that the primary server is experimenting a failure. On the other hand, SENSATION replicates efficiently data and takes advantage of this replication by routing requests towards the closest server storing the information thus decreasing the routing overhead.

III. PRELIMINARIES

The spontaneity of self-organizing networks makes the provision of a scalable and efficient location service in their context a non-trivial problem. Since a dynamic association between the identification and the location of a node is needed, a mechanism to manage this association has to be provided. Furthermore, this latter should minimize the control message overhead for routing and location discovery. An efficient solution is to perform an indirect routing [START_REF] Hubaux | Towards self-organized mobile ad hoc networks: the terminodes project[END_REF][3] [START_REF] Xue | A scalable location management scheme in mobile ad-hoc networks[END_REF].

A routing operation is referred as indirect when it is performed in two steps: (i) first the target node is located and then (ii) a directed communication with the target is performed. The indirect-routing allows the network to decouple the location information of a node from the location itself. With this approach, the information can be totally distributed, which is important for achieving scalability in large scale networks.

Distributed Hash Tables (DHT) represent the basis of indirect routing and provides a general mapping between any information and a location by using hash functions. A DHT uses a virtual addressing space V, which is partitioned and assigned to different nodes in the network. As an example, consider an addressing space V = [0, 30[ is shared among 3 nodes i, j, k such that node i gets the partition q(i) = [20, 30[, node j gets q(j) = [10, 20[ and node k gets q(k) = [0, 10[.

Each information is hashed into a key (hash(v) = key v ∈ V) in V and then stored in the node containing the hash key in its partition. Yet, in Fig. 1(a), node k has a content C to register. By applying hash(C) = 25 it gets the key of C, which is within the partition of node i. So, node k registers C in node i. Usually, node k also stores the location of C (i.e. it registers its own address). Later, when a node j is looking for content C, it applies the same hash function, obtaining the same result (i.e. hash(C) = 25), thus knowing that it has to contact node i. (cf. Fig. 1(b)). Upon the request, node i answers node j with the information previously registered. (Fig. 1(c)). If this information is the location of C, then node j gets the address of node k and can then directly communicate with k. When implementing any DHT mechanism some events related to the creation and management of the DHT-based structure have to be considered. At the following, we discuss how such events are performed.

Node Arrival: When a node u enters the network, it has to join the DHT-based structure. To do so, u retrieves the way to contact a node already in the structure, which is then used as an entry-point to the DHT-based structure. Then, a partition in the logical address space is assigned to u. Routing information is then updated among nodes to reflect the presence of u in the structure. Finally, u retrieves all the (key, value) pairs under its responsibility from the node that previously stored them. Node Failure: When a node fails, its stored data is lost unless the DHT is using a replication mechanism to keep multiple copies on different nodes. Some DHTs follow the simpler softstate approach which does not guarantee persistence of data. Data items are pruned from the DHT unless the application refreshes them periodically. Therefore, a node failure leads to a temporary loss of application data until the data is refreshed. Node Departure: A node departure normally does not represent a critical event in DHT implementations. This is due to the fact that, this event often explores notification primitives to be used by nodes before leaving the infrastructure. This allows other nodes to copy application data from the leaving node, to recover the left logical address space, and to immediately update their routing information.

IV. RELATED WORKS

We briefly discuss here the works most related to SENSA-TION. For more details, we invite the reader to check the referred papers.

A. Content Addressable Network (CAN)

In [START_REF] Ratnasamy | A scalable content-addressable network[END_REF] the authors introduced the notion of multidimensional structured overlays and showed its improved routing efficiency with respect to the classical one-dimensional counterpart. In particular, they proved that the average path length in a system with n nodes and d dimensions scales as

O(d(n 1 d )).

Nodes arrival and partition assignment:

In CAN, an identifier in the form [x, y, z] (if d = 3) is assigned to each data item. Each node is said to own a zone. CAN ensures that the entire space is divided into non-overlapping zones. Because a key represents a point P in the identifier space, (key, value) pairs are stored on the node owning the zone which covers P . A new node n joining a CAN system sends a join message to node v, which is the current node responsible for the zone where n lays. Then, v splits its zone in half and assigns one half to n (cf. Fig. 2(b)). Finally, v transfers to n the keys lying in the zone it has become responsible for. Routing over the CAN overlay: For routing purposes, a CAN node stores information only about its immediate neighbors. Two nodes in a d-dimensional space are considered neighbors if their coordinates overlap in one dimension and are adjacent to each other in d-1 dimension (e.g. neighbors N 1 and N 6 in Fig. 2(a)). If the node does not own the zone of the destination, it forwards the message to its neighbor with the coordinates closest to the destination (Fig. 2(a)). In a d-dimensional space equally partitioned into x zones, this procedure results in an average of O((d/4)(x Node failure: The zones of failing nodes must be taken over by alive nodes to maintain a valid partitioning of the identifier space. A node detects the failure of a neighbor when it ceases to send update messages. Through an efficient message advertising, the neighboring node with the smallest zone volume merges the deserted zone with its own zone if possible. Alternatively, it temporarily manages both zones.

Node departure: When a node l deliberately leaves a CAN system, it notifies a neighbor n whose zone can be merged with l ′ s zone. If no such neighbor exists, l chooses the neighbor with the smallest zone volume. It then copies the contents of its hash table to the selected node so this data remains available. SENSATION and CAN: uses CAN as a framework to distribute the responsibilities area of servers in a geographical way. CAN allows SENSATION to designate the contact and entry nodes in every layer (so for each kind of products) in an easy and homogeneous way. CAN has been chosen rather than other DHT scheme because of its low complexity and geographic features that it provides to the data distribution.

B. Tribe

In [START_REF] Viana | Indirect routing using distributed location information[END_REF], the authors proposed the Tribe protocol, specifically designed for large scale self-organizing networks. Tribe creates a topology that is a logical network representation and describes the relative location of nodes according to their neighborhood in the physical network. Nodes arrival and partition assignment: When a node arrives in the network, it receives a control region which will serve for two purposes: node identification and routing. A new node u in the network receives the control region from its neighbors which control region is the largest. This latter one gives the highest half part of its region to the new node v and becomes its parent node. Tribe thus builds a tree as illustrated by links between nodes on Fig. 3. Routing in the Tribe structure: The routing operation needs to be performed to reach a node responsible for a given key returned by the hash function, i.e. either when a node needs to register an information or to find it. Let p(u) = [p ⊖ u , p ⊕ u [ be the control region of node u. When node u entered the network, it has been assigned the virtual space p init (u) = [p ⊖ u , p ⊕ uinit [ where p ⊕ u ≤ p ⊕ uinit since from then, u may have shared its initial space with its children. When node u needs to reach the node responsible for a key key ∈ V, it proceeds as follows.

• If key ∈ p(u), u can answer the request.

• If key / ∈ p init (u), then forwards to its parent.

• If p ⊕ u < key ≤ p ⊕ uinit , then forwards to its child v such that key ∈ p init (v).
Every node reiterates this process till reaching the node responsible for the key. Node failure and departure: Similar to CAN, the zones of failing or leaving nodes are taken over by alive nodes, i.e. the parents of the missing node in the tree. In the case of failures, the keys stored by the failed node are lost. Discontinuity between the control region of parents and missing nodes may happen, forcing parents temporarily manage multiple zones. SENSATION and Tribe: Tribe is the DHT used by SENSA-TION in every single layer to organize data concerning a kind of objects. Tribe has been chosen as framework rather than any other DHT schemes because of its tree structure which is the most appropriate structure to perform the kind of operations provided by SENSATION (unicast, brodacast, anycast, k-cast).

C. SOLIST

In [START_REF] Busnel | Solist: A lightweight multioverlay structure for wireless sensor networks[END_REF] the authors presented the SOLIST structured overlay, which provides an efficient * -cast suite for wireless sensor networks. SOLIST identifies a set of basic functionalities widely used in distributed applications and propose an efficient implementation of this suite in a multi-layer structured network. The basic idea is to assign a type to each sensor and to a layer. A layer is composed by all sensors of the same type. Fig. 4 shows a SOLIST multi-layer projection, composed by a common basic layer and a group of overlay layers. Node arrival and routing: Each node in SOLIST belongs to the common basic layer and is assigned to a virtual coordinate in a relative Cartesian space. Messages in the basic layer are routed using a lightweight geographic routing protocol. After joining the basic layer, a node has to be included in an overlay t. For this (the same is performed to query about type t), a given sensor has to contact at least one node belonging to the corresponding layer t. To find out such a node, SOLIST proceeds in two steps. The first step consists in contacting an entry-point for the asked layer. The entry-point will not necessarily belong to layer t but it is aware of the closest sensor belonging to it. The second step consists in reaching the contact node belonging to the layer t. This two-steps contact phase allows reaching with limited energy, bandwidth, and time costs, the closest node belonging to the asked layer. In order to identify the entry-points and the contact nodes, SOLIST uses hash functions. The joint of nodes and routing in the overlay follow the CAN structure previously explained. SENSATION and SOLIST: SOLIST is a general framework that has inspired the design of SENSATION. They although differ since SOLIST has been designed for wireless networks and thus is constraint by wireless links features and neighborhood definitions. SENSATION considers wired Internet networks and thus assumes that there exists an IP underlying routing allowing to easily reach every server. Yet, although applying the same basic principles as SOLIST, SENSATION re-defines every operation to fit other assumptions and to be compliant to business needs and requirements.

V. SENSATION

A. Solution overview

SENSATION provides a self-organizing structure to manage data in a wired stock oriented network, distributed over several geographic sites. It aims at answering stock management requests which may concern either a product, a family of products, or even a geographical site.

In SENSATION, a type is assigned to each data item in a SOLIST-like fashion [START_REF] Busnel | Solist: A lightweight multioverlay structure for wireless sensor networks[END_REF]. A type may represent a product kind (i.e., trousers) or a location (i.e., Warehouse A), since it is addressed without distinction. Each type is associated to a layer. To address requests concerning a product kind or a geographical area, requests will be sent to the corresponding set of layers. As an example let us consider to have a sport articles inventory (a city inventory), composed by bikes and rackets (two different products, i.e. layers): if a request aims at retrieving such an inventory, then independent requests are sent to both racket and bike layers and the results are aggregated afterwards. Using SOLIST mechanisms, we can broadcast, kcast and unicast efficiently into these layers. Once a layer is reached, a Tribe structure is linking nodes. Each layer t is an overlay network composed by nodes and links. Nodes represent databases and servers sharing data items of type t. When a node n joins the overlay network of a layer t, a virtual space partition together with a set of neighboring nodes are assigned to n; the latter represents other nodes in t-layer which are connected to n. Note that since this is a logical network, links may not be direct in the physical underlying network. SENSATION uses Tribe [START_REF] Viana | Indirect routing using distributed location information[END_REF] to assign the space partition to nodes and to create links. In addition to the overlays and as in SOLIST, nodes also belong to a common basis space. SENSATION defines this space and assigns logical coordinates in this space to nodes, which allow their location (cf. Section V-B). We use the CAN protocol in this space in order to benefits the d-dimensional virtual space and to map it with geographical coordinates.

The structure is then used for three purposes: (i) Distributed storing: every node which has fresh data of a given type t, firstly retrieves the closest node managing that type t. Through this node, the Tribe t-layer is acceded and the node responsible for storing the searched data is updated. (ii) Replication: any level of replication can be imposed to SENSATION. Indeed, once the Tribe layer is reached, just applying different hash functions to the item ID to be stored would change the server responsible for the storing. (iii) Efficient request management: thanks to the use of several layers, a request will not be flooded in the network but directed to nodes concerned by the request, thus diminishing the latency and limiting the communication overhead. The first step consisting in reaching the proper layer allows the node selection; then, the use of Tribe within an overlay facilitates the request management. Indeed, the tree-like structure of Tribe is useful to aggregate counting requests in each level of the tree and to stop the request when enough nodes have been reached. We use Tribe instead of other tree base p2p system because of its lower complexity.

B. Data management structure

The SENSATION structure has to include all nodes of all sites of the network. Considering a national scale, sites represent the cities where a store is located. Thus, the lookup structure will be divided in NC cells, being each cell corresponding to a site.

In the following, a cell coordinate (X C , Y C ) is assigned to each cell (city), representing the relative position in the virtual coordinate system along the x and y dimensions. More in details, the cell located in the bottom left corner of the grid has (0, 0) coordinate, the next ones have coordinates equal to (1, 0) and (0, 1), along the x and y dimensions respectively, and so on. Then, each cell is logically divided into T square areas, where T is maximum number of types supported by the application and should be a perfect square number (cf. Fig. 5). Each area represents a virtual location in the cell, with type coordinate (X T , Y T ) within a cell; each location acts as an entry-point for a different type in the logical cell. Thus, type coordinates (X T , Y T ) in cells i and j represent entry-points for the same layer T . For the sake of simplicity in the following we will consider virtual grids divided into the same number of cells along the x and y dimensions. This assumption does not limit the applicability of the approach, since one can build a grid with some unused cells.

By construction, we have exactly T entry-points within each cell, one for each type managed by the application 4 . This means that, whenever an action has to be performed on an item of type t (insertion, lookup, etc.) a requesting node u has firstly to reach the t entry-point within the cell he belongs to. By contacting this entry-point node, u can reach the layer t; once in the layer, he can traverse the Tribe tree ending in the node which has actually stored the item. The critic point is how to share among nodes the virtual space represented by the entry-point set. We simply propose to share the entry-points set among the nodes in a cell, by using CAN. For this reason, at a steady state the nodes in a cell share the entry-points so as each of them is responsible of an non-overlapping partition of the DHT, being the DHT the entry-point set 5 . Like in CAN, we use a bi-dimensional congruential mapping function in order to determine the type-t entry-point in the (X C , Y C ) cell (ep

(XC ,YC ) t
), which is:

ep (X C ,Y C ) t = " Xep (X C ,Y C ) t , Y ep (X C ,Y C ) t " = " mod(t, d) + XC • d, - t d + YC • d « (1)
where d = √ T , t d is the integer division between t and d and mod(t, d) is the remainder after this division. When ep (XC ,YC ) t is computed, the request can be routed (using CAN) towards the requested entry-point. Once reached the right layer, Tribe is used to reach the node storing the item. Virtual coordinate assignment: to be inserted in the structure, nodes firstly needs coordinates, which are given by the user who arbitrarily assigns to each new node a unique geographic position in the grid. On the basis on the assigned site, a unique logic ID in the virtual system is generated as a bit sequence containing information about the virtual cell coordinates (X C , Y C ) and the relative position within the cell (X T , Y T ):

ID = |bin(XC , nbC)|bin(YC , nbC)|bin(XT , nbT )|bin(YT , nbT )|
where bin(x, n) is the binary integer representation of x over n bits, nbC

= ⌈log 2 (N C)⌉ 2 , nbT = ⌈log 2 (T )⌉ 2
and | represents a string concatenation. To better understand this translation from a virtual site into a unique address, consider a user plugs a new node to the network in the geographical coordinate (7, 11) of a grid of N C = 9 cells. If T = 16, the resulting virtual ID is 8-bits long: 2 bits being used for codifying each field. From Fig. 5, it is clear that coordinate (7, 11) belongs to cell (1, 2) and to square 3, 3 in that cell. Thus, ID = 01|10|11|11 (i.e. 01 being the binary representation of X , 10 the binary representation of Y C , and 11 the binary representation of X T and Y T , on 2 bits each). Adding a node: to join the structure, a node u has to (i) obtain a portion of the entry-point set in the common basis space (i.e. join CAN) and (ii) obtain a portion of the Tribe addressing space in all the layers corresponding to the types of objects it stores and has to register (i.e. join Tribe). Consider a node u wants to join SENSATION. The nearest CAN node v already in the structure has to give to u a portion of the entrypoints it is currently managing. Let us consider, for instance, that u receives an entry-points set P = 1, 2, 7, 8. This means that u will represent the entry-point for any request concerning types 1, 2, 7, 8 within the cell, so that u has also to join the same layers in Tribe. In other words, it has to obtain a portion of the Tribe addressing space in each of the mentioned layers. Adding items: when an item of type t has to be stored in the infrastructure, the node which is currently managing the entrypoint t is contacted by using CAN (note that this operation is purely local, in the sense that the responsible node of type t is local to the cell). Since this node is also registered in the Tribe t-layer, the request can be forwarded using Tribe. Notice that, when the right layer is reached, any level of replication of the data can be imposed, in order to increase the reliability. Just applying different hash functions to same item ID, in fact, would result in a different node managing the hashed ID (thus, the storing node). The only constrain in having a level of replication r is that the hash functions set r has to be known by all nodes. With this technique a tunable faulttolerance level can be introduced. Moreover, this technique lets the application further diminish the overhead cost introduced by Tribe. This aspect will be explained later on. Lookup phase: when a query has to be answered, firstly the responsible node of the requested type is contacted, by using CAN. This phase is common to the adding phase. Once in the right layer and according to the query, a different scheme is used. In particular, for unicast queries, the request is routed using Tribe until the node managing the requested hashed ID is reached. This node is the responsible of directly providing the answer to the asking user. When a replication level r is imposed, we know that actually the item (if it was added) was stored r times in the layer. For this reason, it is less expensive (from a latency and communication overhead point of view) computing the hash function r times and reaching the Tribe node at the minimum distance from the contact node.

C. Example

To conclude this section we provide an example. Let us assume that a node B wishes to draw an inventory of trousers using SENSATION. B has first to contact the closest entrypoint of the type "trousers". For this, by applying Eq. 1, B contacts ep t using CAN and gets the location of the nearest node C managing trousers (the contact node) (Fig. 6). Note that ep t knows node C since the latter has been registered at node ep t using the same Eq. 1. The counting request is then sent to C. Since C has previously joined the layer corresponding to trousers, it can forward the message to all nodes managing trousers that have previously registered in this layer. The counting request will be sent in broadcast mode in the overlay and the answer will contain the number of trousers in the entire network.

2(4) 1( 5) A different request may be to know whether a product exists. Node B simply contacts the closest entry-point for the asking type. If the entry-point returns a node ID then the existence is proved, otherwise the entry-point returns NOT FOUND. Finally, if a user wants to know whether there are at least k items of a given type, he contacts the closest entrypoint which communicates to the nearest contact node (node C). Then, the user sends a k = 10-cast request to C; node C decreases k by the number of items of the given type it is currently managing and forwards the request to the next node in Tribe overlay; the operation is repeated until k = 0, or all nodes in the layer are contacted.

1(6) 1(8) 1(7) 2(5) 2(6) 2(8) 2(7) B 2 (3)

VI. SIMULATION

Exhaustive performance analysis is performed to analyze the routing cost of requests, the robustness at various replication levels, and the distribution of the information in SENSATION. Scenario: a square universe is divided into 64 cells of equal size and 10 nodes are randomly placed in each cell (it follows that 640 nodes are inserted). Items are then added in the following way: 100 items of type i are inserted from randomly extracted nodes, where i ∈ [START_REF] Busnel | Solist: A lightweight multioverlay structure for wireless sensor networks[END_REF]400]. Each experiment was performed 30 times and results were averaged. Overhead: after the registration phase, each registered item is queried by a node. This action (i.e. denoted as unicast query) in a classical database network should not have any cost, since the information is stored in the local node. On the other side, using SENSATION, the entry-point of the requested type has to be contacted (routing with CAN). Fig. 8 shows the overhead introduced by CAN for reaching the requested entry-points. In the shown histogram, it can be easily seen that more than 35% of the entry-points can be contacted with a routing cost of 1 hop. Note that this overhead is independent on the replication level introduced in Tribe layers.

Dealing with node failures: here, a percentage of failing nodes varying within 0 and 100% is considered. Note that, when a node is experimenting a failure, its registered items are unavailable (it is a database failure), while the routing in the layers is still possible. It means that during the failure the information is not available, but CAN and Tribe can react to the failure and auto-organize again. Fig. 7(a) shows, for different replication levels and loss regimes, the percentage of lost information (this is equivalent of showing the failure rate of unicast queries). It can be noticed that, with a level of replication equal to 1 the loss of information is linear. Indeed, the information is uniformly distributed as the number of failures. Moreover, as expected, increasing the level of replication in the Tribe layers increases the reliability of SENSATION. With a low replication level equal to 2 and even having 50% of failing nodes, only 25% of data are lost. This same amount of losses is even achieved when 70% of nodes are down with a replication level equal to 3. In addition, it is worth noting that this reflects the worst scenario since in these simulations, failures appear randomly while in realistic scenario, when a node fails, its closest nodes are more likely to fail rather than other ones in the network. Since data are spread randomly, in realistic scenario, data losses will indeed be less numerous. Information about an item is lost if and only if the k nodes in which the item was stored are simultaneously experimenting a failure; otherwise, after the re-organization the item is registered again. Lost are only temporary. Unfortunately, this behavior is not to be expected in broadcast queries. Indeed, a broadcast query, in fact, can be correctly served (i.e. produce the right answer) if and only if all the items of the requested type are present in any of the k nodes in which they were registered. Thus, just the disappearing of an item of the given type (the item on which the unicast query is failing) produces a of the broadcast query. Nevertheless, as shown by Fig. 7(c), SENSATION well resists to these failures.

VII. CONCLUSION

We have proposed SENSATION, a new self-organizing stock management structure, allowing data replication, distributed storing, and requests management. These features help in the distributed management of new storing warehouse management, which tends to increase in scale and to be more and more interconnected. Results show that SENSATION is effective in providing reliability and scalability for different replication levels and loss regimes. Future works would include a detailed study on the cost of replication towards the gain in reliability. In addition, some real implementations and tests should be performed to complete the full analysis.

Fig. 1 .

 1 Fig. 1. (a) Node k stores content C, and registers information about C on node i which is its rendezvous node. (b) Lookup phase of node j to contact the rendezvous node of C. (c) Lookup answer with information about C.

1 d

 1 )) routing steps. This expresses that increasing the number of dimensions significantly reduces the average route length. (a) Route from node N 1 to a key K with coordinates (x, y) in a two-dimensional CAN topology. Neighbor set of N 1 : {N 2, N 6, N 5}. (b) New node N 7 arrives in N 1's zone. N 1 shares its with N 7. Updated neighbor set of N 1 : {N 7, N 2, N 6, N 5}.

Fig. 2 .

 2 Fig. 2. CAN mechanisms illustration.

Fig. 3 .

 3 Fig. 3. Tribe virtual space sharing. (a) node A is alone and responsible for the whole virtual space V = [0, 30[. (b) Node B pops up and gets half of A partition. (c) Node C appears, A gives again half of its partition. (d) Node D arrives, B shares its partition since it has a larger partition than node A.

Fig. 4 .

 4 Fig. 4. Projection of 3 groups of nodes ( , and •) into three layers.

Fig. 5 .

 5 Fig. 5. Coordinate assignment to a node.

Fig. 6 .

 6 Fig. 6. Node B retrieving the nearest node of LIGH-trousers-LAYER.

  (a) Percentage of lost information. (b) Successful unicast queries. (c) Percentage of failing broadcast queries.

Fig. 7 .

 7 Fig. 7. Performance of SENSATION varying the replication level in Tribe and the percentage of failing servers.

  Request performance: fig. 7(b) plots the percentage of successful unicast queries, at different replication levels and loss regimes. Results show that unicast queries are pretty well managed by SENSATION with a sufficiently low order of replication and even at relatively high loss regime. This has

Fig. 8 .

 8 Fig. 8. Overhead in CAN.

Note that there may be less than T entry points. If a position is empty, the closest server handles the role of the entry point for this empty position.

This is one of the main differences between SOLIST and SENSATION.