• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>RSTI >Analyse du nombre de perturbations lors du maintien d'un arbre de connexion de faible diamètre
【24h】

Analyse du nombre de perturbations lors du maintien d'un arbre de connexion de faible diamètre

机译：维护小直径连接轴时的干扰数量分析

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

摘要

Many internet distributed services, as games or virtual meetings, are massive (many participants), dynamic (members can join and leave) and connected. A tree can be used to connects the members. The dynamic aspect implies that this tree must be updated and its quality must be controlled. In this paper we propose an analysis of the number of changes in routing paths that are necessarily to keep a good quality (we call that a rebuilding). We show in a first part that in the worst case, a rebuilding is necessarily more or less at each step, for any algorithm. In a second part we propose a simple updating algorithm and we prove (using random walks) that it makes at most a logarithmic (in the number of events) number of rebuilding.%Certains services répartis sur internet comme les jeux ou les réunions virtuelles sont massifs (nombreux participants), évolutifs (les membres entrent et sortent au fil du temps) et connectés. Un arbre peut être utilisé pour connecter les divers participants. La non-permanence des membres fait que cet arbre doit être mis à jour pour s'adapter et sa qualité doit être maîtrisée. Dans cet article, nous proposons une analyse du nombre défais où il faut modifier en profondeur les routes déjà existantes pour conserver une bonne qualité de l'arbre (ce que nous appelons reconstruction).Nous montrons que dans le pire cas une reconstruction est nécessaire quasiment à chaque étape et ceci quel que soit l'algorithme mis en œuvre. Nous proposons également un algorithme simple de mise à jour et nous prouvons que celui-ci ne fait en moyenne qu 'auplus un nombre logarithmique de reconstructions (en nombre d'événements).
机译：许多Internet分布式服务，例如游戏或虚拟会议，都是大规模的（许多参与者），动态的（成员可以加入和离开）并相互连接。可以使用树来连接成员。动态方面意味着必须更新此树，并且必须控制其质量。在本文中，我们提出了对路由路径更改数量的分析，这些更改必须保持良好的质量（我们称之为重建）。我们在第一部分中显示，在最坏的情况下，对于任何算法，重建都必定在每个步骤中或多或少地进行。在第二部分中，我们提出了一种简单的更新算法，并证明（使用随机游动）它最多使重建数量（事件数量）达到对数。％某些服务在互联网上通用，在jeux ou les上通用断层块（nombreux的参与者），évolutifs（临时成员和临时成员）和连接。参加潜水者活动的参加者。非永久性常任理事国和司法常任理事国。 Dans cet的文章，建议书中的内容进行了分析，并改进了保存路径，并保存了保存的内容（重建Appérons）。NémontronsQuénésApélones重建àétapeet ceci quel que soit l'algorithme mis enuvre。简单易懂的算法和方法论的证明，无论是对数还是对数的重建，都可以用一种简单的方法进行。

著录项

  • 来源
    《RSTI》 |2011年第7期|p.781-808|共28页
  • 作者

    Etienne Birmelé; François Delbot; Christian Laforest; Nicolas Thibault;

  • 作者单位

    Laboratoire Statistique & Génome UMR CNRS 8071, INRA 1152 Université d'Evry, Tour Evry 2 523 place des terrasses, F-91000 Evry;

    Laboratoire IBISC, EA 4526 Université d'Evry, Tour Evry 2 523 place des terrasses, F-91000 Evry;

    LIMOS, UMR 6158 CNRS Université B. Pascal Campus scientifique des Cézeaux F-63173 Aubière cedex;

    ERMES, EA 4441 Université Paris 2 12place Panthéon, F-75005 Paris;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 fre
  • 中图分类
  • 关键词

    arbre de connexion; dynamicité; marche aléatoire; analyse en moyenne;

    机译：连接轴;动力随机漫步平均分析;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号