Browse Prior Art Database

Controlling Resynchronization Attempts

IP.com Disclosure Number: IPCOM000106215D
Original Publication Date: 1993-Oct-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 80K

Publishing Venue

IBM

Related People

Dolev, D: AUTHOR [+2]

Abstract

In a typical message passing network, queueing and other high message traffic phenomena tend to occur at random but to last longer than and be exacerbated by a small number of immediate retrials. Many protocols (e.g., Probabilistic Clock Synchronization) respond to a large round trip message delay by immediately retrying some fixed number of times, or until a satisfactory round trip delay is obtained. The advantage of this approach is that the first delay may have been caused by some part of the receiving process not being available. The immediate retry may not suffer the scheduling delay because the receiving process is still scheduled. However, when the delay is caused by queuing or similar high message traffic phenomena, immediate retrials make matters worse by adding to the traffic.

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

Controlling Resynchronization Attempts

      In a typical message passing network, queueing and other high
message traffic phenomena tend to occur at random but to last longer
than and be exacerbated by a small number of immediate retrials.
Many protocols (e.g., Probabilistic Clock Synchronization) respond to
a large round trip message delay by immediately retrying some fixed
number of times, or until a satisfactory round trip delay is
obtained.  The advantage of this approach is that the first delay may
have been caused by some part of the receiving process not being
available.  The immediate retry may not suffer the scheduling delay
because the receiving process is still scheduled.  However, when the
delay is caused by queuing or similar high message traffic phenomena,
immediate retrials make matters worse by adding to the traffic.

      Assume a clock synchronization protocol like [1,2] in which a
process maintains an estimate of its current precision as a logical
clock P that ticks at a worst case rate of drift for clocks of the
type of the underlying hardware clock.  We assume that there is given
a user requested precision R. Also assume that at times the process
attempts to resynchronize and reduce P and that P may be recomputed
as a function of the round trip message delay to some other process.
However, it may not be possible to obtain a round trip delay that
produces a precision as small as R.

      In describing our method below, a unit of time for precision
that is small with respect to the precisions obtained was used.  For
example, the unit may be one millisecond, when the precisions
obtained range from 10 to 100 milliseconds.

      This method introduces a third variable Q that represents the
current precision the process is attempting to maintain.  Initially Q
is set to max(P+1,R), (assuming some P is given initially).  When the
current P becomes...