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)$.