Time Optimal Self-Stabilizing Synchronization
Extended Abstract
Baruch Awerbuch Shay Kutten Yishay Mansour Boaz Patt-Shamir George Varghese
November 18, 1992
Abstract
In this paper we present a time optimal self-stabilizing scheme for network synchronization.
Our construction has two parts. First, we give a simple rule by which each node can compute its
pulse number as a function of its neighbors' pulse numbers. The rule we give stabilizes in time
bounded by the diameter of the network, does not invoke global operations, and does not require any
additional memory space. However, it assumes that pulse numbers may grow unboundedly. The second
part of the construction (which is of independent interest on its own right) takes care of this
problem. Specifically, we present the first self-stabilizing reset procedure that stabilizes in time
proportional to the diameter of the network. This procedure can be combined with unbounded-register
protocols to yield bounded-register algorithms.