Self-stabilizing neighborhood synchronizer in tree networks
Self-stabilizing neighborhood synchronizer in tree networks
复制标题
树形网络中的自稳定邻域同步器
DOI：
10.1109/icdcs.1999.776551
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
C. Johnen;L. O. Alima;A. Datta;S. Tixeuil
提出了一种自稳定同步技术，称为邻域同步器(/SPL NSCR//SPL SSCR/)，它使树状网络中的节点与其邻居同步。/SPL NSCR//SPL SSCR/方案的内存需求非常小--每个处理器只有一位。算法/SPL NSCR//SPL SSCR/本身就是自稳定的。我们应用我们的同步器设计了一个树形网络中的广播算法/SPL BSCR//SPL ASCR/。算法/SPL BSCR//SPL ASCR/也是固有的自稳定的，仅需要2小时+2m-1轮来广播m个消息，其中h是树的高度。
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.