Algorithmique de la mobilité

↑ Accueil du cours


Protocoles de population

Le modèle des protocoles de population (PP) est un modèle abstrait pour l'algorithmique distribuée (de type transformation de graphes). Dans ce modèle, une étape de calcul correspond à une modification atomique des états de deux noeuds voisins. De plus, afin de casser la symétrie locale entre ces deux voisins, deux rôles différents leurs sont attribués pendant l'interaction: l'un est initiateur, l'autre est répondant.

L'environnement d'exécution consiste en un ordonnanceur et un algorithme. L'ordonnanceur (aussi appelé adversaire ou démon) est responsable de choisir quelle paire de noeud interagit à chaque étape. L'algorithme, de son côté, réalise l'interaction en modifiant l'état des deux noeuds choisis. C'est aussi lui qui détermine l'état initial des noeuds, ce dernier pouvant être uniforme (tout les noeuds commencent dans le même état) ou non-uniforme (un ou plusieurs noeuds démarrent dans un état différent, appelé état distingué).

Structure d'un protocole

Avant de coder l'ordonnanceur, nous pouvons créer une classe PPNode qui encapsule les propriétés de tout protocole de population et dont nos propres protocoles hériteront plus tard. Ces propriétés se traduisent par trois méthodes abstraites que nos protocoles devront implémenter (quitte à les laisser vide). Ces méthodes correspondent aux mêmes éléments que plus haut, c'est à dire :

Voici la classe abstraite correspondante (PPNode).

import io.jbotsim.core.Node;

public abstract class PPNode extends Node {
    // Assign default initial state to underlying node
    public abstract void onStart();
    // Assign distinguished initial state to underlying node
    public abstract void onSelection();
    // Execute interaction (from the initiator side)
    public abstract void interactWith(Node responder);
}

Exemple: protocole basique pour la propagation d'information

Ce protocole consiste à propager une information depuis un noeud initial (état distingué) à tous les autres noeuds du réseau, initialement non-informés (état par défaut). Lorsqu'une interaction a lieu entre deux noeuds, le traitement consiste à tester si l'un des deux noeuds est informé et l'autre non, et si tel est le cas, ce dernier devient informé également. Cette règle pourrait être représentée graphiquement comme suit: o--x → o--o. Pour une meilleure visualisation, on peut encoder les états sous forme de couleurs, par exemple en rouge les noeuds informés et en bleu les non-informés. Ainsi, l'état initial par défaut pour tous les noeuds est le bleu, et lorsqu'on clique sur un noeud pour le sélectionner, il prend la couleur rouge. Voici le code correspondant.

import io.jbotsim.core.Color;
import io.jbotsim.core.Node;

public class PPNodeAlgo1 extends PPNode {
    @Override
    public void onStart() {
        setColor(Color.blue);
    }
    @Override
    public void onSelection() {
        setColor(Color.red);
    }
    @Override
    public void interactWith(Node responder) {
        if (this.getColor() == Color.red && responder.getColor() == Color.blue)
            responder.setColor(Color.red);
        else if (this.getColor() == Color.blue && responder.getColor() == Color.red)
            this.setColor(Color.red);
    }
}

Une fois l'ordonnanceur et la méthode main() créés (plus loin ci-dessous), l'exécution de ce protocole de ce protocole donnera quelque chose de similaire à cette figure. Une vidéo est aussi disponible ici.

Exécution d'un protocole de population.

L'ordonnanceur

Écrivons maintenant l'ordonnanceur qui décide globalement à chaque étape quelle paire de noeuds interagissent. Ici, le choix sera fait aléatoirement (u.a.r.) parmi tous les liens du réseau, et l'interaction aura lieu entre les deux noeuds du lien choisi, en appelant la méthode interactWith sur le noeud initiateur (seulement). Voici le code.

import io.jbotsim.core.Link;
import io.jbotsim.core.Topology;
import io.jbotsim.core.event.ClockListener;

import java.util.List;

public class PPScheduler implements ClockListener {
    Topology tp;

    public PPScheduler(Topology topology) {
        tp = topology;
        tp.addClockListener(this);
    }

    @Override
    public void onClock() {
        // Retrieve all links
        List<Link> links = tp.getLinks();
        if ( ! links.isEmpty() ) {
            // Pick a link at random
            Link selectedLink = links.get((int) (Math.random() * links.size()));
            // Make it bold for visualization
            drawInteraction(selectedLink);
            // Pick initiator side at random
            PPNode initiator = (PPNode) selectedLink.endpoint((int) (Math.random() * 2));
            PPNode responder = (PPNode) selectedLink.getOtherEndpoint(initiator);
            // Perform interaction
            initiator.interactWith(responder);
        }
    }

    // Draw a given link in bold (and unbold others)
    public void drawInteraction(Link selectedLink){
        for (Link link : tp.getLinks())
            link.setWidth(1);
        selectedLink.setWidth(3);
    }
}

Méthode main() (et sa classe)

On y est presque ! Il n'y a plus qu'à fixer les paramètres de la simulation dans la méthode main(), à savoir créer une topologie; specifier quel type de noeud doit être utilisé par défaut (ici PPNodeAlgo1); ralentir l'exécution à 100ms le round pour y voir mieux; et enfin créer l'ordonnanceur et le viewer.

