Fehlereindämmende selbststabilisierende Algorithmen für große, infrastrukturlose vernetzte Systeme (FESA)
Zusammenfassung der Projektergebnisse
Innerhalb des Projektes FESA wurde eine Methodik zur Erhöhung der Fehlertoleranz großer infrastrukturloser Netze entwickelt. Sie zielt darauf ab, die Auswirkungen einzelner, nicht dauerhaft anhaltender Fehler, welche in einem eingeschwungenen Systemzustand auftreten, räumlich und zeitlich einzudämmen. Dies bedeutet, dass einerseits die Ausbreitung eines lokal aufgetretenen Fehlers innerhalb des Netzes verhindert wird und gleichzeitig möglichst schnell wieder ein legaler Betriebszustand erreicht wird. Solche temporären Fehler können beispielsweise durch spontane Veränderungen des Speichers eines Teilnehmers hervorgerufen werden (so genannte soft errors). Durch die immer noch voranschreitende Integrationsdichte von Halbleiterspeichern wird die kosmische Strahlung heute als der Hauptfaktor für soft errors angesehen. Die neu entwickelte Methodik kann auf eine sehr große Klasse von selbststabilisierenden Algorithmen angewendet werden. Dies sind verteilte Algorithmen, welche ohne äußere Einwirkung in endlicher Zeit einen Systemzustand herstellen, welcher einer gegebenen Spezifikation entspricht. Die Methodik basiert darauf, Abbilder des Speicherzustandes jedes Netzteilnehmers redundant auf einer kleinen Anzahl von Nachbarn abzulegen. Mittels dieser Kopien kann nach einem temporär aufgetretenen lokalen Fehler direkt wieder ein korrekter Systemzustand hergestellt werden. Somit hat ein solcher Fehler keine Auswirkungen auf das Umfeld des fehlerhaften Teilnehmers. Das heißt, der Fehler pflanzt sich nicht fort. Das System verhält sich, bis auf den einen Teilnehmer, jederzeit gemäß der Spezifikation. Die Herausforderung bestand darin, temporäre Fehler zu erkennen und die Ausführung des Algorithmus solange zu unterbrechen, bis der Fehler repariert ist. Ein ununterbrochener Betrieb gemäß der Beschreibung des Algorithmus könnte zu einer Fehlerausbreitung führen, im schlimmsten Fall würde das gesamte Netz davon betroffen sein. Zwar würde das System von sich aus wieder einen spezikationskonformen Zustand erreichen, doch das Gesamtsystem wäre für einen längeren Zeitraum gestört und ein Arbeiten gemäß der Spezifikation wäre nicht gesichert. Zur praktischen Umsetzung der Methodik wurde ein Transformator entwickelt. Er transformiert beliebige selbststabilisierende Algorithmen, die üblicherweise in Form von überwachten Anweisungen (guarded Statements) beschrieben sind, so dass die oben angegebenen Eigenschaften erfüllt sind. Zu diesem Zweck fügt er neue Zustandsvariablen und neue Regeln hinzu. Die in FESA entwickelte Methodik unterscheidet sich wesentlich von den bisher bekannten Verfahren: • Der notwendige zusätzliche Speicherbedarf ist beschränkt. Während die bisher bekannten Verfahren den Speicherbedarf um den Faktor 2m/n+1 erhöhen, steigt der Bedarf jetzt nur noch den Faktor 4, d.h. das Verfahren skaliert wesentlich besser. Hierbei bezeichnet n die Anzahl der Teilnehmer und m die Anzahl der Verbindungen des Netzes. • Die so genannte Korrekturausfallzeit (fault-gap) - d.h. die Zeitspanne, welche ein System benötigt, um nach einem temporären Fehler sich soweit zu erholen, dass die Spezifikation wieder erfüllt ist und zugleich ein weiterer temporärer Fehler verkraftet werden kann - wurde drastisch verkürzt. Sie betrug bei den bisher bekannten Verfahren Ω(n), im neuen Verfahren ist sie Ό(1), das heißt unabhängig von der Größe des Netzes. • Das neue Verfahren setzt nicht mehr voraus, dass die Teilnehmer a priori über Kenntnisse hinsichtlich der Größe des Netzes verfügen. Im Gegensatz zu existierenden Methodiken kann das Verfahren auch in dynamischen Netzen angewendet werden. Das bedeutet, dass sich die Topologie des Netzes im Laufe der Zeit ändern darf. Beispiele für Topologieänderungen sind das Auftreten neuer oder das Wegfallen bestehender Verbindungen. Eine solche Methodik existierte bis zu diesem Zeitpunkt noch nicht. Die Besonderheit besteht dabei darin, dass auch Topologieänderungen, die gleichzeitig zu temporären Speicherfehlern auftreten, korrekt behandelt werden. Die oben angegebenen Eigenschaften der Methodik hinsichtlich Speicherbedarf und Kenntnis der Netzgröße bleiben dabei erhalten. Nur die Korrekturausfallzeit steigt an. Ein weiterer Vorteil des neuen Verfahrens besteht darin, dass Eigenschaften des ursprünglichen Algorithmus - beispielsweise die Erfüllung eines Sicherheitsprädikates (safty predicate) - erhalten bleiben. Sie gelten auch noch in den transformierten Algorithmen. Als Beispiel sei an dieser Stelle die Eigenschaft der Superstabilisierung genannt. Die zum Zeitpunkt der Antragstellung bekannten Transformatoren waren nur unter dem zentralen Scheduler einsetzbar. Ein Scheduler ist für die Steuerung der Ausführung der Aktionen der einzelnen Teilnehmer zuständig. Der zentrale Scheduler ist ein theoretisches Konzept, er unterbindet jegliche Nebenläufigkeit. Die Verwendung dieses Konzeptes erleichtert wesentlich die Durchführung des Korrektheitsbeweises und die der Analyse der Laufzeit. Er entspricht jedoch nicht den praktischen Gegebenheiten. Große Netze werden asynchron betrieben, wobei jeder Teilnehmer seine eigene Ausführungsgeschwindigkeit hat. Ein solches Verhalten wird durch den verteilten Scheduler abgebildet. Das in FESA entwickelte Verfahren verwendet diesen allgemeinen Scheduler und ist somit für den praktischen Einsatz tauglich. Beim Korrektheitsbeweis des vorgeschlagenen Verfahrens wurde ein neuer Ansatz zum Beweis der Stabilität von Algorithmen unter dem verteilten Scheduler entwickelt. Die neue Technik hat vielfältige Anwendungen und ist als eigenständiges Ergebnis von hohem Wert einzustufen. Das neue Verfahren erleichtert wesentlich die Entwicklung fehlereindämmender selbststabilisierender Algorithmen, da die Eigenschaft der Fehlereindämmung automatisch durch den Transformator hinzugefügt werden kann. Mit der Anwendung des Transformators auf existierende Algorithmen, wird die Anzahl hochgradig fehlertoleranter Algorithmen stark vergrößert. Die Bedeutung solcher Algorithmen ist durch die rasante Nutzung des Internets für Anwendungen in sicherheitskritischen Bereichen in den letzten Jahren stark angestiegen. Die verstärkte Nutzung des Internet durch mobile Nutzer erfordert den Einsatz von Verfahren, welche für dynamische Netze geeignet sind. Auch hier wird die neu entwickelte Methodik zu Einsatz kommen. Die durchgeführten Arbeiten legen den Grundstein für weitere Untersuchungen. Von hohem Interesse sind beispielsweise Verfahren, welche nicht nur einen einzelnen temporären Fehler tolerieren, sondern mehrere gleichzeitige Fehler. Liegen die Fehlerorte weit genug auseinander (beispielsweise in einem Abstand von mindestens vier), so ist das jetzige Verfahren schon anwendbar. Die abgegebenen Garantien können aber nicht mehr eingehalten werden, wenn beispielsweise bei benachbarten Teilnehmern gleichzeitig ein temporärer Fehler auftritt. Es wäre sehr wichtig, entsprechende Transformatoren zu entwickeln. Die große Herausforderung besteht in der Erkennung solcher Fehlersituationen. Die Behebung dieser Fehler kann eventuell durch eine geschickte Verteilung von redundanten Daten durchgeführt werden. Es ist fraglich, ob sich solche Verfahren mit einer konstanten Korrekturausfallzeit und einem konstanten zusätzlichem Speicheraufwand realisieren lassen.
Projektbezogene Publikationen (Auswahl)
- A new technique for proving self-stabilization under the distributed scheduler. In: Proceedings of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'10), Band 6366 der Reihe Lecture Notes in Computer Science, Seiten 65-79. Springer, 2010
Sven Köhler und Volker Turau
- Fault-containing self-stabilization in asynchronous systems with constant fault-gap. In: Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS'10), Seiten 418-427. IEEE Computer Society, Juni 2010
Sven Köhler und Volker Turau
- A fault-containing self-stabilizing (3 - 2/(delta+1))-approximation algorithm for vertex cover in anonymous networks. Theoretical Computer Science, 412(33):4361-4371, 2011
Volker Turau und Bernd Hauck
- Construction of connected dominating sets in large-scale manets exploiting self-stabilization. In: Proceedings of the 5th International Workshop on Localized Algorithms and Protocols for Wireless Sensor Networks (LOCALGOS'11), Juni 2011
Stefan Unterschütz und Volker Turau
- Space-efficient fault-containment in dynamic networks. In: Proceedings of the 13th International Symposium on Stabilization, Safety, ahd Security of Distributed Systems (SSS'11), Band 6976 der Reihe Lecture Notes in Computer Science, Seiten 311-325. Springer, 2011
Sven Köhler und Volker Turau
