ToleranceZone - A Fault Tolerant Middleware Idioms based on Self-Stabilizing Techniques

• Applicants: Professor Dr.-Ing. Jörg Nolte; Professor Dr. Volker Turau
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2011 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 188522762

• Final Report Year: 2019

Final Report Abstract

Ein wesentlicher Unterschied zwischen klassischen drahtgebundenen verteilten Systemen und drahtlosen low-power Sensornetzen besteht in der deutlich geringeren Zuverlässigkeit der Nachrichtenübertragung und der größeren Dynamik der Netztopologie. Klassische Fehlertoleranztechniken sind für diese Art der Netze nicht ausreichend, weil die explizite Erkennung und Behandlung aller möglichen Fehlerarten zu viele Ressourcen benötigt. Als alternativen Ansatz untersucht das Projekt deshalb Selbststabilisierende Algorithmen, bei denen Netzwerkknoten lokal auf Zustandsänderungen ihrer direkten Nachbarn reagieren, um in einen global stabilen Zustand zurückzukehren. Selbststabilisierung wurde bisher im Wesentlichen als theoretisches Konzept im Kontext fehlertoleranter verteilter Algorithmen untersucht. Dabei wurden sehr restriktive Modellannahmen getroffen, wie zum Beispiel ein gemeinsamer Speicher, global synchronisierte Schritte und eine statische Topologie. Diese Annahmen sind in drahtlosen ad-hoc Netzen nicht gegeben. Die Auswirkungen der fehlerbehafteten Kommunikation und der dynamischen Nachbarschaft auf die Stabilisierungsdauer wurden bisher nicht untersucht. Das Projekt ToleranceZone erbringt den Nachweis, dass es möglich ist, die Konvergenzzeit für eine gegebene Störungsrate den Anforderungen der Anwendung anzupassen, um so einen deutlich höheren Grad an Fehlertoleranz ohne wesentliche Laufzeiteinbußen zu erreichen. Der Fokus liegt dabei auf grundlegenden Mustern der Datenaggregation und -reduktion, Nachbarschaftsverwaltung und Gruppenkommunikation. Zusammengefasst sind die Kernergebnisse des Projekts: 1. Selbststabilisierende Algorithmen für synchrone statische Netze lassen sich effizient auf asynchrone verteilte ad-hoc Netze transformieren. 2. Durch das Einspeisen von Verbindungsaufzeichnungen aus realen Netzen in deterministische Simulationen wurde es möglich, reproduzierbare und vergleichbare Experimente unter realistischen Netzbedingungen durchzuführen. 3. Um Konvergenz praktisch zu erreichen, ist eine Dämpfung der natürlichen Fluktuationen in der Funknachbarschaft zwingend notwendig. Dies kann durch eine selbststabilisierende Nachbarschaftstopologie, die Verbindungen mit geringer Qualität ausblendet, erreicht werden. 4. Selbststabilisierende Algorithmen erlauben die Umsetzung skalierbarer dynamischer Publish-Subscribe Gruppen mit Routing-Unterstützung für Multicasts an Gruppenmitglieder, sowie Routing-Strukturen für die Datenaggregation. 5. TDMA Zeitscheiben basierend auf einer simplen selbststabilisierenden Uhrensynchronisation reduzieren effektiv Kollisionen, Idle Listening und Overhearing bei gleichzeitiger signifikanter Verbesserung der Energieeffizienz. 6. Mit selbststabilisierenden Algorithmen können kompakte Routing-Strukturen für Publish-Subscribe Systeme sehr effizient in sub-linearer Zeit erstellt werden. 7. Randomisierte verteilte Algorithmen lassen sich in vielen Fällen leicht erweitern, so dass sie die Eigenschaft der Selbststabilisierung haben.

Publications

• Link stability in a wireless sensor network - an experimental study. In Proc. 3rd Int. Conf. on Sensor Systems and Software, 2012
  S. Lohs, R. Karnapke, and J. Nolte
  
• Self-stabilizing sensor networks for emergency management. In PerCom-WORKSHOPS 2012:2012 IEEE International Conference on Pervasive Computing and Communications Workshops, pages 721 - 726. IEEE Computer Society, March 2012
  S. Lohs, R. Karnapke, J. Nolte, and A. Lagemann
  
• Agile and stable neighborhood protocol for wireless sensor networks. In 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS’13), Japan, 2013
  G. Siegemund, V. Turau, C. Weyer, S. Lohs, and J. Nolte
  
• A dynamic topology control algorithm for wireless sensor networks. In Proceedings of the International Conference on Ad-hoc, Mobile and Wireless Networks. ADHOC-NOW 2015, pages 3-18, June 2015
  G. Siegemund, V. Turau, and Ch. Weyer
  
• Self-stabilizing structures for data gathering in wireless sensor networks. In Proceedings of the International Conference on Sensor Technologies and Applications, Sensorcomm, pages 1-8, Venice, Italy, August 2015
  S. Beyer, S. Lohs, J. Nolte, R. Karnapke, and G. Siegemund
  
• Influence of topology-fluctuations on self-stabilizing algorithms. In 2016 International Conference on Distributed Computing in Sensor Systems (DCOSS), pages 122-124, May 2016
  S. Lohs, G. Siegemund, J. Nolte, and V. Turau
  
• Self-stabilization - a mechanism to make networked embedded systems more reliable? In 2016 IEEE 35th Symposium on Reliable Distributed Systems (SRDS), pages 317-326, Sep. 2016
  S. Lohs, J, Nolte, G. Siegemund, and V. Turau
  
• Computing the fault-containment-time of self-stabilizing algorithms using markov chains and lumping. In Stabilization, Safety, and Security of Distributed Systems - 19th International Symposium(SSS 2017), pages 62-77, November 2017
  V. Turau
  
• Scalable routing for topic-based publish/subscribe systems under fluctuations. In Proceedings of International Conference on Distributed Computing Systems - ICDCS 2017, pages 1608-1617, June 2017
  V. Turau and G. Siegemund
  
• A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time. In Lecture Notes in Computer Science - Proceedings of 25th International Colloquium on Structural Information and Communication Complexity (Scirocco 2018), pages 72-87, June 2018
  V. Turau
  
• A O(log n) Distributed Algorithm to Construct Routing Structures for Pub/Sub Systems. In 20th International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS2018), pages 65-79, November 2018
  V. Turau
  
• A self-stabilizing publish/subscribe middleware for loT applications. ACM Transactions on Cyber-Physical Systems (TCPS), 2, Issue 2, Article 12:1-12, June 2018
  G. Siegemund and V. Turau
  
• Computing fautt-containment times of self-stabilizing algorithms using lumped markov chains. Algorithms, 11(58), May 2018
  V. Turau
  
• Concurrent distributed serving with mobile servers. In Proceedings of The 30th International Symposium on Algorithms and Computation (ISAAC 2019), December 2019
  A. Ghodselahi, F. Kuhn, and V. Turau
  
• Self-stabilizing randomized algorithms. In Lecture Notes in Computer Science - Proceedings of 26th International Colloquium on Structural Information and Communication Complexity (Scirocco 2019), pages 309-324, July 2019
  V. Turau