A model for distributed computing in real-time systems

Abstract

Diese Dissertation stellt ein neues, fehlertolerantes Modell für verteile Datenverarbeitung in Echtzeitsystemen vor, das sowohl die Perspektive der klassischen verteilten Datenverarbeitungsmodelle als auch die der Echtzeitsystemforschung berücksichtigt. Üblicherweise wird bei der Analyse von verteilten Algorithmen die vereinfachende Annahme getroffen, dass Rechenschritte in Nullzeit durchgeführt werden. Unser Modell basiert auf den bisher gängigen Modellierungstechniken verteilter System, lässt jedoch im Unterschied dazu die Nullzeitannahme fallen.<br />Diese Vorgehensweise erlaubt größtmögliche Wiederverwendbarkeit existierender Ergebnisse, eröffnet jedoch auch die bisher verschlossene Möglichkeit, Scheduling-Analysen durchzuführen. Mit Hilfe der in dieser Arbeit vorgestellten Transformationsalgorithmen untersuchen wir die Beziehung zwischen dem klassischen synchronen Systemmodell und unserem Echtzeitmodell: Wir zeigen, wie Algorithmen von einem in das andere Modell übergeführt werden können und welche Eigenschaften echter Computersysteme durch die Nullzeitannahme bisher nur verfälscht wahrgenommen wurden.<br />Um diesen Unterschied anhand eines konkreten Beispiels zu demonstrieren, untersuchen wir das Problem der deterministischen Uhrensynchronisation in fehlerfreien Systemen mit perfekter Ganggenauigkeit und zeigen, dass -- in unserem Echtzeitmodell -- kein Algorithmus existieren kann, der optimale Synchronisationsgenauigkeit bei konstanter Laufzeit sicherstellt. Da jedoch ein solcher Algorithmus im klassischen Systemmodell bekannt ist, haben wir hier ein Beispiel, bei dem die klassische Analyse zu optimistische Ergebnisse liefert. Wir zeigen, dass das Erreichen optimaler Synchronisationsgenauigkeit einen Zeitaufwand von Omega(n) erfordert und präsentieren einen dazu passenden O(n)-Algorithmus.<br />Allgemein gilt, dass bei diesem Synchronisationsproblem die Anzahl der Nachrichten, die von einem Algorithmus benötigt werden, in Abhängigkeit von der Synchronisationsgenauigkeit steht. Dieses Ergebnis führt uns einerseits zu der oben erwähnten Schranke von Omega(n) für optimale Genauigkeit, erlaubt jedoch auch Aussagen über den nicht-optimalen Fall:<br />Es zeigt sich, dass nicht-optimale Synchronisationsgenauigkeit auch von einem Algorithmus mit konstanter Laufzeit erreicht werden kann, allerdings nur dann, wenn das darunterliegende Netzwerksystem Broadcasts in konstanter Zeit erlaubt.<br />Auch die Synchronisation von Uhren mit Gangabweichung wird in dieser Arbeit unter dem Echtzeitaspekt behandelt. Konkret untersuchen wir das Teilproblem, den aktuellen Wert einer auf einem anderen Computersystem befindlichen Uhr so genau wie möglich zu schätzen, präsentieren einen Algorithmus, der dieses Problem löst, und beweisen, dass keine bessere Schätzgenauigkeit erzielt werden kann. Abschließend zeigen wir, wie diese Schätzmethode mit einer optimalen Konvergenzfunktion in einem hochpräzisen, fehlertoleranten Uhrensynchronisationsalgorithmus kombiniert werden kann.<br />

This work introduces a fault-tolerant real-time distributed computing model for message-passing systems, which reconciles the distributed computing and the real-time systems perspective: By just replacing instantaneous computing steps with computing steps of non-zero duration, we obtain a model that both facilitates real-time schedulability analysis and retains compatibility with classic distributed computing analysis techniques and results. We provide general simulations and validity conditions for transforming algorithms from the classic synchronous model to our real-time model and vice versa, and investigate whether/which properties of real systems are inaccurately or even wrongly captured when resorting to zero step-time models.<br />We revisit the well-studied problem of deterministic drift- and failure-free internal clock synchronization for this purpose, and show that no clock synchronization algorithm with constant running time can achieve optimal precision in our real-time model. Since such an algorithm is known for the classic model, this is an instance of a problem where the standard distributed computing analysis gives too optimistic results. We prove that optimal precision is only achievable with algorithms that take Omega(n) time in our model, and present a matching O(n) algorithm.<br />As a more general result, we provide a lower bound on the number of messages required to obtain a certain clock synchronization precision.<br />In the case of optimal precision, this leads to the aforementioned bound of Omega(n). With respect to non-optimal precision equal to the message delay uncertainty, our result implies that constant time complexity is possible if, and only if, the system allows for constant-time broadcasts.<br />As a first step towards worst-case optimal deterministic clock synchronization with drifting clocks in real-time systems, which is an open problem even in classic distributed computing, we define and prove correct an optimal remote clock estimation algorithm, which is a pivotal function in both external and internal clock synchronization, and determine a matching lower bound for the achievable maximum clock reading error. Moreover, we show how to combine our clock estimation method with an optimal convergence function, resulting in a high-precision fault-tolerant clock synchronization algorithm.<br />