Exercice linux - Simulation de l’algorithme de Bar-Ilan et Zernick -

Le but de l’algorithme de Bar-Ilan et Zernick est de construire un arbre couvrant aléatoire d’un graphe de manière totalement décentralisée. Cet algorithme est basé sur la circulation aléatoire d’un jeton dans le graphe: le nœud qui crée le jeton est la racine de l’arbre couvrant. Lorsqu’un nœud du graphe reçoit le jeton pour la première fois, il marque l’émetteur du jeton comme étant son père dans l’arbre couvrant. L’algorithme se termine lorsque tous les nœuds du graphe ont été visités.

Chaque nœud possède une variable “visite” qui est initialisée à “faux” et une variable “pere” qui indique l’identité du nœud du père. À la réception du jeton J, l’algorithme suivant est exécuté:

algorithme 1 Réception d’un jeton J sur un site i provenant du nœud j

Envoyer J à k choisi uniformément au hasard parmi les voisins de i

1) Combien de types de nœud sont-ils nécessaires? Et de messages? Créez un simulateur “barilan” et configurez le “makefile”.

2) L’émetteur d’un message “MsgEvent *msg” peut être récupéré à l’aide de la méthode “getEmitter()”. Quelles sont les données nécessaires dans le jeton?

3) D’après l’algorithme de Bar-Ilan et Zernick, quelles sont les données nécessaires sur chaque nœud? Modifiez la (ou les) classes du (ou des) nœud(s). Écrivez la méthode “MessageReception”.

4) Où créer le premier message? Modifiez le simulateur et exécutez-le.

5) À la fin de l’exécution, affichez l’arbre couvrant du réseau (indication: vous pouvez utiliser la structure “GraphTree”).

dans le fichier de statistiques (fichier .sta) le temps nécessaire pour couvrir 25%, 50%, 75% et 100% du réseau.