Le temps,
les coupures,
les snapshots.

Diagramme du sujet (exo2.pdf). P : p1, p2, p2', p3, p3', p4, p5, p6. Q : q1, q2, q3, q3', q4, q5, q6, q7, q8, q9, q10, q11. R : r1..r6. Messages lus sur les flèches : p1→q3, p2→q6, q2→p5, q4→p3, q5→r2, q2→r1, q7→r5, r3→q9, q10→r6. Les événements primés (p2', p3', q3') servent à la question 3, ils ne portent aucun message.

Q1Que représentent p5, q1, p2, r4 ?

Trois natures d'événement existent : émission, réception, interne (local, sans message).

• p5 : une réception (P reçoit le message parti de q2).
• p2 : une émission (P envoie le message reçu en q6).
• q1 : un événement interne de Q (aucune flèche ne le touche).
• r4 : un événement interne de R (entre l'émission r3 et la réception r5, sans message).

Q2Les canaux sont-ils FIFO ?

Non, pas tous. Regarde le canal Q→P : q2 envoie un message (reçu en p5), puis plus tard q4 en envoie un autre (reçu en p3). Or p3 est avant p5 sur P : le message parti le plus tard (q4→p3) arrive le premier. Il y a dépassement, donc Q→P n'est pas FIFO. Les autres canaux utilisés respectent l'ordre d'émission : P→Q (p1→q3 puis p2→q6) et Q→R (q2→r1, q5→r2, q7→r5) sont FIFO.

Q3Peut-on avoir ces échanges ?

Règle : un message e→f est possible si et seulement s'il ne crée pas de cycle causal, c'est-à-dire s'il n'existe pas déjà un chemin causal de f vers e (sinon f serait à la fois avant et après e). On ne compare jamais les hauteurs entre deux processus différents : il n'y a pas d'horloge globale, seule la relation « arrivé avant » compte.

• Émission en q5, réception en p2' : existe-t-il un chemin de p2' vers q5 ? P n'envoie qu'en p1 et p2, tous deux avant p2' : rien ne sort de P après p2', donc aucun chemin de p2' vers q5. Pas de cycle. Oui, possible. C'est exactement le message ajouté au test 2 du cours ; avec q4→p3, il rend le canal Q→P non FIFO (q4 émet avant q5, mais p2' est reçu avant p3).
• Émission en p3', réception en q3' : il existe déjà le chemin q3' → q4 → p3 → p3' (q4 envoie à p3). Le nouveau message p3'→q3' fermerait la boucle q3' → … → p3' → q3' : cycle causal. Non, impossible.

Q4Horloges de Lamport

Même règle qu'à l'exercice 2 : +1 avant chaque événement local et chaque envoi ; à la réception, max puis +1. On obtient :

P	p1=1	p2=2	p2'=3	p3=6	p3'=7	p4=8	p5=9	p6=10
Q	q1=1	q2=2	q3=3	q3'=4	q4=5	q5=6	q6=7	q7=8
Q (suite)	q8=9	q9=10	q10=11	q11=12
R	r1=3	r2=7	r3=8	r4=9	r5=10	r6=12

Valeurs demandées : sur P après p6 = 10, sur Q après q11 = 12, sur R après r6 = 12.

Q5Profondeur et durée

La profondeur du diagramme (durée minimum) est la plus longue chaîne causale, soit la plus grande valeur de Lamport atteinte : 12. Un chemin critique menant à r6 : p1→q3, puis q3'→q4→q5, puis q5→r2, r3→q9, q10→r6. Il compte 4 messages. Si chaque transmission dure au plus τmax et qu'on néglige les événements locaux, la durée maximum le long de ce chemin est de l'ordre de 4·τmax.

Q6Événements concurrents à q6

q6 est la réception du message de p2. Son passé causal est {p1, p2, q1, q2, q3, q3', q4, q5} ; son futur est {q7, q8, q9, q10, q11, r5, r6}. Tout le reste lui est concurrent :

p2', p3, p3', p4, p5, p6, r1, r2, r3, r4 (10 événements). Par exemple r1 vient de q2 comme q6, mais sur une autre branche : aucun ne cause l'autre.

Q7heure(a) < heure(b) n'implique pas a → b

Contre-exemple : r1 (Lamport 3) et q6 (Lamport 7). On a heure(r1) < heure(q6), pourtant r1 et q6 sont concurrents (tous deux issus de q2, sur des branches différentes, sans chaîne causale entre eux). Un entier de Lamport plus petit ne prouve donc pas la précédence causale. C'est exactement la limite que les horloges vectorielles corrigent.

Diagramme du sujet (exo2.pdf, figure 1), le même que celui des animations « Lamport » et « Vecteurs » ci-dessus. P1 : a1, b1, c1, d1 ; P2 : a2, b2, c2, d2 ; P3 : a3, b3, c3. Huit messages : a1→a2, a2→b1, a3→b2, b1→b3, c1→c2, c2→c3, c2→d1, c3→d2. Frontières des coupes : C = {a1, b2, b3}, C' = {c1, c2, c3}, C'' = {d1, d2, c3}.

Q1Modèle atomique ?

Oui. Chaque événement est ponctuel (instantané) et les événements d'un même processus sont totalement ordonnés ; un message relie une émission à une réception, sans durée modélisée à l'intérieur d'un événement. D'où des événements qui reçoivent et émettent en même temps : a2 (reçoit de a1, envoie à b1), b1 (reçoit de a2, envoie à b3), et c2 qui reçoit de c1 puis émet vers c3 et d1. C'est le modèle atomique de Mattern : on raisonne uniquement sur l'ordre des événements, jamais sur leur durée réelle.

Q2Estampilles de Lamport

Règle : +1 avant chaque événement local et chaque envoi ; à la réception, max puis +1 (un événement qui reçoit et émet compte une seule fois). On obtient :

P1	a1=1	b1=3	c1=4	d1=6
P2	a2=2	b2=3	c2=5	d2=7
P3	a3=1	b3=4	c3=6

Lance l'animation « Lamport » et vérifie chaque valeur : les entiers croissent le long des flèches.

Q3Horloges vectorielles [P1, P2, P3]

P1	a1=[1,0,0]	b1=[2,1,0]	c1=[3,1,0]	d1=[4,3,1]
P2	a2=[1,1,0]	b2=[1,2,1]	c2=[3,3,1]	d2=[3,4,3]
P3	a3=[0,0,1]	b3=[2,1,2]	c3=[3,3,3]

Q4Commenter c1 et c3

c1 = [3,1,0] et c3 = [3,3,3]. On a c1 ≤ c3 composante par composante (3≤3, 1≤3, 0≤3) et c1 ≠ c3, donc c1 < c3, c'est-à-dire c1 → c3 : ils sont comparables. C'est logique, il existe une chaîne causale c1 → c2 → c3.

Q5b3 contre c2, puis b3 contre d2

Lamport : b3 = 4 et c2 = 5. On aurait envie de conclure b3 → c2 car 4 < 5. Faux : L(a) < L(b) ne prouve rien. Les vecteurs tranchent : b3 = [2,1,2], c2 = [3,3,1]. Sur P3, 2 > 1 ; sur P2, 1 < 3. Aucune inégalité ne tient dans un seul sens : b3 || c2, ils sont concurrents. Voilà pourquoi Lamport ne suffit pas.

Pour b3 et d2 : Lamport donne 4 < 7, ce qui ne suffit toujours pas. Vecteurs : b3 = [2,1,2], d2 = [3,4,3]. Cette fois 2≤3, 1≤4, 2≤3 : donc b3 < d2, c'est-à-dire b3 → d2. Comparables, via la chaîne b3 → c3 → d2.

Q6Les coupes C, C', C'' sont-elles cohérentes ?

Une coupe est cohérente si sa frontière ne coupe aucun message « à l'envers » (réception dans le passé, émission dans le futur). Test avec les vecteurs : VCut = max des vecteurs de la frontière, cohérente si et seulement si VCut[k] = Vk[k] pour tout k (la diagonale).

• C, frontière {a1, b2, b3} : VCut = max([1,0,0], [1,2,1], [2,1,2]) = [2,2,2], diagonale (a1[1], b2[2], b3[3]) = (1,2,2). VCut[1]=2 ≠ 1 : incohérente. Concrètement, b3 (passé) a reçu le message de b1, mais b1 est après a1 sur P1, donc dans le futur.
• C', frontière {c1, c2, c3} : VCut = max([3,1,0], [3,3,1], [3,3,3]) = [3,3,3] = diagonale (3,3,3). Cohérente. Deux messages sont en transit : c2→d1 et c3→d2.
• C'', frontière {d1, d2, c3} : VCut = max([4,3,1], [3,4,3], [3,3,3]) = [4,4,3] = diagonale (4,4,3). Cohérente.

Coupe D (pour s'entraîner), frontière {d1, b2, c3} : VD = max([4,3,1], [1,2,1], [3,3,3]) = [4,3,3]. Composantes 1 et 3 conformes (d1[1]=4, c3[3]=3), mais VD[2]=3 ≠ b2[2]=2 : incohérente. c3 et d1 dépendent tous deux de c2, troisième événement de P2, alors que la frontière arrête P2 à b2 : on garderait des réceptions sans leur cause.

Q7S = Σ si et R = Σ ri sur C, C', C''

On compte, sous chaque frontière, les messages émis (si) et reçus (ri) par chaque processus. c2 émet deux messages.

Coupe	s1+s2+s3 = S	r1+r2+r3 = R
C	1+1+1 = 3	0+2+1 = 3
C'	3+3+2 = 8	1+3+2 = 6
C''	3+3+2 = 8	2+4+2 = 8

Piège : sur C on a S = R alors que la coupe est incohérente. Le message a1→a2 est compté émis et reçu, mais b1→b3 est compté reçu sans être émis, et a2→b1 émis sans être reçu : les deux erreurs se compensent.

Q8Peut-on conclure la terminaison ?

Sur C'', S = R = 8 : sur une coupe cohérente, cela veut dire qu'aucun message n'est en transit, les canaux sont vides. Mais S = R ne suffit pas seul : C montre S = R sur une coupe incohérente. Il faut une coupe cohérente et des processus passifs. C'' est cohérente, donc si les processus sont passifs à cet instant, l'algorithme est terminé. Sur C', S > R : deux messages en vol, on ne peut rien conclure.

Q9Événements concurrents et diagonale des vecteurs

Affirmation : si des événements de vecteurs Vt1, ..., Vtn sont deux à deux concurrents, alors le max composante par composante vaut la diagonale (Vt1[1], Vt2[2], ..., Vtn[n]).

Intuition : Vti[i] compte les événements que Pi a lui-même estampillés (sa propre « hauteur »). Dans la colonne j, Vti[j] dit combien d'événements de Pj ont influencé l'événement i. Si i et j sont concurrents, i ignore l'événement j, donc Vti[j] < Vtj[j] : personne ne connaît autant d'événements de Pj que Pj lui-même. Le max de la colonne j est donc atteint pour i = j, soit Vtj[j], la diagonale.

Exemple sur le diagramme, trio deux à deux concurrent {c1, b2, b3} : c1=[3,1,0], b2=[1,2,1], b3=[2,1,2] (aucun vecteur n'est ≤ un autre). max = [3,2,2] = (c1[1], b2[2], b3[3]) = (3, 2, 2). C'est justement le vecteur de la coupe cohérente de frontière {c1, b2, b3}. Attention, {d1, c2, b3} ne marche pas : c2 → d1 (message c2→d1). On retrouve la condition VCut[k]=Vk[k] : une coupe est cohérente si et seulement si sa frontière est faite d'événements deux à deux concurrents.

1La version non bornée (le point de départ)

Chaque demande porte une estampille de Lamport. Un processus accorde (grant) la ressource à l'autre s'il ne la veut pas, ou si sa propre estampille de requête est plus grande que celle reçue (égalité départagée par l'identité 0/1). Autrement dit, la plus petite estampille gagne. C'est l'exclusion mutuelle de Lamport réduite à deux processus. Ennui : les estampilles croissent sans fin, le compteur n'est pas borné.

2L'indice : quel écart maximal entre les deux estampilles ?

C'est la clé. Avant de pouvoir redemander la ressource, un processus doit l'avoir acquise, utilisée, puis relâchée ; ce cycle échange des messages (request, grant, release) avec l'autre, ce qui recale l'horloge de l'autre au passage. Conséquence : à tout instant, les deux estampilles de requête en jeu ne diffèrent que de 1 au plus. Un processus ne peut jamais prendre plus d'une requête d'avance.

3Donc oui, des estampilles bornées suffisent

Puisqu'on n'a jamais besoin de distinguer un écart supérieur à 1, coder des valeurs arbitrairement grandes est inutile. On garde le compteur dans un petit ensemble (par exemple {0, 1, 2}) et on compare modulo : avec un écart borné par 1, « qui est le plus petit » reste sans ambiguïté malgré le repli à 0. Quand les deux processus sont d'accord et qu'aucune requête n'est en cours (système au repos), on remet les deux compteurs à 0.

4Le tic borné, pas à pas

// horloge L dans {0..K}, K petit (K=2 suffit pour 2 processus)
Événement local ou envoi :
     L := (L + 1) mod (K+1)

Réception d'une estampille l :
     L := (max_cyclique(L, l) + 1) mod (K+1)

Comparer deux requêtes (moi, autre) (écart borné par 1) :
     si moi = autre alors l'identité (0 < 1) départage
     sinon le plus petit au sens cyclique gagne

Retour au repos (aucune requête, horloges d'accord) :
     L := 0   // les deux processus se resynchronisent à 0

On obtient le même ordre d'accès que la version non bornée : la comparaison désigne toujours le même gagnant, car l'information utile (l'ordre de deux requêtes proches) est préservée. Seule la taille du compteur change.

1Le scénario qui pose problème

P1 envoie M1 (ts=1) à P2 et M2 (ts=2) à P3 ; à la réception, P3 envoie M3 (ts=4) à P2. P2 reçoit donc M1 (ts=1) et M3 (ts=4). Parfois il les reçoit dans l'ordre (1 puis 4) : pas de souci. Mais rien ne l'empêche de recevoir M3 (ts=4) avant M1 (ts=1) : les canaux sont FIFO mais point-à-point, M1 et M3 voyagent sur des canaux différents, aucun ne « double » l'autre. P2 risque alors de traiter ts=4 avant ts=1.

2Le vrai problème à résoudre

Quand P2 reçoit un message d'un processus, comment être sûr qu'aucun autre processus ne lui enverra plus tard un message d'estampille plus petite ? Sans cette garantie, impossible de traiter en ordre croissant.

3L'idée : messages « null » et attente d'un message par source

Avant de traiter un message au niveau applicatif, P attend d'avoir reçu un message de chaque source possible. Pour que ça arrive toujours : chaque fois qu'un processus envoie un message applicatif à un destinataire, il diffuse aussi un message « null » estampillé à tous les autres. Comme les données sont émises infiniment souvent (hypothèse), les messages null aussi. Le récepteur finit donc toujours par avoir, de chaque source, un message (null ou non) : il peut comparer les estampilles et traiter le plus ancien en toute sécurité.

4L'algorithme sur Pi

// Log[k] = dernier message connu de Pk ; init : null, ts = -infini
Message M reçu de Pj (Log[j] vide ou déjà délivré) :
     synchroniser l'horloge de Lamport ;
     Log[j] := M ;
     plusVieux := M ;
     pour tout k ≠ i, k ≠ j :
         si Log[k].ts < plusVieux.ts alors plusVieux := Log[k] ;
     si plusVieux ≠ null et pas encore délivré :
         délivrer plusVieux à l'application ; marquer délivré

Envoi applicatif de M :
     L := L + 1 ;
     envoyer M estampillé L au destinataire ;
     envoyer "null" estampillé L à tous les autres

Deux subtilités : (1) si Pj renvoie un message alors que le précédent n'est pas encore délivré, il faut le bufferiser (les canaux de capacité infinie servent à ça, on ne le consomme pas tout de suite) ; (2) recevoir un message null peut débloquer la délivrance d'un message non-null devenu le plus ancien.

IdéeLe marqueur double un message applicatif

Deux processus P et Q, canal P→Q non-FIFO. Déroulé :

• P envoie un message applicatif m à Q.
• P initie le snapshot : il enregistre son état, puis envoie le marqueur sur P→Q. Le marqueur part après m.
• Canal non-FIFO : le marqueur dépasse m et arrive chez Q en premier.
• Q reçoit le marqueur : il enregistre son état et note le canal P→Q comme vide (rien reçu avant).
• Q reçoit ensuite m. Ce message a été envoyé avant le snapshot de P, il aurait dû être compté comme « en transit », mais Q le reçoit après son propre enregistrement et le traite comme un message post-snapshot.

Conséquence : m disparaît du snapshot (ni dans l'état d'un processus, ni dans l'état du canal). L'état global enregistré est incohérent : il « perd » un message. La propriété FIFO est donc nécessaire pour que le marqueur ne double jamais un message applicatif, garantissant que tout ce qui précède le marqueur sur un canal est bien capturé.

SetupDeux canaux, un seul jeton

Anneau P ⇄ Q, deux canaux (P→Q et Q→P). Un seul exemplaire de m circule. P envoie m en premier. À l'instant considéré, P détient m, son état vaut 101. P envoie m à Q, puis immédiatement initie le snapshot.

DérouléApplication de Chandy-Lamport

• P enregistre son état Sp = 101 et envoie le marqueur sur P→Q (derrière m, canal FIFO).
• Q reçoit d'abord m : son état passe à 102. Puis Q reçoit le marqueur : il enregistre Sq = 102 et note le canal P→Q comme vide (m a été reçu avant le marqueur, il est donc dans l'état de Q, pas dans le canal).
• Q rediffuse le marqueur sur Q→P. P le reçoit : ayant déjà enregistré son état, il note le canal Q→P comme vide (rien reçu dessus entre-temps, m circulait dans l'autre sens).