STABILIZING PHASE-CLOCKS

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 pro tocols in which all processes are identical and use a constant amount of space per process. One solution is a deterministic protocol for a t ree network; another solution is a probabilistic protocol for a networ k of arbitrary topology.