Published by MIT Press. Copyright 2000 Massachusetts Institute of
Your institution may already be a
subscriber to CJTCS. If not,
for legitimate access to all journal articles.
Orthogonal Accuracy Clock Synchronization
Ulrich Schmid (Technische Universitaet Wien)
14 August 2000
We present description and analysis of a novel orthogonal accuracy clock
synchronization algorithm (OA), which takes care of both precision and accuracy with
respect to external time. It is based on the generic algorithm introduced by (Schmid and
Schossmaier 97) and uses a convergence function based on Marzullo's fault-tolerant
intersection function. As far as precision is concerned, we show that OA has the same
worst-case performance as the well-known fault-tolerant midpoint algorithm of (Welch and Lynch 88).
Hwever, relying on a perception-based hybrid fault model, and a fairly realistic system model,
our results are valid for a wide variety of node and link faults and apply to very
high-precision applications as well: Impairments due to clock granularity and discrete
rate adjustment cannot be ignored here anymore. Our accuracy analysis focuses on the nodes'
local accuracy interval, which provides the application with an on-line bound on the current
deviation from external time. We show that this bound could get larger than twice
the necessary lower bound ("traditional accuracy"), hence OA is definitely suboptimal in