print page

Self-Stabilizing Systems

Contact Prof. Dr. rer. nat. Volker Turau
Staff Christian Renner
Gerry Siegemund
Andreas Weigel
Christoph Weyer

Project Description

A distributed system is self-stabilizing, if it returns to a legitimate state regardless of the initial state and remains in a legitimate state until a fault occurs. Self-stabilization is a non-masking approach to fault-tolerance. In this institute we analyse self-stabilizing algorithms with respect to their efficiency, behaviour in case of a fault and create tools that support the development of such algorithms.

Subprojects

Publications

Sven Köhler and Volker Turau. Space-efficient fault-containment in dynamic networks. In Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'11), Springer, October 2011, pp. 311–325. Grenoble, France.
[BibTeX] [Abstract] [DOI]
@InProceedings{Telematik_KT_SSS11, author = {Sven Köhler and Volker Turau}, title = {Space-efficient fault-containment in dynamic networks}, booktitle = {Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'11)}, pages = {311-325}, series = {Lecture Notes in Computer Science}, volume = {6976}, publisher = {Springer}, day = {10-12}, month = oct, year = 2011, location = {Grenoble, France}, }
Abstract: Bounding the impact of transient small-scale faults by self-stabilizing protocols has been pursued with independent objectives: Optimizing the system's reaction upon topological changes (e.g. super-stabilization), and reducing system recovery time from memory corruptions (e.g. fault-containment). Even though transformations adding either super-stabilization or fault-containment to existing protocols exists, none of them preserves the other. This paper makes a first attempt to combine both objectives. We provide a transformation adding fault-containment to silent self-stabilizing protocols while simultaneously preserving the property of self-stabilization and the protocol's behavior in face of topological changes. In particular, the protocol's response to a topology change remains unchanged even if a memory corruption occurs in parallel to the topology change. The presented transformation increases the memory footprint only by a factor of 4 and adds O(1) bits per edge. All previously known transformations for fault-containing self-stabilization increase the memory footprint by a factor of 2m/n.
Volker Turau and Bernd Hauck. A new Analysis of a Self-Stabilizing Maximum Weight Matching Algorithm with Approximation Ratio 2. Theoretical Computer Science, 412(40):5527–5540, September 2011. Stabilization, Safety and Security.
[BibTeX] [Abstract] [DOI]
@Article{Telematik_HT_2010_TCS_Matching, author = {Volker Turau and Bernd Hauck}, title = {A new Analysis of a Self-Stabilizing Maximum Weight Matching Algorithm with Approximation Ratio 2}, pages = {5527-5540}, journal = {Theoretical Computer Science}, volume = {412}, number = {40}, month = sep, year = 2011, keywords = {Self-stabilizing algorithms, approximation algorithm, weighted matching, distributed algorithms}, issn = {0304-3975}, note = {Stabilization, Safety and Security}, }
Abstract: The maximum weight matching problem is a fundamental problem in graph theory with a variety of important applications. Recently Manne and Mjelde presented the first self-stabilizing algorithm computing a 2-approximation of the optimal solution. They established that their algorithm stabilizes after O(2^n) (resp. O(3^n)) moves under a central (resp. distributed) scheduler. This paper contributes a new analysis improving these bounds considerably. In particular it is shown that the algorithm stabilizes after O(nm) moves under the central scheduler and that a modified version of the algorithm also stabilizes after O(nm) moves under the distributed scheduler. The paper presents a new proof technique based on graph reduction to analyze the complexity of self-stabilizing algorithms.
Christian Renner, Sebastian Ernst, Christoph Weyer and Volker Turau. Prediction Accuracy of Link-Quality Estimators. In Proceedings of the 8th European Conference on Wireless Sensor Networks (EWSN'11), February 2011. Bonn, Germany. Acceptance rate 20%.
[BibTeX] [Abstract] [PDF]
@InProceedings{Telematik_REWT_HoPS, author = {Christian Renner and Sebastian Ernst and Christoph Weyer and Volker Turau}, title = {Prediction Accuracy of Link-Quality Estimators}, booktitle = {Proceedings of the 8th European Conference on Wireless Sensor Networks (EWSN'11)}, day = {23-25}, month = feb, year = 2011, location = {Bonn, Germany}, note = {Acceptance rate 20%}, }
Abstract: The accuracy of link-quality estimators (LQE) is mission-critical in many application scenarios in wireless sensor networks (WSN), since the link-quality metric is used for routing decisions or neighborhood formation. Link-quality estimation must offer validity for different timescales. Existing LQEs describe and approximate the current quality in a single value only. This method leads to a limited accuracy and expressiveness about the presumed future behavior of a link. The LQE developed in this paper incorporates four quality metrics that give a holistic assessment of the link and its dynamic behavior; therefore, this research is an important step to achieving a higher prediction accuracy including knowledge about the short- and long-term behavior.
Sven Köhler and Volker Turau. Fault-containing self-stabilization in asynchronous systems with constant fault-gap. Distributed Computing, 2011.
[BibTeX] [DOI]
@Article{Telematik_KT_2011_DC, author = {Sven Köhler and Volker Turau}, title = {Fault-containing self-stabilization in asynchronous systems with constant fault-gap}, journal = {Distributed Computing}, year = 2011, issn = {0178-2770}, }
Volker Turau and Bernd Hauck. A fault-containing self-stabilizing (3 - 2/(Delta+1))-approximation algorithm for vertex cover in anonymous networks. Theoretical Computer Science, 412(33):4361–4371, 2011.
[BibTeX] [Abstract] [DOI]
@Article{Telematik_HT_2011_TCSVC, author = {Volker Turau and Bernd Hauck}, title = {A fault-containing self-stabilizing (3 - 2/(Delta+1))-approximation algorithm for vertex cover in anonymous networks}, pages = {4361-4371}, journal = {Theoretical Computer Science}, volume = {412}, number = {33}, year = 2011, keywords = {Self-stabilizing algorithms, Fault tolerance, Distributed algorithms, Graph algorithms}, }
Abstract: The non-computability of many distributed tasks in anonymous networks is well known. This paper presents a deterministic self-stabilizing algorithm to compute a 3 - (2 / (Delta+1))-approximation of a minimum vertex cover in anonymous networks. The algorithm operates under the distributed unfair scheduler, stabilizes after O(n+m) moves respectively O(Delta) rounds, and requires O(log n) storage per node. Recovery from a single fault is reached within a constant time and the contamination number is O(Delta). For trees the algorithm computes a 2-approximation of a minimum vertex cover.
Sven Köhler and Volker Turau. A new Technique for proving Self-Stabilization under the Distributed Scheduler. In Proceedings of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'10), Springer, September 2010, pp. 65–79. New York, NY, USA.
[BibTeX] [Abstract] [DOI] [PDF]
@InProceedings{Telematik_KT_ProofTechnique, author = {Sven Köhler and Volker Turau}, title = {A new Technique for proving Self-Stabilization under the Distributed Scheduler}, booktitle = {Proceedings of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'10)}, pages = {65-79}, series = {Lecture Notes in Computer Science}, volume = {6366}, publisher = {Springer}, day = {20-22}, month = sep, year = 2010, location = {New York, NY, USA}, }
Abstract: Proving stabilization of a complex algorithm under the distributed scheduler is a non-trivial task. This paper introduces a new method which allows to extend proofs for the central scheduler to the distributed scheduler. The practicability of the method is shown by applying it to two existing algorithms, for which stabilization under the distributed scheduler was an open problem.
Sven Köhler and Volker Turau. Fault-containing self-stabilization in asynchronous systems with constant fault-gap. In Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS'10), IEEE Computer Society, June 2010, pp. 418–427. Genoa, Italy.
[BibTeX] [Abstract] [DOI] [PDF]
@InProceedings{Telematik_KT_FaultContain, author = {Sven Köhler and Volker Turau}, title = {Fault-containing self-stabilization in asynchronous systems with constant fault-gap}, booktitle = {Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS'10)}, pages = {418-427}, publisher = {IEEE Computer Society}, day = {21-25}, month = jun, year = 2010, location = {Genoa, Italy}, }
Abstract: This paper presents a new transformation which adds fault-containment properties to any silent self-stabilizing protocol. The transformation features a constant slow-down factor and the fault-gap – that is the minimal time between two containable faults – is constant. The transformation scales well to arbitrarily large systems and avoids global synchronization.
Volker Turau. Self-Stabilizing Vertex Cover in Anonymous Networks with Optimal Approximation Ratio. Parallel Processing Letters, 20(2):173–186, 2010.
[BibTeX] [DOI]
@Article{Telematik_T_2010_PPL, author = {Volker Turau}, title = {Self-Stabilizing Vertex Cover in Anonymous Networks with Optimal Approximation Ratio}, pages = {173-186}, journal = {Parallel Processing Letters}, volume = {20}, number = {2}, year = 2010, }
Volker Turau and Bernd Hauck. A Self-Stabilizing Approximation Algorithm for Vertex Cover in Anonymous Networks. In Proceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'09), Springer, November 2009, pp. 341–353. Lyon, France.
[BibTeX] [Abstract] [DOI]
@InProceedings{Telematik_HT_2009_VC, author = {Volker Turau and Bernd Hauck}, title = {A Self-Stabilizing Approximation Algorithm for Vertex Cover in Anonymous Networks}, booktitle = {Proceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'09)}, pages = {341-353}, series = {Lecture Notes in Computer Science}, volume = {5873}, publisher = {Springer}, day = {3-6}, month = nov, year = 2009, location = {Lyon, France}, }
Abstract: This paper presents a deterministic self-stabilizing algorithm that computes a 3-approximation vertex cover in anonymous networks. It reaches a legal state after O(n+m) moves or 2n + 1 rounds respectively and recovers from a single fault within a constant containment time. The contamination number is 2 Delta + 1. An enhanced version of this algorithm achieves a 2-approximation on trees.
Andreas Lagemann, Jörg Nolte, Christoph Weyer and Volker Turau. Mission Statement: Applying Self-Stabilization to Wireless Sensor Networks. In Proceedings of the 8th GI/ITG KuVS Fachgespräch "Drahtlose Sensornetze" (FGSN'09), August 2009, pp. 47–49. Hamburg, Germany.
[BibTeX] [Abstract] [PDF]
@InProceedings{Telematik_LNWT_2009_SelfWISE, author = {Andreas Lagemann and Jörg Nolte and Christoph Weyer and Volker Turau}, title = {Mission Statement: Applying Self-Stabilization to Wireless Sensor Networks}, booktitle = {Proceedings of the 8th GI/ITG KuVS Fachgespräch "Drahtlose Sensornetze" (FGSN'09)}, pages = {47-49}, day = {13-14}, month = aug, year = 2009, location = {Hamburg, Germany}, }
Abstract: Long living and unattended deployments of wireless sensor networks requires fault-tolerant solutions. Self-stabilizing algorithms are providing these properties in an elegant and verifiable way. Recently, a lot of research has been performed to determine appropriate means to apply these promising technique to wireless sensor networks. In this paper the current state of the art in this field is given. Additionally, three major challenges are presented for achieving self-stabilizing sensor networks.
Christoph Weyer, Volker Turau, Andreas Lagemann and Jörg Nolte. Programming Wireless Sensor Networks in a Self-Stabilizing Style. In Proceedings of the Third International Conference on Sensor Technologies and Applications (SENSORCOMM'09), June 2009. Athens, Greece.
[BibTeX] [Abstract] [Slides]
@InProceedings{Telematik_WLT_2009_SelfWISE, author = {Christoph Weyer and Volker Turau and Andreas Lagemann and Jörg Nolte}, title = {Programming Wireless Sensor Networks in a Self-Stabilizing Style}, booktitle = {Proceedings of the Third International Conference on Sensor Technologies and Applications (SENSORCOMM'09)}, day = {18-23}, month = jun, year = 2009, location = {Athens, Greece}, }
Abstract: Wireless Sensor Networks (WSNs) operate in an unstable environment and thus are subject to arbitrary transient faults. Self-stabilization is a promising technique to add tolerance against transient faults in a self-contained non-masking way. A core factor for the applicability of a given self-stabilizing algorithm is its convergence time. This paper analyses the average stabilization time of three algorithms commonly regarded as central building blocks for WSNs. The analysis is accomplished with SelfWISE, a framework providing programming abstractions for selfstabilizing algorithms. The performed analysis considers the target models as well as network size and density. This demonstrates the usability of SelfWISE for evaluating selfstabilizing algorithms under a wide range of models.
Christoph Weyer and Volker Turau. SelfWISE: A Framework for Developing Self-Stabilizing Algorithms. In Proceedings of the 16th ITG/GI - Fachtagung Kommunikation in Verteilten Systemen (KiVS'09), March 2009, pp. 67–78. Kassel, Germany.
[BibTeX] [Abstract] [Slides]
@InProceedings{Telematik_TW_2009_SelfWISE, author = {Christoph Weyer and Volker Turau}, title = {SelfWISE: A Framework for Developing Self-Stabilizing Algorithms}, booktitle = {Proceedings of the 16th ITG/GI - Fachtagung Kommunikation in Verteilten Systemen (KiVS'09)}, pages = {67-78}, day = {2-6}, month = mar, year = 2009, location = {Kassel, Germany}, }
Abstract: This paper introduces SelfWISE, a framework for enabling wireless sensor networks to be programmed in a self-stabilizing manner. The framework eases the formal specification of algorithms by abstracting from low-level details such as wireless channel and hardwarespecific characteristics. SelfWISE consists of a language for expressing self-stabilizing algorithms, a runtime environment for simulating algorithms in wireless sensor networks, and supporting tools. The hereby applied transformation of formally described algorithms into the simulation environment preserves the self-stabilizing properties. Development, evaluation, and debugging of self-stabilizing algorithms is considerably facilitated by utilizing SelfWISE.
Volker Turau and Bernd Hauck. A Self-Stabilizing Algorithm for Constructing Weakly Connected Minimal Dominating Sets. Information Processing Letters, 109(14):763–767, 2009.
[BibTeX] [Abstract] [DOI]
@Article{Telematik_HT_2009_WCMDS, author = {Volker Turau and Bernd Hauck}, title = {A Self-Stabilizing Algorithm for Constructing Weakly Connected Minimal Dominating Sets}, pages = {763-767}, journal = {Information Processing Letters}, volume = {109}, number = {14}, year = 2009, keywords = {Self-stabilizing algorithms, Fault tolerance, Distributed algorithms, Graph algorithms}, issn = {0020-0190}, }
Abstract: This paper presents a new distributed self-stabilizing algorithm for the weakly connected minimal dominating set problem. It assumes a self-stabilizing algorithm to compute a breadth-first tree. Using an unfair distributed scheduler the algorithm stabilizes in at most O(nmA) moves, where A is the number of moves to construct a breadth-first tree. All previously known algorithms required an exponential number of moves.
Volker Turau and Christoph Weyer. Fault Tolerance in Wireless Sensor Networks through Self-Stabilization. International Journal of Communication Networks and Distributed Systems, 2(1):78–98, 2009.
[BibTeX] [Abstract] [DOI]
@Article{Telematik_TW_2009_SelfStabilization, author = {Volker Turau and Christoph Weyer}, title = {Fault Tolerance in Wireless Sensor Networks through Self-Stabilization}, pages = {78-98}, journal = {International Journal of Communication Networks and Distributed Systems}, volume = {2}, number = {1}, year = 2009, }
Abstract: Wireless sensor networks (WSNs) suffer from resource limitations, high failure rates and faults caused by the lossy nature of wireless communication. This can lead to situations, where nodes lose synchrony and programs reach arbitrary states. Traditional approaches to fault tolerance like fault masking or global resets are not feasible for WSNs. Applying the concepts of self-stabilisation to achieve fault tolerance is a promising concept. However, the majority of self-stabilising algorithms found in the literature is based on models not suitable for WSNs. This paper proposes a problem-independent transformation for algorithms that stabilise under the central daemon scheduler such that they meet the demands of a WSN. Furthermore, a comparison with transformers from the literature is made through a series of simulations. Finally, the proposed transformer is evaluated with a real sensor network in a field test.
Bernd Hauck. Worst-Case Analysis of a Self-Stabilizing Algorithm Computing a Weakly Connected Minimal Dominating Set. Technical Report urn:nbn:de:gbv:830-tubdok-5126, Hamburg University of Technology, Hamburg, Germany, October 2008.
[BibTeX] [Abstract] [PDF]
@TechReport{Telematik_Hauck_2008_WorstCaseSelfStabilizingWeaklyConnectedMDSet, author = {Bernd Hauck}, title = {Worst-Case Analysis of a Self-Stabilizing Algorithm Computing a Weakly Connected Minimal Dominating Set}, number = {urn:nbn:de:gbv:830-tubdok-5126}, institution = {Hamburg University of Technology}, address = {Hamburg, Germany}, month = oct, year = 2008, }
Abstract: Recently, Srimani and Xu presented a self-stabilizing algorithm that computes a weakly connected minimal dominating set. They prove an upper bound of O(2^n) until stabilization but they do not provide a lower bound. This paper verifies by giving an example that their algorithm indeed requires O(2^n) moves on a certain graph.
Volker Turau. Linear Self-Stabilizing Algorithms for the Independent and Dominating Set Problems using an Unfair Distributed Scheduler. Information Processing Letters., 103(3):88–93, July 2007.
[BibTeX] [Abstract] [DOI] [PDF]
@Article{Telematik_TT_2007_Selfstabilizing, author = {Volker Turau}, editor = {A. Tarlecki}, title = {Linear Self-Stabilizing Algorithms for the Independent and Dominating Set Problems using an Unfair Distributed Scheduler}, pages = {88-93}, journal = {Information Processing Letters.}, volume = {103}, number = {3}, month = jul, year = 2007, }
Abstract: This paper presents distributed self-stabilizing algorithms for the maximal independent and the minimal dominating set problems. Using an unfair distributed scheduler the algorithms stabilizes in at most max{3n-5,2n} resp. 9n moves. All previously known algorithms required O(n2) moves.
Volker Turau and Christoph Weyer. Randomized Self-stabilizing Algorithms for Wireless Sensor Networks. In Proceedings of the First International Workshop on Self-Organizing Systems (IWSOS'06), September 2006, pp. 74–89. Passau, Germany.
[BibTeX] [Abstract] [DOI] [PDF] [Slides]
@InProceedings{Telematik_TW_2006_RandomizedSelfStabilizing, author = {Volker Turau and Christoph Weyer}, title = {Randomized Self-stabilizing Algorithms for Wireless Sensor Networks}, booktitle = {Proceedings of the First International Workshop on Self-Organizing Systems (IWSOS'06)}, pages = {74-89}, day = {18-20}, month = sep, year = 2006, location = {Passau, Germany}, }
Abstract: Wireless sensor networks (WSNs) pose challenges not present in classical distributed systems: resource limitations, high failure rates, and ad hoc deployment. The lossy nature of wireless communication can lead to situations, where nodes lose synchrony and programs reach arbitrary states. Traditional approaches to fault tolerance like replication or global resets are not feasible. In this work, the concept of self-stabilization is applied to WSNs. The majority of self-stabilizing algorithms found in the literature is based on models not suitable for WSNs: shared memory model, central daemon scheduler, unique processor identifiers, and atomicity. This paper proposes problem-independent transformations for algorithms that stabilize under the central daemon scheduler such that they meet the demands of a WSN. The transformed algorithms use randomization and are probabilistically self-stabilizing. This work allows to utilize many known self-stabilizing algorithms in WSNs. The proposed transformations are evaluated using simulations and a real WSN.

Students' theses

Completed Theses