Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Simple Join Clock Synchronization

IP.com Disclosure Number: IPCOM000109094D
Original Publication Date: 1992-Jul-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 1 page(s) / 55K

Publishing Venue

IBM

Related People

Dolev, D: AUTHOR [+4]

Abstract

An algorithm is disclosed for allowing a new processor to join a network of processors with synchronized clocks in such a way that its clock is synchronized with that of the other processes, despite the potential presence of faulty processors. It is significantly simpler than a previously disclosed join algorithm (1), but is based on similar ideas.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 58% of the total text.

Simple Join Clock Synchronization

       An algorithm is disclosed for allowing a new processor to
join a network of processors with synchronized clocks in such a way
that its clock is synchronized with that of the other processes,
despite the potential presence of faulty processors.  It is
significantly simpler than a previously disclosed join algorithm (1),
but is based on similar ideas.

      As in the earlier algorithm, processors in the network
resynchronize their clocks periodically, at prespecified
synchronization times.  However, not all synchronization times are
necessarily used for synchronization:  if no process wants to join,
then resynchronization can be done infrequently.  By having many
potential synchronization times available, we allow a processor to
join soon after requesting to do so, without the overhead of frequent
resynchronizations.

      When a processor wishes to join (i.e., to synchronize its clock
with the other processors), it sends a "Request to join" message to
all its neighbors.  Each processor receiving such a message initiates
an atomic broadcast, adding the requester to a list JOINERS of
processors that want to join.  The join takes place at the first
possible synchronization time after the request.  The processors
already joined use the synchronization algorithm of (2): basically,
the first process to reach the prearranged synchronization time T
sends out a message saying "the time is T" signed with its
(unforgettable...