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

Abstract : 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.
Type de document :
[Research Report] RR-6297, INRIA. 2007, pp.20
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger
Contributeur : Cédric Tedeschi <>
Soumis le : mercredi 19 septembre 2007 - 16:08:36
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:29:09


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00173050, version 2



Eddy Caron, Frédéric Desprez, Franck Petit, Cédric Tedeschi. Snap-stabilizing Prefix Tree for Peer-to-peer Systems. [Research Report] RR-6297, INRIA. 2007, pp.20. 〈inria-00173050v2〉



Consultations de la notice


Téléchargements de fichiers