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.57 KB; posted at December 29 2008; )