World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

SNAP-STABILIZING PREFIX TREE FOR PEER-TO-PEER SYSTEMS

    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 et al. , 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 Scholar
    • A. Buiet al., State-Optimal Snap-Stabilizing PIF in Tree Networks, Proceedings of the 4th International Workshop on Self-Stabilizing Systems (1999) pp. 78–85. Google Scholar
    • A Buiet al., Distributed Computing 20(1), 3 (2007). ISIGoogle Scholar
    • F. Cappelloet al., 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 et al. , A Repair Mechanism for Tree-structured Peer-to-peer Systems , HiPC 2006 , LNCS . Google Scholar
    • E.   Caron et al. , 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 Scholar
    • Eddy Caronet al., 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 et al. , 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
    • E. W. Dijkstra, Commun. ACM 17(11), 643 (1974), DOI: 10.1145/361179.361202. Crossref, ISIGoogle Scholar
    • S.   Dolev , Self-Stabilization ( The MIT Press , 2000 ) . CrossrefGoogle Scholar
    • J. J. Dongarraet al., ACM Trans. Math. Softw. 16(1), 1 (1990), DOI: 10.1145/77626.79170. Crossref, ISIGoogle Scholar
    • T.   Herault et al. , 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
    • T. Herman and T. Masuzawa, Information Processing Letters 77, 115 (2001), DOI: 10.1016/S0020-0190(00)00208-8. Crossref, ISIGoogle 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 et al. , Distributed Resource Discovery on PlanetLab with SWORD , Proceedings of the ACM/USENIX Workshop on Real, Large Distributed Systems (WORLDS) . Google Scholar
    • S.   Ramabhadran et al. , 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 et al. , 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
    • C. Schmidt and M. Parashar, IEEE Internet Computing 8(3), 19 (2004), DOI: 10.1109/MIC.2004.1297269. CrossrefGoogle Scholar
    • Y.   Shu et al. , Supporting Multi-Dimensional Range Queries in Peer-to-Peer Systems , Peer-to-Peer Computing ( 2005 ) . Google Scholar
    • I.   Stoica et al. , Chord: A Scalable Peer-to-Peer Lookup service for Internet Applications , ACM SIGCOMM . Google Scholar