print page

SelfWISE

A Framework for Developing Self-Stabilizing Algorithms

Project Description

Fault-tolerance is an important property of massive distributed systems. The concept of self-stabilization possesses inherent tolerance against transient faults, e.g., corruption of messages or memory. Many investigations in the field of self-stabilization are mainly theoretical. The applications of evaluation under real conditions, e.g., in wireless networks, are rarely considered.

The SelfWISE framework enables wireless networks to be programmed in a self-stabilizing manner. Due to the utilization of SelfWISE the development, evaluation, and debugging of self-stabilizing algorithms are considerably facilitated. SelfWISE consists of a language for expressing self-stabilizing algorithms, a runtime environment for simulating algorithms in wireless sensor networks, and supporting tools.

By using a formal language for specifying the algorithms, low-level details are abstracted, e.g., characteristics of the wireless channel or hardware specific restrictions. Hiding these details of a wireless network enables an algorithm developer to concentrate on the algorithms itself. Since many of the self-stabilizing algorithms are developed for a serial execution, an execution under distributed control in not possible. Therefore, several transformations exist, that transforms the algorithms into a distributed version by preserving their self-stabilizing property. SelfWISE offers a simple interface for developing such transformations and to evaluate they in several scenarios for different algorithms.

Publications

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{\"o}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{\"a}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{\"o}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.

Students' theses

Completed Theses