S�minaire du 28 avril 03, Jean-Fran�ois Marckert.

�lection �conome d'un leader dans un r�seau

On s'int�resse � deux probl�mes d'�lection dans un r�seau. Pour rendre les choses plus intuitives, on parlera du mod�le du talkie-walkie (TK) et du mod�le du t�l�phone (P). Dans le mod�le du TK les individus peuvent faire trois choix~: parler, �couter ou �teindre le TK. Dans le mod�le P, les individus ont deux choix~: parler et/ou �couter (ils peuvent faire les deux en m�me temps) ou �teindre.

Dans ces deux mod�les, $n$ individus cherchent � �lire l'un d'entre eux (mais ne connaissent pas $n$). On donne dans chacun de ces cas une strat�gie permettant de mener � bien l'�lection (en un temps moyen $O(\log n)$)\,; ces proc�dures d'�lection ont �galement la propri�t� d'�tre efficaces en terme d'�nergie (c'�tait d'ailleurs une des motivations)~: les appareils ne seront allum�s qu'un temps moyen $O(\log\log n)$.