We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Optimal Snap-Stabilizing Neighborhood Synchronizer in Tree Networks.
- Authors
Johnen, Colette; Alima, Luc O.; Datta, Ajoy K.; Tixeuil, Sébastien; Das, S. K.
- Abstract
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.
- Subjects
SYNCHRONIZATION; PARALLEL processing
- Publication
Parallel Processing Letters, 2002, Vol 12, Issue 3/4, p327
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626402001026