Eddy Caron

Florent Chuffart

Anissa Lamani

Franck Petit

Optimization in a Self-Stabilizing Service Discovery Framework for Large Scale Systems

Ability to find and get services is a key requirement in the development of large-scale distributed systems. We consider dynamic and unstable environments, namely Peer-to-Peer (P2P) systems. In previous work, we designed a service discovery solution called Distributed Lexicographic Placement Table (DLPT), based on a hierarchical overlay structure. A self-stabilizing version was given using the Propagation of Information with Feedback (PIF) paradigm. In this paper, we introduce the self-stabilizing COPIF (for Collaborative PIF) scheme. An algorithm is provided with its correctness proof. We use this approach to improve a distributed P2P framework designed for the services discovery. Significantly efficient experimental results are presented.

Introduction

, mainly to handle range queries, automatic completion of partial search strings, and to extend to multi-attribute queries.

Although fault-tolerance is a mandatory feature of systems targeted for large scale platforms (to avoid data loss and to ensure proper routing), tree-based distributed structures, including tries, offer only a poor robustness in dynamic environment. The crash of one or more nodes may lead to the loss of stored objects, and may split the tree into several subtrees.

The concept of self-stabilization [16] is a general technique to design distributed systems that can handle arbitrary transient faults. A self-stabilizing system, regardless of the initial state of the processes and the initial messages in the links, is guaranteed to converge to the intended behavior in finite time.

In [10], a self-stabilizing message passing protocol to maintain prefix trees over practical P2P networks is introduced. The protocol is based on self-stabilizing PIF (Propagation of Information with Feedback) waves that are used to evaluate the tree maintenance progression. The scheme of PIF can be informally described as follows: a node, called initiator, initiates a PIF wave by broadcasting a message m into the network. Each non-initiator node acknowledges to the initiator the receipt of m. The wave terminates when the root has received an acknowledgment from all other nodes. In arbitrary distributed systems, any node may need to initiate a PIF wave. Thus, any node can be the initiator of a PIF wave and several PIF protocols may run concurrently (in that case, every node maintains locally a data structure per initiator).

, it merges waves initiated at different points in the network. In the worst case where only

one PIF wave runs at a time, our scheme does not slow down the normal progression of the wave. Finally, we present experimental results showing the efficiency of our scheme use in a large scale P2P tree-based overlay designed for the services discovery.

Roadmap. The related works are presented in Section 2. Section 3 provides the conceptual and computational models of our framework. In Section 4, we present and prove the correctness of our self-stabilizing collaborative protocol. In Section 5, experiments show the benefit of the COPIF approach. Finally, concluding remarks are given in Section 6.

2 Related Work 2.1 Self-stabilizing Propagation of Information PIF wave algorithms have been extensively proposed in the area of self-stabilization, e.g., [START_REF] Arora | Distributed reset[END_REF][START_REF] Awerbuch | Time optimal self-stabilizing synchronization[END_REF][START_REF] Bui | Snap-stabilization and PIF in tree networks[END_REF][START_REF] Cournier | Snap-stabilizing PIF algorithm in arbitrary networks[END_REF][START_REF] Varghese | Self-stabilization by counter flushing[END_REF] to quote only a few. Except [START_REF] Awerbuch | Time optimal self-stabilizing synchronization[END_REF][START_REF] Cournier | Snap-stabilizing PIF algorithm in arbitrary networks[END_REF][START_REF] Varghese | Self-stabilization by counter flushing[END_REF], all the above solutions assume an underlying self-stabilizing rooted spanning tree construction algorithm. The solutions in [START_REF] Bui | Snap-stabilization and PIF in tree networks[END_REF][START_REF] Cournier | Snap-stabilizing PIF algorithm in arbitrary networks[END_REF] have the extra desirable property of being snapstabilizing. A snap-stabilizing protocol guarantees that the system always maintains the desirable behavior. This property is very useful for wave algorithms and other algorithms that use PIF waves as the underlying protocols. The basic idea is that, regardless of the initial configuration of the system, when an initiator starts a wave, the messages and the tasks associated with this wave will work as expected in a normal computation. A snap-stabilizing PIF is also used in [START_REF] Caron | Snap-stabilizing prefix tree for peer-to-peer systems[END_REF] to propose a snap-stabilizing service discovery tool for P2P systems based on prefix tree.

Resource Discovery

The resource discovery in P2P environments has been intensively studied [START_REF] Meshkova | A survey on resource discovery mechanisms, peer-topeer and service discovery frameworks[END_REF]. Although DHTs [START_REF] Ratnasamy | A Scalable Content-Adressable Network[END_REF][START_REF] Rowstron | Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-To-Peer Systems[END_REF][START_REF] Stoica | Chord: A Scalable Peer-to-Peer Lookup service for Internet Applications[END_REF] were designed for very large systems, they only provide rigid mechanisms of search. A great deal of research went into finding ways to improve the retrieval process over structured peer-to-peer networks. Peer-to-peer systems use different technologies to support multi-attribute range queries [START_REF] Bharambe | Mercury: Supporting Scalable Multi-Attribute Range Queries[END_REF][START_REF] Cai | Maan: A multi-attribute addressable network for grid information services[END_REF][START_REF] Schmidt | Enabling Flexible Queries with Guarantees in P2P Systems[END_REF][START_REF] Shu | Supporting Multi-Dimensional Range Queries in Peer-to-Peer Systems[END_REF]. Trie-structured approaches outperform others in the sense that logarithmic (or constant if we assume an upper bound on the depth of the trie) latency is achieved by parallelizing the resolution of the query in several branches of the trie.

Trie-based related work

Among trie-based approaches, Prefix Hash Tree (PHT) [START_REF] Ramabhadran | Prefix Hash Tree: an Indexing Data Structure over Distributed Hash Tables[END_REF] dynamically builds a trie of the given key-space (full set of possible identifiers of resources) as an upper layer mapped over any DHT-like network. Faulttolerance within PHT is delegated to the DHT layer. Skip Graphs, introduced in [START_REF] Aspnes | Skip Graphs[END_REF], are similar to tries, and rely on skip lists, using their own probabilistic fault-tolerance guarantees. P-Grid is a similar binary trie whose nodes of different sub-parts of the trie are linked by shortcuts like in Kademlia [START_REF] Maymounkov | Kademlia: A Peer-to-Peer Information System Based on the XOR Metric[END_REF]. The faulttolerance approach used in P-Grid [START_REF] Datta | Range Queries in Trie-Structured Overlays[END_REF] is based on probabilistic replication.

