Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Thèse:   
Analyses et preuves formelles d’algorithmes distribués probabilistes

Date 2014-06-16  14:00-16:00
TitreAnalyses et preuves formelles d’algorithmes distribués probabilistes 
RésuméL’intérêt porté aux algorithmes probabilistes est, entre autres, dû à leur simplicité. Cependant, leur analyse peut devenir très complexe et ce particulièrement dans le domaine du distribué. Nous mettons en évidence des algorithmes, optimaux en terme de complexité en bits résolvant les problèmes du MIS et du couplage maximal dans les anneaux, qui suivent le même schéma. Nous élaborons une méthode qui unifie les résultats de bornes inférieures pour la complexité en bits pour les problèmes du MIS, du couplage maximal et de la coloration. La complexité de ces analyses pouvant facilement mener à l’erreur et l’existence de nombreux modèles dépendant d’hypothèses implicites nous ont motivés à modéliser de façon formelle les algorithmes distribués probabilistes correspondant à notre modèle (passage de messages, anonyme et synchrone), en vue de prouver formellement des propriétés relatives à leur analyse. Pour cela, nous développons une bibliothèque, RDA, basée sur l’assistant de preuve Coq. 
LieuAmphi (50) 
LaboratoireLaBRI 
DoctorantAllyx Fontaine 
Directeur de thèseAkka Zemmari, Pierre Castéran 



Aucun document lié à cet événement.

Retour
Retour à l'index