Talks and Poster Presentations (with Proceedings-Entry):
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.
English abstract:
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-540-92221-6_24