A Time Optimal Self-Stabilizing Synchronizer Using A Phase Clock
Baruch Awerbuch Shay Kutten
Yishay Mansour Boaz Patt-Shamir
George Varghese
Abstract:
A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous
distributed algorithm, where each node maintains a local ‘pulse counter’ that simulates
the global clock in a synchronous network. In this paper we present a time optimal self-stabilizing
scheme for such a synchronizer, assuming unbounded counters. We give a simple rule by which each
node can compute its pulse number as a function of its neighbors’ pulse numbers. We also show
that some of the popular correction functions for phase clock synchronization are not self-stabilizing
in asynchronous networks. Using our rule, the counters stabilize in time bounded by the diameter
of the network, without invoking global operations. We argue that the use of unbounded counters
can be justified by the availability of memory for counters that are large enough to be practically
unbounded, and by the existence of reset protocols that can be used to restart the counters in some
rare cases where faults will make this necessary.
Index Terms: C. Computer Systems Organization C.2 COMPUTER-COMMUNICATION NETWORKS
C.2.1 Network Architecture and Design Subjects: Distributed networks; G. Mathematics
of Computing G.2 DISCRETE MATHEMATICS G.2.2 Graph Theory; General Terms: Algorithms;
Reliability, Theory.