Un algorithme de Las Vegas : l'élection d'un chef

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 stochastiques, 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 votants ; au début, les n candidats sont votants, et à la fin, le seul candidat qui reste votant est le chef élu. À chaque tour, chaque candidat votant tire un nombre au hasard compris entre 1 et le nombre de votants, 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   1   2   3   4   5   6   7   8   9
tire     1   2   3   9  10   3   8   5   1   1 
         1                               1   2
         2                               2
         2                               2
         2                               1

La seule difficulté de programmation provient du cas t=0 qui oblige à conserver en mémoire l'activité d'un candidat afin de recommencer le vote. La méthode tour() définit ce que fait chaque candidat. La méthode chef() définit le << protocole >> de l'élection et retourne le chef élu :

 

class Election { 
  private Random g; 
  private int nbCandidats; 
  private int nbVotants; 
  Candidat[] candidats; 
  private int nbActifs;
    
  Election(int n) {
    nbCandidats = n;
    candidats = new Candidat[n];
    for (int i=0; i<nbCandidats; i++) {
      candidats[i] = new Candidat();
    }
    nbVotants = n;
    g = new Random();
  }

  class Candidat {
    boolean votant;
    boolean éliminé;
    Candidat() {
      votant = true;
      éliminé = false;
    }
    void tour() {
      int choix = g.nextInt(1+nbVotants);
      if (choix != 1) {
        votant = false;  // devient inactif
      } else {
        nbActifs ++;
      }
    }
  }      

  int chef() {
    int élu = 0;
    while (nbVotants != 1) {
      nbActifs = 0;
      for (int i=0; i<nbCandidats; i++) {
        if (candidats[i].votant) {
          candidats[i].tour();
        }
      } 
      for (int i=0; i<nbCandidats; i++) {
        if (!candidats[i].éliminé) {
          if (nbActifs == 0) candidats[i].votant = true;
          else if (nbActifs>1 && !candidats[i].votant)
            candidats[i].éliminé = true;
          else if (nbActifs==1 && candidats[i].votant)
            élu = i;
        }
      }
      if (nbActifs != 0) nbVotants = nbActifs;
    }
    return élu;
  }
  
  public static void main(String[] args) {
    Election élection = new Élection(10);
    System.out.println(élection.chef());
  }
}

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.