Self-stabilization with global rooted synchronizers

Abstract

We propose a self-stabilizing synchronization technique, called the global rooted synchronization, that synchronizes processors in a tree network. This synchronizer converts a synchronous protocol for tree networks into a self-stabilizing version. The synchronizer requires only O(1) memory (other than the memory needed to maintain the tree) at each node regardless of the size of the network, stabilizes in O(h) time, where h is the height of the tree, and does not invoice any global operations. Applications of this technique are presented.