Horloges logiques, ordre des événements et modèles de défaillance

Informatique de gestion · Master 1

Temps et ordre dans les systèmes répartis : Lamport, horloges vectorielles et pannes.

Introduction

Dans un système distribué, il n'existe pas d'horloge globale parfaite : les horloges physiques de chaque machine dérivent et la synchronisation par NTP n'est précise qu'à quelques millisecondes ou davantage. Se fier aux horodatages pour ordonner des événements entre machines conduit à des erreurs, comme l'écrasement d'une écriture récente par une plus ancienne.

Leslie Lamport a défini la relation « arrivé avant » : au sein d'un processus, les événements sont ordonnés ; l'envoi d'un message précède sa réception ; et la relation est transitive. Les horloges de Lamport attribuent à chaque événement un compteur qui respecte cet ordre : si A précède B alors C(A) < C(B). La réciproque est fausse. Les horloges vectorielles, qui conservent un compteur par processus, permettent en plus de détecter la concurrence de deux événements.

La seconde difficulté est la défaillance. On distingue l'arrêt franc (panne-arrêt), l'omission de messages, la défaillance temporelle et la défaillance byzantine, où un nœud se comporte de façon arbitraire ou malveillante. Un détecteur de pannes fondé sur des délais d'attente ne peut qu'estimer : un nœud lent est indiscernable d'un nœud en panne.

Objectifs d'apprentissage

Expliquer pourquoi les horloges physiques ne suffisent pas à ordonner des événements
Définir la relation arrivé-avant de Lamport
Mettre à jour des horloges de Lamport et vectorielles sur un exemple
Distinguer événements causaux et concurrents
Classer les modèles de défaillance et comprendre les limites des détecteurs de pannes

Concepts clés

Dérive des horloges: Chaque machine a une horloge qui dérive ; NTP réduit l'écart sans l'annuler, donc les horodatages entre machines sont peu fiables pour l'ordre.
Relation arrivé-avant: Ordre partiel fondé sur l'ordre local, l'envoi avant la réception et la transitivité.
Horloge de Lamport: Compteur qui garantit : si A arrive avant B, alors son horodatage est inférieur ; la réciproque n'est pas vraie.
Horloge vectorielle: Un compteur par processus ; la comparaison permet de distinguer causalité et concurrence.
Modèles de défaillance: Arrêt franc, omission, défaillance temporelle, défaillance byzantine ; plus le modèle est large, plus la tolérance coûte cher.

Conclusion

Raisonner sur le temps et les pannes demande de renoncer à l'intuition d'un monde instantané et unique. Les horloges logiques ordonnent selon la causalité ; les horloges vectorielles révèlent la concurrence ; les modèles de défaillance précisent ce que l'on accepte de tolérer.

Ces notions expliquent des choix concrets de bases répliquées : résolution de conflits, versionnement, délais d'attente, et limites des promesses de disponibilité.

Cartes

Pourquoi n'y a-t-il pas d'horloge globale dans un système distribué ?: Les machines n'ont que des horloges locales qui dérivent, et les messages mettent un temps variable à circuler.
Que fait NTP ?: Il synchronise approximativement les horloges des machines avec des serveurs de temps de référence, avec une précision limitée et variable.
Que signifie « A arrive avant B » ?: A précède B s'ils sont dans le même processus dans cet ordre, ou si A est l'envoi d'un message dont B est la réception, ou par transitivité.
Deux événements sont-ils concurrents quand ils ne sont pas ordonnés par arrivé-avant ?: Oui : aucun ne peut avoir influencé l'autre, indépendamment de l'heure à laquelle ils ont eu lieu.
Comment fonctionne une horloge de Lamport ?: Chaque processus incrémente son compteur avant un événement ; à la réception d'un message, il prend le maximum entre son compteur et celui du message, puis ajoute un.
Si C(A) < C(B) pour des horloges de Lamport, peut-on conclure que A précède B ?: Non : l'inégalité n'est qu'une condition nécessaire ; elle ne prouve pas la causalité.
Comment les horloges vectorielles détectent-elles la concurrence ?: Si ni l'un ni l'autre vecteur n'est inférieur ou égal composante par composante à l'autre, les événements sont concurrents.
Quel inconvénient ont les horloges vectorielles ?: Leur taille croît avec le nombre de processus, ce qui coûte en stockage et en messages.
Qu'est-ce qu'une panne-arrêt (crash) ?: Un nœud cesse de fonctionner définitivement ou jusqu'à redémarrage, sans comportement erroné avant l'arrêt.
Qu'est-ce qu'une défaillance byzantine ?: Un comportement arbitraire d'un nœud (erreur, corruption, malveillance) ; elle exige des protocoles plus coûteux comme ceux tolérant f fautifs parmi 3f+1.
Pourquoi un détecteur de pannes est-il imparfait ?: Un délai d'attente dépassé peut venir d'un réseau lent ou d'un nœud surchargé : on ne peut pas distinguer lenteur et arrêt avec certitude.

Glossaire

Horloge logique: Compteur qui ordonne les événements selon la causalité plutôt que selon l'heure physique.
Causalité: Lien selon lequel un événement a pu influencer un autre.
Événements concurrents: Événements qui n'ont pu s'influencer mutuellement.
Horloge vectorielle: Vecteur de compteurs, un par processus, qui capture la causalité.
Défaillance byzantine: Défaillance où un nœud agit de manière arbitraire ou malveillante.
Détecteur de pannes: Mécanisme qui estime, par délais d'attente, quels nœuds sont défaillants.