About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1993
Conference paper
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.