SurePaths Réunion finale

Novembre 2006

Problématique

Mesure de la disponibilité et de la fiabilité des systèmes redondants

Comment évaluer les probabilités de panne, le MTTF ? Chaînes de Markov (temps discret ou continu) Espace d’états trop grand où on mesure des probabilités

trop petites Techniques et Outils

Simulation à événements rares Borne Stochastique ou Polyhédrale

et Analyse Numérique Markovienne

Simulation

2 approches pour une problématique unique: simulation d’événements rares

Simulation Parfaite (ID)

Quasi Monte-Carlo (Armor)

Simulation Parfaite

Repose sur le couplage dans le passé pour obtenir un échantillon distribué selon loi stationnaire

Couplage : deux trajectoires de simulation, utilisant la même séquence d’aléas, qui se rejoignent

Partir de tous les points et faire coupler toutes les trajectoires. Utilisation de propriétés de monotonie pour accélérer les simulations

(faire coupler les trajectoires issus des points minimaux et maximaux) identification d’événements monotones unification du formalisme de description d’événements

Simulation Parfaite (2)

Application des techniques de réduction de variance pour améliorer l’erreur d’estimation

Mise en œuvre des techniques de couplages de trajectoires par variables antithétiques

Développement du logiciel PSI 2 introduction d’événements monotones basés sur des tables d’index utilisation de variables antithétiques étude du couplage sur fonction de « reward » pour optimiser le temps de

simulation

Quasi Monte-Carlo

Méthode déterministe convergeant plus rapidement que Monte Carlo, mais champ d’application plus restreint

Randomisation pour une estimation de la variance Contribution récente : développement d’une

méthode (Array-RQMC) très efficace pour simuler les chaînes de Markov sur un espace d’états totalement ordonné

Contribution pour l’évaluation d’événements rares Etude et amélioration des méthodes « d’importance

splitting » Combinaison de ces méthodes avec la technique array-

RQMC Etude et définition de propriétés de robustesse à la rareté

des estimateurs, avec applications en fiabilité Mise en œuvre efficace des estimateurs standards pour

l’analyse d’événements rares ; ajout du calcul des sensibilités

Borne Stochastique

Preuve de plusieurs algorithmes pour construire des bornes stochastiques pour des chaînes de Markov, fonction de la comparaison des distributions (st, icx), de la structure visée pour l’algorithme numérique (souvent la lumpabilité), de l’ordre sur les états (partiel, total)

2 propriétés fondamentales : monotonie stochastique et comparaison de matrices

Comparaison « st » : comparaison trajectorielle Comparaison « icx » : élément extrémal d’une

distribution de même moyenne

Monotonie

La notion de monotonie apparaît comme une notion fondamentale et transversale (événementielle en simulation, sur les opérateurs).

Monotonie : un événement ou un opérateur conserve l’ordre sur les états, sur les variables aléatoires, ou sur les distributions.

Passer d’un ordre total (approche actuelle) à la structure d’ordre partiel naturel au modèle (réseau de files, réseau de Petri) où très souvent on peut montrer la monotonie.

Borne Polyhédrale

Peu de techniques existent pour calculer des bornes de métriques en transitoire.

Nous avons développé une approche permettant de calculer des bornes de la MTTF d’un système (ou de la récompense moyenne cumulée, si le modèle contient des coûts ou des récompenses).

Outils de base : algèbre linéaire et analyse des trajectoires de la chaîne de Markov sous-jacente.

« Stochastic Model checking »

Consiste à évaluer sur tous les états de la chaîne une formule probabiliste impliquant des transitoires, les chemins ou les probabilités stationnaires.

Le « Model checking » Markovien repose sur les chaînes en temps discret ou continu.

On a prouvé la faisabilité des techniques de bornes « st » pour le calcul de tous les types de formules en temps discret ou continu.

Bornes et Algébre de Processus

« Stochastic process algebra » : ajout d’une temporisation exponentielle à une algèbre de processus classique (PEPA à partir de CSP, Hillston, Edimbourg)

Avantage : « Stochastic Model checker » pour PEPA (Birmingham)

Borne « st » et « icx » pour des spécifications PEPA de la distribution d’un temps de cycle ou d’un « Time To Failure »

Surcharge UML vers PEPA et PEPA vers descripteur tensoriel (à la PEPS)

Réseau d’automates stochastiques

Définition et mise en œuvre d’un modèle PH-SAN

Extensions vers un modèle Qu-San Utilisation des MDD Intégration dans PEPS Modularité de PEPS

Collaborations

Intégration dans l’outil PEPS d’un algorithme de borne (extraction de colonne et de lignes à partir du descripteur tensoriel). Publié, ID-PRiSM

Améliorer la précision des bornes « st » par application d’un polynôme sur la matrice de transition. Publié, ID-PRiSM

Simulation parfaite utilisant des techniques de réduction de variance. Publié, ID-ARMOR

Approche mixte (pohyhédrale et stochastique) sur des problèmes de disponibilité. En cours ARMOR-PRiSM.

Collaborations (suite)

Intégration dans PEPS des calculs sur les transitoires. En cours, ID-ARMOR-PRiSM.

Plusieurs algorithmes publiés par PRiSM (transitoires des matrices de classe C, bornes stochastiques sur la disponibilité ponctuelle) suite à des discussions avec ARMOR.

Optimisation du codage des transitions dans une simulation parfaite pour minimiser le temps de couplage. En cours, PRiSM-ID.

Publications

Liste détaillée sur le site. 9 revues ou chapitres de livre 34 conférences internationales. 5 posters ou rapports internes 2 thèses soutenues (I. Sbeity, A. Couto da Silva) 2 thèses à soutenir avant décembre 2007

(A. Busic, S. Younes)

Logiciels

Peps : analyse numérique de chaînes de Markov, structure d’accueil ?

Psi et Psi2 : simulation parfaite pour matrice stochastique quelconque et amélioration pour système monotone (1 dépôt ANL et un autre en cours)

Xborne : les algorithmes de calcul de borne, à modifier pour être intégrables à d’autres outils d’analyse numérique ou de « Stochastic Model Checking ».

Poursuite du projet

Projet Blanc 2005 ID+PRiSM : monotonie stochastique.

Projet Model Checking Stochastique (SETIN 2006) (PRiSM, ID, INT, LAMSADE, Paris I).

Collaboration Versailles Birmingham : SPA + Model Checking + Borne Stochastique : en cours de montage (CNRS DRI puis Europe).

Poursuite du projet (suite)

ARC INRIA sur la simulation d’événements rares (Armor + projets INRIA Aspi, Mathfi, Omega) + Univ. Bamberg+ CWI + EDF + CENA

Collaboration INRIA-FQNRT avec l’Université de Montréal : Quasi-Monte Carlo et Splitting. Séjour Sabbatique à Rennes de P. L’Ecuyer depuis juillet 2006.