Yves METIVIER
Yves Metivier Professeur (ENSEIRB)

Équipe LaBRI : Combinatoire et Algorithmique
Fonction administrative : Président du Conseil Scientifique
Courrier électronique : yves.metivierarobaselabri.fr
Bureau : 116
Tél : +33 (0)5 40 00 69 09


Recherche

Le cadre général est l'algorithmique distribuée.

Les points plus particulièrement développés sont :

- Modélisation à l'aide des calculs locaux. On a obtenu
un algorithme efficace pour élire dans un réseau asynchrone avec communication par échange de messages en mode asynchrone, i.e., les messages sont de taille polynomiale,
alors que les algorithmes connus utilisent des messages de taille exponentielle.
On a également obtenu une caractérisation des réseaux pour lesquels il existe un algorithme d'élection avec le modèle d'Angluin et avec le modèle où un échange de message est synchrone
(atomic send/receive) (a priori, aucune caractérisation n'était connue à ce jour).



- Algorithmes distribués probabilistes. Présentation et analyse d'un algorithme d'élection en un seul passage dans les arbres tel que tous les sommets ont la même probabilité d'être élus. Présentation et analyse d'un algorithme optimal (en temps et en bits) pour calculer un ensemble indépendant maximal, idem pour la coloration.



- Agents mobiles. Equivalence entre un modèle de système distribué et un modèle à base d'agents mobiles ; cette équivalence induit des résultats publiés par ailleurs.

Extrait de publications


Yves Métivier, John Michael Robson, Nasser Saheb-Djahromi, Akka Zemmari. An Optimal Bit Complexity Randomized Distributed MIS Algorithm. Structural Information and Communication Complexity, 16th International Colloquium, SIROCCO 2009, May 2009, Piran, Slovenia. Springer, 5869 (5-6), pp.323-337, 2009, Lecture Notes in Computer Science.

Yves Métivier, John Michael Robson, Nasser Saheb-Djahromi, Akka Zemmari. About Randomised Distributed Graph Colouring and Graph Partition Algorithms. Information and Computation, Elsevier, 2010, 208 (2), pp.1296-1304.

Jérémie Chalopin, Antoni Mazurkiewicz, Yves Métivier. Labelled (hyper)graphs, negotiations and the naming problem. International conference on graph transformation (ICGT), Sep 2008, United Kingdom. Springer, 5214, pp.54-68, 2008, Lecture notes in computer science.

Jérémie Chalopin, Emmanuel Godard, Yves Métivier. Local terminations and distributed computability in anonymous networks. International symposium on distributed computing (DISC), Sep 2008, Arcachon, France. Springer, 4218, pp.47-62, 2008, Lecture notes in computer science.

Jérémie Chalopin, Yves Métivier. An efficient message passing algorithm based on Mazurkiewicz s algorithm. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2007, 80 (1-3), pp.221-246.


Responsabilité pédagogique

Création de l'enseignement d'algorithmique distribuée à l'ENSEIRB.

Administration

Directeur adjoint de l'ENSEIRB (2004-2009).
Directeur adjoint (chargé de la recherche) de l'IPB (depuis juillet 2009).


Page mise à jour le 13/08/2010 à 10:56