Horloges vectorielles et causalité

Les horloges vectorielles horodatent les événements de manière à ce que la comparaison de deux horodatages révèle précisément si l'un précède causalement l'autre ou si les deux sont concurrents.

Definition

Une horloge vectorielle attribue à chaque événement un vecteur de compteurs, un par processus ; un événement précède causalement un autre si et seulement si son vecteur est inférieur ou égal à celui de l'autre composante par composante et strictement inférieur dans au moins une composante, et les événements sont concurrents dans le cas contraire.

Scope

Ce sujet aborde le mécanisme des horloges vectorielles — un compteur par processus, mis à jour lors d'événements locaux et fusionné à la réception des messages — l'ordre partiel qu'il induit, et son utilisation pour détecter la causalité et la concurrence. Il couvre également les vecteurs de version, la structure étroitement liée utilisée pour détecter les mises à jour conflictuelles entre répliques, et le coût spatial inhérent au suivi précis de la causalité.

Core questions

• Comment les horodatages peuvent-ils capturer la causalité précisément plutôt que seulement de manière cohérente ?
• Comment les événements concurrents (sans lien causal) sont-ils distingués des événements ordonnés ?
• Comment les vecteurs de version détectent-ils les mises à jour conflictuelles entre répliques ?

Key theories

Caractérisation de la causalité par les horloges vectorielles

En maintenant un vecteur de compteurs par processus qui est maximisé point par point à la réception des messages, les horloges vectorielles font en sorte que l'ordre composante par composante sur les horodatages est exactement égal à la relation « s'est produit avant » (happened-before), de sorte que la concurrence est détectable.

Vecteurs de version pour la détection des conflits de répliques

Les vecteurs de version appliquent la même idée aux objets répliqués, permettant aux répliques de déterminer si une version en domine une autre ou si deux versions sont en conflit et doivent être réconciliées.

Relation avec les horloges logiques

Les horloges vectorielles affinent strictement les horloges logiques scalaires de Lamport : les horodatages scalaires garantissent seulement que l'ordre est cohérent avec la causalité, tandis que les horodatages vectoriels déterminent la causalité exactement au coût d'un espace de O(n) par horodatage.

Clinical relevance

Les horloges vectorielles et de version constituent le mécanisme standard pour la cohérence causale et la détection des conflits dans les systèmes de stockage à cohérence éventuelle, l'édition collaborative et les systèmes de clés-valeurs répliqués, où la décision de savoir si deux mises à jour sont en conflit est essentielle pour une réconciliation correcte.

History

S'appuyant sur le temps logique de Lamport, Fidge et Mattern ont introduit indépendamment les horloges vectorielles en 1988-1989 ; les vecteurs de version, étroitement liés, étaient déjà apparus en 1983 pour détecter les incohérences entre répliques, et ces structures restent centrales dans les systèmes de données répliquées modernes.

Debates

Le coût spatial du suivi précis de la causalité

Les horloges vectorielles nécessitent une entrée par processus, ce qui se prête mal à l'échelle dans les systèmes avec de nombreux participants ou des participants changeants ; cela a stimulé la recherche sur la compression, l'élagage et les alternatives approximatives qui échangent la précision contre la compacité.

Key figures

• Colin Fidge
• Friedemann Mattern
• Leslie Lamport

Seminal works

• fidge1988
• mattern1989
• parker1983

Frequently asked questions

En quoi les horloges vectorielles améliorent-elles les horloges de Lamport ?

Les horloges de Lamport garantissent seulement que l'ordre des horodatages est cohérent avec la causalité, elles ne peuvent donc pas déterminer si deux événements sont concurrents. Les horloges vectorielles rendent la comparaison exacte : on peut directement déduire si un événement s'est produit avant un autre ou s'ils sont concurrents.