Partiell Synchrone Verteilte Echtzeitsysteme

Das Projekt "Partially Synchronous Distributed Real-Time Systems" (PSRTS) ist der Schaffung einer soliden wissenschaftlichen Basis für verteilte fehlertolerante Systeme mit harten Echtzeitanforderungen gewidmet, die im Gegensatz zu existierenden Architekturen einen hohen Grad an Parallelität zulassen und daher nicht "synchron per Konstruktion" sein können. Existierende synchrone Lösungen basieren auf einem feingranularen globalen Zeitbegriff, der es möglich macht, verteilt ablaufende Berechnungen eng miteinander zu synchronisieren: So kommunizieren z.B. im Falle des populären Time-Triggered Protocols TTP global zeitsynchronisierte Prozesse mittels Zeitschlitzverfahren (TDMA) über einen (redundanten) seriellen Bus. Während dieser Ansatz, der die Parallelität natürlich beträchtlich einschränkt, die Realisierung von Fehlertoleranz und Echtzeitfähigkeit stark erleichtert, macht er es auf der anderen Seite unmöglich, die gesamte Rechenleistung des verteilten Systems der Anwendung zur Verfügung zu stellen: Wegen des unvermeidlichen Overheads synchroner Berechnung und Kommunikation sind es im wesentlichen die langsamsten Teile des Systems, die die Gesamtgeschwindigkeit bestimmen. Abgesehen von der daraus resultierenden Verschwendung von Ressourcen besteht dadurch auch die Gefahr, die für die Realisierung von "Synchronität per Konstruktion" erforderlichen Schranken für die maximalen Verzögerungszeiten von Komponenten zu optimistisch abzuschätzen und somit das System gelegentlich außerhalb der Spezifikation zu betreiben. Angesichts der oftmals gravierenden Einschränkungen bezüglich des Energie- und Platzbedarfs von Automotive- und Aerospace-Anwendungen auf der einen und deren Sicherheitsanforderungen auf der anderen Seite ist es naheliegend, zu versuchen, den Grad der Parallelität im System zu erhöhen und somit sowohl die Verschwendung von Ressourcen als auch die Gefahr der Fehlspezifikation von kritischen Zeitparametern zu verkleinern. Die einschlägige Forschung hat mehrere Wege aufgezeigt, wie dies realisiert werden kann: Der Grad der Synchronität eines verteilten Echtzeitsystems kann im Wesentlichen zeitlich, räumlich oder aber algorithmisch reduziert werden. Wir konzentrieren uns ausschließlich auf den letzteren Ansatz, der aus der Forschungsperspektive besonders vielversprechend und herausfordernd erscheint: So gibt es zahlreiche Forschungsergebnisse im Bereich partiell synchroner verteilter Algorithmen, die als Ausgangsbasis herangezogen werden können. Auf der anderen Seite ist die Frage, wie man eine Analyse der Antwortzeiten in einem System durchführen kann, das nicht synchron per Konstruktion ist, nach unserem Kenntnisstand ein noch unerforschtes Gebiet. Das beantragte Projekt PSRTS hat genau diesen Durchschnitt der Gebiete verteilte Algorithmen und Echtzeitsysteme zum Gegenstand: Das konkrete Ziel ist es, durch Modifikation, Adaptierung und Erweiterung bestehender Ansätze die Theorie verteilter Algorithmen um eine angemessene Echtzeit-Perspektive zu erweitern. Das Projekt besteht aus drei klar umrissenen Teilbereichen: (1) Der Definition eines Distributed Real-Time Computing Models, das mit herkömmlichen Distributed Computing Models kompatibel ist, es aber auch erlaubt, alle relevanten Aspekte des Echtzeit-Schedulings und der Echtzeit-Analyse mit einzubeziehen, (2) der Auswahl und/oder Definition eines partiell synchronen Systemmodells, das synchron genug ist, um alle wichtigen Problemstellungen (wie z.B. Consensus) zu lösen, aber asynchron genug ist, um eine signifikante Parallelität der Berechnungen zu erlauben, und (3) die Entwicklung von Methoden und Techniken für eine hinreichend handhabbare aber dennoch realistische Analyse des Echtzeitverhaltens von mit (1) und (2) verträglichen verteilten Algorithmen, die es erlaubt, die immanente zyklische Abhängigkeit des Zeitverhaltens eines verteilten Algorithmus und des darunterliegenden verteilten Computersystems aufzulösen.

Das Projekt PSRTS (Partially Synchronous Distributed Real-Time Systems) war der Schaffung einer soliden wissenschaftlichen Basis für verteilte fehlertolerante Systeme mit harten Echtzeitanforderungen gewidmet, die im Gegensatz zu existierenden Architekturen einen hohen Grad an Parallelität zulassen und daher nicht synchron per Konstruktion sind. Im Gegensatz dazu basieren existierende synchrone Lösungen auf einem feingranularen globalen Zeitbegriff, der es möglich macht, verteilt ablaufende Berechnungen eng miteinander zu synchronisieren: So kommunizieren z.B. im Falle des populären Time-Triggered Protocols TTP global zeitsynchronisierte Prozesse mittels Zeitschlitzverfahren über einen (redundanten) Bus. Nun erleichtert dieser Ansatz zwar die Realisierung von Fehlertoleranz und Echtzeitfähigkeit sehr stark, macht es aber auf der anderen Seite unmöglich, die gesamte Rechenleistung des verteilten Systems der Anwendung zur Verfügung zu stellen: Wegen des unvermeidlichen Overheads synchroner Berechnung und Kommunikation sind es im Wesentlichen die langsamsten Teile des Systems, die die Gesamtgeschwindigkeit bestimmen. Abgesehen von der daraus resultierenden schlechten Auslastung, d.h., der Verschwendung von Ressourcen, besteht dadurch aber auch die Gefahr, das System gelegentlich außerhalb der Spezifikation zu betreiben. Angesichts der oftmals gravierenden Einschränkungen bezüglich des Energie- und Platzbedarfs z.B. in Automotive- und Aerospace-Anwendungen ist es wichtig, zu versuchen, den Grad der Parallelität im System zu erhöhen und somit sowohl die Verschwendung von Ressourcen als auch die Gefahr der Fehlspezifikation von kritischen Zeitparametern zu verkleinern. PSRTS war der Entwicklung der wissenschaftlichen Grundlagen für derartige Systeme gewidmet und hat folgende primären Ergebnisse erzielt:Ein umfassendes Real-Time Model, dem ersten verteilte Berechnungsmodell, das fehlertolerante verteilte Algorithmen mit einer realistischen Echtzeit-Analyse verträglich macht. Im Wesentlichen ersetzt es in Nullzeit ablaufende Zustandsübergänge durch zeitbehaftete, nichtunterbrechbare Operationen, wodurch Wartezeiten und Ablaufplanung relevant werden.Mehrere Instanzen von partiell synchronen Systemmodellen, wie dem zeitfreien Asynchronous Bounded Cycle Modell, die verschiedene Relaxationen von Synchronitätsbedingungen bieten, sowie passende Algorithmen für fehlertolerante verteilte Agreement-Probleme und entsprechende Beweistechniken. Komplexe (Echtzeit-)Analysetechniken, primär basierend auf nicht-standard Algebren, und ihre Anwendung auf Netzwerk-Algorithmen. Diese Methoden erlauben es, verteilte Systeme als lineare dynamische Systeme zu behandeln.Zusätzlich zu diesen primären Forschungsergebnissen hat PSRTS auch mehrere Folgeprojekte stimuliert, inklusive transdisziplinärer Forschung in Formaler Verifikation und in digitalen Integrierten Schaltungen