Horloges logiques et physiques

Les horloges logiques ordonnent les événements par causalité sans référence au temps réel, tandis que la synchronisation des horloges physiques maintient les horloges en temps réel de machines distinctes proches les unes des autres malgré la dérive.

Definition

Une horloge logique attribue à chaque événement un horodatage entier qui est monotone le long de chaque processus et augmente lors de la communication, capturant l'ordre causal ; la synchronisation des horloges physiques est le processus d'ajustement des horloges matérielles des machines afin qu'elles indiquent approximativement le même temps réel.

Scope

Ce sujet couvre les horloges logiques (scalaires) de Lamport et la relation d'antériorité causale qu'elles respectent, la construction d'un ordre total à partir d'horodatages logiques, et la synchronisation des horloges physiques — limitant la dérive, échangeant des horodatages pour estimer le décalage, et les algorithmes (méthode de Cristian, algorithme de Berkeley, NTP) utilisés en pratique. Il contraste les situations où le temps logique causal est suffisant et celles où le temps réel est véritablement requis.

Core questions

• Comment les horodatages peuvent-ils être attribués de manière à respecter la relation d'antériorité causale ?
• Comment un ordre total cohérent sur les événements est-il construit à partir d'horloges logiques ?
• Dans quelle mesure les horloges physiques peuvent-elles être synchronisées étant donné la variabilité du délai réseau et de la dérive ?

Key theories

Horloges logiques de Lamport

Chaque processus maintient un compteur incrémenté à chaque événement et transmis avec les messages ; les horodatages résultants respectent la relation d'antériorité causale, et les égalités résolues par l'identifiant de processus produisent un ordre total cohérent avec la causalité.

Synchronisation probabiliste et par aller-retour

La méthode de Cristian estime l'heure d'une horloge distante en mesurant le temps d'aller-retour et en supposant un délai symétrique, fournissant des bornes probabilistes sur l'erreur de synchronisation réalisable sur un réseau.

Protocole NTP (Network Time Protocol)

Le NTP organise les serveurs de temps en une hiérarchie stratifiée et utilise le filtrage statistique des mesures de décalage répétées pour discipliner les horloges sur Internet à quelques millisecondes près.

Clinical relevance

Les horloges logiques ordonnent les opérations dans les magasins répliqués et les files d'attente de messages sans se fier au temps universel, tandis que la synchronisation physique sous-tend les bases de données ordonnées par horodatage, le traçage distribué et les protocoles de sécurité qui dépendent d'une erreur d'horloge bornée.

History

L'article de Lamport de 1978 sur les horloges logiques a redéfini le temps dans les systèmes distribués comme une notion causale plutôt que physique ; en parallèle, Cristian et d'autres ont développé la synchronisation probabiliste, et le NTP de Mills est devenu le mécanisme standard pour maintenir l'alignement des horloges Internet.

Debates

Temps logique versus temps physique pour l'ordonnancement des opérations

Les horloges logiques garantissent la correction causale sans se fier aux horloges matérielles, mais ne peuvent pas relier les événements au temps réel ; les horloges physiques permettent un raisonnement en temps réel au risque d'un ordonnancement incorrect lorsque la dérive dépasse le délai de message, ce qui motive les approches hybrides.

Key figures

• Leslie Lamport
• Flaviu Cristian
• David Mills

Seminal works

• lamport1978
• mills1991
• cristian1989

Frequently asked questions

Si a a un horodatage Lamport plus petit que b, est-ce que a s'est produit avant b ?

Pas nécessairement — un horodatage plus petit est compatible avec la relation d'antériorité causale mais ne l'implique pas, car des événements concurrents peuvent recevoir des horodatages ordonnés. Pour décider précisément de la causalité, il faut des horloges vectorielles, et non des horloges logiques scalaires.