Résumé | En algorithmique distribuée, plusieurs problèmes n'admettent
pas de solution déterministe sous certaines hypothèses (anonymat par
exemple). On se retrouve donc à devoir concevoir une solution
probabiliste à ces problèmes.
Dans cet exposé, je montrerai quelques exemples de solutions
probabilistes à des problèmes fondamentaux en algorithmique distribuée
tels que le MIS, le coloriage ou la décomposition de graphes. Je
présenterai en particulier une analyse d'un algorithme optimal pour réaliser
le coloriage.
Cet exposé présente des travaux menés en collaboration avec
Y. Métivier, J.M. Robson et N. Saheb. |