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

Rédigé par GC Team, Publié le 01 Mars 2010, Mise à jour le Mardi, 10 Août 2021 22:10
Participez au vote ☆☆☆☆☆★★★★★

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

1
2
3
4

Si visite = faux alors
visite - vrai
pere - j
Fin Si

 

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

{sidebar id=6}{sidebar id=1}

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

6) Afin de réaliser des statistiques sur le temps nécessaire à la couverture complète du réseau, faites apparaître

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