Abstract | ||
---|---|---|
We propose a snap-stabilizing synchronization technique, called the \emph{Neighborhood Synchronizer} (${\mathcal NS}$) that synchronizes nodes with their neighbors in a tree network. The ${\mathcal NS}$ scheme has optimal memory requirement --- only one bit per processor. ${\mathcal NS}$ is \emph{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 (${\mathcal BA}$) in tree networks. ${\mathcal BA}$ is also snap-stabilizing and needs only $2h+2m-1$ rounds to broadcast $m$ messages, where $h$ is the height of the tree. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1142/S0129626402001026 | Parallel Processing Letters |
Keywords | Field | DocType |
self stabilization,distributed algorithms,broadcasting,synchronizer | Broadcast algorithm,Broadcasting,Synchronization,Computer science,Synchronizer,Parallel computing,Computer network,Self-stabilization,Distributed algorithm,Distributed computing,Tree network | Journal |
Volume | Issue | Citations |
12 | 3-4 | 9 |
PageRank | References | Authors |
0.58 | 12 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Colette Johnen | 1 | 364 | 31.21 |
Luc Onana Alima | 2 | 348 | 18.43 |
Ajoy Kumar Datta | 3 | 317 | 40.76 |
Sébastien Tixeuil | 4 | 978 | 93.01 |