Systèmes distribués et temps physique

Élément logiciel exécutant une tâche, un calcul par exemple, en exécutant un ensemble d'instructions. Chaque instruction correspond à un événement local : événements interne, événements d'émission de message, événements de réception de message.

Permet la communication entre processus. Il peut être uni/bidirectionnel, fiable/non fiable, FIFO/non FIFO, et synchrone/asynchrone.

Un état est la situation dans laquelle se trouve un processus à un instant donné (valeurs des variables, ensembles de données de la mémoire, ensemble de données circulant sur un canal de communication). État local: propre à un processus; État global: propre au système.

L'ensemble des valeurs des variables à un temps (instant t), or chaque processus possède une mémoire et horloge physique locales et pas de mémoire et d'horloge globales dans un système distribué.

Système où les processus peuvent communiquer entre eux par l'envoi de messages. Les processus s'exécutent en parallèle.

Système dont les actions des processus sont synchronisées, généralement par une horloge commune. Les processus peuvent se synchroniser pour réaliser l'émission et/ou la réception de messages.

Système où les processus peuvent se produire à des moments imprévisibles, sans synchronisation. L'ordre des événements n'est pas garanti.

Représente la séquence des événements dans un système distribué, affichant l'ordre des événements, les processus qui les ont générés et leurs relations temporelles.

Synchronisation des horloges des processus d'un système distribué afin qu'ils soient cohérents.

Méthode permettant de synchroniser les horloges des processus en se basant sur des informations internes au système, comme des compteurs ou des événements.

Méthode permettant de synchroniser les horloges des processus en se basant sur des informations externes au système, comme des signaux radio ou des horloges atomiques.

Temps universel coordonné (UTC), une convention internationale définissant le temps physique réel.

Une horloge atomique qui dérive d'une microseconde tous les trois ans.

Une horloge logique qui utilise des vecteurs pour représenter l'état d'un processus. Chaque élément dans le vecteur correspond à un processus différent et stocke le nombre d'événements qui ont eu lieu sur ce processus. Cette horloge permet de déterminer l'ordre partiel des événements.

La logique d'ordonnancement des événements utilisant l'horloge de Mattern. Si le vecteur d'un événement est inférieur ou égal au vecteur d'un autre événement, le premier événement est considéré comme étant arrivé avant le second.

L'horloge de Mattern ne peut pas définir un ordre global total des événements. Cela signifie que deux événements peuvent être considérés comme simultanés, même s'ils ne le sont pas réellement.

Une horloge logique qui utilise une matrice pour représenter l'état d'un processus. Chaque ligne et colonne de la matrice correspond à un processus différent. La matrice stocke des informations sur le nombre d'événements qui ont eu lieu sur les différents processus, ainsi que le nombre de messages échangés entre les processus.

L'élément diagonal de la matrice de l'horloge matricielle représente la connaissance qu'a le processus du nombre d'événements locaux qui se sont déjà produits sur les différents processus.

Les processus sont synchronisés à chaque nouvel événement local, émission de message et réception de message.

Avant de délivrer un message, l'horloge matricielle vérifie que le récepteur a reçu tous les messages précédents du même émetteur et que les messages reçus de tous les autres processus sont à jour.

Un événement qui cause un autre événement. Par exemple, si l'événement e11 mène à l'événement e12, on dit que e11 cause e12.

Un graphe qui représente les dépendances causales entre les événements dans un système distribué. Chaque nœud représente un événement, et un arc entre deux nœuds indique une relation de cause à effet entre ces deux événements.

Un système de délivrance de messages qui garantit que les messages sont délivrés dans l'ordre dans lequel ils sont envoyés. Si deux messages sont envoyés successivement de Pi vers Pj, le premier sera délivré avant le deuxième.

Un système de délivrance de messages qui garantit que les messages sont délivrés dans l'ordre des causes. Si l'envoi d'un message m1 par Pi à destination Pn précède l'envoi de m2 par Pj à destination Pn, alors m1 sera délivré avant m2.

Un numéro entier utilisé pour marquer les événements dans un système distribué. Chaque processus possède un compteur d'horlogee propre. Un événement e sur le processus Pi est daté par H(e) = Hi. Le compteur est incrémenté à chaque événement local.

Un vecteur d'horloges qui est utilisé pour marquer les événements dans un système distribué. Chaque processus possède son propre vecteur d'horloges. Le vecteur d'horloges contient la valeur de l'horloge de chaque processus dans le système.

Un ordre partiel qui peut être établi entre les événements dans un système distribué. Si un événement e est causalement dépendant d'un autre événement k, alors Hi(e) < Hj(k), où Hi est l'horloge de Lamport du processus Pi et Hj est l'horloge de Lamport du processus Pj.

Une limite de l'horloge de Lamport. Bien que e → k⇒ H(e) < H(k) soit vrai, H(e) < H(k) ⇒ e → k ne l'est pas. Cela signifie que l'horloge de Lamport ne peut pas garantir que les événements ont eu lieu en séquence.

Assure que le processus receveur a reçu tous les messages précédents envoyés par le processus émetteur.

Assure que le processus receveur a reçu tous les messages reçus par le processus émetteur avant d'envoyer le message actuel.

L'horloge vectorielle est mise à jour en prenant la valeur maximale entre la valeur actuelle et la valeur de l'horloge vectorielle du message reçu.

L'émetteur Pi incrémente sa composante dans l'horloge vectorielle Vi et ajoute l'estampille temporelle Vm au message m.

Une file d'attente triée par estampilles matricielles est utilisée pour stocker les messages retardés.

Chaque processus possède une horloge vectorielle représentant son propre temps logique.

Le protocole Birman-Schiper-Stephenson utilise des horloges vectorielles pour gérer l'ordre des événements dans un système distribué.

Les messages retardés sont mis en attente dans une file d'attente jusqu'à ce que les conditions de la règle 2 soient remplies.

Technique de sauvegarde où chaque processus enregistre son état local indépendamment des autres processus.

Technique de sauvegarde où les processus se synchronisent avant d'enregistrer leur état, garantissant ainsi un instantané cohérent du système.

Un ensemble d'événements, un pour chaque processus du système, qui marque un point de cohérence dans l'état du système.

Une coupure est dite cohérente si la datation de la coupure est identique à la datation du dernier événement de chaque processus.

Algorithme permettant d'enregistrer un état global cohérent d'un système distribué.

Pour enregistrer l'état global, il faut que tous les messages envoyés par chaque processus aient été reçus par un autre processus.

Un message spécial utilisé par l'algorithme de Chandy-Lamport pour signaler aux processus qu'il faut enregistrer leur état.