• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Structural information and communication complexity >Algorithms for Extracting Timeliness Graphs
【24h】

Algorithms for Extracting Timeliness Graphs

机译：提取及时性图的算法

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

摘要

We consider asynchronous message-passing systems in which some links are timely and processes may crash. Each run defines a timeliness graph among correct processes: (p, q) is an edge of the timeliness graph if the link from p to q is timely (that is, there is a bound on communication delays from p to q). The main goal of this paper is to approximate this timeliness graph by graphs having some properties (such as being trees, rings, ...). Given a family S of graphs, for runs such that the timeliness graph contains at least one graph in S then using an extraction algorithm, each correct process has to converge to the same graph in S that is, in a precise sense, an approximation of the timeliness graph of the run. For example, if the timeliness graph contains a ring, then using an extraction algorithm, all correct processes eventually converge to the same ring and in this ring all nodes will be correct processes and all links will be timely.We first present a general extraction algorithm and then a more specific extraction algorithm that is communication efficient (i.e., eventually all the messages of the extraction algorithm use only links of the extracted graph).
机译：我们考虑异步消息传递系统，其中某些链接及时且进程可能崩溃。每次运行都会在正确的过程中定义一个时间线图：（p，q）是从p到q的链接是及时的（即，从p到q的通信延迟有一定限度）的时间线图的边缘。本文的主要目标是通过具有某些属性（例如树，环等）的图来近似此及时性图。给定一个图族S，对于运行情况，以使及时性图包含S中的至少一个图，然后使用提取算法，每个正确的过程都必须收敛到S中的同一图，即在精确意义上近似为运行的及时性图。例如，如果及时性图包含一个环，则使用提取算法，所有正确的过程最终会收敛到同一个环，并且在这个环中，所有节点将是正确的过程，并且所有链接都将是及时的。然后是一种更具通信效率的更具体的提取算法（即，最终提取算法的所有消息仅使用提取图的链接）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号