Browse Prior Art Database

Implementation Issues In Clock Synchronization

IP.com Disclosure Number: IPCOM000127982D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 9 page(s) / 31K

Publishing Venue

Software Patent Institute

Related People

Micah Beck: AUTHOR [+5]

Abstract

We present some results from an experimental implementation of a recent clocks syn-chronization algorithm. This algorithm was designed to overcome arbitrary processor failures, and to achieve optimal accuracy, i.e., the accuracy of synchronized clocks (with respect to real time) is as good as that specified for the underlying hardware clocks. Our system was implemented on a set of workstations on a local area broadcast net-work. Initial results indicate that this algorithm can form the basis of an accurate, reli-able, and practical distributed time service.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 14% of the total text.

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Implementation Issues In Clock Synchronization

Micah Beck* T.K. Srikanth Sam Toueg

TR 86-749 May 1986

Department of Computer Science Cornell University Ithaca, NY 14853

The work of this author was supported in part by a Hewlett Packard Faculty Development Fellowship.

ABSTRACT

We present some results from an experimental implementation of a recent clocks syn- chronization algorithm. This algorithm was designed to overcome arbitrary processor failures, and to achieve optimal accuracy, i.e., the accuracy of synchronized clocks (with respect to real time) is as good as that specified for the underlying hardware clocks. Our system was implemented on a set of workstations on a local area broadcast net-work. Initial results indicate that this algorithm can form the basis of an accurate, reli-able, and practical distributed time service.

1. Introduction

An important problem in distributed computing is that of synchronizing clocks in spite of faults [Dole84, Drum86, Guse84, Halp84, Lamp85, Lund84, Marz841. Given "hardware" clocks whose rate of drift from real time is within known bounds, synchronization consists of maintaining logical clocks that are never too far apart. Processes maintain these logical clocks by computing periodic adjustments to their hardware clocks.

Although the underlying hardware clocks have a bounded rate of drift from real time, the drift of logical clocks can exceed this bound. In other words, while synchronization ensures that logical clocks are close together, the accuracy of these logical clocks (with respect to real time) can be lower than that specified for hardware clocks. This reduction in accuracy might appear to be an inherent consequence of synchronization in the presence of arbitrary processor failures and variation in message'delivery times. All previous synchronization algo-rithms exhibit this reduction in clock accuracy.

In a recent paper [Srik851, we showed that accuracy need not be sacrificed in order to achieve synchronization. We presented a synchronization algorithm where logical clocks have the same accuracy as the underlying physical clocks. We showed that no synchronization algorithm can achieve a better accuracy, and therefore our algorithm is optimal in this respect.

*The work of this author was supported in part by a Hewlett Packard Faculty Development Fellowship. n previous results, a different algorithm has been derived for each model of failure. In contrast, ours is a unified solution for several models of failure: crash, omission, or arbitrary

Cornell University Page 1 Dec 31, 1986

Page 2 of 9

Implementation Issues In Clock Synchronization

(i.e., "Byzantine") failures with and without message authentication. With simple modifications, our solution also provides for initial clock synchronization and for the integra-tion of new clocks.

In this paper, we describe some initial experimental results from an implementation, of thi...