log(n)-approximation d'un arbre de Steiner auto-stabilisant et dynamique

Lélia Blin 1, 2, * Maria Gradinariu Potop-Butucaru 3, * Stephane Rovedakis 1, *
* Auteur correspondant
2 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
3 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Résumé : Ce travail est motivé entre autre, par le maintient distribué d'infrastructures optimisées pour la communication d'un groupe d'utilisateurs dispersé sur un réseau dynamique. Les domaines d'application typiques de telles structures sont les systèmes de publish/subscribe, bases de données distribuées, systèmes multicasts. Dans ce papier nous décrivons un algorithme distribué qui construit et maintient un arbre de Steiner approché connectant un groupe dynamique de membres dispersé sur un réseau dynamique. Le coût de la solution retournée par notre algorithme est au plus $\log |S|$ fois le coût de la solution optimale, $S$ étant le groupe de membres à interconnecter. Notre algorithme améliore les solutions existantes de plusieurs façons. Premièrement, il tolère le dynamisme des membres et du réseau, autrement dit les membres peuvent rejoindre ou quitter le groupe et les noeuds ou liens du réseau peuvent apparaître ou disparaître du réseau. Deuxièmement notre algorithme est auto-stabilisant, en d'autres termes il tolère les fautes transitoires. Enfin, notre algorithme est super-stabilisant, ce qui signifie que l'on garantie des propriétés sur la structure construite durant la convergence de l'algorithme et malgré le dynamisme du réseau.
Type de document :
Communication dans un congrès
Chaintreau, Augustin and Magnien, Clemence. 11èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2009), Jun 2009, Carry-Le-Rouet, France. 2009
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00383216
Contributeur : Stephane Rovedakis <>
Soumis le : mardi 12 mai 2009 - 14:04:39
Dernière modification le : jeudi 11 janvier 2018 - 06:26:28
Document(s) archivé(s) le : jeudi 10 juin 2010 - 21:18:26

Fichier

SS_Steiner-Algotel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00383216, version 1

Collections

Citation

Lélia Blin, Maria Gradinariu Potop-Butucaru, Stephane Rovedakis. log(n)-approximation d'un arbre de Steiner auto-stabilisant et dynamique. Chaintreau, Augustin and Magnien, Clemence. 11èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2009), Jun 2009, Carry-Le-Rouet, France. 2009. 〈inria-00383216〉

Partager

Métriques

Consultations de la notice

239

Téléchargements de fichiers

145