In our approach, the DLPT was initially designed for the purpose of service discovery over dynamic computational grids and aimed at solving some drawbacks of similar previous approaches. An advantage of this technology is its ability to take into account the heterogeneity of the underlying physical network to build a more efficient tree overlay, as detailed in [START_REF] Caron | Efficiency of Tree-Structured Peer-to-Peer Service Discovery Systems[END_REF].

P2P Service Discovery Framework

In this section we present the conceptual model of our P2P service discovery framework and the DLPT data structure on which it is based. Next, we convert our framework into the computational model on which our proof is based.

Conceptual Model

The two abstraction layers that compose our P2P service discovery framework are organized as follow: (i) a P2P network which consists of a set of asynchronous peer (physical machines) with distinct identifiers. The peer communicate by exchanging messages. Any peer P1 is able to communicate with another peer P2 only if P1 knows the identifier of P2. The system is seen as an undirected graph G = (V, E) where V is the set of peers and E is the set of bidirectional communication link; (ii) an overlay that is built on the P2P system, which is considered as an undirected connected labeled tree G = (V , E ) where V is the set of nodes and E is the set of links between nodes. Two nodes p and q are said to be neighbors if and only if there is a link (p, q) between the two nodes. To simplify the presentation we refer to the link (p, q) by the label q in the code of p. The overlay can be seen as an indexing system whose nodes are mapped onto the peers of the network. Henceforth, to avoid any confusion, the word node refers to a node of the tree overlay, i.e., a logical entity, whereas the word peer refers to a physical node part of the P2P system.

Reading and writing features of our service discovery framework are ensured as follow. Nodes are indexed with service name and resource locations are stored on nodes. So, client requests are treated by any node, rooted to the targeted service labeled node along the overlay abstraction layer, indexed resource locations are returned to the clients or updated . A more detailed description of the implementation of our framework is given in [START_REF] Caron | Implementation and evaluation of a P2P service discovery system[END_REF] and briefly reminded in Section 5.1.

The Distributed Lexicographic Placement Table (DLPT [START_REF] Caron | A Dynamic Prefix Tree for Service Discovery Within Large Scale Grids[END_REF][START_REF] Caron | Efficiency of Tree-Structured Peer-to-Peer Service Discovery Systems[END_REF]) is the hierarchical data structure that ensures request routing across overlay layer. DLPT belongs to the category of overlays that are distributed prefix trees, e.g., [START_REF] Aspnes | Skip graphs[END_REF][START_REF] Sriram Ramabhadran | Prefix hash tree: an indexing data structure over distributed hash table[END_REF][START_REF] Aberer | P-grid: a self-organizing structured P2P system[END_REF]. Such overlays have the desirable property of efficiently supporting range queries by parallelizing the searches in branches of the tree and exhibit good complexity properties due to the limited depth of the tree. More particularly, DLPT is based on the particular Proper Greatest Common Prefix Tree (PGCP tree) overlay structure. A Proper Greatest Common Prefix Tree (a.k.a radix tree in [START_REF] Donald | PATRICIA-Practical Algorithm To Retrieve Information Coded in Alphanumeric[END_REF]) is a labeled rooted tree such that the following properties are true for every node of the tree: (i) the node label is a proper prefix of any label in its subtree; (ii) the greatest common prefix of any pair of labels of children of a given node are the same and equal to the node label.

Designed to evolve in very dynamic systems, the DLPT integrates a self-stabilization mechanisms [START_REF] Caron | Self-Stabilization in Tree-Structured Peer-to-Peer Service Discovery Systems[END_REF], providing the ability to recover a functioning state after arbitrary transient failures. As such, the truthfulness of information returned to the client needs to be guaranteed. We use the PIF mechanism to check whether DLPT is currently in a recovering phase or not.

Computational Model

In a first step, we abstract the communication model to ease the reading and the explanation of our solution. We assume that every pair of neighboring nodes communicate in the overlay by direct reading of variables. So, the program of every node consists in a set of shared variables (henceforth referred to as variables) and a finite number of actions. Each node can write in its own variables and read its own variables and those of its neighbors. Each action is constituted as follow: < Label >::< Guard >→< Statement >. The guard of an action is a Boolean expression involving the variables of p and its neighbors. The statement is an action which updates one or more variables of the node p. Note that an action can be executed only if its guard is true. Each execution is decomposed into steps. Let y be an execution and A an action of p (p ∈ V ). A is enabled for p in y if and only if the guard of A is satisfied by p in y. Node p is enabled in y if and only if at least one action is enabled at p in y.

The state of a node is defined by the value of its variables. The state of a system is the product of the states of all nodes. The local state refers to the state of a node and the global state to the state of the system. Each step of the execution consists of two sequential phases atomically executed: (i) Every node evaluates its guard; (ii) One or more enabled nodes execute their enabled actions. When the two phases are done, the next step begins. Formal description (Section 4.2) and proof of correctness of the proposed collaborative propagate information feedback algorithm will be done using this computational model. Nevertheless, experiments are implemented using the classical message-passing model over an actual peer-to-peer system [START_REF] Bolze | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF][START_REF] Drost | JEL: Unified Resource Tracking for Parallel and Distributed Applications[END_REF].

Collaborative Propagation of Information with Feedback Algorithm

In this section, we first present an overview of the proposed Collaborative Propagation of Information with Feedback Algorithm (COPIF). Next, we provide its formal description.

Overview of the COPIF

Before explaining the idea behind COPIF, let us first recall the well-known PIF wave execution. Starting from a configuration where no message has been broadcast yet, a node, also called initiator, initiates the broadcast phase and all its descendant except the leaf participate in this task by sending also the broadcast message to their descendants. Once the broadcast message reaches a leaf node of the network, they notify their ancestors of the end of the broadcast phase by initiating the feedback phase. During both broadcast and feedback steps, it is possible to collect information or perform actions on the entire data structure. Once all the nodes of the structure have been reached and returned the feedback message, the initiator retrieve collected information and executes a special action related to the termination of the PIF-wave. In the sequel, we will refer to this mechanism as classic-PIF.

However, the PIF mechanism is a costly broadcast mechanism that involves the whole platform. In this paper, we aim to increase the parallelism of the PIF by making several PIF waves collaborating together. Let us now define some notions that will be used in the description of our solution:

