Fehlereindämmende selbststabilisierende Algorithmen für große, infrastrukturlose vernetzte Systeme (FESA)

• Applicant: Professor Dr. Volker Turau
• Subject Area: Theoretical Computer Science
• Term: from 2008 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 80176979

Ziel dieses Vorhabens ist die Entwicklung einer Methodik zur Erhöhung der Fehlertoleranz großer infrastrukturloser Netze. Fehlertoleranz ist die Eigenschaft eines Systems, seine Funktionsweise auch dann aufrechtzuerhalten, wenn unvorhergesehene Ereignisse oder Fehler in Hard- oder Software auftreten. In großen, infrastrukturlosen Netzen kann dies nur durch dezentrale Verfahren, wie etwa Selbststabilisierung, erreicht werden. Ein Verfahren ist selbststabilisierend, wenn es aus sich heraus, also ohne äußeres Zutun, nach transienten Fehlern selbsttätig in einen korrekten Zustand zurückkehrt. Die Entwicklung selbststabilisierender Algorithmen verfolgte bisher das Ziel, die Zeitspanne vom Auftreten eines Fehlers bis zur Wiedererlangung eines kor-rekten Systemzustandes zu minimieren. Dabei wird in Kauf genommen, dass wäh-rend der Übergangsphase ein beträchtlicher Teil des Netzes seinen Dienst nicht erbringen kann. Das beantragte Projekt hat das Ziel, die Auswirkungen von transienten Fehlern nicht nur zeitlich sondern auch räumlich zu begrenzen, d.h. es wird eine Fehlereindäm-mung angestrebt. Es soll eine Methodik zum Entwurf selbststabilisierender Algorithmen entwickelt werden, bei denen nur Knoten in der unmittelbaren Umgebung des Fehlerverursachers in die Fehlerbehebung involviert sind. Dadurch kann der überwiegende Teil des Netzes auch während der Übergangsphase seinen Dienst erbringen. Angestrebt wird ein problemunabhängiges Verfahren, welches existierende selbststabilisierende Algorithmen so erweitert, dass die resultierenden Algorithmen fehlereindämmend sind. Dies hat den enormen Vorteil, dass bereits existierende Algorithmen zusätzlich die Eigenschaft der Fehlereindämmung erhalten. Primäres Anwendungsfeld sind Algorithmen für drahtlose Netze, wie etwa Sensornetze. Dazu werden die entsprechenden Randbedingungen wie asynchrones Modell, broadcast als Kommunikationsprimitive, unzuverlässige Kommunikation und beschränkte Ressourcen berücksichtigt.

• DFG Programme: Research Grants