Selbst-stabilisierende Algorithmen Universität Potsdam, Sommersemester 2010

Sprechstunden:

Hinweis:

Die Themen und Termine stehen nun bereit.

Zielgruppe:

Bachelor, Master, Diplom

Voraussetzung:

Vorlesungen „Grundlagen Betriebssysteme und Rechnernetze“, „Verteilte Systeme“

Vorlesungssprache:

Deutsch

Umfang:

Seminar (2 SWS)

Informatikfachzuordnung:

Theoretische Informatik
Praktische Informatik

Leistungspunkte:

3 Leistungspunkte

Anforderungen:

Vortrag und Ausarbeitung

Zeit und Ort:

		Do	12:15–13:45 Uhr	03.04.1.02

Beginn:

	22. April 2010

Belegung:

Die Belegung erfolgt elektronisch entsprechend den Bestimmungen des Instituts für Informatik.

Aktuelle Informationen

23.07.2010 Der Raum für das Blockseminar am 23.9.2010 lautet 1.02.
09.04.2010 Auflistung der Themen und Termine
09.04.2010 Auflistung der Themen und Termine
31.03.2010 Ankündigung des Seminars

Inhaltsübersicht

Aus der Einführung zu „Self-Stabilization“ von Shlomi Dolev:

The self-stabilization paradigm was introduced by Edsger W. Dijkstras in 1973. A self-stabilizing system is a system that can automatically recover following the occurence of (transient) faults. The idea is to design systems that can be started in an arbitrary state and still converge to a desired behavior. The occurence of faults can cause the system to reach an arbitrary state. Self-stabilizing systems that experience faults recover automatically from such faults, since they are designed to start in an arbitrary state.

Die Themen 1–6 basieren auf dem Buch von Shlomi Dolev „Self-Stabilization“:

1. Thema: Einführung und erstes Beispiel: Spanning Tree Construction (Ausarbeitung); (Kapitel 2.1-2.5, Seite 5-16); Termin: 10.6.2010
2. Thema: Auf Dijkstras Spuren: Selbst-stabilisierende Algorithmen für wechselseitigen Ausschluss (Ausarbeitung); (Kapitel 2.6-2.7, Seite 16-27); Termin: 17.6.2010
3. Thema: Selbst-stabilisierende Algorithmen dank Recomputation und Konvergenzbeweise anhand der Beispiele „Synchronous Consensus“, „Maximal Matching“ und „Leader Election“ (Ausarbeitung); (Kapitel 2.8-2.9, Seite 27-36); Termin: 1.7.2010
4. Thema: Berechnung der Stabilization-Time anhand der Scheduler-Luck-Game-Methode (Ausarbeitung); (Kapitel 2.9, Seite 36-45); Termin: 15.7.2010
5. Thema: Warum es kein perfektes Data-Link-Protokoll geben kann!?; (Kapitel 3, Seite 57-68); Termin: 22.7.2010
6. Thema: Self-Stabilizing Algorithms for Model Conversions (Ausarbeitung); (Kapitel 4.1-4.2, Seite 71-82)

Die Themen 7–10 behandeln selbst-stabilisierende Algorithmen aus speziellen Anwendungsfeldern, wobei die meisten sich mit selbst-stabilisierende Algorithmen für Sensornetze befassen. Grundlage sind jeweils verschiedene Konferenzbeiträge:

7. Thema: Self-stabilizing Algorithms for Minimal Dominating Sets and Maximal Independent Sets; (S.T. Hedetniemi, D.P. Jacobs, P.K. Srimani, Computers and Mathematics with Applications, 2003)
8. Thema: Linear Time Self-Stabilizing Colorings (Ausarbeitung); (S.T. Hedetniemi, D.P. Jacobs, P.K. Srimani, Infomation Processing Letters, Volume 87, Issue 5, 2003)
9. Thema: Transformationen für Sensornetze; (Abschnitt 2.2 in „Programming Wireless Sensor Networks in a Self-Stabilizing Style“ von C. Weyer, V. Turau, A. Lagemann und J. Nolte, IEEE SENSORCOMM 2009, und die dort angegebenen Quellen [2,3])
10. Thema: Programming Wireless Sensor Networks in a Self-Stabilizing Style; (C. Weyer, V. Turau, A. Lagemann und J. Nolte, IEEE SENSORCOMM 2009 und die dort angegebenen Quellen [10,13])

Die Vorträge zu den Themen 6–10 werden als Blockveranstaltung am 23.9.2010 im Raum 1.02 durchgeführt.

Literatur

Shlomi Dolev: Self-Stabilization, MIT Press, 2000