print page

Project Work

Emperical Evalutation of Fault-Containing Self-Stabilizing Algorithms

A self-stabilizing distributed system reaches a legitimate state from any arbitrary initial state and without any external intervention. That makes self-stabilization an elegant approach for non-masking fault-tolerance. Every faulty state is simply understood as another initial state of the system. Inspite their theoretical nature, self-stabilizing algorithms can be adapted to distributed systems like wireless sensor networks. For example, they can be used for establishing spanning trees for packet routing.

It may happen that some nodes are affected by a fault, for example memory corruption. A self- stabilizing algorithm will reach a legitimate state again without any external intervention. But gener- ally speaking, self-stabilizing algorithms do not always recover very quickly from such faults. Instead, the algorithm’s behaviour causes the fault to spread to neighboring nodes (contamination) and it takes a rather long time until the system reaches a ligitimate state again. In the example above, a broken spanning will lead to data loss and so a quick recovery is very desirable.

The class of fault-containing algorithms deals with that problem. These algorithms recognize and repair faults in very little time and in fact, every self-stabilizing algorithm may be transformed into a fault-containing self-stabilizing algorithm.

The goal of this Bachelor Thesis is the emperical evaluation of the fault-containment properties of existing self-stabilizing algorithms and transformers. This includes (but is not limited to) the metrics containment time, contamination number and fault-gap. To do so, a simulator is to be developed, that implements the theoretical model of computation commonly used in self-stabilization. Furthermore, a model for fault-injection has to be implemented. The simulation software can be written in Java or C++.

Start date 8. April 2010
End date 30. September 2010
Documents Flyer
Supervisor Dr. rer. nat. Sven Köhler