Skip to Main content Skip to Navigation
New interface
Journal articles

Snap-Stabilizing Prefix Tree for Peer-to-Peer Systems

Eddy Caron 1, 2 Frédéric Desprez 1, 2 Franck Petit 1, 3 Cédric Tedeschi 4 
2 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
4 MYRIADS - Design and Implementation of Autonomous Distributed Systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : Several factors still hinder the deployment of computational grids over large scale platforms. Among them, the resource discovery is one crucial issue. New approaches, based on peer-to-peer technologies, tackle this issue. Because they efficiently allow range queries, Tries (a.k.a., Prefix Trees) appear to be among promising ways in the design of distributed data structures indexing resources. Despite their lack of robustness in dynamic settings, trie-structured approaches outperform other peer-to-peer fashioned technologies by efficiently supporting range queries. Within recent trie-based approaches, the fault-tolerance is handled by preventive mechanisms, intensively using replication. However, replication can be very costly in terms of computing and storage resources and does not ensure the recovery of the system after arbitrary failures. Self-stabilization is an efficient approach in the design of reliable solutions for dynamic systems. It ensures a system to converge to its intended behavior, regardless of its initial state, in a finite time. A snap-stabilizing algorithm guarantees that it always behaves according to its specification, once the protocol is launched. 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(n2) actions. However, simulations allow to state that this worst case is far from being reached and to confirm the average complexities, showing the practical efficiency of this protocol.
Complete list of metadata
Contributor : Eddy Caron Connect in order to contact the contributor
Submitted on : Friday, January 6, 2017 - 12:00:15 AM
Last modification on : Tuesday, October 25, 2022 - 4:18:39 PM



Eddy Caron, Frédéric Desprez, Franck Petit, Cédric Tedeschi. Snap-Stabilizing Prefix Tree for Peer-to-Peer Systems. Parallel Processing Letters, 2010, 20 (1), pp.15-30. ⟨10.1142/S012962641000003X⟩. ⟨hal-01427726⟩



Record views