Browse Prior Art Database

Implementation Issues In Clock Synchronization

IP.com Disclosure Number: IPCOM000148369D
Original Publication Date: 1986-May-31
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

Beck, Micah: AUTHOR [+4]

Abstract

Micah Beck*

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 12

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 Packat-d Faculty Development

Fellowship.

[This page contains 1 picture or other non-text object]

Page 2 of 12

[This page contains 1 picture or other non-text object]

Page 3 of 12

Implementation Issues In Clock Synchronization

Micah Beck*

Srikanth

Sam Toueg


Computer Science Department, Cornell University, Ithaca, NY 14853

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 Fellowehip.

TX.

Y

.

[This page contains 1 picture or other non-text object]

Page 4 of 12

   In previous results, a different algorithm has been derived for each model of failure. In contrast, ours is a unified solution for several models of fa...