FinalRE51Jan06.doc - net

Final U.V. RE51
Sans documents
18 Janvier 06 Exercice 1 Les architectures distribuées sont motivées par la baisse du coût et
l'accroissement des performances des machines et par l'existence des
réseaux. Donnez les caractéristiques de ces architectures.
Exercice 2 Les systèmes distribués soulèvent un grand nombre de problèmes que l'on
résout par des algorithmes distribués. Donnez et expliquez ces problèmes.
Exercice 3 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. Donnez ces concepts en détaillant leurs
fonctionnements.
Exercice 4 : Algorithmes de parcours a) Donner un algorithme de parcours 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 5 : 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) L'algorithme de Lamport pour l'exclusion mutuelle est basé sur le
mécanisme de l'estampillage. Expliquer ce mécanisme ainsi que son intérêt.
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.
a) 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.
b) Proposez une solution alternative pour une meilleure exploitation de ces
réseaux.
Pour l' exercice 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.