28532 articles – 22057 Notices  [english version]

tel-00136083, version 1

Méthodes probabilistes pour la vérification des systèmes distribués

Stéphane Messika () 1

École normale supérieure de Cachan - ENS Cachan (14/12/2004), Laurent Fribourg (Dir.)

Résumé : Les probabilités sont de plus en plus utilisées dans la conception et l'analyse des systèmes logiciels et matériels informatiques. L'introduction des tirages aléatoires dans les algorithmes concurrents et distribués permet de résoudre certains problèmes insolubles dans le cadre déterministe et de réduire la complexité de nombreux autres. Nous avons été amenés à étudier deux types de propriétés probabilistes. La convergence : cette propriété assure que, quel que soit l'état de départ et quel que soit l'enchainement des actions, le système atteindra toujours (avec probabilité 1) un ensemble donné d'états d'arrivée en un nombre fini d'actions (auto-stabilisation).L'accessibilité : ce type de propriété répond à des questions telles que "quelle est la probabilité p qu'une exécution partant d'un état initial donné atteigne un état final donné ? Quelles sont les bornes maximales et minimales de p ?" En ce qui concerne le premier point, nous avons développé de nouveaux critères permettant d'assurer la convergence et d'en calculer la vitesse (mixing time). Ces crotères utilisent l'analogie avec des modèles de physiquestatistique (champs de Markov) et exploitent des outils d'analyse probabiliste classiques (coupling, chaînes de Markov, processus de décision markoviens). Pour le second point, nous avons obtenu des résultats pratiques sur la vérification de protocoles de communication, comme le protocole Ethernet, en les modélisant à l'aide d'automates temporisés probabilistes et utilisant des outils de model-checking temporisés (HyTech) et probabiliste (PRISM, APMC).

  • 1 :  Laboratoire Spécification et Vérification [Cachan] (LSV)
  • CNRS : UMR8643 – INRIA – École normale supérieure de Cachan - ENS Cachan
  • Domaine : Informatique/Réseaux et télécommunications
  • Mots-clés : model-checking – probabilités – chaînes de Markov – systèmes distribués – processus de décision markovien – auto-stabilisation – automates temporisés probabilistes
 
  • tel-00136083, version 1
  • oai:tel.archives-ouvertes.fr:tel-00136083
  • Contributeur : 
  • Soumis le : Lundi 12 Mars 2007, 11:09:07
  • Dernière modification le : Lundi 12 Mars 2007, 13:17:19