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.

THE RELAXED-RING: A FAULT-TOLERANT TOPOLOGY FOR STRUCTURED OVERLAY NETWORKS

    Fault-tolerance and lookup consistency are considered crucial properties for building applications on top of structured overlay networks. Many of these networks use the ring topology for the organization or their peers. The network must handle multiple joins, leaves and failures of peers while keeping the connection between every pair of successor-predecessor correct. This property makes the maintenance of the ring very costly and temporarily impossible to achieve, requiring periodic stabilization for fixing the ring. We introduce the relaxed-ring topology that does not rely on a perfect successor-predecessor relationship and it does not need a any periodic maintenance. Leaves and failures are considered as the same type of event providing a fault-tolerant and self-organizing maintenance of the ring. Relaxed-ring's limitations with respect to failure handling are formally identified, providing strong guarantees to develop applications on top of the architecture. Besides permanent failures, the paper analyses temporary failures and false suspicions caused by broken links, which are often ignored.

    References

    • PlanetLab. http://www.planet-lab.org, 2008 . Google Scholar
    • Luc Onana Alimaet al., Dks (n, k, f): A family of low communication, scalable and fault-tolerant infrastructures for p2p applications, CCGRID '03: Proceedings of the 3st International Symposium on Cluster Computing and the Grid (IEEE Computer Society, 2003) p. 344. Google Scholar
    • Eric A. Brewer, Towards robust distributed systems (abstract), PODC '00: Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing (ACM Press, 2000) p. 7. Google Scholar
    • Raphaël Collet and Peter Van Roy, Advanced Topics in Exception Handling Techniques (2006) pp. 121–140. CrossrefGoogle Scholar
    • DistOz Group. P2PS: A peer-to-peer networking library for Mozart-Oz. http://p2ps.info.ucl.ac.be, 2008 . Google Scholar
    • Ali Ghodsi. Distributed k-ary System: Algorithms for Distributed Hash Tables. PhD dissertation, KTH — Royal Institute of Technology, Stockholm, Sweden, December 2006 . Google Scholar
    • R.   Gummadi et al. , The impact of dht routing geometry on resilience and proximity ( 2003 ) . Google Scholar
    • Xiaozhou Li, Jayadev Misra, and C. Greg Plaxton. Active and concurrent topology maintenance. In DISC, pages 320-334, 2004 . Google Scholar
    • Xiaozhou Li, Jayadev Misra and C. Greg Plaxton, Distributed Computing 19(2), 126 (2006). Crossref, ISIGoogle Scholar
    • Boris Mejías. CiNiSMO: Concurrent Network Simulator in Mozart-Oz, Université catholiquc de Louvain, Belgium, http://p2ps.info.ucl.ac.be/cinismo, 2008 . Google Scholar
    • Boris   Mejías and Peter   Van Roy , A relaxed-ring for self-organising and fault-tolerant peer-to-peer networks , XXVI International Conference of the Chilean Computer Science Society ( IEEE Computer Society , 2007 ) . Google Scholar
    • Monika   Moser and Seif   Haridi , Atomic commitment in transactional dhts , Proceedings of the CoreGRID Symposium , CoreGRID series ( Springer , 2007 ) . Google Scholar
    • Mozart Community. The Mozart-Oz programming system. http://www.mozartoz.org, 2008 . Google Scholar
    • Tallat M.   Shafaat et al. , Key-Based Consistency and Availability in Structured Overlay Networks , Proceedings of the 3rd International ICST Conference on Scalable Information Systems (Infoscale'08) ( ACM , 2008 ) . Google Scholar
    • Ion Stoicaet al., Chord: A scalable Peer-To-Peer lookup service for internet applications, Proceedings of the 2001 ACM SIGCOMM Conference (2001) pp. 149–160. Google Scholar