Browse Prior Art Database

Decentralizing Technique Applied to Master-Slave Clock Synchronization

IP.com Disclosure Number: IPCOM000119246D
Original Publication Date: 1991-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 3 page(s) / 92K

Publishing Venue

IBM

Related People

Cristian, F: AUTHOR [+3]

Abstract

A method is described for converting a master-slave clock synchronization protocol into a decentralized clock synchronization protocol that accommodates multiple time signal sources, large heterogeneous networks, and multiple processor failures. The method is applicable to any protocol for synchronizing a slave clock to a master such that, after failure-free execution of the protocol, the slave can obtain an upper bound estimate on the precision of the synchronization. The method has two variants: a master-driven variant and a slave-driven variant. In both variants, each clock acts as a slave running the master-slave protocol with each of its neighbors. Each clock maintains a current upper bound estimate of the precision of its synchronization with some external time source.

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

Decentralizing Technique Applied to Master-Slave Clock Synchronization

      A method is described for converting a master-slave clock
synchronization protocol into a decentralized clock synchronization
protocol that accommodates multiple time signal sources, large
heterogeneous networks, and multiple processor failures.  The method
is applicable to any protocol for synchronizing a slave clock to a
master such that, after failure-free execution of the protocol, the
slave can obtain an upper bound estimate on the precision of the
synchronization.  The method has two variants:  a master-driven
variant and a slave-driven variant.  In both variants, each clock
acts as a slave running the master-slave protocol with each of its
neighbors.  Each clock maintains a current upper bound estimate of
the precision of its synchronization with some external time source.
When the result of adding the estimated precision for its most recent
synchronizaton attempt with a neighbor to that neighbor's estimated
precision would be an improvement over the clock's own estimated
precision, then the new synchronization is adopted.  The variants
differ only in whether the synchronization attempts are prompted by
the masters (diffusing out from the multiple external sources) or
prompted by the slaves when their estimated precision deteriorates.

      Master-Driven Algorithm The following procedure is used by
every processor.  A processor with access to an external time clock
has an extra task that periodically sends "synch?" messages.  In the
protocol, send__x stands for sending to processor x, and send__*
stands for sending to all immediate neighbors.  In what follows
assume that p is a known bound on the rate of clock drift for any
processor.  Each processor maintains a clock precision estimate x.
For simplicity, assume that a processor with access to an outside
real-time clock has x(t)=0, for any time t.  For any other processor,
let to be the most recent time it set x (using the task adjust__x),
and xo be the new value.  Then, at any future time t > to, current__x
= xo + (t - to)p.  This dynamic, and sometimes pessimistic, estimate
enables a processor to decide when it can obtain a better precision
of its clock, via the help of its neighbors.
 1 task Synchronizer;
 2  cycle
 3  select
 4   receive__x("synch?",x) T   [current__x&x: iterate]; /* as slave
*/
 5                              T'Eclock.read;
 6                              send__x...