3.4 Modélisations par des structures arborescentes
107
Il est facile de modifier l’algorithme pour qu’il désigne toujours un vainqueur
(ou un perdant, selon le point de vue qu’on adopte !) : lorsque tous tirent la même
valeur, que ce soit Pile ou Face, tous participent au tour suivant. Dans ce cas, le
nombre d’essais est égal à la longueur de la branche conduisant à la feuille la plus
à gauche du trie. C’est cette variante qui est souvent analysée, par exemple par
Prodinger [217] ou par Fill et al. [78]. Une autre manière d’exprimer le nombre de
tours pour désigner le payeur est de voir ce nombre comme égal à la somme de la
hauteur de la feuille la plus à gauche dans l’arbre PATRICIA qui serait obtenu en
compactant les branches filiformes du trie (cela correspond au nombre de tours qui
réduisent effectivement le nombre de participants) et du nombre de « virages » y
conduisant (c’est le nombre de tours qui n’ont pas permis d’éliminer au moins un
participant).
Un raffinement de l’analyse de l’algorithme des buveurs de bière considère le
nombre de personnes (survivants) restant en lice après un temps t. Cela revient à
regarder le nombre de clés qui ont un préfixe donné de longueur t, i.e., la taille
d’un sous-arbre dont la racine est à profondeur t ; cf. par exemple l’article de
Louchard et Prodinger [168]. Une autre variante s’intéresse, au contraire, à la
situation rencontrée à un temps t avant la fin de l’algorithme (rappelons que le
temps de fin est une variable aléatoire) : il s’agit ici de regarder le nombre de clés
contenues dans le sous-arbre de hauteur t et contenant la feuille la plus à gauche de
l’arbre ; cf. Louchard [167].
3.4.5 Protocole en arbre
Considérons un réseau de communication, formé d’un canal commun de transmission, qui ne peut transmettre à chaque instant donné qu’un message au plus, et de
stations reliées à ce canal. Lorsqu’une station écoute le canal partagé, il peut être
dans un des trois états suivants : inoccupé : aucune station n’émet ; émission :
une seule station émet ; collision : plusieurs stations essaient d’émettre au même
moment, ce qui provoque un conflit. Il existe plusieurs algorithmes pour résoudre
ces conflits ; nous nous intéressons ici au protocole en arbre dans sa version la plus
simple, dite à accès bloqué. Des protocoles en arbre plus généraux sont considérés
dans Mohamed et Robert [186] et y sont analysés par une approche probabiliste
(figure 3.34).
Lorsque n stations veulent émettre au même moment, et entrent donc en collision,
l’ensemble de ces stations est divisé en deux par un tirage à pile ou face. Les stations ayant
tiré Pile résolvent récursivement leurs conflits ; les stations ayant tiré Face résoudront
ensuite à leur tour leurs propres conflits. Si une seule station tire Pile, elle peut alors
émettre.
Ce protocole de résolution de collisions est celui du réseau Aloha, développé
au début des années 70 par l’université de Hawaï et qui est à la base du protocole
Ethernet. Les articles le présentant sont dus à Capetanakis [32] et à Tsybakov et
Mikhailov [242] ; l’on pourra se reporter par exemple à Flajolet et Jacquet [85] pour
son analyse.
107
Il est facile de modifier l’algorithme pour qu’il désigne toujours un vainqueur
(ou un perdant, selon le point de vue qu’on adopte !) : lorsque tous tirent la même
valeur, que ce soit Pile ou Face, tous participent au tour suivant. Dans ce cas, le
nombre d’essais est égal à la longueur de la branche conduisant à la feuille la plus
à gauche du trie. C’est cette variante qui est souvent analysée, par exemple par
Prodinger [217] ou par Fill et al. [78]. Une autre manière d’exprimer le nombre de
tours pour désigner le payeur est de voir ce nombre comme égal à la somme de la
hauteur de la feuille la plus à gauche dans l’arbre PATRICIA qui serait obtenu en
compactant les branches filiformes du trie (cela correspond au nombre de tours qui
réduisent effectivement le nombre de participants) et du nombre de « virages » y
conduisant (c’est le nombre de tours qui n’ont pas permis d’éliminer au moins un
participant).
Un raffinement de l’analyse de l’algorithme des buveurs de bière considère le
nombre de personnes (survivants) restant en lice après un temps t. Cela revient à
regarder le nombre de clés qui ont un préfixe donné de longueur t, i.e., la taille
d’un sous-arbre dont la racine est à profondeur t ; cf. par exemple l’article de
Louchard et Prodinger [168]. Une autre variante s’intéresse, au contraire, à la
situation rencontrée à un temps t avant la fin de l’algorithme (rappelons que le
temps de fin est une variable aléatoire) : il s’agit ici de regarder le nombre de clés
contenues dans le sous-arbre de hauteur t et contenant la feuille la plus à gauche de
l’arbre ; cf. Louchard [167].
3.4.5 Protocole en arbre
Considérons un réseau de communication, formé d’un canal commun de transmission, qui ne peut transmettre à chaque instant donné qu’un message au plus, et de
stations reliées à ce canal. Lorsqu’une station écoute le canal partagé, il peut être
dans un des trois états suivants : inoccupé : aucune station n’émet ; émission :
une seule station émet ; collision : plusieurs stations essaient d’émettre au même
moment, ce qui provoque un conflit. Il existe plusieurs algorithmes pour résoudre
ces conflits ; nous nous intéressons ici au protocole en arbre dans sa version la plus
simple, dite à accès bloqué. Des protocoles en arbre plus généraux sont considérés
dans Mohamed et Robert [186] et y sont analysés par une approche probabiliste
(figure 3.34).
Lorsque n stations veulent émettre au même moment, et entrent donc en collision,
l’ensemble de ces stations est divisé en deux par un tirage à pile ou face. Les stations ayant
tiré Pile résolvent récursivement leurs conflits ; les stations ayant tiré Face résoudront
ensuite à leur tour leurs propres conflits. Si une seule station tire Pile, elle peut alors
émettre.
Ce protocole de résolution de collisions est celui du réseau Aloha, développé
au début des années 70 par l’université de Hawaï et qui est à la base du protocole
Ethernet. Les articles le présentant sont dus à Capetanakis [32] et à Tsybakov et
Mikhailov [242] ; l’on pourra se reporter par exemple à Flajolet et Jacquet [85] pour
son analyse.