Let an ordered alphabet A be a finite set of letters. Lets define ≺ an order on A. A non empty word w over A is a finite sequence of letters a 1 , ... , a i , ..., a l such as l > 0. The concatenation of two words u and v, denoted as uv, is equal to the word a 1 , ..., a i , ..., a k , b 1 , ..., b j , ..., b l such that u = a 1 , ..., a i , ..., a k and v = b 1 , ..., b j , ..., b l . A word u is a prefix (respectively, proper prefix) of a word v if there exists a word w such that v = uw (respectively, v = uw and u = v). The Greatest Common Prefix (respectively, Proper Greatest Common Prefix) of w 1 and w 2 , denoted GCP(w 1 , w 2 ) (respectively PGCP(w 1 , w 2 ), is the longest prefix u shared by w 1 and w 2 (respectively, such that ∀i ≥ 1, u = w i ).

Let us now describe the outline of the proposed solution through the P2P framework use case.

Use Case. The idea of the algorithm is the following: When a user is looking for a service, it sends a request to the DLPT to check whether the service exists or not. Once the request is on one node of the DLPT, it is routed according to the labelled tree in the following manner: let l request be the label of the service requested by the user and let l p be the label of the current node u p . In the case of PGCP(l request , l p ) is true, u p checks whether there exists a child u q in the DLPT having a label l q such that PGCP(l request , l q ) is satisfied. If such a node exists, then u p forwards the request to its child u q . Otherwise (PGCP(l request , l p ) is not satisfied), if we keep exploring the sub-tree routed in u p , the service will not be found. u p sends in this case the request to its father node in the DLPT. By doing so, either (i) the request is sent to one node u p such that l p = l request , or (ii) the request reaches a node u p such that it cannot be routed anymore. In the former case, the service being found, a message containing the information about the service is sent to the user. In the latter case, the service has not been found and the message "no information about the service" is sent to the user. However, the node has no clue to trust the received information or not. In other words, in the former case, u p does not know whether it contains the entire service information or if a part of the information is on a node being at a wrong position in the tree due to transient faults. In the latter case, u p does not know whether the service is really not supported by the system or if the service is missed because it is at a wrong position.

In order to solve this problem, u p initiates a PIF wave to check the state of all the nodes part of the DLPT. Note that several PIF waves can be initiated concurrently since many requests can be made in different parts of the system. The idea of the solution is to make the different PIF waves collaborating in order to check whether the tree is under construction or not. For instance, assume that two PIF waves, PIF1 and PIF2, are running concurrently on two different parts of the tree, namely on the subtrees T 1 and T 2, respectively. Our idea is to merge PIF1 and PIF2 so that PIF1 (respectively, PIF2) do not traverse T 2 (resp., T 1) by using data collected by PIF2 (resp.PIF1). Furthermore, our solution is required to be self-stabilizing.

COPIF. Basically, the COPIF scheme is a mechanism enabling the collaboration between different PIF waves. Each node u p of the DLPT has a state variable S p that includes three parameters S p = (Phase, id f , id PIF ). Parameter id PIF refers to the identifier of the PIF wave which consists of the couple (id peer ,l u i ), where id peer is the identifier of the peer hosting the node u i that initiated the PIF wave and l u i is the label of the node u i . The value id f refers to the identifier of the neighbor from which u p received the broadcast. It is set at NULL in the case u p is the initiator. Phase can have four values: C, B, FC and FI. The value C (Clean) denotes the initial state of any node before it participates in a PIF wave. The value B (Broadcast) or FC (Feedback correct) or FI (Feedback incorrect) means that the node is part of a PIF wave. Observe that in the case there is just a single PIF wave that is executed on the DLPT, then its execution is similar to the previously introduce classic-PIF.

When more than one PIF wave are executed, four cases are possible while the progression of the COPIF wave. First (i), if there is a node u p in the C state having only one neighboring node q in the B state and no other neighboring node in the FI or FC state, then p changes its state to B. Second (ii), if there exists a leaf node u p in the C state having a neighbor u q in the B state, then u p changes its state to FC (resp. FI) if its position in the DLPT is correct (resp. incorrect). Next (iii), if there is a node u p in C-phase having two neighboring nodes u q and u q in the B state with different id PIF then, u p changes its state to B and sets its id f to u q such that the id PIF of u q is smaller than id PIF of u q . Finally (iv), if there exists a node u p that is already in the B state such that its id f is u q and there exists another neighboring node u q which is in the B state with a smaller id PIF and a different id f , then u p changes its father by setting id f at u q .

Notice that in the fourth cases, u q (previously, the id f of u p ) will have to change its id f as well since it has now a neighbor u p in the B state with a smaller id peer . By doing so, the node u i that initiated a PIF wave with a smaller id will change its id peer . Similarly, notice that u i is not an initiator anymore. Hence it changes its id f from NULL to the id of its neighbor with a smallest id PIF . So, only one node will get the answer (the feedback of the COPIF), this node being the one with the smallest id PIF . Therefore, when an initiator sets its id f to a value different from NULL (as u i previously), it sends a message to the new considered initiator (can be deduced from id PIF ) to subscribe to the answer. So, when an initiator node receives the feedback that indicates the state of the tree, it notifies all its subscribers of the answer.

C C B,1 C B,2 C C B,1 B,1 B,2 C F,1 B,1 B,1 B,2 B,1 F,1 B,1 B,1 B,2 B,1 F,1 B,1 B,1 B,1 i) ii) iii) iv) … … … … … … … … … … Fig. 2. 4 CoPIF wave transition.

Formal Description

In the following we first define the data and variables that are used for the description of our algorithm. We then present the formal description in Algorithm 1.

-Predicates • Request PIF : Set at true when the peer wants to initiate a PIF wave (There is a Service -Request which could not find the desired service). -Variables

• S p = (A, q, q ): refers to the state of the node p such that: A corresponds to the phase of the PIF wave p is in. A ∈ {B, FI, FC,C} for respectively Broadcast, Feedback State-Incorrect, Feedback State-Correct, Clean. q refers to the identity of the peer that initiates the PIF wave. q' refers to the identity of the neighboring node of p in the DLPT from which p got the Broadcast. • N p : refers to the set of the identities of the nodes that are neighbor to p • State DLPT : refers to the state of the DLPT • min p : q ∈ N p , S q = (B, id q , z) ∧ z = p ∧ id p = min{id q , q ∈ N p , S q = (B, id q , z ) ∧ z = p}.

-Functions

• Send(@dest,@source, Msg): @source sends the message Msg to @dest.

• Add(Mylist, item): Add to my list the subject item.

Character '-' in the algorithm means any value.

Correctness Proof.

In the following, we prove the correctness of our algorithm. Let us first define our self-stabilizing CoPIF wave:

Definition 1. (CoPIF wave)

A finite computation e is called CoPIF wave if and only if the following conditions hold:

-Each node in the system is able to initiate a PIF wave in a finite time.

-All the nodes of the system are visited by CoPIF wave.

-Exactly one node of the system (that initiated a PIF wave) receives the acknowledgement from all the other nodes.

Let us now define some notions that will be used later.

