Information transmission under random emission constraints - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Combinatorics, Probability and Computing Année : 2014

Information transmission under random emission constraints

Résumé

We model the transmission of a message on the complete graph with n vertices and limited resources. The vertices of the graph represent servers that may broadcast the message at random. Each server has a random emission capital that decreases at each emission. Quantities of interest are the number of servers that receive the information before the capital of all the informed servers is exhausted and the exhaustion time. We establish limit theorems (law of large numbers, central limit theorem and large deviation principle), as n tends to infinity, for the proportion of visited vertices before exhaustion and for the total duration. The analysis relies on a construction of the transmission procedure as a dynamical selection of successful nodes in a Galton-Watson tree with respect to the success epochs of the coupon collector problem.
Fichier principal
Vignette du fichier
CDS3_21_10.pdf (362.07 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00637304 , version 1 (31-10-2011)
hal-00637304 , version 2 (21-11-2012)

Identifiants

Citer

Francis Comets, François Delarue, René Schott. Information transmission under random emission constraints. Combinatorics, Probability and Computing, 2014, 23, pp.973-1009. ⟨10.1017/S096354831400039X⟩. ⟨hal-00637304v2⟩
563 Consultations
336 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More