Dynamic Tree Algorithms

Abstract : In this paper, a general tree algorithm processing a random flow of arrivals is analyzed. Capetanakis-Tsybakov-Mikhailov's protocol in the context of communication networks with random access is an example of such an algorithm. In computer science, this corresponds to a trie structure with a dynamic input. Mathematically, it is related to a stopped branching process with exogeneous arrivals (immigration). Under quite general assumptions on the distribution of the number of arrivals and on the branching procedure, it is shown that there exists a {\em positive} constant $\lambda_c$ so that if the arrival rate is smaller than $\lambda_c$, then the algorithm is stable under the flow of requests, i.e. that the total size of an associated tree is integrable. At the same time a gap in the earlier proofs of stability of the literature is fixed. When the arrivals are Poisson, an explicit characterization of $\lambda_c$ is given. Under the stability condition, the asymptotic behavior of the average size of a tree starting with a large number of individuals is analyzed. The results are obtained with the help of a probabilistic rewriting of the functional equations describing the dynamic of the system. The proofs use extensively this stochastic background throughout the paper. In this analysis, two basic limit theorems play a key role: the renewal theorem and the convergence to equilibrium of an auto-regressive process with moving average.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

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

Contributeur : Philippe Robert <>
Soumis le : dimanche 21 septembre 2008 - 11:03:52
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : vendredi 4 juin 2010 - 11:38:49


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00323350, version 1
  • ARXIV : 0809.3577



Hanene Mohamed, Philippe Robert. Dynamic Tree Algorithms. 2008. 〈inria-00323350〉



Consultations de la notice


Téléchargements de fichiers