GMNP13
Summary
Giroire, F., Modrzejewski, R., Nisse, N. and P\'erennes, S. (2013) Maintaining Balanced Trees For Structured Distributed Streaming Systems. In Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO).. Springer. ((URL)) (PDF)
Abstract
In this paper, we propose and analyze a simple localized 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 tree in {$O(n^2)$} turns. We then describe a more restrictive model, adding a small extra information to each node, for which the convergence is reached in {$O(n\log n)$} turns and this bound is tight. We then exhibit by simulation that the convergence is much faster (logarithmic number of turns in average) for a random tree.
Bibtex entry
@INPROCEEDINGS { GMNP13,
AUTHOR = { Giroire, F. and Modrzejewski, R. and Nisse, N. and P\'erennes, S. },
TITLE = { Maintaining Balanced Trees For Structured Distributed Streaming Systems },
BOOKTITLE = { Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO) },
YEAR = { 2013 },
PUBLISHER = { Springer },
SERIES = { Lecture Notes in Computer Science },
ABSTRACT = { In this paper, we propose and analyze a simple localized 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 tree in {$O(n^2)$} turns. We then describe a more restrictive model, adding a small extra information to each node, for which the convergence is reached in {$O(n\log n)$} turns and this bound is tight. We then exhibit by simulation that the convergence is much faster (logarithmic number of turns in average) for a random tree. },
URL = { http://hal.inria.fr/hal-00824269 },
PDF = { http://hal.inria.fr/hal-00824269/PDF/report.pdf },
BOARD = { yes },
}