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.