Optimal Snap-Stabilizing Neighborhood Synchronizer in Tree Networks.

We propose a snap-stabilizing synchronization technique, called the Neighborhood Synchronizer (NS) that synchronizes nodes with their neighbors in a tree network. The NS scheme has optimal memory requirement — only one bit per processor. NS is snap-stabilizing, 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 (BA) in tree networks. B4 is also snap-stabilizing and needs only 2h + 2ra - 1 rounds to broadcast m messages, where h is the height of the tree. [ABSTRACT FROM AUTHOR]