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.

Abstract

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.

• Preformatted versions of the article
  • DVI (338,676 bytes)
  • PostScript (767,850 bytes)
  • PDF (540,348 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX (cj00-03.tex, 248,769 bytes)
  • BIBTeX (cj00-03.bib, 33,688 bytes)
  • Parameter settings for custom formatting (cjropts.tex, 165 bytes)
  • Self citation in BIBTeX (311 bytes)
• Online discussion
• Instructions for Readers

DOI: 10.4086/cjtcs.2000.003

---

Volume 2000, Article 2 Article 4
Volume 2000 Published articles