Skip to Main content Skip to Navigation
Journal articles

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

Résumé : 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 de fois 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'au plus un nombre logarithmique de reconstructions (en nombre d'événements).
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-00730900
Contributor : Etienne Birmele <>
Submitted on : Tuesday, September 11, 2012 - 1:39:46 PM
Last modification on : Tuesday, June 30, 2020 - 11:56:07 AM

Links full text

Identifiers

Collections

Citation

Etienne Birmele, François Delbot, Christian Laforest. Analyse du nombre de perturbations lors du maintien d'un arbre de connexion de faible diamètre. Technique et Science Informatiques, Hermès-Lavoisier, 2011, 30 (7), pp.781--808. ⟨10.3166/tsi.30.781-808⟩. ⟨hal-00730900⟩

Share

Metrics

Record views

250