• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >The Distributed Spanning Tree Structure
【24h】

The Distributed Spanning Tree Structure

机译：分布式生成树结构

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

摘要

Search algorithms are a key issue to share resources in large distributed systems as peer networks. Several distributed interconnection structures and algorithms have already been studied in this context. With expanding ring algorithms, the efficiency of searches depends on the topology used to send query requests and the dynamics of the structure. In this paper, we present an interconnection structure that limits the number of messages needed for search queries. This structure, called Distributed Spanning Tree (DST), defines each node as the root of a spanning tree. So, it behaves as a tree for the number of messages but it balances the load generated by the requests among computers, and thus, it avoids to overload the root node. This structure is scalable because it needs only a logarithmic memory space per computer to be maintained. A formal and practical description of the structure is presented and we describe traversal algorithms. Simulations show that DST-based searches behave better than randomly generated graphs and trees as it generates less messages to query all computers while avoiding the tree bottlenecks.
机译：搜索算法是在大型分布式系统（如对等网络）中共享资源的关键问题。在这种情况下，已经研究了几种分布式互连结构和算法。使用扩展环算法，搜索的效率取决于用于发送查询请求的拓扑和结构的动态性。在本文中，我们提出了一种互连结构，该结构限制了搜索查询所需的消息数量。这种称为分布式生成树（DST）的结构将每个节点定义为生成树的根。因此，它就像消息数量的树一样，但它平衡了计算机之间的请求所产生的负载，因此避免了根节点的过载。这种结构是可扩展的，因为它仅需要维护每台计算机的对数存储空间。给出了结构的形式化描述和实用描述，并描述了遍历算法。仿真表明，基于DST的搜索比随机生成的图形和树表现更好，因为它生成较少的消息来查询所有计算机，同时避免了树瓶颈。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号