Optimal Snap-Stabilizing Neighborhood Synchronizer in Tree Networks
Optimal Snap-Stabilizing Neighborhood Synchronizer in Tree Networks
复制标题
树形网络中的最优捕捉稳定邻域同步器
DOI：
10.1142/s0129626402001026
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
C. Johnen;L. O. Alima;A. Datta;S. Tixeuil
我们提出了一种稳定快照的同步技术，称为邻域同步器，它使树形网络中的节点与其邻居同步。该方案具有最优的存储需求--每个处理器只有一位。是快速稳定的[11]，这意味着它总是按照它的规范运行。在稳定时间方面，所提出的快速稳定化同步器是最优的。通过在树形网络中设计一个高效的广播算法，展示了该同步器的应用。也是Snap稳定的，只需要2小时+2m-1轮就可以广播m条消息，其中h是树的高度。
We propose a snap-stabilizing synchronization technique, called the Neighborhood Synchronizer that synchronizes nodes with their neighbors in a tree network. The scheme has optimal memory requirement — only one bit per processor. is snap-stabilizing [11], 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 in tree networks. is also snap-stabilizing and needs only 2h + 2m - 1 rounds to broadcast m messages, where h is the height of the tree.