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.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00173050
Contributor : Cédric Tedeschi <>
Submitted on : Wednesday, September 19, 2007 - 4:08:36 PM
Last modification on : Monday, May 13, 2019 - 4:32:44 PM

Identifiers

  • HAL Id : inria-00173050, version 2

Collections

Citation

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⟩

Share

Metrics

Record views

360

Files downloads

418