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 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.
This work was developed with financial support from the ANR (Agence Nationale de la Recherche) through the LEGO project referenced ANR-05-CIGC-11. An early version of this work was published in [8].
References
J. Aspnes and G. Shah , Skip Graphs, Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2003) pp. 384–393. Google Scholar-
S. Basu , NodeWiz: Peer-to-Peer Resource Discovery for Grids , 5th International Workshop on Global and Peer-to-Peer Computing (GP2PC) . Google Scholar D. Bein , A. K. Datta and V. Villain , Snap-Stabilizing Optimal Binary Search Tree, Proceedings of the 7th International Symposium on Self-Stabilizing Systems (SSS '05) (2005) pp. 1–17. Google ScholarA. Bui , State-Optimal Snap-Stabilizing PIF in Tree Networks, Proceedings of the 4th International Workshop on Self-Stabilizing Systems (1999) pp. 78–85. Google Scholar- Distributed Computing 20(1), 3 (2007). ISI, Google Scholar
F. Cappello , Grid'5000: a Large Scale, Reconfigurable, Controlable and Monitorable Grid Platform, SC'05: Proc. The 6th IEEE/ACM International Workshop on Grid Computing Grid'2005 pp. 99–106. Google Scholar-
E. Caron , A Repair Mechanism for Tree-structured Peer-to-peer Systems , HiPC 2006 ,LNCS . Google Scholar -
E. Caron , Snap-Stabilizing Prefix Tree for Peer-to-peer Systems , SSS 2007 ( Springer Verlag , Berlin Heidelberg , 2007 ) . Google Scholar E. Caron , F. Desprez and C. Tedeschi , A Dynamic Prefix Tree for the Service Discovery Within Large Scale Grids, P2P2006 (IEEE, Cambridge, UK.) pp. 106–113. Google ScholarEddy Caron , Self-Stabilization in Tree-Structured P2P Service Discovery Systems, 27th International Symposium on Reliable Distributed Systems (SRDS 2008), IEEE Computer Society (IEEE, Napoli, Italy, 2008) pp. 207–216. Google Scholar-
A. Datta , Range Queries in Trie-Structured Overlays , The Fifth IEEE International Conference on Peer-to-Peer Computing . Google Scholar - S Delaët, S Devismes, M Nesterenko and S Tixeuil. Snap-Stabilization in Message-Passing Systems. In 10th International Conference on Distributed Computing and Networking (ICDCN'09), number 5408 in LNCS, pages 281–286, 2009 . Google Scholar
- Commun. ACM 17(11), 643 (1974), DOI: 10.1145/361179.361202. Crossref, ISI, Google Scholar
-
S. Dolev , Self-Stabilization ( The MIT Press , 2000 ) . Crossref, Google Scholar - ACM Trans. Math. Softw. 16(1), 1 (1990), DOI: 10.1145/77626.79170. Crossref, ISI, Google Scholar
-
T. Herault , A model for large scale self-stabilization , 21th International Parallel and Distributed Processing Symposium (IPDPS 2007) . Google Scholar T. Herman and T. Masuzawa , A Stabilizing Search Tree with Availability Properties, Proceedings of the 5th International Symposium on Autonomous Decentralized Systems (ISADS'01) (2001) pp. 398–405. Google Scholar- Information Processing Letters 77, 115 (2001), DOI: 10.1016/S0020-0190(00)00208-8. Crossref, ISI, Google Scholar
A. Iamnitchi and I. Foster , On Death, Taxes, and the Convergence of Peer-to-Peer and Grid Computing, IPTPS (2003) pp. 118–128. Google Scholar-
D. Oppenheimer , Distributed Resource Discovery on PlanetLab with SWORD , Proceedings of the ACM/USENIX Workshop on Real, Large Distributed Systems (WORLDS) . Google Scholar -
S. Ramabhadran , Prefix Hash Tree An indexing Data Structure over Distributed Hash Tables , Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing . Google Scholar -
S. Ratnasamy , A Scalable Content-Adressable Network , ACM SIGCOMM . Google Scholar -
A. Rowstron and P. Druschel , Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-To-Peer Systems , International Conference on Distributed Systems Platforms (Middleware) . Google Scholar - IEEE Internet Computing 8(3), 19 (2004), DOI: 10.1109/MIC.2004.1297269. Crossref, Google Scholar
-
Y. Shu , Supporting Multi-Dimensional Range Queries in Peer-to-Peer Systems , Peer-to-Peer Computing ( 2005 ) . Google Scholar -
I. Stoica , Chord: A Scalable Peer-to-Peer Lookup service for Internet Applications , ACM SIGCOMM . Google Scholar