import io.jbotsim.core.Topology;
import io.jbotsim.ui.JViewer;

public class MainPP {
    public static void main(String[] args) {
        Topology tp = new Topology();
        tp.setDefaultNodeModel(PPNodeAlgo1.class);
        tp.setTimeUnit(100);
        new PPScheduler(tp);
        new JViewer(tp);
        tp.start();
    }
}

Exercices

Q1. Vérifiez que tout fonctionne bien et assurez-vous d'avoir bien compris le code de toutes ces classes. Pour mémoire, on peut sélectionner un noeud en cliquant dessus avec la molette (sur PC) et via command-shift-clic (sur mac).

Dans la suite, nous allons considérer trois protocoles dont le but est de compter combien de noeuds sont présents dans le réseau. Ces protocoles vont du plus limité (mais très simple) jusqu'au meilleur.

Counting v1: Dans ce premier protocole, l'un des noeuds est distingué comme compteur et son rôle est de compter les noeuds avec lesquels il interagit. Les autres sont initialement dans l'état non compté, puis à mesure que le compteur interagit avec eux, ils passent dans l'état compté. Il est essentiel d'avoir ces deux états, sinon le compteur risque de compter plusieurs fois le même noeud.

Q2. Implémenter ce protocole de comptage dans une classe dédiée qui hérite de PPNode. On peut représenter les trois états (i.e. compteur, compté, et non compté) par trois couleurs, et le décompte par une variable entière que seule le compteur utilise. Ce protocole est très limité, et c'est normal ! On ne vous demande pas de l'améliorer.

Astuce de visualisation: il est possible de redéfinir la méthode toString() pour qu'elle renvoie le décompte lorsqu'elle est appelée sur le noeud compteur (et une chaine vide sur les autres noeuds). Cette méthode sera utilisée automatiquement par JBotSim pour remplir l'étiquette des noeuds.

Q3. Quelle condition le graphe sous-jacent doit-il satisfaire pour que l'algorithme ait une chance de compter tout le monde ?

Bien sûr, cette hypothèse est rarement vérifiée en pratique et il est préférable que votre protocole fonctionne avec moins d'hypothèses.

Counting v2 (highlander): Définissons maintenant un second protocole de comptage. Il ne sera pas encore parfait, mais sera mieux que le précédent pour (au moins) deux aspects : 1) il a une initialisation uniforme, c.à.d. qu'il n'a pas besoin de noeud distingué (tout le monde a le même état initialement), et 2) il est susceptible de réussir dans plus de graphes. Son principe est le suivant : initialement chaque noeud est un compteur dont le décompte est égal à 1 (il s'est compté lui-même). Puis, lorsque deux compteurs non-nuls interagissent, ils s'affrontent. Le gagnant (disons l'initiateur) reste compteur et l'autre (le répondant) n'est plus compteur. De plus, le perdant se fait voler son décompte par le gagnant, qui cumule maintenant les deux décomptes.

Q4. Implémenter ce protocole.

Q5. On dira que l'exécution a réussi s'il ne reste qu'un seul compteur à la fin. En effet, il est clair que si seulement un compteur reste, alors ce dernier connait le nombre total de noeuds dans le réseau (qui a parlé d'invariant ?). Est-il vrai que l'algorithme a des chances de réussir (même petites) du moment que le graphe est connexe ? Si oui, le succès est-il garanti pour autant dans n'importe quel graphe connexe ? Maintenant, vous comprenez sûrement pourquoi l'ordonnanceur est parfois appelé adversaire.

Counting v3 (highlander, le retour): Nous allons maintenant concevoir un protocole de comptage encore meilleur. Son initialisation est uniforme et cette fois, il fonctionne dans tous les graphes connexes. Son principe est quasiment le même que pour Counting v2, à ceci près que les interactions sont légèrement plus complexes. Comme précédemment, si deux compteurs interagissent, l'un des deux obtient la somme de leurs décomptes et l'autre n'est plus compteur. Mais si l'interaction implique un compteur et un non-compteur, alors il se passe aussi quelque chose : leurs rôles sont échangés, le compteur devient non-compteur et le non-compteur devient compteur en volant le décompte du compteur. En bref, l'état complet du compteur migre sur un autre noeud.

Q6. Implémenter ce protocole.

Q7. Supposons pour un instant que le graphe d'interaction soit complet et qu'on continue à utiliser un ordonnanceur aléatoire. Soit E[T] l'espérance du temps qu'il faut jusqu'à ce qu'il n'y ait plus qu'un seul compteur. Quel protocole entre Counting v2 and Counting v3 a l'espérance la plus petite ? Autrement dit, lequel converge le plus vite en moyenne ?

Q8 (facultatif, demandez à l'enseignant). Combien de temps cela prendra-t-il (toujours en espérance et dans un graphe complet) en function du nombre de noeuds $n$. Si vous êtes flemmards, vous pouvez lancer des simulations et faire la moyenne pour différentes valeurs de $n$. Autrement, l'analyse mathématique est belle car elle donne à l'arrivée une formule très simple !

Suite de la séance

  1. Un algorithme de maintien d'une forêt d'arbres couvrants dans un réseau très dynamique.