Une horloge vectorielle est un dispositif logiciel introduit indépendamment en 1988 par Colin Fidge et Friedemann Mattern afin de donner à chaque processus d'un système distribué asynchrone des informations sur la relation de causalité arrivé-avant.
Chaque processus p possède un vecteur d'entiers appelé estampille dans lequel chaque composant estampille[i] est l'estimation par p de la valeur de l'horloge de Lamport du processus i. En particulier, estampille[p] est exactement l'horloge de Lamport de p. Il est mis à jour selon les règles suivantes :
un événement interne provoque l'incrémentation d'estampille[p] ;
avant l'envoi d'un message, estampille[p] est incrémenté et le message est envoyé avec la nouvelle valeur de l'estampille ;
lors de la réception d'un message, chaque composante j ≠ p de l'estampille prend la valeur max(estampille[j] du message, estampille[j] courante). Ensuite, estampille[p] est incrémenté.
Pour comparer deux horloges logiques, on dit que c ≺ c' (l'estampille c précède l'estampille c''') si et seulement si les deux conditions suivantes sont vérifiées :
∀ i, c[i] ≤ c'[i] (toute datation de site de l'estampille c est inférieure ou égale à la datation correspondante dans c'),
∃ i tel que c[i] < c'[i] (il existe au moins une datation strictement inférieure'').
Si c ⊀ c' et c' ⊀ c, alors c ∥ c' (les deux horloges ne sont pas comparables).
Les horloges vectorielles capturent totalement la relation → : pour deux événements a et b, a → b si et seulement si l'estampille de a est inférieure à celle de b. D'autre part, a et b sont indépendants si et seulement si leurs estampilles ne sont pas comparables.
Les horloges vectorielles donnent une information plus précise que les horloges logiques pour un coût plus élevé en mémoire. Elles sont utilisées dans des algorithmes d'exclusion mutuelle, de débogage et d'optimisation de systèmes distribués.
Bien qu'il soit possible de déterminer totalement la relation → en utilisant des horloges vectorielles, il est parfois nécessaire d'utiliser des dispositifs plus élaborés : les horloges matricielles.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Une horloge vectorielle est un dispositif logiciel introduit indépendamment en 1988 par Colin Fidge et Friedemann Mattern afin de donner à chaque processus d'un système distribué asynchrone des informations sur la relation de causalité arrivé-avant. Chaque processus p possède un vecteur d'entiers appelé estampille dans lequel chaque composant estampille[i] est l'estimation par p de la valeur de l'horloge de Lamport du processus i. En particulier, estampille[p] est exactement l'horloge de Lamport de p.
Un calcul distribué, ou réparti ou encore partagé, est un calcul ou un traitement réparti sur plusieurs microprocesseurs et plus généralement sur plusieurs unités centrales informatiques, et on parle alors d'architecture distribuée ou de système distribué. Le calcul distribué est souvent réalisé sur des clusters de calcul spécialisés, mais peut aussi être réalisé sur des stations informatiques individuelles à plusieurs cœurs. La distribution d'un calcul est un domaine de recherche des sciences mathématiques et informatiques.
Computing is nowadays distributed over several machines, in a local IP-like network, a cloud or a P2P network. Failures are common and computations need to proceed despite partial failures of machin
Explore l'ingénierie décentralisée des systèmes, les algorithmes de consensus, la tolérance aux défauts, les défauts byzantins, et les applications pratiques des systèmes tolérants aux défauts.