Algorithm 1 COPIF -PIF Initiation • R1: Request PIF ∧ S p = (C, -, -) ∧ ∀ q ∈ N p , S q = (-, -, p) → S p = (B, (id peer , l p ), NULL), State DLPT = Unknown • R2: Request PIF ∧ S p = (B, id, q) ∧ q = NULL → Send(@id, id peer, Interested), State DLPT = Unknown -Broadcast propagation • R3: S p = (C, -, -) ∧ ¬Request PIF ∧ ∃ q ∈ N p , (S q = (B, k, -) ∧ q = min p ∧ ¬∃ q ∈ N p , q = q , S q = (B, k, -)) ∧ ∀ q ∈ N p , S q = (FI ∨ FC, -, p) → S p = (B, k, q) -Father-Switch • R4: ∃ q ∈ N p , S p = (B, id, q) ∧ ∃ q ∈ N p , (q = q ∧ S q = (B, id , ?) ∧ id < id ∧ q = min p ) → S p = (B, id , q )
-initiator resignation • R5: S p = (B, id, NULL) ∧ ∃ q ∈ N p , S q = (B, id , ?) ∧ id < id ∧ q = min p ) → S p = (B, id , q), Send(@id, id peer, Interested) -Feedback initiation

• R6: |N p | = 1 ∧ State = Correct ∧ ∃ q ∈ N p , S q = (B, id, ?) → S p = (FC, id, q) • R7: |N p | = 1 ∧ State = Incorrect ∧ ∃ q ∈ N p , S q = (B, id, ?) → S p = (FI, id, q) -Feedback propagation • R8: ∃ q ∈ N p , S q = (B, id, -) ∧ S p = (B, -, q) ∧ ∀ q ∈ N p /{q}, S q = (FC, -, p) → S p = (FC, id, q) • R9: ∃ q ∈ N p , S q = (B, id, -) ∧ S p = (B, -, q) ∧ ∀ q ∈ N p /{q}, S q = (FI ∨ FC, -, p) ∧ ∃ q ∈ N p /{q} S q = (FI, ?, p) → S p = (FI, id, q)
-Cleaning phase initiation • R10: ∀ q ∈ N p , S q = (FC, id , p) ∧ S p = (B, id, NULL) ∧ id = (id peer , l p ) → State DLPT = Correct, Request PIF = f alse, S p = (C, NULL, NULL), Send(@ListToContact, 'DLPT Correct'), State DLPT = Unknown • R11: ∀ q ∈ N p , S q = (FI ∨FC, id , p) ∧ S p = (B, id, NULL) ∧ id = (id peer , l p ) ∧ ∃ q ∈ N p /{q} S q = (FI, -, p) → State DLPT = Incorrect, Request PIF = f alse, S p = (C, NULL, NULL), Send(@ListToContact, 'DLPT Incorrect'), State DLPT = Unknown -Cleaning phase propagation • R12: ∃ q ∈ N p , S p = (FI ∨ FC, id, q) ∧ (S q = (C, -, -) ∨ q = NULL) → S p = (C, NULL, NULL)

-Correction Rules • R13: S p = (B, id, NULL) ∧ id = (id peer, l p ) → S p = (C, NULL, NULL)

• R14: ∃q ∈ N p S p = (FI ∨ FC, id, q) ∧ ∃ q ∈ N p , q = q ∧ S q = (FI ∨ FC, -, -) → S p = (C, NULL, NULL)

