Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download
Contributor : Cédric Tedeschi Connect in order to contact the contributor
Submitted on : Wednesday, September 19, 2007 - 4:08:36 PM
Last modification on : Wednesday, October 26, 2022 - 8:14:53 AM


  • 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, LIP RR-2007-39, INRIA, LIP. 2007, pp.20. ⟨inria-00173050v2⟩



Record views


Files downloads