Identifiant pérenne de la notice : 205628494
Notice de type
Notice de regroupement
Note publique d'information : Un système distribué peut être représenté par un graphe étiqueté : les sommets correspondent
aux processeurs, les arêtes aux liens de communication et les étiquettes associées
aux sommets codent les états des processeurs. Un algorithme distribué est alors décrit
par un système de règles de transition locale où l'étiquette suivante d'un sommet
est fonction de son étiquette actuelle et de celles de ses voisins (réétiquetage local).
Les réétiquetages opérant sur des voisinages disjoints se déroulent en parallèle,
de manière asynchrone. Dans ce cadre, on étudie la réalisabilité et non-réalisabilité
des tâches distribuées. Nous illustrerons notre méthode en nous intéressant en particulier
à certains problèmes spécifiques aux systèmes distribués (élection d'un noeud, reconnaissance
de certaines propriétés topologiques du graphe sous-jacent au réseau, calcul de métriques
du réseau comme par exemple la taille ou le diamètre). Dans tous ces cas, on présente
une caractérisation complète de ce qui est réalisable par calcul distribué en fonction
de la topologie du graphe sous-jacent mais également du degré de connaissance qu'a
le réseau sur lui-même ("connaissance structurelle"). Ces conditions nécessaires et
suffisantes sont principalement exprimées en termes de fermetures par s̀̀imilarités''
des familles de réseaux considérées. Ces s̀̀imilarités'' sont décrites de manière
combinatoire à l'aide de morphismes de graphes particuliers : les revêtements et les
quasi-revêtements. Les preuves des conditions nécessaires emploient des techniques
de simulation à base de revêtements et quasi-revêtements. Les algorithmes distribués
présentés pour les preuves des conditions suffisantes se fondent essentiellement sur
un algorithme de cartographie du réseau sous-jacent. Celui-ci est construit à partir
des extensions d'un algorithme d'énumération de A. Mazurkiewicz et d'un algorithme
de détection des propriétés stables de Shy, Szymanski et Prywes.
paprika.idref.fr
data.idref.fr
Documentation
