Final U - net

Final U.V. RE51
Sans documents
21 Janvier 03
J.Gaber(gaber@utbm.fr)
Exercice 1 : Parcours distribué en largeur
a) Donner l'algorithme du parcours distribué en largeur d'un système
distribué.
b) Cet algorithme permet la construction d'une arborescence quelconque de
racine le processus initiateur. Donner un ou plusieurs exemples
d'applications permettant d'illustrer l'intérêt de la construction de
cette structure arborescente. Exercice 2 : Parcours distribué en profondeur
Donner un algorithme distribué utilisant un parcours en profondeur et qui
permet à un initiateur de déterminer la taille d'un système distribué. La
taille d'un système distribué est définie comme le nombre de processus
appartenant à ce système (e.g., le nombre de sites dans le réseau).
Initialement, un site ne connaît que ses voisins immédiats. Exercice 3 : Le coloriage d'un graphe
Soit G un graphe représentant le réseau de communication d'un système
distribué. On désire colorier ce graphe selon le principe de coloriage
suivant :
- deux sites voisins immédiats sont de couleurs différentes,
- on utilise le nombre minimum de couleurs possible. On représente les
couleurs par des entiers naturels.
Donner un algorithme distribué, avec un seul initiateur, permettant le
coloriage du graphe. Exercice 4 : L'exclusion mutuelle
a) L'algorithme de Naimi-Tréhel utilise une structure arborescente pour
résoudre le problème de l'exclusion mutuelle. Considérons l'exemple
suivant. On dispose d'un système distribué contenant 5 sites. On suppose
que le graphe (i.e., le réseau) connectant les sites est complet. Soit le
scénario suivant :
1) initialement, le site 1 possède le privilège et utilise la section
critique, le site 2 demande à entrer en section critique et le site
1 quitte la section critique,
2) le site 3 demande à entrer en section critique,
3) le site 4 demande à entrer en section critique,
4) le site 2 quitte la section critique.
Pour chacun de ces cas, donner l'arborescence associée.
b) Donner l'algorithme de Naimi-Tréhel.
c) On souhaite maintenant apporter la modification suivante aux hypothèses
de l'algorithme de départ. La section critique peut être accessible par k
processus simultanément au lieu d'un seul processus à la fois. Donner
l'algorithme de Naimi-Tréhel modifié. Exercice 5 : Algorithmes de routage, Agents Mobiles
Pour mettre en ?uvre un algorithme de routage, des tables de routage sont
construites. Elles permettent de décider sur quelle ligne sortante, un
message (i.e., paquet) entrant doit être retransmis.
a) Donnez le principe d'un algorithme distribué de construction de ces
tables dans les réseaux filaires,
b) Donnez le principe d'un algorithme distribué de construction de ces
tables dans les réseaux sans fil. Exercice 6 (facultatif) : Tendance actuelle
Nous avons vu en cours que la conception des algorithmes distribués est
basée sur l'utilisation de concepts propres qui ont été proposé pour
remédier aux problèmes soulevés par les systèmes distribués à cause de
l'absence de mémoire commune et d'horloge globale.
- Ces concepts sont-ils toujours valable dans le contexte actuelle de
réseaux sans fil et des réseaux mobiles ?
- Dressez une liste de problèmes soulevés par ce nouveau contexte ainsi que
leurs causes. Pour les exercices 1, 2 3 et 4 : a) il faut décrire le principe de
l'algorithme, puis b) il faut donner et justifier la liste des variables
utilisées avec leurs valeurs initiales et les messages utilisés. Ensuite,
c) vous donnez le texte l'algorithme et d) vous donnez son coût en nombre
de messages.