[Back]

H. Moser, U. Schmid:
"Optimal Deterministic Remote Clock Estimation in Real-Time Systems";
Talk: 12th International Conference On Principles of Distributed Systems, Luxor, Ägypten; 2008-12-15 - 2008-12-18; in: "Principles of Distributed Systems", Lecture Notes in Computer Science / Springer Verlag, Volume 5401 (2008), ISBN: 978-3-540-92220-9; 363 - 387.

In an OPODIS´06 paper, we laid down the foundations of a real-time distributed computing model (RT-Model) with non-zero duration computing steps, which reconciles correctness proofs and real-time schedulability analysis of distributed algorithms. By applying the RT-Model to the well-known drift-free internal clock synchronization problem, we proved that classic zero step-time analysis sometimes provides too optimistic results. The present paper provides 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 in the RT-Model. Moreover, we show how to combine our optimal clock estimation algorithm with existing clock synchronization algorithms.

http://dx.doi.org/10.1007/978-3-540-92221-6_24