À propos de mathématiques
Algorithme en arbre et théorème de renouvellement
Mohamed, Hanène1
1 INRIA Rocquencourt Domaine de Voluceau B.P. 105, 78153 Le Chesnay Cedex France
Femmes & math, Forum 8 des Jeunes Mathématiciennes, Tome 8 (2006), pp. 57-62.

Un réseau de communication à accès multiple est un système distribué de n noeuds, appelés stations, partageant un canal commun de transmission ne pouvant transmettre qu’un seul message par unité de temps. Ce canal renvoie une information ternaire, i.e. chaque station envoyant un message au réseau peut simultanément écouter le canal est ainsi détecter une collision s’il y a eu au moins deux essais de transmission, un silence si aucune station n’a envoyé de messages, ou alors un succès si une seule station a transmis son message vers le réseau.

Question : Comment un tel système sans contrôle central peut s’ordonner pour transmettre ses messages en un temps fini ?

On s’intéresse à l’algorithme décrit ci-dessus, appelé algorithme en arbre ou diviser pour régner, et ce d’un point de vue probabiliste.

Mohamed, Hanène 1

1 INRIA Rocquencourt Domaine de Voluceau B.P. 105, 78153 Le Chesnay Cedex France 
@article{RFM_2006__8__57_0,
     author = {Mohamed, Han\`ene},
     title = {Algorithme en arbre et th\'eor\`eme de renouvellement},
     journal = {Femmes & math},
     pages = {57--62},
     publisher = {Association femmes et math\'ematiques},
     volume = {8},
     year = {2006},
     language = {fr},
     url = {http://www.numdam.org/item/RFM_2006__8__57_0/}
}
TY  - JOUR
AU  - Mohamed, Hanène
TI  - Algorithme en arbre et théorème de renouvellement
JO  - Femmes & math
PY  - 2006
SP  - 57
EP  - 62
VL  - 8
PB  - Association femmes et mathématiques
UR  - http://www.numdam.org/item/RFM_2006__8__57_0/
LA  - fr
ID  - RFM_2006__8__57_0
ER  - 
%0 Journal Article
%A Mohamed, Hanène
%T Algorithme en arbre et théorème de renouvellement
%J Femmes & math
%D 2006
%P 57-62
%V 8
%I Association femmes et mathématiques
%U http://www.numdam.org/item/RFM_2006__8__57_0/
%G fr
%F RFM_2006__8__57_0
Mohamed, Hanène. Algorithme en arbre et théorème de renouvellement. Femmes & math, Forum 8 des Jeunes Mathématiciennes, Tome 8 (2006), pp. 57-62. http://www.numdam.org/item/RFM_2006__8__57_0/

[1] John I. Capetanakis, Tree algorithms for packet broadcast channels, IEEE Transactions on Information Theory 25, 1979. | MR | Zbl

[2] B. S. Tsybakov and V. A. Mikhaïlov, Free synchronous packet access in a broadcast channel with feedback, Problems Inform. Transmission 14, 1978. | MR | Zbl

[3] P. Mathys and P. Flajolet, Q -ary collision resolution algorithms in random access systems with free or blocked channel access, IEEE Transactions on Information Theory 31, 1985. | MR | Zbl

[4] Philippe Robert, On the asymptotic behavior of some algorithms, Random Structures & Algorithms 27, 2005. | MR | Zbl

[5] Hanène Mohamed and Philippe Robert, A probabilistic analysis of some tree algorithms, Annals of Applied Probability 15, 2005. | MR | Zbl