• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Parallel and Distributed Computing >Searching for a black hole in interconnected networks using mobile agents and tokens
【24h】

Searching for a black hole in interconnected networks using mobile agents and tokens

机译：使用移动代理和令牌在互连网络中搜索黑洞

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

摘要

We study the impact of the topological structure on the complexity of the Black hole search (Bhs) problem using mobile agents that communicate via tokens. First, we show that the token model can support the same cost as in the whiteboard model, despite the fact that communication between mobile agents is considerably more restricted (and complex) in a token model than in a whiteboard one. More precisely, in this paper, we focus on three specific topologies, namely: an asynchronous (ⅰ) hypercube, (ⅱ) torus and (ⅲ) complete network. With knowledge of which of these topologies is being used, we present token-based solutions for Bhs where the number of moves executed by a team of two co-located anonymous agents can be reduced to θ(n). These proposed solutions do not require the availability of a map and do not assume FIFO on either nodes or links. Second, we consider the use of scattered agents for Bhs in an asynchronous (ⅰ) torus and (ⅱ) complete network. We show that, using 3 scattered agents and 7 tokens in total, a black hole can be located with θ(n) moves in an oriented asynchronous torus. Again, the solution does not assume FIFO on the links and nodes. If the number of scattered agents in a torus increases, the cost is reduced but communication between these agents becomes significantly more complicated. We propose an algorithm that solves Bhs using k(k ＞ 3) scattered agents, with only 1 token per agent, with O(k~2n~2) moves. Beyond theoretical proofs, we also discuss simulations of an actual system in order to evaluate our proposed solutions.
机译：我们使用通过令牌进行通信的移动代理研究拓扑结构对黑洞搜索（Bhs）问题的复杂性的影响。首先，我们证明令牌模型可以支持与白板模型相同的成本，尽管与令牌模型相比，在令牌模型中移动代理之间的通信受到的限制（和复杂性）要大得多。更准确地说，在本文中，我们关注于三种特定的拓扑，即：异步（ⅰ）超立方体，（ⅱ）圆环和（ⅲ）完整网络。了解了使用哪种拓扑后，我们为Bhs提供了基于令牌的解决方案，其中两个同位匿名代理组成的团队执行的移动次数可以减少到θ（n）。这些提出的解决方案不需要映射的可用性，并且不假定节点或链接上的FIFO。其次，我们考虑在异步（ⅰ）圆环和（ⅱ）完整网络中对Bhs使用分散代理。我们证明，总共使用3个分散的代理和7个令牌，可以定位θ（n）在定向异步环面中移动的黑洞。同样，该解决方案不假定链接和节点上的FIFO。如果圆环中分散的代理数量增加，则成本会降低，但是这些代理之间的通信会变得更加复杂。我们提出了一种算法，该算法使用k（k＞ 3）个分散的智能体来求解Bhs，每个智能体仅具有1个令牌，并且具有O（k〜2n〜2）个运动。除了理论证明之外，我们还讨论了实际系统的仿真，以便评估我们提出的解决方案。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号