Systemsoftware und Verteilte Systeme

Modellierung und Analyse verteilter, selbststabilisierender Algorithmen als digitale Regelkreise

Masterarbeit oder Diplomarbeit. In angepasster Form kann die Arbeit auch als Studienarbeit (DPO3), Individuelles Projekt BSc, Individuelles Projekt Diplom angerechnet werden

Ansprechpartner:

Themengebiete

  • Selbststabilisierung

Hintergrund

Selbststabilisierende Algorithmen sind verteilte Algorithmen, die transiente Fehler, die den Zustand der Programmvariablen korrumpieren, tolerieren. Diese Eigenschaft hat bedeutende Vorteile: zum einen muß ein selbststabilisierender Algorithmus nicht initialisiert werden, zum anderen bedarf er keiner Wartung während des laufenden Betriebs. Selbststabilsierende Algorithmen "achten somit selber darauf'', daß sie so schnell wie möglich wieder in einen Zustand geraten, in dem sie sinnvolle Arbeit verrichten können und dort verbleiben, solange keine neuen Fehler auftreten. Der Nachteil selbststabiliserender Algorithmen: sie sind nicht leicht zu finden. Insbesondere ist die Beweisführung, d.h., der Nachweis, daß ein Algorithmus die Selbststabilisierungseigenschaft besitzt, nicht leicht. Ein anschauliches Beispiel eines selbstabilisierenden Systems ist z.B. ein Stehaufmännchen, das sich in Abwesenheit von Störungen immer wieder senkrecht aufrichtet und in diesem Zustand verharrt, bis erneut Störungen auftreten. Um den Beweis der Selbststabilisierungseigenschaft durchführen zu können, hat es sich in einigen Fällen als äußerst hilfreich erwiesen, den Algorithmus als Regelkreis (im Sinne der Regelungstechnik) aufzufassen und Beweismethoden der Regelungstechnik zum Nachweis der Stabilität des Regelkreises anzuwenden. Ist der Regelkreis in einem bestimmten Sinne stabil, dann kann i.d.R. leicht auf eine Selbststabilisierung des dem Regelkreis zugrundeliegenden Algorithmus geschlossen werden.

Aufgabenbeschreibung

Im Rahmen der Diplomarbeit/des Individuellen Projekts sollen Beweismethoden der Regelungstechnik zwecks Nachweises von Stabilität auf ihre Übertragbarkeit zum Beweis der Selbststabilisierung verteilter Algorithmen hin untersucht und exemplarisch veranschaulicht werden. Dabei ist insbesondere eine Herausarbeitung der Vor- und Nachteile der einzelnen Beweismethoden wünschenwert. Desweiteren soll untersucht werden, inwieweit diese Methoden verwendet werden können, um ebenfalls Aussagen über die Konvergenzzeit zu machen, d.h., nach wievielen Berechnungszyklen ein selbststabilisierendes System wieder arbeitsfähig ist.

Vorkenntnisse

  • verteilte Algorithmen
  • Grundkenntnisse aus der Regelungstechn

Kommentar

Die Arbeit enthält praktische Anteile.