Résumé | En algorithmique distribuée, il n'est pas rare de modéliser le
non-déterminisme d'un système en donnant à un adversaire le choix de
l'action à exécuter. Pour peu que les actions soient randomisées, le
système devient alors un automate probabiliste, dont le comportement, si
on sélectionne aléatoirement les actions à effectuer, devient celui
d'une chaîne de Markov.
L'objectif du présent travail est d'explorer dans quelles conditions les
resultats classiques de convergence sur les chaînes de Markov persistent
dans ce genre de situation moins confortable. L'idée est de pouvoir les
appliquer pour pouvoir affirmer, sous des hypothèses minimales, la
convergence de ces systèmes non déterministes vers des distributions
bien définies.
Orateur: Philippe Duchon |