Instantanés et état global

Un instantané global saisit une vue cohérente de l'état d'un calcul distribué — l'état local de chaque processus plus les messages en transit — sans interrompre le fonctionnement du système.

Definition

Un état global cohérent est une collection d'états de processus locaux et de contenus de canaux correspondant à une coupe cohérente — une coupe dans laquelle, pour chaque réception de message enregistrée, l'envoi correspondant est également enregistré — de sorte que cet état aurait pu survenir pendant le calcul même si aucun instant global n'a été observé.

Scope

Ce sujet aborde la notion d'état global cohérent et la coupe qui le définit, l'algorithme d'instantané basé sur des marqueurs de Chandy-Lamport et ses hypothèses (canaux FIFO, livraison fiable), ainsi que l'application des instantanés à la détection de propriétés stables telles que la terminaison et le blocage (deadlock), et à la création de points de contrôle (checkpointing) et à la récupération distribués.

Core questions

• Qu'est-ce qui rend un état global enregistré cohérent plutôt qu'impossible ?
• Comment un tel état peut-il être enregistré pendant que le calcul continue de s'exécuter ?
• Comment les propriétés stables comme la terminaison et le blocage (deadlock) sont-elles détectées à partir d'instantanés ?

Key theories

Coupes cohérentes

Un état global correspond à une coupe à travers les séquences d'événements des processus ; la coupe est cohérente précisément lorsqu'elle est fermée sous la relation « s'est produit avant » (happened-before), garantissant qu'aucun message n'est reçu avant d'être envoyé dans l'état enregistré.

Algorithme d'instantané de Chandy-Lamport

Un initiateur enregistre son état et envoie un marqueur sur chaque canal sortant ; chaque processus, à la première réception d'un marqueur, enregistre son état puis enregistre les messages entrants sur les autres canaux jusqu'à l'arrivée de leurs marqueurs, capturant ainsi le contenu des canaux.

Détection de propriétés stables

Puisque les instantanés capturent un état dans lequel le système aurait pu se trouver, toute propriété stable (une propriété qui reste vraie une fois qu'elle est établie, comme la terminaison ou le blocage (deadlock)) détectée dans un instantané est réellement vérifiée, faisant des instantanés un outil de détection général.

Clinical relevance

Les algorithmes d'instantanés alimentent les mécanismes de point de contrôle/redémarrage distribués pour la récupération après panne, y compris la prise d'instantanés asynchrone utilisée par les moteurs de traitement de flux modernes pour fournir des garanties d'exécution « exactement une fois » (exactly-once guarantees), ainsi que la détection de blocage (deadlock) et de terminaison dans les calculs de longue durée.

History

L'algorithme de Chandy et Lamport de 1985 a fourni la première méthode pratique pour enregistrer un état global cohérent sans arrêter le système ; Mattern et d'autres ont généralisé la théorie des coupes sous-jacente, et la technique est ensuite devenue fondamentale pour le traitement de flux tolérant aux pannes.

Key figures

• K. Mani Chandy
• Leslie Lamport
• Friedemann Mattern

Seminal works

• chandy1985
• mattern1989
• lynch1996

Frequently asked questions

La prise d'un instantané nécessite-t-elle de mettre le système en pause ?

Non. L'algorithme de Chandy-Lamport enregistre un état global cohérent pendant que le calcul se poursuit, en propageant des marqueurs le long des canaux ; l'état enregistré est un état dans lequel le système aurait pu se trouver, même s'il n'a jamais été globalement arrêté.