Maintaining Balanced Trees For Structured Distributed Streaming Systems

Frédéric Giroire 1 Remigiusz Modrzejewski 1 Nicolas Nisse 1 Stéphane Pérennes 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Dans cet article, nous proposons et analysons un algorithme local simple pour ́equilibrer un arbre. La motivation vient des syst'emes distribu ́es de diffusion en temps r ́eel, dans lesquels une source diffuse un contenu vers des r ́ecepteurs via un arbre, un noeud transmettant les donn ́ees 'a ses enfants. Ces syst'emes sont soumis 'a un niveau ́elev ́e d'arriv ́ees et de d ́eparts (churn). Il est donc crucial d'ˆetre en mesure de r ́eparer efficacement l'arbre de diffusion afin de permettre une distribution efficace des donn ́ees. En particulier, en raison de limitations de bande passante, un arbre de diffusion efficace doit veiller 'a ce que les degr ́es des noeuds soient born ́es. Par ailleurs, pour minimiser le d ́elai de la diffusion en continu, la profondeur de l'arbre de diffusion doit ́egalement ˆetre contrˆol ́ee. Nous proposons ici un algorithme de r ́eparation distribu ́e simple dans lequel chaque nœud ex ́ecute des op ́erations locales en fonction de son degr ́e et de la taille des sous-arbres de ses enfants. Dans un cadre synchrone, nous montrons tout d'abord, qu''a partir de n'importe quel arbre avec n nœuds, notre processus converge vers un arbre ́equilibr ́e en O(n2) tours. Nous d ́ecrivons ensuite un mod'ele plus restrictif, en ajoutant une petite information suppl ́ementaire pour chaque nœud, pour lequel la convergence est atteinte en O(n log n) tours, cette borne ́etant serr ́ee. Nous mettons ensuite en ́evidence par simulation que la con- vergence est beaucoup plus rapide (nombre logarithmique de tours en moyenne) pour un arbre al ́eatoire.
Type de document :
Rapport
[Research Report] RR-8309, INRIA. 2013
Liste complète des métadonnées


https://hal.inria.fr/hal-00824269
Contributeur : Frédéric Giroire <>
Soumis le : mardi 21 mai 2013 - 14:36:02
Dernière modification le : samedi 17 septembre 2016 - 01:36:49
Document(s) archivé(s) le : mardi 4 avril 2017 - 09:04:10

Fichier

report.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00824269, version 1

Collections

Citation

Frédéric Giroire, Remigiusz Modrzejewski, Nicolas Nisse, Stéphane Pérennes. Maintaining Balanced Trees For Structured Distributed Streaming Systems. [Research Report] RR-8309, INRIA. 2013. <hal-00824269>

Partager

Métriques

Consultations de
la notice

421

Téléchargements du document

150