[Back]

H. Moser:
"A Model for Distributed Computing in Real-Time Systems";
Supervisor, Reviewer: U. Schmid, L. Welch; Institut für Technische Informatik, 2009; oral examination: 2009-05-20.

This work introduces a fault-tolerant real-time distributed computing model for messagepassing
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.
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
(n) time in our model, and present a matching
O(n) algorithm.
As a more general result, we provide a lower bound on the number of messages required to
obtain a certain clock synchronization precision. In the case of optimal precision, this leads
to the aforementioned bound of
(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.
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.

Distribiuted Computing, Model

http://publik.tuwien.ac.at/files/PubDat_184405.pdf