• R15: S p = (B, id, q) ∧ (S q = (B, -, -) ∨ [S q = (B, id , -) ∧ id > id] → S p = (C, NULL, NULL)

• R16: S p = (B, -, q) ∧ S q = (FI ∨ FC, -, -) → S p = (C, NULL, NULL)

• R17: ∃q ∈ N p , S p = (B, id, q) ∧ S q = (B, id, p) → S p (C, NULL, NULL)

• R18: ∃ q, q ∈ N p , S p = (B, id, q) ∧ q = q ∧ S q = (B, id, z) ∧ z = p → S p = (F, id, q)

• R19: ∃ q, q ∈ N p , S p = (C, NULL, NULL) ∧ S q = (B, id, z) ∧ z = p ∧ S q = (B, id, z ) ∧ z = p → S p = (F, id, q) • R20: ∃ q, q ∈ N p , S p = (B, id, q) ∧ S q = (B, id , z) ∧ z = p ∧ id < id ∧ S q = (B, id , z ) ∧ z = p ∧ id < id → S p = (B, id , q)
-Event: Message reception • Message 'idpeer,Interested': Add(ListToContact, id peer)

• Message 'Contact id for an answer': Send(@id, id peer, Interested)

• Message 'DLPT Correct':

State DLPT = Correct • Message 'DLPT Incorrect': State DLPT = Incorrect Definition 2

. (abnormal sequences of type A)

We say that a configuration contains an abnormal sequence of type A if there exists a node p of state S p = (B, id, q) such as one of these conditions holds:

1. q = NULL ∧ id = (id peer , l p).

2. q = NULL ∧ S q = (B, id , z) ∧ id > id ∧ z = p.

3. q = NULL ∧ S q = (B, id, p). 4. q = NULL ∧ S q = (B, -, -).

In the following we refer to each case by type Ai where 1 ≤ i ≤ 4.

Definition 3. (abnormal sequences of type B)

We say that a configuration contains an abnormal sequence of type B if there exists a node p of state S p = (C, NULL, NULL) such as ∃ q, q ∈ N p , S q = (B, id, z) ∧ S q = (B, id, z ) ∧ z = p ∧ z = p.

Definition 4. (Dynamic abnormal sequence)

We say that a configuration contains a dynamic abnormal sequence if there exists two nodes p and q such as S p = (B, id, z) with z = q and S p = (B, id, z ) with z = p.

Definition 5. (Trap sequence)

We say that a configuration contains a trap sequence if there exists a sequence of nodes p 0 , p 1 , ..., p k such that the following three conditions hold:

(i) S p 0 = (B, id, z) ∧ z = p 1 . (ii) S p k = (B, id, z ) ∧ z = p k-1 . (iii) ∀ 1 ≤ i ≤ k -1, S p i = (C, NULL, NULL). Definition 6. (Path)
The sequence of nodes P id = p 0 , p 1 , ..., p k is called a path if ∀ 1 ≤ i ≤ k, S p i = (B, id, p i-1 ) ∧ S p 0 = (B, id, NULL). p 0 is said to be the extremity of the path.

Definition 7. (FullPath)

For any node p such as S p = (C, NULL, NULL), a unique path PN = p 0 , p 1 , ..., p k is called FullPath, if and only if ∀ 1 ≤ i ≤ k, S p i = (B ∨ F, -, p i-1 ) ∧ S p 0 = (B ∨ F, -, p). p is said to be the extremity of the path.

Definition 8. (SubTree) For any node p, we define a set of SubTree(p) of nodes as follow: for any node q, q ∈ SubTree(p) if and only if p and q are part of the same FullPath such as p is the extremity of the path.

In the following, we say that a node p clean its state if it updates its state to S p = (C, NULL, NULL).

Let us first show that a configuration without abnormal sequences of type A and B is reached in a finite time.

Lemma 1 No abnormal sequence of type A can be created dynamically.

Proof. Let consider each abnormal sequence of type A separately:

1. Type A1. Note that the only rule in the algorithm that allows p to set its state to S p = (B, id, NULL) is R1.

Note also that when R1 is executed on p, id = (id peer , l p). Thus we are sure that the abnormal sequence A1 is never created dynamically. 2. Type A2. Note that the only case where p sets its state to S p = (B, id, q) such as q = NULL is when S q = (B, id , z) such as id < id and z = p (see Rules R3, R4 and R5). Thus we are sure that no abnormal sequence of type A2 is created dynamically.

S p = (F, id, q) (the scheduler will make the choice between q and q ). When all the nodes on which R19 is enabled execute R19. A configuration without any abnormal sequence of type B is reached and the lemma holds.

Let us show now that a configuration without dynamic abnormal sequences is reached in a finite time.

Lemma 7 If the configuration contains a trap sequence, then this sequence was already in the system in the starting configuration.

Proof. The proof is by contradiction. We suppose that the trap sequence can be created during the execution using the PIF waves that were initiated after the starting configuration. First of all note that since the identifier of each PIF wave is unique, there is only one initiator for each PIF wave. Thus, there is at most one PIF wave that can be executed for each id (considering only the PIF waves that were executed after the initial configuration). On the other hand, when a PIF wave is executed, the only rules that makes a node change its father id are R4 and R5. Note that when one of these rules is enabled on p, p has a neighboring node q in the broadcast phase with a smaller PIF id. When one of these rules is executed, p changes both the identifier of its father and the identifier of the PIF wave. Thus we are sure that if the configuration contains a trap sequence then, this sequence was already in the system in the starting configuration.

Lemma 8

No dynamic abnormal sequence is created dynamically eventually.

Proof. The two cases bellow are possible:

1. There is a node p that has a clean state S p = (C, NULL, NULL) such as it has two neighboring nodes q and q with S q = (B, id, z), S q = (B, id, z ), z = p and z = p. In this case R19 is enabled on p. When the rule is executed, p sets its state directly to the feedback phase S p = (F, id, q ∨ q ) (the adversary will choose between q and q ). Thus we are sure that no dynamic abnormal sequence is reached in this case. 2. There are two neighboring nodes p and p such as the two following condition hold: (i) ∃q ∈ N p , S q = (B, id, z) ∧ z = p and (ii) ∃q ∈ N p , S q = (B, id, z ) ∧ z = p . Note that on both p and p , R3 is enabled. When the rule is executed only on one node, we retrieve Case 1. Thus, no dynamic abnormal configuration is reached. In the case R3 is executed on both p and p then a dynamic abnormal sequence is created. However, observe that the latter case cannot happen infinitely often since in a correct execution, it is impossible to reach a configuration where two PIF waves with the same id are executed on two disjoint sub-trees (refer to Lemma 7). So we are sure that a limited number of dynamic abnormal sequences can be created (due to the arbitrary starting configuration). Thus we are sure that, after a finite time, no dynamic abnormal configuration is reached.

From the cases above, we can deduce that no dynamic abnormal sequence is created dynamically eventually and the lemma holds.

Lemma 9 Every execution of Algorithm 1 contains a suffix of configurations containing no dynamic abnormal sequences.

Proof. From Lemma 8, a limited number of dynamic abnormal sequences can be created. Let's consider the system when all the dynamic abnormal sequences have been created (no other Dynamic abnormal sequence can be created). Note that when the configuration contains a dynamic abnormal sequence, there are at least two nodes p and q that are neighbors such as S p = (B, id, z), S q = (B, id, z ), z = q and z = p. Note that R18 is enabled on both p and q. When the rule is executed on at least one of the two nodes (let this node be the node p), S p = (F, id, z) and the lemma holds.

From the lemmas above we can deduce that a configuration without any abnormal sequences of (type A and B), any dynamic abnormal sequences is reached in a finite time.

In the following we consider the system when there are no abnormal sequences (Dynamic, Type A and B). We have the following lemma: Lemma 10 Let P id = p 0 , p 1 , ..., p k be a path. If there exist 1 ≤ i ≤ k such as p i changes its state to S p i = (B, id , q) with q = p i-1 and id < id then, ∀ 0 ≤ j ≤ i, p j will also updates their state to S p j = (B, id , p j+1 ) in a finite time.

Proof. Note that when p i changes its state to S p i = (B, id , q) with q = p i-1 and id < id, p i-1 becomes neighbor of a node (p i ) that is in the broadcast phase with a smallest id, p i-1 changes its state to S p i-1 = (B, id , p i ) by executing R4. Note that now R15 now is enabled on p i-1 and so on, thus we are sure that ∀ 1 ≤ j ≤ i, p j will updates their state to S p j = (B, id , p j+1 ). Note that when p 1 updates its state, R5 becomes enabled on p 0 , when R5 is executed, p 0 = (B, id, p 1 ). Thus the lemma holds.

Let us refer by Initial -PIF waves, the set of PIF waves that were already in execution in the initial configuration (they were not initiated after the faults). Recall that the starting configuration can be any arbitrary configuration. Thus, some PIF waves can be separated by nodes that are in the feedback phase: PIF id and PIF id are said to be separated by nodes in the feedback phase if there exists a sequence of nodes p 0 , p 1 , ..., p k such that S p 0 = (B, id, z) with z = p 1 and S p k = (B, id , z ) with z = p k-1 and (S p 1 = (F, id, p 0 ) ∨ S p -1 = (F, id , p k )). Let refer by PIF friendly set S i , the set of nodes that are part of PIF waves that are not separated by nodes in the feedback phase. Note that 1 ≤ i ≤ k.

In the following, we say that there is a Partial-Final sequence in a PIF friendly set S i , if there exists a node p such that S p = (B, id, NULL) and ∀ q ∈ S i /{p}, q ∈ SubTree(p) and S q = (F, -, -) (refer to Figure 3). Proof. Let consider a single PIF friendly set S i . It is clear that if in S i there is only one PIF wave that is executed, then the lemma holds since the PIF wave in S i behaves as the PIF wave described in [START_REF] Bui | Snap-stabilization and PIF in tree networks[END_REF]. In the following we suppose that there are at least two PIF waves that are executed in each PIF friendly set.

Observe that the behavior of PIF waves when they are alone (when they do not meet any other PIF wave) is similar to the well now PIF schema in [START_REF] Bui | Snap-stabilization and PIF in tree networks[END_REF], thus, we will not discuss their progression in this case. Let us consider the PIF wave that has the smallest identifier id in the set S i (let refer to its initiator by InitTarget). The cases bellow are then possible:

1. There exists a node p such as S p = (C, NULL, NULL) ∧ ∃ q, q ∈ N p , S q = (B, id, z) ∧ S q = (B, id , z ).

Note that id < id . In this case p sets its state to the broadcast phase and chooses q as its father S p = (B, id, q). Note that for the node q we retrieve case 2. 2. There exists a node p such as S p = (B, id , q) ∧ ∃ q ∈ N p , S q = (B, id, z) ∧ z = p. Note that id < id . In this case we are sure that S q = (B, id , z) with id ≤ id and z = p (recall that there in no more abnormal sequences). Thus, p changes its state to S p = (B, id, q ). Note that p was part of path P id . From Lemma 10, all the nodes on the path will updates their state as well. Thus the initiator of the PIF wave of identifier id will be able to know that there is another PIF wave with a smaller id that is being executed (let refer to such a node by Init id ). Init id updates it state to be part of the PIF wave of identifier id (refer to Rule R5). Note that only the node that are on the path of both p and Init id updates their state. The other nodes (that were part of PIF id ) don't have to update their state since when the nodes of the path update their state, they are already part of SubTree(p).

Observe that since some of the nodes that are part of SubTree(p) do not change their state, Some PIF waves can be seen as PIF waves with smaller id. Refer to Figure 4. (From the figure (case (c)) we can observe that p is not aware of the presence of the PIF wave of id = 0 since it did not change its state). Let p 0 be the node that is neighbor to the initiator of the PIF wave PIF1 that has the smallest id. Note that S p 0 = (B, id, z) (p in Figure 4) and let p k be the node that is neighbor to the initiator of the other PIF (the one that can be considered as the PIF wave with the smallest id, the PIF wave with id = 1 in Figure 4). Observe that S p k = (B, id , z ). Let P = p 1 , p 2 , p 3 , ...p k-1 be the sequence of nodes between p 0 and p k such as S p i = (B, id , p i-1 ) and id > id. Note that on p k-1 , R4 is enabled. When the rule is executed, p k-1 updates its state to S p k-1 = (B, id , p k ). Note that on p k-2 , R4 becomes enabled thus, p k-2 will have the same behavior, it updates its state to S p k-2 = (B, id , p k-2 ) and so on. Hence, all the nodes on P except p 1 will updates their state and set it at (B, id , p i+1 ). Note that p 1 is able to detect the presence of the two PIF waves since it has two neighboring nodes that are part of different PIF waves, it is able to detect that p 2 think that the PIF with the identifier id is the smallest one. Thus, p 1 updates its state by changing the identifier of the PIF waves to set it at the smallest one. (S p 1 = (B, id, z)). By doing so, R4 becomes enabled on p 2 . When the rule is executed, p 2 updates its state and so on.

Let p init be the node that initiates a PIF wave that has the smallest id within the PIF friendly S i . From the two cases above, we can deduce that all the nodes part of the same S i will be part of the SubTree(p init ). Note that when the feedback phase finished its execution, all the nodes in S i except p init will be in the feedback phase. Thus a Partial-Final configuration is reached and the lemma holds.

From the two cases above, we can deduce that after a finite time, a final-partial configuration is reached in a finite time and the lemma holds.

Lemma 12 Every node belonging to a PIF friendly set eventually clean its state.

Proof. Note that when the configuration of type partial-Final is reached in each set, there is only one node p that is enabled. Observe that S p = (B, id, NULL) (refer to the Rules R10 and R11). When p executes R10, it updates its state to S p = (C, NULL, NULL). Let N 1 be the set of nodes that are neighbor of p. Recursively, let N i be the set of nodes that are neighbor of one node that is part of N i-1 . Note that R12 becomes enabled on all the nodes part of S1, when the rule is executed, each node clean its state. In the same manner, R12 becomes enabled on the nodes part of S 2 , and so on. Thus we are sure all the nodes part of each PIF friendly set will eventually clean their state and the lemma holds.

From Lemma 12, all the nodes part of Initial -PIF waves clean their state in a finite time. Thus we are sure that a configuration without any Initial -PIF wave is reached in a finite time. Initiator p q' q (b) a PIF wave with id = 0 is initiated. p updates its state.

B,3 B,1 B,0 B,3 B,0 B,1
Initiator Initiator p q' q p' (c) A PIF wave with id = 1 is initiated. p believe that it is the smallest one and updates its state.

B,0 B,1 B,0 B,3 B,0 B,1
Initiator Initiator p q' q p' (d) q' notices the situation and updates the id PIF . Let us now consider the system at that time (without Initial -PIF waves). In the following we extend the notion of Partial-Final configuration as follow: we say that a configuration is of type Final-Configuration if there exists in the system a single PIF friendly set such that there exists a node p that verifies the following condition: S p = (B, id, NULL) and ∀ q ∈ S i /{p}, q ∈ SubTree(p) and S q = (F, -, -)

The following lemma follows:

Lemma 13 If there are many PIF waves that are executed then after a finite time, Final Configuration is reached.

Proof. Note that since all the PIF waves that are on the system were initiated by nodes, there is exactly one PIF friendly set i.e., there are no PIF waves that are separated by nodes in the feedback phase (since the Feedback phase is initiated from the leaves of the tree overlay and a node p is allowed to change its to the feedback phase only if all its neighboring nodes except his father are already in the feedback phase). Observe that all the nodes of the system are part of the PIF friendly set. Observe also that the partial-Final configuration in this case is exactly the same as the Final configuration. Thus, we can deduce from Lemma 11 that Final configuration is reached in a finite time. and the lemma holds.

Lemma 14 Starting from a final configuration, all the nodes of the system eventually clean their state.

Proof. Can be deduce directly from Lemma 12 (since Partial-Final configuration is the same as Final configuration when there is a single PIF friendly set in the system). Thus, the lemma holds.

Theorem 1. Every node is infinitely often able to initiate a PIF wave Proof. Directly follows from Lemma 14 and the fact that if Rule R1 becomes enabled on p, then it remains enabled until R1 is executed-R3 cannot be enabled while Request PIF = true.

We can now state the following result: Theorem 2. Algorithm 1 is a self-Stabilizing CoPIF algorithm.

Proof. From Theorem 1, each node is able to generate a PIF waves in a finite time. From Lemma 13, all the nodes of the system were visited by the CoPIF wave. Thus, all of them acknowledge the receipt of the question (whether the tree overlay is in a correct state or not) and give an answer to the latter. Finally, from Lemma 13 one node p of the system receives the answer (S p = (B, id, NULL)). Hence we can deduce that Algorithm 1 is a self-Stabilizing CoPIF algorithm and the theorem holds.

Evaluation

In order to evaluate qualitatively and quantitatively the efficiency of COPIF, we drive a set of experiments. As mentioned before, the DLPT approach and its different features have been validated through analysis and simulation [START_REF] Tedeschi | Peer-to-Peer Prefix Tree for Large Scale Service Discovery[END_REF]. The scalability and performance of its implementation, SBAM (Spades BAsed Middleware) has ever been improved in [START_REF] Caron | Implementation and evaluation of a P2P service discovery system[END_REF]. Our goal is now to show the efficiency of the previously described QoS algorithm (Section 4). We will focus on the size of the tree, and number of PIF that collaborate simultaneously. We will observe the behavior not only from the number of exchanged messages point of view but also in term of duration needed to performs COPIFS.

SBAM

We use the term peer to refer to a physical machine that is available on the network. In our case, a peer is an instantiated Java Virtual Machine connected to other peers through the communication bus. We call nodes the vertices of the prefix tree.

SBAM is the Java implementation of the DLPT. SBAM proposes 2-abstraction layers in order to support the distributed data structure: the peer-layer and the agent-layer. The peer-layer is the closest to the hardware layer. It relies on the Ibis Portability Layer (IPL) [START_REF] Drost | JEL: Unified Resource Tracking for Parallel and Distributed Applications[END_REF] that enables the P2P communication. We instantiate one JVM per machine, also called peer. JVM communicate all together as a P2P fashion using the IPL communication bus. The agent-layer supports the data structure. Each node of the DLPT is instantiated as a SBAM agent. Agents are uniformly distributed over peers and communicate together in a transparent way using a proxy interface. Since we want to guarantee truthfulness of information exchanged between SBAMagents, the implementation of an efficient mechanism ensuring quality of large scale service discovery is quite challenging. In the state model described in the section 3.2 a node has to read the state and the variables of its neighbors. In SBAM, the feature is implemented using synchronous message exchange between agents. Indeed, when a node has to read its neighbor states, it sends a message to each and wait all responses. Despite the fact that this kind of implementation is expensive, especially on a large distributed data structure, experiment (Section 5.6) shown that our model implementation stays efficient, even on a huge prefix tree.

Experimental platform

Experiments were run on the Grid'5000 platform4 [START_REF] Bolze | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF], more precisely on a dedicated cluster HP Proliant DL165 G7 17 units, each of them equipped with 2 AMD Opteron 6164 HE (1.7GHz) processors, each processor gathering 12 cores, thus offering a 264-cores platform for these experiments. Each unit consists of 48 GB of memory. Units are connected through two Gigabit Ethernet cards. For each experiment, we deployed one peer per unit.

Scenario of experiments

The initialization of an experiment works in three phases: (i) the communication bus is started on a computing unit (Section 5.2), (ii) 16 peers are launched and connected together through the communication bus, and (iii) a pilot is elected using the elect feature of the communication bus.

After the initialization, the pilot drives the experiment. It consists in two sequential steps. First, it sends n insertion requests to the distributed tree structure. An insertion request leads to the addition of a new entry in the DLPT tree (Section 3). The insertion requests are sent to a random node of the tree and routed following the lexicographic pattern to the targeted node. Doing so, the node sharing the greatest common prefix with the service name is reached. If the targeted label does not exist, a new node is created on a randomly chosen peer and linked to the existing tree.

In the final step, the pilot selects a set of nodes to initiate classic-PIFs and COPIFS (Section 4). In order to observe distributions, 10 replications of this basic scenario are executed.

Failures

At this level of description we can distinguish two kind of failure: (i) failures in the DLPT data structure, when the prefix tree data structure is corrupted; (ii) failures in the COPIF state variables, when state variable dedicated to COPIF feature are corrupted.

In our experiments, we consider that the DLPT data structure is not corrupt. It corresponds to the worst case in term of COPIF truthfulness check. Indeed, if the entire DLPT data structure is correct, the COPIF has to explore the entire DLPT data structure to check it.

Next, remind that the objective of our experiment is to evaluate the efficiency of COPIF compared to classic-PIF. So, we consider that the COPIF state variables are not corrupted and we measure the number of messages and the duration of COPIF when the self-stabilization COPIF has converged, it means after the clean part of the COPIF state variables.

Parameters and indicators

The experiments conducted are influenced by two main parameters. First, n denotes the number of inserted services in the tree. Second, k refers to the number of PIF waves that are collaborating together.

40000}. The number of PIF that collaborate (k) was taken from the set {1, 2, 4, 8, 16, 32, 64}. For each couple (n, pi f ), 10 replications are performed. Thus, 210 experiments were conducted.

