User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Reversible phase transitions in a structured overlay network with churn

Primary tabs

Paul, Ruma R. [UCL] Van Roy, Peter [UCL] Vlassov, Vladimir [KTH Royal Institute of Technology]

Distributed applications break down when the underlying system has too many node or communication failures. In this paper, we propose a general approach to building distributed applications that lets them survive hostile conditions such as these failures. We extend an existing Structured Overlay Network (SON) that hosts a transactional replicated key/value store to be Reversible, i.e., it is able to regain its original functionality as the environment hostility recedes. For this paper we consider the environment hostility to be measured by the Churn parameter, i.e., the rate of node turnover (nodes failing and being replaced by new correct nodes). In order to describe the qualitative behavior of the SON at high churn, we introduce the concept of Phase of the SON. All nodes in a phase exhibit the same qualitative properties, which are different for the nodes in different phases. We demonstrate the existence of Phase Transitions (i.e., a significant fraction of nodes changes phase) as churn varies and show that our concept of phase is analogous to the macroscopic phase of physical systems. We empirically identify the Critical Points (i.e., when there exists more than one phase simultaneously in significant fractions of the system) observed in our experiments. We propose an API to allow the application layer to be informed about the current phase of a node.We analyze how the application layer can use this knowledge for self-adaptation, self-optimization and achieve reversibility in the application-level semantics.

Document type Communication à un colloque (Conference Paper) – Présentation orale sans comité de sélection
Access type Accès restreint
Publication date 2016
Language Anglais
Conference "International conference on networked systems, NETYS", Marrakec, Morocco (du 18/05/2016 au 20/05/2016)
Journal information "Lecture Notes in Computer Science" - Vol. 9944 LNCS, p. 318-333 (2016)
Peer reviewed yes
issn 0302-9743
e-issn 1611-3349
Publisher Springer (Heidelberg)
Publication status Publié
Affiliations UCL - SST/ICTM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Links
  1. Aberer K., Alima L.O., Ghodsi A., Girdzijauskas S., Haridi S., Hauswirth M., The Essence of P2P: A Reference Architecture for Overlay Networks, 10.1109/p2p.2005.38
  2. Aberer, K., Datta, A., Hauswirth, M.: Route maintenance overheads in DHT overlays. In: Proceedings of WDAS (2004)
  3. Aikat Jay, Kaur Jasleen, Smith F. Donelson, Jeffay Kevin, Variability in TCP round-trip times, 10.1145/948205.948241
  4. Alima, L.O., El-Ansary, S., Brand, P., Haridi, S.: DKS (n, k, f): a family of low communication, scalable and fault-tolerant infrastructures for p2p applications. In: Proceedings of CCGrid (2003)
  5. Apel, S., Böhm, K.: Self-organization in overlay networks. In: CAiSE Workshop on Adaptive and Self-Managing Enterprise Applications (ASMEA) (2005)
  6. Banaei-Kashani, F., Shahabi, C.: Criticality-based analysis and design of unstructured peer-to-peer networks as “complex systems”. In: Proceedings of CCGrid (2003)
  7. Dijkstra Edsger W., Self-stabilizing systems in spite of distributed control, 10.1145/361179.361202
  8. El-Ansary, S., Aurell, E., Brand, P., Haridi, S.: Experience with a physics-style approach for the study of self properties in structured overlay networks. In: SELF-STAR: International Workshop on Self-* Properties in Complex Information Systems (2004)
  9. El-Ansary, S., Aurell, E., Haridi, S.: A physics-inspired performance evaluation of a structured peer-to-peer overlay network. In: Proceedings of PDCN (2005)
  10. Freedman, M.J., Lakshminarayanan, K., Rhea, S., Stoica, I.: Non-transitive connectivity and DHTs. In: Proceedings of WORLDS (2005)
  11. Ghodsi, A.: Distributed k-ary system: algorithms for distributed hash tables. Ph.D. thesis, KTH, Sweden (2006)
  12. Gummadi K., Gummadi R., Gribble S., Ratnasamy S., Shenker S., Stoica I., The impact of DHT routing geometry on resilience and proximity, 10.1145/863955.863998
  13. Jelasity Márk, Babaoglu Ozalp, T-Man: Gossip-Based Overlay Topology Management, Engineering Self-Organising Systems (2006) ISBN:9783540333425 p.1-15, 10.1007/11734697_1
  14. Kong Joseph S., Bridgewater Jesse S.A., Roychowdhury Vwani P., Resilience of structured P2P systems under churn: The reachable component method, 10.1016/j.comcom.2008.01.051
  15. Krishnamurthy, S., Ardelius, J.: An analytical framework for the performance evaluation of proximity-aware structured overlays. Technical report, SICS, Sweden (2008)
  16. Krishnamurthy S., El-Ansary S., Aurell E., Haridi S., An Analytical Study of a Structured Overlay in the Presence of Dynamic Membership, 10.1109/tnet.2007.905590
  17. Krishnamurthy Supriya, El-Ansary Sameh, Aurell Erik, Haridi Seif, Comparing Maintenance Strategies for Overlays, 10.1109/pdp.2008.18
  18. Leitao Joao, Pereira Jose, Rodrigues Luis, Epidemic Broadcast Trees, 10.1109/srds.2007.27
  19. Liben-Nowell David, Balakrishnan Hari, Karger David, Analysis of the evolution of peer-to-peer systems, 10.1145/571825.571863
  20. Mejías, B.: Beernet: A relaxed approach to the design of scalable systems with self-managing behaviour and transactional robust storage. Ph.D. thesis, UCL, Belgium (2010)
  21. Paul Ruma R., Van Roy Peter, Vlassov Vladimir, Interaction between Network Partitioning and Churn in a Self-Healing Structured Overlay Network, 10.1109/icpads.2015.37
  22. Scholtes Ingo, Botev Jean, Höhfeld Alexander, Schloss Hermann, Esch Markus, Awareness-Driven Phase Transitions in Very Large Scale Distributed Systems, 10.1109/saso.2008.49
  23. Shafaat, T.M.: Partition tolerance and data consistency in structured overlay networks. Ph.D. thesis, KTH, Sweden (2013)
  24. Stoica Ion, Morris Robert, Karger David, Kaashoek M. Frans, Balakrishnan Hari, Chord : A scalable peer-to-peer lookup service for internet applications, 10.1145/383059.383071
  25. Wikipedia. Phase (matter) (2016). https://en.wikipedia.org/wiki/Phase_(matter)
Bibliographic reference Paul, Ruma R. ; Van Roy, Peter ; Vlassov, Vladimir. Reversible phase transitions in a structured overlay network with churn.International conference on networked systems, NETYS (Marrakec, Morocco, du 18/05/2016 au 20/05/2016). In: Lecture Notes in Computer Science, Vol. 9944 LNCS, p. 318-333 (2016)
Permanent URL http://hdl.handle.net/2078.1/198113