Please enable JavaScript.
Coggle requires JavaScript to display documents.
Le temps Logique dans les systèmes répartis, Roua Frigui 1MR Dsir -…
Le temps Logique
dans les systèmes répartis
Ordre Causal
Relation de précédence directe
e précède directement e': e -> e'
L'événement e se produit juste avant e' sur le même processus.
e correspond à l'envoi d'un message, e' à sa réception par un autre processus.
Relation Transitive
e -> e' et e' -> e'' donc e -> e"
Relation de précédence causale
la fermeture reflexive et transitive de la relation de précédence directe.
Elle définit un ordre partiel des évènements
e précède causalement e':
réflexivité
transitivité
trois ensembles d'évènements
Passé: évènements antérieurs à e
Futur: évènements postérieurs à e
Concurrent: évènements concurrents avec e
Délivrance causale
Explication: La délivrance (del) d'un message m le rend accessible aux applications. Elle peut être retardée à la réception pour garantir un ordre spécifique.
Ordre de délivrance FIFO
les messages sont délivrés dans l'ordre d'arrivée, le premier reçu étant le premier délivré.
Ordre de délivrance causale
assure que les messages sont délivrés selon la causalité des événements, préservant ainsi la logique des relations de cause à effet.
Horloges et estampilles scalaires
Définition
e • > e’ ⇒ HLe ⊆ HLe’
Principe
Chaque site commence avec un compteur à 0. L'horloge logique du site s'incrémente à chaque événement local, incluant les opérations purement locales ou l'envoi de messages. Lors de l'envoi d'un message, l'horloge de l'émetteur est incrémentée et estampillée sur le message.
Propriétés
Pour instaurer un ordre strict, on ajoute à l'horloge logique d'un site son identification. L'estampille logique d'un événement HL(e) sur un site i est notée (HLi, i). On a (HLi, i) ⊂ (HLj, j) si HLi < HLj ou si HLi = HLj et i < j.
Horloges et estampilles vectorielles
Principes
Chaque site a une horloge vectorielle de n entiers.
Les messages portent l'estampille actuelle de cette horloge.
La réception d'un message permet au site récepteur de synchroniser son horloge avec celle de l'émetteur.
Les événements locaux et l'envoi de messages incrémentent les composants de l'horloge.
À la réception d'un message, l'horloge du site est incrémentée, et chaque composant est mis à jour en prenant le maximum entre sa valeur actuelle et celle de l'estampille du message.
inconvénients
Un ordre artificiel aux événements concurrents,
Ne permettent pas de remédier à la défaillance vis-à-vis de l'ordre FIFO.
Ne garantissent pas la livraison causale des messages.
Propriétés
EVe est l’estampille vectorielle de e :
⇒ ∀ i , EVe [ i ] = Card ( {e’ / e’ ∈ Si et e’ • > e } )
⇒ EVe ⊆ Eve’ ⇔ ∀ i, EVe [i] ≤ Eve’ [i]
– e • > e’ ⇔ EVe ⊆ Eve’
– e || e’ ⇔ EVe || Eve’
Horloges et estampilles matricielles
inconvénients
Ne corrige pas la défaillance
de la livraison causale des messages.
Définition et principe
Sur le site Si, la matrice HMi enregistre le nombre de messages envoyés et reçus, ainsi que l'estampille vectorielle représentant la connaissance des événements locaux sur d'autres sites.
=> la matrice HMi garde trace des échanges, et la synchronisation des horloges dépend de la réception de messages conformes à des conditions préalables.
La synchronisation des horloges se fait ainsi :
Lors d'un événement local sur Si, HMi[i, i] est incrémenté.
Lors de l'envoi d'un message du site i vers le site j, HMi[i, i] et HMi[i, j] sont incrémentés.
À la réception d'un message m du site j sur le site i, des conditions sont vérifiées (ordre FIFO, réception complète des messages). Si satisfaites, l'horloge du site i est mise à jour, sinon la livraison est retardée.
Roua Frigui 1MR Dsir
