Grande école publique d'Ingénieurs en Informatique

Thèse de Lakhdar Akroun le 8 décembre

Lakhdar Akroun soutiendra le lundi 08 Décembre 2014 à 14h sa thèse intitulée « décidabilité et complexité de la relation de simulation entre services web orientés données ».

Titre : the relation of simulation between data-centric web services.

résumé: In this thesis we address the problem of analyzing specifications of data-centric Web service interaction protocols (also called data-centric business protocols). Specifications of such protocols include data in addition to operation signatures and messages ordering constraints. Analysis of data-centric services is a complex task because of the inherently infinite states of the underlying service execution instances. Our work focuses on characterizing  the problem of checking a refinement relation between service interaction protocol specifications. More specifically, we consider the problem of checking the simulation preorder when service business protocols are represented using data-centric state machines. First we study the Colombo model ~\cite{BerardiCGHM05}. In this framework, a service (i) exchanges messages using variables; (ii) acts on a shared database; (iii) has a transition based behavior. We show that the simulation test for unbounded Colombo is undecidable. Then, we consider the case of bounded Colombo where we show that simulation is (i) EXPTIME-complete for Colombo services without any access to the database, and (ii) 2-EXPTIME-complete when only bounded databases are considered. In the second part of this thesis, we define  a generic model to study the impact of various parameters on the simulation test in the context of data-centric services. The generic model is a guarded transition system acting (i.e., read and write) on databases (i.e., local and shared) and exchanging messages with its environment (i.e., other services or users) where all actions are queries over the shared and local database.

Membres du jury :
Véronique Benzaken, Professeur, Université Paris-Sud 11, examinatrice
Kais Klai, HDR, Université Paris 13, rapporteur
Michael Rusinowitch,  Professeur, Université de Lorraine Nancy, examinateur
Gwen Salaun, HDR, Ensimag, Grenoble INP, rapporteur
Farouk Toumani, Professeur, Université Blaise Pascal, directeur de thèse
Lhouari Nourine Professeur, Université Blaise Pascal, co-encadrant

Haut de page