OPTIMAL SNAP-STABILIZING NEIGHBORHOOD SYNCHRONIZER IN TREE NETWORKS

Abstract

We propose a snap-stabilizing synchronization technique, called the Neighborhood Synchronizer[Formula: see text] that synchronizes nodes with their neighbors in a tree network. The [Formula: see text] scheme has optimal memory requirement — only one bit per processor. [Formula: see text] is snap-stabilizing [11], meaning that it always behaves according to its specification. The proposed synchronizer being snap-stabilizing is optimal in terms of stabilization time. We show an application of the synchronizer by designing an efficient broadcast algorithm [Formula: see text] in tree networks. [Formula: see text] is also snap-stabilizing and needs only 2h + 2m - 1 rounds to broadcast m messages, where h is the height of the tree.