Systèmes Répartis - Horloges Logiques PDF

# Systèmes Répartis ## H. Mansouri ## Laboratoire des Réseaux et des Systèmes Distribués ## LRSD ## Chapitre 3 ## Horloges Logiques dans les Systèmes Répartis ### Plan 1. Système distribué, Processus, Canal de communication 2. Système synchrone / Asynchrone 3. État et horloge globales 4. Temp...

# Systèmes Répartis ## H. Mansouri ## Laboratoire des Réseaux et des Systèmes Distribués ## LRSD ## Chapitre 3 ## Horloges Logiques dans les Systèmes Répartis ### Plan 1. Système distribué, Processus, Canal de communication 2. Système synchrone / Asynchrone 3. État et horloge globales 4. Temps logique et horloge logique 5. Délivrance FIFO vs Délivrance causale 6. Horloge scalaire (Lamport) 7. Horloge vectorielle (Mattern) 8. Horloge matricielle ### Horloge scalaire (Horloge de Lamport) Horloge logique respectant les dépendances causales: - Une date (estampille) est associée à chaque événement: couple (Np, Nv) - Np: numéro du processus - Nv: numéro d'événement - Les dates des événements d'un même processus sont différentes. - Les dates des événements d'envoi et de réception d'un même message sont différentes. ### Horloge de Lamport - Un compteur entier Hi est conservé sur chaque processus Pi - Un événement e sur le processus Pi est daté par H(e) = Hi. - **Initialisation** - Hi = 0, pour tout i - **A chaque événement local e sur Pi** - Hi(e) := Hi(e) + 1; //e est daté par Hi - **Chaque message est estampillé par la date de son émission sur le processus Pi:** Hi(émission) - **A la réception de e sur un processus Pj:** - Hj(réception) := max (Hj, Hi(émission))+ 1 ### Horloge de Lamport A diagram with 3 processes (P1, P2, P3) showing events and messages between them. - Each event is labeled with a timestamp: (Np, Nv) - Each message is labeled with the timestamp of its sender. ### Horloge de Lamport - **Ordonnancement partiel:** - e → K⇒ Hi(e) < Hj(k) - e12? e22 - e13? e22 - e14? e34 - **Ordonnancement total:** - H(e) = H(k) e?k - **Ordonnancement artificielle des événements concurrents:** - ek (Hi(e) < Hj(k)) ou (Hi(e) = Hj(k) et i < j) - e12 e22e13e22e14 e34 - e11<e31<e12<e21<e32<e13<e22<e33<e14<e34<e35< e23 < e24 < e15 ### Horloge de Lamport - **Limite:** - H(e) = H(k) e?k - H(e) < H(k) e → k??!!! - Ordonnancement artificielle des événements concurrents. - ek (Hi(e) < Hj(k)) ou (Hi(e) = Hj(k) et i < j) - Ne permet pas d'assurer l'ordre FIFO ni la délivrance causale. ### Horloge de Mattern - Horloge qui assure la réciproque de la dépendance causale: - Hi(e) < Hj(k)e → K - Permet également de savoir si 2 événements sont concurrents. - Localement, chaque processus Pi a un vecteur Vi de taille égale au nombre de processus. - Vi[j] contient la valeur de l'horloge du processus Pj. ### Horloge de Mattern - **Initialement:** - Vi = 0 - **A chaque événement local à Pi:** - Vi[i] := Vi[i] + 1 - **Chaque message m porte une estampille de l'émetteur Pi:** - Vm = Vi - **A la réception de Vm par un site Pj:** - Vi[j] := Vj[j] + 1; - Vj[K] := max (Vj[K], Vm [K]) pour k∈[1,n] k≠j ### Horloge de Mattern A diagram with 3 processes (P1, P2, P3) showing events and messages between them. - Each event is labeled with a timestamp: (Np, Nv, Vp) - Each message is labeled with the timestamp of its sender. ### Horloge de Mattern - **Ordonnancement partiel:** - Vk: Vi[k] ≤ Vj[k] = Vi ≤ Vj - Vi≤ Vj A∃r/Vi[r]<Vj[r] ⇒ Vi < Vj - (Vi < Vj) et¬(Vj < Vi) ⇒ Vi || Vj - Vi (e) < Vj (r) er - Vi (e) || Vj (r)e || r ### Horloge de Mattern A diagram with 3 processes (P1, P2, P3) showing events and messages between them. - Each event is labeled with a timestamp: (Np, Nv, Vp) - Each message is labeled with the timestamp of its sender. ### Horloge de Mattern - **Limite** - Ne permet pas de définir un ordre global total - Ne permettent pas de garantir une délivrance causale des messages A diagram showing a sequence of messages between 3 processes (Pi, Pj, Pn) with timestamps of each. ### Horloge Matricielle - n processus dans le système - Mi[n,n] pour chaque processus Pi: - Ligne i: informations sur les événements de Pi - Mi[i,i]: nombre d'événements sur Pi - Mi[i,j]: nombre de message envoyer par Pi à Pj - Ligne j: informations que l'on sait sur les événements de Pj : - Mi[j,j]: nombre d'événements que l'on sait sur Pj - Mi[j,k]: nombre de message que l'on sait que Pj a envoyé à Pk ### Horloge Matricielle A diagram illustrating a matrix Mi with 3 processes and shows relationships between events and messages between them. ### Horloge Matricielle Sur le processus Pi, la matrice Mi va : - mémoriser le nombre de messages que le processus Pi a envoyé aux différents autres processus, - l'élément diagonal représente la connaissance qu'a Pi du nombre d'événements locaux qui se sont déjà produits sur les différents processus Pj, - mémoriser, pour chacun des autres processus Pj, le nombre de messages émis par ce site dont le processus Pi a connaissance, - Ainsi, la valeur Mi[j,k] donne le nombre de messages en provenance du processus Pj délivrables sur le processus Pk dont le processus Pi a connaissance. ### Horloge Matricielle - **Initialement:** - Mi = 0 - **A chaque événement local à Pi:** - Mi[i,i] := Mi[i,i] + 1 - **A Chaque envoi de message de Pi vers Pj :** - Mi[i,i] := Mi[i,i] + 1 - Mi[i,j] := Mi[i,j] + 1 - **Chaque message m porte l'estampille de l'émetteur Pi:** - Mm= Mi - **A la réception de Mm par un site Pj :** - if ((Mm[i,j] = Mj[i,j] + 1) et (vk≠ i/j, Mm[k,j] ≤ Mj[k,j])) { - Mj[i,j] := Mj[i,j] + 1 - Mj[k,r] := max (Mj[k,r], Mm [k,r]) pour k/r ∈ [1,n] k/r≠j } ### Horloge Matricielle Le récepteur du message m, soit Pj retarde la délivrance de m jusqu'à ce que les deux conditions suivantes soient satisfaites: - **La condition 1: Mm[i,j] = Mj[i,j] + 1** - Assure que Pj a reçu tous les messages émanant de Pi et précédant m. - **La condition 2: ∀ k≠i/j, Mm[k,j] ≤ Mj[k,j]** - Assure que Pj a reçu tous les messages envoyons avant l'envoi de m. Les messages retardés sont mis en attente au niveau du processus dans une file d'attente triée selon leurs estampilles matricielle. ### Horloge Matricielle A diagram illustrating a matrix Mi with 3 processes and shows relationships between events and messages between them. ### Protocole Birman-Schiper-Stephenson - Les processus se transmettent les messages par diffusion. - L'implémentation du protocole est fondé sur les règles suivantes: - **Règle1:** Avant la diffusion d'un message m, le processus émetteur Pi incrémente sont horloge vectorielle Vi tel que: Vi[i] := Vi[i] + 1, L'estampille est intégrée dans m: Vm = Vi[] - **Règle 2:** Le récepteur du message m, soit Pj retarde la délivrance de m jusqu'à ce que les 2 conditions suivantes soient satisfaites: - Vj[i] = Vm[i]-1 - ∨ k∈ [1,2,...n]-{i}, Vj[k] ≥ Mm[k] ### Protocole Birman-Schiper-Stephenson - La condition 1 de la règle 2 assure que Pj a reçu tous les messages émanant de Pi et précédant m, - La condition 2 assure que Pj a reçu tous les messages qui sont reçus par Pi avant d'avoir émis m. - **Règle 3:** Quand un message est délivré au niveau de Pj, son horloge vectorielle Vj est mise à jour selon la règle: Vj[k] := max(Vj[k], Vm[k]) ### Protocole Birman-Schiper-Stephenson A simple network diagram with 3 processes (P0, P1, P2) showing a message m being sent from P0 to P1. - m arrives at P1 - P0 acknowledges the receipt with m* - P2 receives m* - P2 receives m.