Strings used to label the nodes of the trees were randomly generated with an alphabet of 2 digits and a maximum length of 18 (in a set of 524287 key).

For each experiment we observe two indicators: (i) the total number of exchanged messages observed and (ii) the time required to perform k classic-PIFs or COPIFS over distributed data structure, i.e., the time between the issue of the PIFs and the receipt of the response on all nodes that initiate PIFs.

For each indicator we obtain 21 sets of 10 values. We present evolution of the median-value of the 10replication according to k, the number of PIFs (Figures 5(a In order to quantitatively evaluate the efficiency of the COPIF strategy, for an indicator (I) and for a given number of PIFs k, we compute the efficiency criterion with the following formula: When the indicators explode in for classic-PIF strategy, they stay stable for COPIF strategy. It qualitatively demonstrates gain of the COPIF strategy over classic-PIF approach. The introduction of the efficiency criterion in Section 5.5 allows us to measure quantitatively this gain and its behavior.

Results

Figure 6(a) and 6(b) present the efficiency of COPIF according to the number of exchanged messages and the duration. On these figures we want to observe the impact of the size of the data structure on the efficiency of COPIF. Figure 6(a) reveals us that, in term of number exchanged messages, on small data structure, the collaborative mechanism is less efficient than on huge one. This result was expected because on small data structure the number of messages due to collision between collaborative PIFs (overhead) represents a more important part of the entire number of exchanged messages. So, the bigger the data structure, the more efficient COPIF.

More interesting is the analyze of the Figure 6(b). Indeed we can observe the same tendency in term of duration but the efficiency decrease faster with the number of PIFs that are simultaneously performed. It is explain by the fact that overhead messages introduced by COPIF are particularly expensive messages in term of duration. It quantitatively demonstrates gain of the COPIF strategy over classic-PIF approach.

Conclusion and Future Work

In this paper we provide a self-stabilized collaborative algorithm called COPIF allowing to check the truthfulness of a distributed prefix tree. COPIF implementation in a P2P service discovery framework is experimentally validate, in qualitative and in quantitative terms. Experiment demonstrates the efficiency of COPIF We conjecture that the stabilization time is in O(h 2 ) rounds and the worst case time to merge several classic-PIF waves is in O(h) rounds, h being the height of the tree. We plan to experimentally validate this two complexities. Indeed, experiment were driven considering no corrupted COPIF variables. In order to do that, we need to define a model of failure, implement or reuse a fault injector and couple it with SBAM before driving a new experiment campaign.

Fig. 1 .

 1 Fig. 1. The PIF Wave.

FFig. 3 .

 3 Fig. 3. Partial-Final sequence in a PIF Friendly Set

  A PIF wave with id=3 is being executed.

Fig. 4 .

 4 Fig. 4. Special Case.

Fig. 5 .

 5 Fig. 5. COPIF behavior

  ) and 5(b)). The comparison of these indicators for classic-PIFs and COPIFS provides us a qualitative overview of the gain obtain using COPIF.

  E I,pi f = I ind,pi f pi f × I coll,pi f , where I classic,pi f (resp. I CoPIF,pi ) is the value of the indicator I for a given k and in an classic-PIF (resp. COPIF) context. The evolution of this efficiency criterion are shown in Figures 6(a) and 6(b).

