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
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
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 : mardi 16 janvier 2018 - 14:49:35

Identifiants

  • HAL Id : hal-01429571, version 1

Collections

Citation

Eddy Caron, Frédéric Desprez, Franck Petit, Cédric Tedeschi. Snap-stabilizing Prefix Tree for Peer-to-peer Systems. 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. 〈hal-01429571〉

Partager

Métriques

Consultations de la notice

291