Maintaining Balanced Trees for Structured Distributed Streaming Systems

Frédéric Giroire 1 Remigiusz Modrzejewski 2 Nicolas Nisse 1 Stéphane Pérennes 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper, we propose and analyze a simple local algorithm to balance a tree. The motivation comes from live distributed streaming systems in which a source diffuses a content to peers via a tree, a node forwarding the data to its children. Such systems are subject to a high churn, peers frequently joining and leaving the system. It is thus crucial to be able to repair the diffusion tree to allow an efficient data distribution. In particular, due to bandwidth limitations, an efficient diffusion tree must ensure that node degrees are bounded. Moreover, to minimize the delay of the streaming, the depth of the diffusion tree must also be controlled. We propose here a simple distributed repair algorithm in which each node carries out local operations based on its degree and on the subtree sizes of its children. In a synchronous setting, we first prove that starting from any n-node tree our process converges to a balanced binary tree in O(n 2) rounds. We then describe a more restrictive model, adding a small extra information to each node, under which we adapt our algorithm to converge in Θ(n log n) rounds.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2017, 232, pp.176 - 188. 〈10.1016/j.dam.2017.07.006〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01620358
Contributeur : Nicolas Nisse <>
Soumis le : vendredi 20 octobre 2017 - 14:41:00
Dernière modification le : mardi 14 novembre 2017 - 08:18:03

Fichier

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

Identifiants

Collections

Citation

Frédéric Giroire, Remigiusz Modrzejewski, Nicolas Nisse, Stéphane Pérennes. Maintaining Balanced Trees for Structured Distributed Streaming Systems. Discrete Applied Mathematics, Elsevier, 2017, 232, pp.176 - 188. 〈10.1016/j.dam.2017.07.006〉. 〈hal-01620358〉

Partager

Métriques

Consultations de la notice

57

Téléchargements de fichiers

7