Algorithme de Chandy-Lamport - Quiz

L'état global d'un système réparti est une capture de l'état de tous les processus du système à un instant donné. Un processus a besoin de cet état pour prendre des décisions ayant un impact sur le système.

Dans un système réparti, les processus sont autonomes et n'ont pas accès à une mémoire partagée. Cela rend difficile de connaître les états de tous les autres processus et donc d'obtenir une vue complète du système.

L'absence d'une horloge globale unique rend impossible la synchronisation précise des événements et la création d'une vision cohérente du temps dans le système.

Le temps de transfert des messages entre les processus peut varier et n'est pas garanti. Cela signifie que des informations peuvent arriver de manière incohérente, rendant difficile la capture d'un état global cohérent.

Un état cohérent représente une vue uniforme du système à un instant donné. Chaque processus dans le système voit le même état, sans aucune incohérence.

Une coupure dans un système réparti correspond à un ensemble d'événements qui marque un instant précis dans l'exécution du système. On peut associer un état global à chaque coupure.

La sauvegarde non coordonnée consiste à prendre le snapshot de l'état de chaque processus sans coordination avec les autres processus. Ceci peut conduire à des incohérences, car les processus peuvent être dans des états divergents.

La sauvegarde coordonnée implique la coordination entre tous les processus du système pour prendre des snapshots. Cette coordination garantit que les snapshots sont pris à un moment spécifique et que l'état global est cohérent.

Une coupure est un ensemble d'événements qui n'ont pas été enregistrés dans l'état global Exemple : (e13, e23, e34) indique que les événements e13, e23, e34 ne sont pas présents dans l'état global.

La cohérence d'un état global est vérifiée si chaque message reçu est correctement émis et si chaque message émis est reçu Exemple : si un message m est reçu dans l'état global, il faut que cet événement soit correctement associé à son événement d'émission.

Un état global incohérent est un état où un message reçu n'a pas été correctement associé à son événement d'émission.

Un état global fortement cohérent est un état où tous les messages émis ont été reçus.

Un état global cohérent transitoire est un état où au moins un message émis n'a pas encore été reçu.

Un ensemble d'événements qui marque un instant précis dans l'exécution du système, permettant de définir un point de cohérence pour l'état global.

Une datation permet de déterminer si chaque processus a vu les mêmes événements avant la coupure, garantissant la cohérence de l'état global.

Un algorithme qui permet de prendre un snapshot cohérent de l'état global d'un système distribué en utilisant un message spécial appelé MARKER.

L'algorithme de Chandy-Lamport suppose que les messages sont reçus dans le même ordre qu'ils sont envoyés sur chaque canal de communication (FIFO).

Un message spécial qui traverse le système distribué pour signaler aux processus de prendre un snapshot de leur état.

Chaque processus enregistre son état lorsqu'il reçoit le MARKER, assurant une cohérence de l'état global.

À l'initialisation, le processus Pi enregistre son état local, envoie un marqueur sur chaque canal sortant et commence à enregistrer l'état de chaque canal entrant. Lorsqu'un processus Pj reçoit un marqueur de Pi, il enregistre son propre état local s'il ne l'a pas déjà fait et commence à enregistrer l'état des canaux entrants de Pi. Si Pj a déjà enregistré son état, il arrête d'enregistrer l'état des canaux entrants. Lorsque Pj a reçu tous les marqueurs, il valide son état local.

L'état global du système est constitué de l'état local de chaque processus et des états des canaux de communication.

L'algorithme n'interfère pas avec l'exécution normale des processus. Il ne ralentit pas le système et ne modifie pas son comportement.

L'algorithme de Chandy-Lamport est utilisé pour prendre un instantané cohérent du système distribué.

L'algorithme de Chandy-Lamport permet de valider l'état local d'un processus après avoir reçu tous les marqueurs.