Snap-stabilizing Prefix Tree for Peer-to-peer Systems

Resource Discovery is a crucial issue in the deployment of computational grids over large scale peer-to-peer platforms. Because they efficiently allow range queries, Prefix Trees appear to be among promising ways in the design of distributed data structures indexing resources. Self-stabilization is an efficient approach in the design of reliable solutions for dynamic systems. A snap-stabilizing algorithm guarantees that it always behaves according to its specification. In other words, a snap-stabilizing algorithm is also a self-stabilizing algorithm which stabilizes in 0 steps. In this paper, we provide the first snap-stabilizing protocol for trie construction. We design particular tries called Proper Greatest Common Prefix (PGCP) Tree. The proposed algorithm arranges the n label values stored in the tree, in average, in O(h+h') rounds, where h and h' are the initial and final heights of the tree, respectively. In the worst case, the algorithm requires an O(n) extra space on each node, O(n) rounds and O(n^2) actions. However, simulations show that, using relevant data sets, this worst case is far from being reached and confirm the average complexities, making this algorithm efficient in practice.La découverte de ressources est un point crucial pour les grilles de calcul dessinées pour être déployées à large échelle. Parce qu’ils permettent des requêtes sur des plages de valeurs, les arbres de préfixes distribués semblent être une structure adaptée `a la recherche décentralisée de ressources géographiquement distribuées. L’auto-stabilisation est une approche efficace pour la mise en place de solutions fiables pour les systèmes dynamiques. Un algorithme dit snap-stabilisant se comporte toujours en accord avec ses spécifications. Autrement dit, un algorithme snap-stabilisant est un algorithme auto stabilisant qui se stabilise en 0 étape. Dans ce rapport, nous décrivons le premier protocole snap-stabilisant pour la construction d’arbres de préfixe distribués. L’algorithme propos´e arrange les n labels stock´es dans l’arbre, en moyenne en O(h+h′), h et h′ étant les hauteurs initiale et finale de l’arbre, respectivement. Dans le pire cas, l’algorithme nécessite un espace mémoire en O(n) sur chaque nœud de l’arbre, O(n) étapes et O(n2) opérations. Nous montrons par simulation que ce pire cas est loin d’être atteint dans des cas réels, confirmant les complexités moyennes, et donc l’efficacité de cet algorithme dans la pratique