Résumé de séminaire

Résumé :

Une élection dans un réseau de processeurs consiste à sélectionner, de manière distribuée, un noeud et un seul dans le réseau. Si le réseau a certaines symétries initiales, le problème n'admet pas de solution, comme l'a montrée D. Angluin en 1980. Ces symétries s'expriment en terme de revêtements de graphes (morphismes conservant les propriétés locales). En 1996, A. Mazurkiewicz a démontré la réciproque du résultat d'Angluin et ainsi donné une caractérisation des réseaux pour lesquels le problème de l'élection admet une solution: les réseaux minimaux pour les revêtements.

Un algorithme générique d'élection pour une famille de réseau est un algorithme distribué élisant pour tout réseau de cette famille. En 1997, un résultat de Y. Métivier, A. Muscholl et P.A. Wacrenier a pour corollaire qu'il n'existe pas d'algorithme générique d'élection pour la famille des réseaux minimaux. Nous présenterons ici une réciproque de leur résultat, ce qui permettra d'aboutir à la caractérisation des familles de réseaux admettant un algorithme générique d'élection. Une application de ce résultat est la description exacte des connaissances sur la structure du réseau que doit posséder tout algorithme d'élection.

Références :

Home Page : http://www.cmi.univ-mrs.fr/~egodard