[ main ] [ back ]

43/2008 : Optimal Deterministic Remote Clock Estimation in Real-Time Systems

RR Number
43/2008
Comment
This download contains an appendix which is not included in the published version.
Conference
12th International Conference On Principles Of DIstributed Systems (OPODIS'08)
Author(s)
Heinrich Moser, Ulrich Schmid
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 scheduling 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.
Bibtex
@techreport{MS08:TR,
  author =       "Heinrich Moser and Ulrich Schmid",
  title =        "Optimal Deterministic Remote Clock Estimation in Real-Time Systems",
  institution =  "Technische Universit{\"a}t Wien, Institut f{\"u}r Technische Informatik",
  address =      "Treitlstr. 1-3/182-1, 1040 Vienna, Austria",
  type =         "Research Report",
  year =         "2008",
  number =       "43/2008",
 url = "http://www.vmars.tuwien.ac.at/php/pserver/docdetail.php?DID=2450&viewmode=paper&year=2008"
}
Download
Get paper.pdf - Adobe PDF-format, (326.5723 KB; posted at July 09 2013; )

[ main ] [ back ]