Chicago Journal of Theoretical Computer Science

Volume 2000

Article 3

Published by MIT Press. Copyright 2000 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe 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 this respect.

DOI: 10.4086/cjtcs.2000.003
[] Volume 2000, Article 2 [] Article 4
[back] Volume 2000 [back] Published articles
[CJCTS home]