Asynchrone Verteilte Algorithmen im Theta-Modell

Seit vielen Jahren wird es als Tatsache angesehen, daß verteilte fehlertolerante Echtzeitsysteme nur auf Basis von synchronen Systemmodellen entwickelt werden können. Synchrone Modelle nehmen an, daß explizite Schranken für Berechnungs- und Datenübertragungszeiten existieren und daß diese von allen korrekten Komponenten im System eingehalten werden. Heutige Implementierungen von fehlteroleranten verteilten Echtzeitsystemen, wie die Time-Triggered Architecture, basieren daher alle auf dem synchronen Paradigma. Allerdings ist es in der Praxis schwierig, diese Schranken unter allen denkbaren Betriebsbedingungen zu garantieren, speziell bei Verwendung von COTS-Komponenten. Die Safety-Properties derartiger synchroner Systeme haben daher unter Umständen eine relativ geringe Coverage. Nun ist es aber eine wohlbekannte Tatsache, daß Safety-Properties wie "Alle Antworten replizierter Server auf Anfragen von Clients müssen konsistent sein" auch in völlig asynchronen Systemen garantiert werden können. Da asynchrone Algorithmen per Definition nicht von Zeitbedingungen abhängen, können sie ihre Safety- und Liveness-Properties auch nicht verletzen, wenn solche Zeitbedingungen (etwa unter unerwarteter Überlast oder Denial-of-Service-Attacks) nicht eingehalten werden. Die Coverage derartiger zeitfreier Lösungen (und somit die Wahrscheinlichkeit korrekter Operation unter unerwarteten Betriebsbedingungen) ist daher notwendigerweise höher als die von Lösungen, deren Korrektheit auf der Einhaltung von Zeitbedingungen basiert. Das vorgeschlagene Projekt ist einem neuartigen partiell synchronen Systemmodell, dem Theta-Modell, gewidmet, das den Entwurf zeitfreier Algorithmen erlaubt und somit schwächer als das synchrone Modell ist. Es basiert auf der sehr einfachen Abstraktion der end-zu-end Berechnungs-und Datenübertragungsverzögerungen bei der Ausführung rundenbasierender verteilter Algorithmen. Das Theta-Modell nimmt an, daß zu jedem Zeitpunkt das Verhältnis zwischen maximaler und minimaler Verzögerungszeit durch eine Konstante Theta beschänkt ist. Gestützt auf einige Vorarbeiten sind wir zuversichtlich, daß das Theta-Modell zeitfreie (also asynchrone) Lösungen für alle wesentlichen Probleme (fehlertoleranter Consensus, Uhrensynchronisation, Atomic Commitment, usw.) im Bereich verteilter fehlertoleranter Algorithmen erlaubt. Weiters vermuten wir, daß Theta nicht notwendigerweise überschritten wird, wenn die Verzögerungszeiten eine angenommene maximale Schranke überschreiten, sodaß die Coverage des Theta-Modells höher als die des synchronen Modells ist. Das Theta-Projekt soll diese Vermutungen verifizieren.

Seit vielen Jahren wird es als Tatsache angesehen, daß verteilte fehlertolerante Echtzeitsysteme nur auf Basis von synchronen Systemmodellen entwickelt werden können. Synchrone Modelle nehmen an, daß explizite Schranken für Berechnungs- und Datenübertragungszeiten existieren und daß diese von allen korrekten Komponenten im System eingehalten werden. Heutige Implementierungen von fehlteroleranten verteilten Echtzeitsystemen, wie die Time-Triggered Architecture, basieren daher alle auf dem synchronen Paradigma. Allerdings ist es in der Praxis schwierig, diese Schranken unter allen denkbaren Betriebsbedingungen zu garantieren, speziell bei Verwendung von COTS-Komponenten. Die Safety-Properties derartiger synchroner Systeme haben daher unter Umständen eine relativ geringe Coverage. Nun ist es aber eine wohlbekannte Tatsache, daß Safety-Properties wie "Alle Antworten replizierter Server auf Anfragen von Clients müssen konsistent sein" auch in völlig asynchronen Systemen garantiert werden können. Da asynchrone Algorithmen per Definition nicht von Zeitbedingungen abhängen, können sie ihre Safety- und Liveness-Properties auch nicht verletzen, wenn solche Zeitbedingungen (etwa unter unerwarteter Überlast oder Denial-of-Service-Attacks) nicht eingehalten werden. Die Coverage derartiger zeitfreier Lösungen (und somit die Wahrscheinlichkeit korrekter Operation unter unerwarteten Betriebsbedingungen) ist daher notwendigerweise höher als die von Lösungen, deren Korrektheit auf der Einhaltung von Zeitbedingungen basiert. Das vorgeschlagene Projekt ist einem neuartigen partiell synchronen Systemmodell, dem Theta-Modell, gewidmet, das den Entwurf zeitfreier Algorithmen erlaubt und somit schwächer als das synchrone Modell ist. Es basiert auf der sehr einfachen Abstraktion der end-zu-end Berechnungs-und Datenübertragungsverzögerungen bei der Ausführung rundenbasierender verteilter Algorithmen. Das Theta-Modell nimmt an, daß zu jedem Zeitpunkt das Verhältnis zwischen maximaler und minimaler Verzögerungszeit durch eine Konstante Theta beschänkt ist. Gestützt auf einige Vorarbeiten sind wir zuversichtlich, daß das Theta-Modell zeitfreie (also asynchrone) Lösungen für alle wesentlichen Probleme (fehlertoleranter Consensus, Uhrensynchronisation, Atomic Commitment, usw.) im Bereich verteilter fehlertoleranter Algorithmen erlaubt. Weiters vermuten wir, daß Theta nicht notwendigerweise überschritten wird, wenn die Verzögerungszeiten eine angenommene maximale Schranke überschreiten, sodaß die Coverage des Theta-Modells höher als die des synchronen Modells ist. Das Theta-Projekt soll diese Vermutungen verifizieren.