• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Parallel and Distributed Computing >Optimal snap-stabilizing depth-first token circulation in tree networks
【24h】

Optimal snap-stabilizing depth-first token circulation in tree networks

机译：树网络中最优的快照稳定深度优先令牌循环

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We address the depth-first token circulation (DFTC) in tree networks. We first consider oriented trees-every processor knows which of its neighbors leads to a particular processor called the root. On such trees, we propose a state optimal DFTC algorithm. Next, we propose a second algorithm, also for trees, but where no processor knows which of its neighbor leads to the root. This algorithm is also optimal in terms of the number of states per processor. Both algorithms works under any daemon, even unfair. Furthermore, both are snap-stabilizing. A snap-stabilizing protocol guarantees that the system always maintains the desirable behavior. In other words, a snap-stabilizing algorithm is also a self-stabilizing algorithm which stabilizes in 0 steps. Thus, both algorithms are also optimal in terms of the stabilization time. Finally, two approaches of the maximum waiting time to initiate a DFTC are also discussed, whether the tree is oriented or not. In every case but one, we show that the waiting time is asymptotically optimal. In the last case, we conjecture the same result. (C) 2006 Elsevier Inc. All rights reserved.
机译：我们解决了树状网络中的深度优先令牌循环（DFTC）。我们首先考虑面向树，每个处理器都知道哪个邻居会导致一个称为根的特定处理器。在这样的树上，我们提出了状态最优DFTC算法。接下来，我们提出了第二种算法，也适用于树，但是没有处理器知道哪个邻居导致根。就每个处理器的状态数而言，该算法也是最佳的。两种算法都可以在任何守护程序下运行，甚至不公平。此外，两者都是快速稳定的。快速稳定协议可确保系统始终保持所需的行为。换句话说，快速稳定算法也是一种以0步稳定的自稳定算法。因此，两种算法在稳定时间方面也是最佳的。最后，还讨论了启动DFTC的最大等待时间的两种方法，无论树是否定向。在除一种情况以外的所有情况下，我们都表明等待时间是渐近最优的。在最后一种情况下，我们推测相同的结果。 （C）2006 Elsevier Inc.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号