Élection d'un chef à Las Vegas

Quand deux personnes d'une égale politesse et sans la moindre imagination s'apprêtent à franchir une porte au même moment, on déplore une interminable suite d'<< après vous, je vous en prie >>. Quand le même phénomène se produit dans un réseau de machines, on constate un blocage irrémédiable. Par exemple, si deux machines d'un réseau local émettent simultanément un paquet de données sur le réseau et constatent une collision, il ne faut pas que ces deux machines réémettent à l'issue d'un même délai. La solution est de briser la symétrie en introduisant de l'aléatoire, en recourant à une catégorie d'algorithmes probabilistes, dits de Las Vegas.

Considérons le problème de l'élection d'un chef parmi $n$ candidats ; ce problème généralise celui du passage de portes et trouve des applications très importantes aux protocoles dans les réseaux de communication qui ne comportent pas de contrôle centralisé.

L'algorithme d'élection consiste à éliminer par tours successifs les candidats actifs ; au début, les $n$ candidats sont actifs, et à la fin, le seul candidat qui reste actif est le chef élu. À chaque tour, chaque candidat tire un nombre au hasard compris entre 1 et le nombre d'actifs, et on compte le nombre $t$ de 1 qui ont été tirés. Si $t=0$, on recommence ; si $t>1$, seuls les candidats qui ont tiré un 1 restent actifs pour le tour suivant ; si $t=1$, on s'arrête, le chef étant celui qui a tiré ce 1. Voici une trace d'exécution de cet algorithme :

candidat 0 tire 1
candidat 1 tire 2
candidat 2 tire 3
candidat 3 tire 9
candidat 4 tire 10
candidat 5 tire 3
candidat 6 tire 8
candidat 7 tire 5
candidat 8 tire 1
candidat 9 tire 1

restent actifs = 3
candidat 0 tire 1
candidat 8 tire 1
candidat 9 tire 2

restent actifs = 2
candidat 0 tire 2
candidat 8 tire 2

restent actifs = 2
candidat 0 tire 2
candidat 8 tire 2

restent actifs = 2
candidat 0 tire 2
candidat 8 tire 2

restent actifs = 2
candidat 0 tire 1
candidat 8 tire 2

restent actifs = 1
le chef est le candidat 0

La seule difficulté de programmation provient du cas $t=0$ qui oblige, d'une part, à conserver en mémoire l'activité d'un candidat, alors qu'il serait plus simple de le déclarer inactif dès qu'il a tiré un nombre différent de 1, et d'autre part, à oublier l'activité précédente quand $t\not= 0$. On utilise pour cela une structure à deux champs pour l'activité courante et l'activité précédente. Ces champs sont initialisés à 1 pour tous. La fonction tour(i,m) définit ce que fait le i-ème candidat quand il reste m candidats actifs (c'est tout ce qu'on demande à un candidat de savoir faire). La fonction chef() définit le << protocole >> de l'élection :

const int N = 10;
struct act { 
  int courante; 
  int precedente; 
};
act activite[N];
int actifs = N;

void init() {
  int i;

  for (i=0; i<N; i++) {
    activite[i].courante = 1;
    activite[i].precedente = 1;
  }
}

void tour(int i, int m) {
  int choix = irand(1, m);

  cout << "candidat " << i << "tire " << choix << endl;
    if (choix != 1) {
      activite[i].courante = 0;    // devient inactif 
    } else {
      actifs ++;
    }
}

int chef() {
  int i;

  init();
  while (actifs != 1) {
    int m = actifs;

    actifs = 0;
    for (i=0; i<N; i++) {
      if (activite[i].courante) {
        tour(i, m);
      }
    }
    if (actifs == 0) {
      // ce tour n'a pas départagé de candidats 
      for (i=0; i<N; i++) {
        // on restitue l'activité précédente 
        activite[i].courante = activite[i].precedente;
      }
    // on restitue le nombre d'actifs 
    actifs = m;
    } else {
      for (i=0; i<N; i++) {
        // on oublie les activités précédentes 
        activite[i].precedente = activite[i].courante;
      }
    }
    cout << "\nrestent actifs = " << actifs << endl;
  }
  for (i=0; !activite[i].courante; i++) { ; }
  return i;
}

Cet algorithme ne termine pas nécessairement, mais quand il termine, le résultat est toujours correct, un chef est élu : ce comportement est différent des algorithmes de Monte-Carlo qui terminent toujours, mais dont le résultat n'est correct qu'avec une certaine probabilité d'erreur. Les probabilités interviennent ici seulement pour estimer le nombre de tours probable.

La probabilité pour que $k$ candidats parmi $n$ actifs ($0\le k\le n$), tirent une valeur donnée entre 1 et $n$ (chacune ayant la même probabilité $1/n$) est donnée par une loi binômiale : $p(n,k) = C_n^k (\frac{1}{n})^k (1 - \frac{1}{n})^{n-k}$. On peut montrer que l'espérance du nombre de tours nécessaires pour choisir un chef parmi $n$ candidats est asymptotiquement constante ; la probabilité que l'algorithme ne termine pas est nulle, autrement dit, la terminaison est presque sûre. L'obstination conduit presque sûrement à un résultat correct.