TP1: Simulation d'Algorithmes d'Election : DAVIS
L'objectif de ce TP est d'étudier différents algorithmes d'élection à
l'aide de davis, un environnement de visualisation d'algorithmes
distribués pour le simulateur JBotSim.
Logiciels de Simulation et Visualisation
Installer le logiciel et lire la documentation
Installation simple
Téléchargez udavis.zip
dans le répertoire courant.
Dézipper udavis.zip
$ unzip udavis.zip
Pour simplifier les commandes ensuite, ajouter ce chemin au PATH
$ export PATH=$PATH:`pwd`/bin
Pour vérifier que tout fonctionne faire
$ udavis
µdavis (version)
A micro viewer for JBotsim.
Usage: udavis [-x] <network class> <id scheme> <size> <algo class>
Ces logiciels nécessitent Java 8 (ou supérieur). En cas de problème,
vérifiez votre CLASSPATH.
Ces logiciels sont en version béta, n'hésitez-pas à emmanuel.godard.ANTISPAM@lif.univ-mrs.fr?subject=Bug%20Davis.
Exemple: Algorithme d'Election
Pour vous familiariser avec le logiciel, téléchargez le fichier suivant. Puis faire
$ udavis UnidirRing RandomIds 25 QElection.java
Que constatez-vous ?
Components de l'algorithm
Familiariser vous avec les components différents du code écrit à "QElection.java"- Comment construire un anneau unidirectionnel? Pour les autres topologies possible voir ici
- Comment faire pour l'attribution d'identifiants aux processus? Voir le doc
L’algorithme écrit dans le fichier "QElection.java" est pour l'election dans les anneaux unidirectionnels. Essayez avec des anneaux de taille différente.
Complexité
On étudie la complexité ie le nombre de messages transmis pendant l'exécution de l'algorithme.
Chaque message reçus apparait sur une ligne de la forme
RECV 649 40 (terminated) -> 24 (passive): 40
où le deuxième champ correspond au numéro du message. Le nombre total de messages est donc le numéro du dernier message reçu.
Notez que vous pouvez lancer une exécution automatiquement (sans GUI) et rediriger les logs dans un fichier avec
$ udavis -x UnidirRing RandomIds 25 QElection.java > QElection.log
Calculer la complexité moyenne en effectuant au moins 15 exécutions. Est-ce que les résultats correspondent avec l’analyse théorique vue pendant le cours ?
On pourra créer de nouveaux schémas d'attribution d'identifiants en
s'inspirant de RandomIds.java