THE RELAXED-RING: A FAULT-TOLERANT TOPOLOGY FOR STRUCTURED OVERLAY NETWORKS
Abstract
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 Alima , 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 ScholarEric 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 ScholarRaphaël Collet and Peter Van Roy , Advanced Topics in Exception Handling Techniques (2006) pp. 121–140. Crossref, Google 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 , 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
- Distributed Computing 19(2), 126 (2006). Crossref, ISI, Google 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 , 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 Stoica , Chord: A scalable Peer-To-Peer lookup service for internet applications, Proceedings of the 2001 ACM SIGCOMM Conference (2001) pp. 149–160. Google Scholar


