# 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.
Keywords :
Document type :
Preprints, Working Papers, ...
Domain :

Cited literature [16 references]

https://hal.inria.fr/inria-00323350
Contributor : Philippe Robert <>
Submitted on : Sunday, September 21, 2008 - 11:03:52 AM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on: : Friday, June 4, 2010 - 11:38:49 AM

### Files

Hal.pdf
Files produced by the author(s)

### Identifiers

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

### Citation

Hanene Mohamed, Philippe Robert. Dynamic Tree Algorithms. 2008. ⟨inria-00323350⟩

Record views
{"ft_lang_label":"__label__en","ft_lang_prob":0.89286804,"math_prob":0.91352093,"size":1462,"snap":"2020-45-2020-50","text_gpt3_token_len":286,"char_repetition_ratio":0.10768176,"word_repetition_ratio":0.0,"special_character_ratio":0.1867305,"punctuation_ratio":0.09375,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.95541495,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-10-22T10:08:20Z\",\"WARC-Record-ID\":\"<urn:uuid:c5926e38-1b49-4f65-aa96-5212e842e7eb>\",\"Content-Length\":\"51691\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:40b298b0-ac6f-41db-b88d-d18f794d9e47>\",\"WARC-Concurrent-To\":\"<urn:uuid:41e680ce-0c71-4fe7-9d09-9256d01593d8>\",\"WARC-IP-Address\":\"193.48.96.10\",\"WARC-Target-URI\":\"https://hal.inria.fr/inria-00323350\",\"WARC-Payload-Digest\":\"sha1:SWZNQKKQTKNO5FUFQKEPEPO7674GTJVW\",\"WARC-Block-Digest\":\"sha1:R3H47TI2KLWDQQLNGJJ37BMU5TQLMQB2\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-45/CC-MAIN-2020-45_segments_1603107879362.3_warc_CC-MAIN-20201022082653-20201022112653-00113.warc.gz\"}"}