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

Created from the Publication Database of the Vienna University of Technology.