Doctorat
Equipe : Intelligence Artificielle et Systèmes d'Inférence
Diagnostic distribué de systèmes respectant la confidentialité
Début le 01/10/2007
Direction : DAGUE, Philippe
Ecole doctorale : Paris XI
Etablissement d'inscription : Université Paris-Saclay
Lieu de déroulement : LRI INRIA LEO
Soutenue le 27/09/2012 devant le jury composé de :
M. Philippe DAGUE, Directeur de Thèse, Université Paris Sud Directeur de thèse
M. Laurent SIMON, Maître de conférence, Université Paris Sud Co-directeur de thèse
M. Philippe JEGOU, Professeur, Université Paul Cézanne Rapporteur
M. Pierre MARQUIS, Professeur, Université d'Artois Rapporteur
Mme Marie-Odile CORDIER, Professeur, Université Rennes 1 Examinatrice
M. Alain DENISE, Professeur, Université Paris Sud Examinateur
Activités de recherche :
Résumé :
Dans cette thèse, nous nous intéressons à diagnostiquer des systèmes intrinsèquement distribués (comme les systèmes pairs-à-pairs) où chaque pair n'a accès qu'à une sous partie de la description d'un système global. De plus, en raison d'une politique d'accès trop restrictive, il se pourra qu'aucun pair ne puisse expliquer le comportement du système global.Dans ce contexte, le challenge du diagnostic distribué est le suivant: expliquer le comportement global d'un système distribué par un ensemble de pairs ayant chacun une vision limitée, tout comme l'aurait fait un unique pair diagnostiqueur ayant, lui, une vision globale du système.
D'un point de vue théorique, nous montrons que tout nouveau système, logiquement équivalent au système pair-à-pairs initialement observé, garantit que tout diagnostic local d'un pair pourra être prolongé par un diagnostic global (dans ce cas, le nouveau système est dit correct pour le diagnostic distribué). Nous montrons aussi que si ce nouveau système est structuré (c-à-d: il contient un arbre couvrant pour lequel tous les pairs contenant une même variable forme un graphe connecté) alors il garantit que tout diagnostic global pourra être retrouvé à travers un ensemble de diagnostics locaux des pairs (dans ce cas le nouveau système est dit complet pour le diagnostic distribué).
Dans un souci de représentation succincte et afin de respecter la politique de confidentialité du vocabulaire de chacun des pairs, nous présentons un nouvel algorithme Token Elimination (TE), qui décompose le système de pairs initial vers un système structuré.
Nous montrons expérimentalement que TE produit des décompositions de meilleurs qualité (c-à-d: de plus petites largeurs arborescentes) que les méthodes envisagées dans un contexte distribué.
À partir du système structuré construit par TE, nous transformons chaque description locale en une Forme Normale Disjonctive (FND) globalement cohérente. Nous montrons que ce dernier système garantit effectivement un diagnostic distribué correct et complet. En plus, nous exhibons un algorithme capable de vérifier efficacement que tout diagnostic local fait partie d'un diagnostic minimal global, faisant du système structuré de FNDs un système compilé pour le diagnostic distribué.
