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

Abstract : Several factors still hinder the deployment of computational grids over large scale platforms. Among them, the resource discovery is one of the crucial issues. New approaches, based on peer- to-peer technologies, tackle this issue. One promising way for indexing resources at large scale is to usetries (a.k.a., prefix trees). Trie-structured approaches outperforms other peer-to-peer fashioned technologies by efficiently supporting range queries. One drawback of using tries is their inherent poor robustness in a dynamic environment, fault-tolerance being a key feature of systems designed to be deployed at large scale. Within re- cent trie-based approaches, the fault-tolerance is handled by preventive mechanisms, intensively using replication. Replication can be very costly in terms of computing and storage resources. Moreover, it does not formally ensure the recovery of the system after arbitrary failures. Self-stabilization is a well known general technique to design distributed systems tolerating arbitrary transient faults. Self-stabilization ensures a system to converge to its intended behavior, regardless of its initial state, in a finite time. Using self-stabilization appears to be a good alternative to inject fault tolerance in peer-to-peer systems. In this purpose, we have designed the first snap-stabilizing distributed algorithm to build a greatest proper common prefix tree (GPCPT) starting from any labeled rooted tree. A snap-stabilizing algorithm guarantees that the system always behaves according to its specification provided that some nodes initiated the algorithm. 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 a given node, O(n) rounds and O(n2) operations. 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 :
Communication dans un congrès
SSS 2007 - 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Nov 2007, Paris, France. Springer Verlag Berlin Heidelberg, 4838, pp.15, Lecture Notes in Computer Science. 〈10.1007/978-3-540-76627-8_9〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01429571
Contributeur : Eddy Caron <>
Soumis le : dimanche 8 janvier 2017 - 22:05:23
Dernière modification le : vendredi 22 juin 2018 - 01:19:52

Lien texte intégral

Identifiants

Collections

Citation

Eddy Caron, Frédéric Desprez, Franck Petit, Cédric Tedeschi. Snap-stabilizing Prefix Tree for Peer-to-peer Systems. SSS 2007 - 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Nov 2007, Paris, France. Springer Verlag Berlin Heidelberg, 4838, pp.15, Lecture Notes in Computer Science. 〈10.1007/978-3-540-76627-8_9〉. 〈hal-01429571〉

Partager

Métriques

Consultations de la notice

323