EXAMEN de RATTRAPAGE

Exercice 1 - Interblocage

Question 1 - Sûreté pour les algorithmes

La sûreté (safety) dans les systèmes répartis garantit que "rien de mauvais n'arrive". Pour les algorithmes de gestion d'interblocage (spécifiquement la détection), la sûreté se traduit par le fait que l'algorithme ne doit jamais détecter de faux interblocages. Si l'algorithme annonce qu'un interblocage est présent, alors cet interblocage doit exister réellement dans le système. Dans le cas de la prévention ou de l'évitement, la sûreté signifie que le système ne doit jamais entrer dans un état d'interblocage.

Question 2 - Vivacité pour les algorithmes

La vivacité (liveness) garantit que "quelque chose de bon finit toujours par arriver". Dans le contexte de la gestion d'interblocage, cela signifie que si un véritable interblocage se produit dans le système, l'algorithme finira obligatoirement par le détecter et par le résoudre dans un délai fini. Cela implique également qu'aucun processus ne subisse de famine infinie à cause de l'algorithme de résolution.

Question 3 - Différence entre évitement et prévention

La différence réside dans le moment et la manière dont on traite le risque d'interblocage :

• La prévention est une approche statique. Elle consiste à concevoir le système de manière à ce qu'au moins l'une des quatre conditions nécessaires de Coffman (exclusion mutuelle, rétention et attente, pas de réquisition, attente circulaire) soit structurellement impossible. L'interblocage ne peut donc physiquement pas se produire.
• L'évitement est une approche dynamique. Le système autorise toutes les conditions, mais à chaque demande de ressource, un algorithme (comme l'algorithme du Banquier) simule l'allocation pour vérifier si le système reste dans un "état sûr". Si l'allocation risque de mener à un interblocage, la demande est mise en attente.

Question 4 - Principe commun de détection

