Time Optimal Self-Stabilizing Synchronization
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
In this paper we present a time optimal self-stabilizing scheme for
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.
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 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.
for proceedings version.