Self-stabilizing neighborhood synchronizer in tree networks

Abstract

Proposes a self-stabilizing synchronization technique, called the Neighborhood Synchronizer (/spl Nscr//spl Sscr/), that synchronizes nodes with their neighbors in a tree network. The /spl Nscr//spl Sscr/ scheme has an extremely small memory requirement-only one bit per processor. Algorithm /spl Nscr//spl Sscr/ is inherently self-stabilizing. We apply our synchronizer to design a broadcasting algorithm /spl Bscr//spl Ascr/ in a tree network. Algorithm /spl Bscr//spl Ascr/ is also inherently self-stabilizing and needs only 2h+2m-1 rounds to broadcast m messages, where h is the height of the tree.