Le principe fondamental de tous les algorithmes de détection d'interblocage est la construction, la mise à jour et l'analyse d'un graphe d'attente (ou graphe d'allocation de ressources). L'algorithme cherche à identifier la présence de cycles (ou de nœuds terminaux spécifiques, selon le modèle de requêtes) dans ce graphe, car l'existence d'un cycle fermé dans le graphe d'attente est la preuve matérielle d'un interblocage.

Question 5 - Impact d'un faux interblocage

Lorsqu'un algorithme détecte à tort un interblocage (faux interblocage), le système déclenche inutilement une procédure de recouvrement. Cette procédure consiste généralement à avorter (tuer) un ou plusieurs processus victimes et à annuler (roll-back) leurs transactions pour briser le cycle supposé. L'impact est une perte de travail utile, un gaspillage des ressources de calcul, et une dégradation injustifiée des performances globales du système.

Exercice 2 - Élection

Question 1 - Trace de l'algorithme sur un anneau

L'anneau est constitué des sites dans l'ordre suivant : 2 -> 1 -> 4 -> 3 -> 2. Le processus 2 initie l'élection. Initialement, pour tous les sites i, la variable M = 0.

• Étape 1 (Initialisation par le site 2) : Le site 2 vérifie que M = 0. Il exécute M := 2 (son propre numéro) et envoie le message <2> à son voisin, le site 1.
• Étape 2 (Réception par le site 1) : Le message reçu contient j = 2. Sur le site 1, M = 0. La condition M < j (0 < 2) est vérifiée. Le site 1 exécute M := 2 et transmet <2> au suivant, le site 4.
• Étape 3 (Réception par le site 4) : Le message reçu contient j = 2. Sur le site 4, M = 0. La condition M < j (0 < 2) est vérifiée. Le site 4 exécute M := 2 et transmet <2> au suivant, le site 3.
• Étape 4 (Réception par le site 3) : Le message reçu contient j = 2. Sur le site 3, M = 0. La condition M < j (0 < 2) est vérifiée. Le site 3 exécute M := 2 et transmet <2> au suivant, le site 2.
• Étape 5 (Réception par le site 2) : Le site 2 reçoit le message <2>. L'identifiant reçu j est 2. Puisque j = i (2 = 2), la condition finale est remplie. Le processus 2 déclare "Je suis le leader".

(Note : Lors de l'étape 5, M sur le site 2 vaut déjà 2, donc la condition M < j qui correspond à 2 < 2 est fausse, le message n'est donc pas retransmis plus loin, ce qui termine correctement l'algorithme.)

Question 2 - Comparaison avec Chang et Roberts

Dans l'algorithme de Chang et Roberts, l'identifiant maximum l'emporte et les identifiants plus petits sont purgés de l'anneau. Comparons les comportements :

• Cas où tous les processus se réveillent spontanément : Dans Chang et Roberts, chaque processus envoie son identifiant. Un processus ne fait suivre un message que si l'identifiant reçu est strictement supérieur au sien. Dans l'algorithme proposé, chaque processus i met M := i et envoie <i>. La variable M conserve toujours la valeur du plus grand identifiant vu par le site. Lorsqu'un message <j> arrive, il n'est transmis que si j > M. Par conséquent, exactement comme chez Chang et Roberts, les messages portant des identifiants faibles seront bloqués par les sites ayant déjà vu (ou possédant) un identifiant plus grand. Le plus grand identifiant fera le tour complet.
• Cas où seulement une portion se réveille : Dans Chang et Roberts, un site non réveillé qui reçoit un message participe passivement en transmettant le message (ou s'active et participe). Dans l'algorithme proposé, un processus non initiateur a M = 0. Lorsqu'il reçoit le premier message de l'élection contenant un identifiant j > 0, la condition 0 < j est toujours vraie. Le site passif met à jour M := j et fait suivre le message. Il se comporte donc comme un routeur passif parfait, ce qui équivaut au comportement d'un site non initiateur chez Chang et Roberts.

Exercice 3 - Horloges logiques

Question 2 - Élimination de la composante site des horloges de Lamport

(Note : Cette question est numérotée 2 dans le document source extrait). Si l'on élimine la composante site (l'identifiant i utilisé pour départager les ex-aequo), la propriété qui est perdue est l'ordre total des événements. Il devient possible que deux événements concurrents se produisant sur deux sites différents possèdent exactement la même estampille temporelle scalaire H. Nous n'obtenons plus qu'un ordre partiel.

Cependant, l'horloge ainsi modifiée respecte toujours la condition de validité faible des observations. Cette condition stipule que pour deux événements e et e', si e -> e' (e précède e' causalement), alors H(e) < H(e'). Puisque l'horloge scalaire s'incrémente sur chaque événement local et prend max(H_local, H_recu) + 1 lors d'une réception, l'estampille d'un événement qui en cause un autre sera toujours strictement inférieure. La condition faible est donc préservée.

Question 3 - Modification des horloges vectorielles de Mattern

Non, cette modification ne garde pas la propriété fondamentale des horloges de Mattern. La propriété fondamentale est : e -> e' <=> Ve < Ve'. L'inégalité vectorielle stricte implique qu'au moins une composante est strictement inférieure.

Exemple illustratif : Considérons deux sites, P1 et P2, avec les vecteurs initiaux V1 = [0, 0] et V2 = [0, 0].

1. Le site P1 exécute un événement d'émission e1 vers P2.
   • Selon la règle modifiée (l'émission est comptabilisée), P1 incrémente sa composante : V1 = [1, 0].
   • L'événement e1 est daté de [1, 0]. Le message part avec l'estampille [1, 0].
2. Le site P2 réceptionne ce message lors de l'événement e2.
   • Selon la nouvelle règle proposée, la réception ne déclenche pas d'incrémentation locale. P2 fait uniquement la mise à jour : V2 = max([0, 0], [1, 0]) = [1, 0].
   • L'événement e2 est daté de [1, 0].

Nous savons par définition causale que l'émission précède la réception : donc e1 -> e2. Selon la propriété fondamentale, nous devrions avoir V(e1) < V(e2). Or, ici nous avons [1, 0] et [1, 0], ce qui signifie que V(e1) = V(e2). L'équivalence est donc rompue, la propriété est perdue.

Exercice 4 - Exclusion mutuelle

Question 1 - Application de l'algorithme sur un diagramme

Attention : Le diagramme d'exécution mentionné ("le diagramme suivant") n'est pas présent dans l'énoncé source extrait. Il est physiquement impossible de déterminer l'ordre d'entrée en section critique ou le contenu des files d'attente sans les messages et leurs estampilles temporelles de départ. Si ce diagramme vous est fourni en annexe, l'ordre d'entrée sera dicté par la plus petite estampille Hi de la requête (en utilisant l'identifiant du site pour départager les ex-aequo), à condition que le processus ait reçu un acquittement de tous les autres processus.

Question 2 - L'importance des communications FIFO

Les communications doivent être de type FIFO (First-In, First-Out) car l'algorithme de Lamport repose de manière critique sur l'ordre de réception des estampilles temporelles. Si les canaux n'étaient pas FIFO, un message de libération (Liberation, H2) ou d'acquittement envoyé par un processus Pi pourrait arriver sur un site distant avant une requête (Demande, H1) envoyée précédemment par ce même processus Pi (avec H1 < H2). Cela fausserait totalement la cohérence de la file d'attente locale du récepteur : il pourrait traiter une libération pour une requête qu'il n'a pas encore mise en file, puis ajouter ensuite la requête qui resterait bloquée indéfiniment. Le canal FIFO garantit que si un site reçoit un message estampillé t d'un processus P, il a la certitude qu'il ne recevra plus aucun message de P avec une estampille inférieure à t, ce qui est indispensable pour prendre la décision sécurisée d'entrer en section critique.

Méthode

Pour aborder ce type de sujet d'Informatique Répartie :

1. Théorie et définitions : Ne confondez jamais les propriétés fondamentales. La sûreté et la vivacité ont des définitions spécifiques qui s'adaptent selon qu'on parle d'interblocage, d'élection ou de consensus. Révisez les définitions exactes (ex: e -> e' <=> Ve < Ve').
2. Déroulement d'algorithmes : Lors du traçage d'un algorithme (comme l'élection en anneau), ne sautez aucune étape. Écrivez l'état de chaque variable (M, état du nœud) pour chaque site, à chaque réception de message. Cela évite les erreurs d'inattention, particulièrement sur la condition de fin.
3. Contre-exemples : Lorsqu'on vous propose une modification d'un algorithme connu (comme ici les horloges de Mattern), cherchez le cas d'usage le plus simple (2 processus, 1 message). Si la modification empêche l'horloge du récepteur d'avancer strictement par rapport à l'émetteur, la preuve de l'échec est faite.
4. Lecture attentive : Basez-vous strictement sur les variables et les conditions fournies dans le pseudo-code de l'énoncé (ex: Si M < j), même si elles diffèrent légèrement des versions canoniques vues en cours. L'examinateur teste votre capacité d'analyse logique, pas seulement votre mémoire.