Figure 5 (

 5 Figure5(a) (resp. 5(b)) presents the evolution of the number of messages (resp. duration) needs to execute PIFs according to number of PIFs (k) that are simultaneously performed and the size of the data structure on which PIFs are performed. The y-axis represents the number of exchanged messages (resp. the duration). On these figures, classic-PIFs and COPIFS strategies are compared. On both curve, the x-axis represents the number of PIF (k) that are simultaneously performed. On these figures, we present 2 curve triplets. Solid (resp. dashed) curves triplet describes indicator in an classic-PIF (resp. COPIF) context. For each triplet, red-triangle-curve (resp. green-+-curve and blue-x-curve) describes behavior of indicator for n = 2500 (resp. n = 10000 and n = 40000).When the indicators explode in for classic-PIF strategy, they stay stable for COPIF strategy. It qualitatively demonstrates gain of the COPIF strategy over classic-PIF approach. The introduction of the efficiency criterion in Section 5.5 allows us to measure quantitatively this gain and its behavior.Figure6(a) and 6(b) present the efficiency of COPIF according to the number of exchanged messages and the duration. On these figures we want to observe the impact of the size of the data structure on the efficiency of COPIF. Figure6(a) reveals us that, in term of number exchanged messages, on small data structure, the collaborative mechanism is less efficient than on huge one. This result was expected because on small data structure the number of messages due to collision between collaborative PIFs (overhead) represents a more important part of the entire number of exchanged messages. So, the bigger the data structure, the more efficient COPIF.More interesting is the analyze of the Figure6(b). Indeed we can observe the same tendency in term of duration but the efficiency decrease faster with the number of PIFs that are simultaneously performed. It is explain by the fact that overhead messages introduced by COPIF are particularly expensive messages in term of duration. It quantitatively demonstrates gain of the COPIF strategy over classic-PIF approach.

  Number of PIF according to the duration.

Fig. 6 .

 6 Fig. 6. COPIF Efficiency

http://www.grid5000.fr/

Acknowledgment

This research is funded by french National Research Agency (08-ANR-SEGI-025). Details of the project on http://graal.ens-lyon.fr/SPADES. Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).

3. Type A3. To create this abnormal sequence dynamically either p or q or both are in the clean state (C, NULL, NULL). In the three cases the node that has a clean state (C, NULL, NULL) (let this node be p) never change its state to set it to the broadcast phase (B, id, q) when S q = (C, NULL, NULL) ∨ S q = (B, id, p). Thus we are sure that no abnormal sequence of type A3 is created dynamically. 4. Type A4. The properties of the PIF algorithm ensure that when a node p is in a broadcast phase (B, id, q) (refer to [START_REF] Bui | Snap-stabilization and PIF in tree networks[END_REF]), then S q = (B, -, -). Thus we are sure that no abnormal sequence of type A4 is created dynamically.

From Lemmas 1, we can deduce that the number of abnormal sequences does not increase.

Lemma 2 Every execution of Algorithm 1 contains a suffix of configurations containing no abnormal sequence of type A1.

Proof. Note that in a case of an abnormal sequence of type A1, there exists a node p whom state Sp = (B, id, q) such as q = NULL ∧ id = (id peer , l p). Note that R13 is enabled on p. When the rule is executed on p, S p = (C, NULL, NULL) and the Lemma holds.

Lemma 3 Every execution of Algorithm 1 contains a suffix of configurations containing no abnormal sequence of type A2.

Proof. Note that in a case of an abnormal sequence of type A2, there exists a node p whom state Sp = (B, id, q) such as q = NULL ∧ S q = (B, id , z) ∧ id > id ∧ z = p. Note that R15 is enabled on p. When the rule is executed S p = (C, NULL, NULL) and the Lemma holds.

Lemma 4 Every execution of Algorithm 1 contains a suffix of configurations containing no abnormal sequence of type A3.

Proof. Note that in a case of an abnormal sequence of type A3, there exists a node p whom state Sp = (B, id, q) such as q = NULL ∧ S q = (B, id, p). Note that R17 is enabled on p. When the rule is executed S p = (C, NULL, NULL) and the Lemma holds.

Lemma 5 Every execution of Algorithm 1 contains a suffix of configurations containing no abnormal sequence of type A4.

Proof. Let S = n 1 , n 2 , ..., n k be the sequence of node on the tree overlay such as S n 1 = (B, -, p) and S n i = (B, -, n i-1 ). Note that in a case of an abnormal sequence of type A3, there exists a node p whom state Sp = (B, id, q) such as q = NULL ∧ S q = (B, -, -). In this case R15 is enabled on p. When the rule is executed S p = (C, NULL, NULL). Note that the state of n 1 is the same as p is the previous round, thus when n 1 executes R15, S n 1 = (C, NULL, NULL). R15 becomes then enabled on n 2 and so on. Thus we are sure to reach in a finite time a configuration without any abnormal sequence of type A4. Proof. Note that in the case of an abnormal sequence of type B there is in the configuration at least one node p such that the following properties hold: S p = (C, NULL, NULL) ∧ ∃ q, q ∈ N p , S q = (B, id, z) ∧ S q = (B, id, z ) ∧ z = p ∧ z = p. Note that in this case R19 is enabled on p. When the rule is executed,