Systèmes Distribués et Latence

Introduction

• Les systèmes distribués sont caractérisés par la latence qui est le retard dû aux communications.
• La latence est significative et variable.
• Par conséquent, le même protocole peut avoir des exécutions et des résultats différents.

Évènements dans un système distribué

• Un événement est tout changement (significatif) de l’état d’un système.
• L’ordre des événements est important.
• Il doit être le même pour tous les processus pour éviter les conflits.
• La synchronisation des horloges est difficile, voire impossible.
• Les processus n’ont pas accès à l’ordre physique des événements.
• Les événements peuvent être perçus différemment par les processus, ce qui pose le problème de la cohérence des décisions.

Relation de causalité

• Le principe de causalité stipule qu'un effet ne peut pas précéder sa cause.
• Il est important de mettre en évidence la dépendance causale entre les événements.
• La relation de précédence causale est définie par trois lois:
  • Ordre local: les événements se produisent dans un ordre donné au niveau d'un même site.
  • Propriété de causalité élémentaire: un événement d'envoi précède nécessairement un événement de réception.
  • Transitivité: si A précède B et B précède C, alors A précède C.
• La précédence causale est une relation d'ordre partiel, il est possible d’avoir des événements concurrents.
• La concurrence logique implique l'absence de causalité entre les événements.
• La concurrence physique correspond à l'occurrence de deux événements au même moment physique.

Ordonnancement des événements distribués

• On utilise des horloges pour dater les événements et établir un ordre.
• Les horloges doivent être monotones et cohérentes:
  • Monotonie: l'horloge doit toujours avancer.
  • Cohérence: si A précède B, alors H(A) < H(B).

Horloges logiques

• L'objectif des horloges logiques est de dater les événements en respectant la causalité et de définir un ordre total sur les événements.
• L'algorithme d'horloge logique de Lamport utilise une variable Hi pour chaque site Si.
• Initialisation: Hi ← 0 pour tous les sites.
• Évènement local sur Si: Hi ← Hi + 1.
• Émission d’un message: le message est estampillé avec la date d’émission.
• Réception d’un message m: Hi ← max (Hi ,H(m)) +1.
• L'ordre défini par les horloges de Lamport est noté "«":
  • a«b si H(a) < H(b).
  • a«b si H(a) = H(b) et Si < Sj (si a est sur Si et b sur Sj).

Horloges vectorielles

• Les horloges vectorielles permettent de capturer la relation causale entre événements.
• Chaque site possède un vecteur d'horloges, où chaque élément représente le numéro de l'horloge du site correspondant.
• Le vecteur d'horloges est mis à jour lors de la réception d'un message.
• Deux événements sont concurrents si leurs vecteurs d'horloges sont non comparables (il n'existe pas de relation d'ordre entre eux).

Conclusion

• La gestion du temps et des états est un élément crucial dans les systèmes distribués.
• Les horloges logiques et les horloges vectorielles sont des outils importants pour gérer la causalité et l'ordre des événements.
• Des concepts comme les événements concurrents, la relation de précédence causale, la monotonie et la cohérence des horloges constituent des éléments importants à comprendre pour concevoir et analyser les systèmes distribués.

Ce quiz explore les concepts fondamentaux des systèmes distribués, y compris la latence et l'importance de l'ordre des événements. Les participants testeront leur compréhension de la relation de causalité ainsi que des défis liés à la synchronisation des horloges. Préparez-vous à répondre à des questions sur les impacts de ces éléments sur les protocoles distribués.