SoCRSS

L'Unisson


13/02/2015
Intervenant(s) : Franck PETIT
Dans un système réparti asynchrone, chaque processus logiciel a son temps propre, son code propre et ses registres propres. Il n’a qu’une connaissance locale du réseau et ne connaît que les liens qui le relient à d’autres processus appelés voisins. Dans un tel environnement, la synchronisation des horloges des processus entre elles est une tâche fondamentale et difficile. Nous nous focalisons au cas où les valeurs d’horloges sont gérées dans un espace discret et fini. Un système distribué synchrone est dit à l’unisson lorsque tous les processus ont leur horloge à la même valeur à chaque unité de temps. Dans un système réparti asynchrone, la meilleure forme d'unisson que l’on puisse espérer atteindre consiste à faire en sorte que les valeurs d’horloge de deux voisins quelconques ne diffèrent pas d’au plus une unité. Un algorithme distribué d’unisson (synchrone ou asynchrone) consiste donc à mettre à l’unisson un système qui ne l’est pas. Un algorithme distribué est dit auto-stabilisant si à partir d’une configuration quelconque du système, toute exécution de l’algorithme atteint en un temps fini (et sans intervention extérieure) une configuration à partir de laquelle tous les suffixes d’exécution possibles sont corrects, c’est-à-dire que tous ces suffixes vérifient la spécification du problème que l’on cherche à résoudre. Lors de cet exposé, après avoir montré que tout algorithme d’unisson est intrinsèquement auto-stabilisant, nous présenterons les propriétés topologiques permettant d'établir la taille mémoire minimale d'une horloge à partir de laquelle il est possible de résoudre l'unisson. Puis nous décrirons des algorithmes optimaux pour ces bornes.
Plus d'informations ici
dimitri.galayko (at) nulllip6.fr
 Mentions légales
Carte du site |