• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Token-Based Function Computation with Memory
【24h】

Token-Based Function Computation with Memory

机译：带存储器的基于令牌的函数计算

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

摘要

In distributed function computation, each node has an initial value and the goal is to compute a function of these values in a distributed manner. In this paper, we propose a novel token-based approach to compute a wide class of target functions to which we refer as “token-based function computation with memory” (TCM) algorithm. In this approach, node values are attached to tokens and travel across the network. Each pair of travelling tokens would coalesce when they meet, forming a token with a new value as a function of the original token values. In contrast to the coalescing random walk (CRW) algorithm, where token movement is governed by random walk, meeting of tokens in our scheme is accelerated by adopting a novel chasing mechanism. We proved that, compared to the CRW algorithm, the TCM algorithm results in a reduction of time complexity by a factor of at least in Erdös-Renyi and complete graphs, and by a factor of in torus networks. Simulation results show that there is at least a constant factor improvement in the message complexity of TCM algorithm in all considered topologies. Robustness of the CRW and TCM algorithms in the presence of node failure is analyzed. We show that their robustness can be improved by running multiple instances of the algorithms in parallel.
机译：在分布式函数计算中，每个节点都有一个初始值，目标是以分布式方式计算这些值的函数。在本文中，我们提出了一种新颖的基于令牌的方法来计算多种目标函数，我们将其称为“基于令牌的带内存的函数计算”（TCM）算法。在这种方法中，节点值被附加到令牌并在网络中传播。每对行进的令牌在遇到时将合并，从而形成具有作为原始令牌值的函数的新值的令牌。与通过随机游走控制令牌移动的合并随机游走（CRW）算法相反，我们的方案中的令牌会议通过采用新颖的追踪机制来加速。我们证明，与CRW算法相比，TCM算法可将时间复杂度至少降低Erdös-Renyi和完整图的因子，并降低圆环网络的因子。仿真结果表明，在所有考虑的拓扑结构中，TCM算法的消息复杂度至少有恒定的提高。分析了节点故障时CRW和TCM算法的鲁棒性。我们表明，通过并行运行算法的多个实例可以提高其鲁棒性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号