Stabilizing phase-clocks.
T Herman and S Ghosh:
Postscript Document and
DVI file.
Abstract
This note considers the problem of synchronizing a network of
digital clocks: the clocks all run at the same rate, however,
an initial state of the network may place the clocks in arbitrary phases.
The problem is to devise a protocol to advance or retard clocks so that
eventually all clocks are in phase. The solutions presented
in this note are protocols in which all processes are identical
and use a constant amount of space per process.
One solution is a deterministic protocol for a tree network;
another solution is a probabilistic protocol for a network of
arbitrary topology.