Time optimal self-stabilizing synchronization

Abstract

In the network synchronization model, each node maintains a local pulse counter such that the advance of the pulse numbers simulates the advance of a clock in a synchronous network. 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 cach node can compute tts pulse number as a function of its neighbors' pulse numbers. This rule stabilizes in time bounded by the diameter of the network, it does not invoke global operations, and does not require any additional memory space. However, this rule works correctly only if the pulse numbers may grow unboundedly. The second part of the construction (which is of independent interest in its own rightJ 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.