Temps et état global
La gestion du temps et de l'état global aborde la manière dont un système distribué ordonne les événements et raisonne sur son état collectif en l'absence d'horloge partagée et de vue globale instantanée.
Definition
Dans un système distribué, les événements se produisent sur des processus distincts sans horloge partagée ; l'étude du temps et de l'état global fournit les relations et les algorithmes — horloges logiques et vectorielles, instantanés et livraison ordonnée — qui permettent au système d'ordonner les événements de manière causale et de capturer des états globaux cohérents.
Scope
Ce champ d'étude englobe les horloges logiques et la relation de précédence (happened-before), la synchronisation des horloges physiques, les horloges vectorielles et la détection de la causalité et de la concurrence, la détermination d'instantanés globaux cohérents, ainsi que les garanties d'ordonnancement (FIFO, causal, total) nécessaires pour la multidiffusion fiable. Collectivement, ces outils permettent aux systèmes distribués de formuler des assertions significatives sur le 'quand' et le 'quel état' malgré l'absence d'une horloge globale.
Sub-topics
Core questions
- Comment les événements sur différents processus peuvent-ils être ordonnés sans horloge physique partagée ?
- Comment un processus peut-il déterminer si deux événements sont causalement liés ou concurrents ?
- Comment un instantané global cohérent peut-il être enregistré pendant que le calcul se poursuit ?
- Quelles garanties d'ordonnancement sur la livraison des messages sont nécessaires pour préserver la causalité ?
Key theories
- Relation de précédence (happened-before) et horloges logiques
- La relation de précédence (happened-before) de Lamport définit un ordre causal partiel sur les événements, et les horloges logiques (scalaires) leur attribuent des horodatages cohérents, fournissant une notion d'ordre indépendante de l'horloge, suffisante pour construire un ordre total pour de nombreux protocoles.
- Horloges vectorielles et causalité
- Les horloges vectorielles étendent les horloges logiques de sorte que la comparaison de deux horodatages capture précisément si un événement en précède causalement un autre ou si les deux sont concurrents, permettant un suivi précis de la causalité.
- Instantanés globaux cohérents
- L'algorithme d'instantané de Chandy-Lamport enregistre un état global cohérent — états des processus plus messages en transit — sans arrêter le système, en propageant des marqueurs le long des canaux.
Clinical relevance
Les horloges logiques et vectorielles sous-tendent la cohérence causale, la détection de conflits dans les stockages répliqués et le débogage des exécutions distribuées ; les instantanés cohérents sous-tendent le pointage distribué (distributed checkpointing), la détection d'interblocages et de terminaison, et la récupération après panne dans le traitement de flux.
History
L'article de Lamport de 1978 a introduit le temps logique et la relation de précédence (happened-before), l'un des résultats les plus cités en informatique ; Chandy et Lamport ont formalisé les instantanés globaux cohérents en 1985 ; et Fidge et Mattern ont développé indépendamment les horloges vectorielles à la fin des années 1980, complétant ainsi la boîte à outils fondamentale pour raisonner sur le temps et l'état.
Key figures
- Leslie Lamport
- K. Mani Chandy
- Colin Fidge
- Friedemann Mattern
Related topics
Seminal works
- lamport1978
- chandy1985
- fidge1988
Frequently asked questions
- Pourquoi les systèmes distribués ne peuvent-ils pas simplement utiliser des horloges physiques synchronisées ?
- Les horloges physiques dérivent et ne peuvent pas être synchronisées parfaitement sur un réseau à délai variable, de sorte que l'ordre temporel réel de deux événements peut être ambigu. Les horloges logiques et vectorielles capturent plutôt l'ordre causal qui est réellement pertinent pour la correction.
- Qu'est-ce qui rend un instantané global 'cohérent' ?
- Un instantané est cohérent si, chaque fois qu'il inclut la réception d'un message, il inclut également l'envoi de ce message. Un tel état aurait pu se produire pendant l'exécution, même si aucun instant unique n'a jamais été observé globalement.