Dans une composition de services Web basée protocole, un ensemble de services composants se collaborent pour donner lieu à un service Composite. Chaque service est représenté par un automate à états finis (AEF). Au sein d’un AEF, chaque transition exprime l’exécution d’une opération qui fait avancer le service vers un état suivant. Une exécution du composite correspond à une séquence de transitions où chacune est déléguée à un des composants. Lors de l’exécution du composite, un ou plusieurs composants peuvent devenir indisponibles. Ceci peut produire une exécution incomplète du composite, et de ce fait un recouvrement est nécessaire. Le recouvrement consiste à transformer l’exécution incomplète en une exécution alternative ayant encore la capacité d’aller vers un état final. La transformation s'effectue en compensant certaines transitions et exécutant d’autres. Cette thèse présente une étude formelle du problème de recouvrement dans une composition de service Web basée protocole. Le problème de recouvrement consiste à trouver une meilleure exécution alternative parmi celles disponibles. Une meilleure alternative doit être atteignable à partir de l’exécution incomplète avec un nombre minimal de compensations visibles (vis-à-vis le client). Pour une exécution alternative donnée, nous prouvons que le problème de décision associé au calcul du nombre de transitions invisiblement compensées est NP-Complet. De ce fait, nous concluons que le problème de décision associé au recouvrement appartient à la classe ΣP2. / In a protocol-based Web service composition, a set of available component services collaborate together in order to provide a new composite service. Services export their protocols as finite state machines (FSMs). A transition in the FSM represents a task execution that makes the service moving to a next state. An execution of the composite corresponds to a sequence of transitions where each task is delegated to a component service. During composite run, one or more delegated components may become unavailable due to hard or soft problems on the Network. This unavailability may result in a failed execution of the composite. We provide in this thesis a formal study of the automatic recovery problem in the protocol-based Web service composition. Recovery consists in transforming the failed execution into a recovery execution. Such a transformation is performed by compensating some transitions and executing some others. The recovery execution is an alternative execution of the composite that still has the ability to reach a final state. The recovery problem consists then in finding the best recovery execution(s) among those available. The best recovery execution is attainable from the failed execution with a minimal number of visible compensations with respect to the client. For a given recovery execution, we prove that the decision problem associated with computing the number of invisibly-compensated transitions is NP-complete. Thus, we conclude that deciding of the best recovery execution is in ΣP2.

L'intelligence ambiante est considérée comme l'une des évolutions majeures de l'informatique ubiquitaire. Elle vise la mise en œuvre des environnements ambiants ou des espaces intelligents permettant d'améliorer la vie quotidienne des utilisateurs, leur bien-être et leur sécurité. Un environnement ambiant dispose d'une multitude d'équipements (capteurs, actionneurs), fournissant des services ubiquitaires atomiques qui sont distribués et de nature hétérogène. Ces services atomiques disponibles dans ce type d'environnement, ne répondent pas directement ou complètement à toutes les exigences et les besoins des utilisateurs. Par ailleurs, ces services de haut niveau peuvent impliquer l'interaction de services ubiquitaires appartenant et/ou contrôlés par différentes structures ou domaines (i.e. environnement multi-domaine). Dans ces travaux de thèse, on a étudié les problématiques reliées à l'agrégation des services ubiquitaires atomiques dans des coopérations et des compositions dans un environnement ambiant multi-domaine afin de répondre à des besoins utilisateurs. Cette étude concerne l'interopérabilité sémantique et comportementale des compositions de services ainsi que leurs spécifications dans un modèle formel basé sur la logique constructive BCDL0. Cette thèse a contribuée par la réalisation d'un canevas sémantique permettant la conception et la vérification formelles des processus coopératifs dans l'assistant à la preuve Isabelle/HOL. Le canevas sémantique proposé consiste en une ontologie de coopération extensible et un langage de spécification de services fiable (Sound) ainsi que des modules de mise en correspondance vers des infrastructures cibles / Ambient Intelligence is considered as the major application domain of ubiquitous computing. It aims at implementing intelligent environments to improve the daily activities, the well-being and the safety of users. An ambient environment has a multitude of devices (sensors, actuators), providing atomic ubiquitous services which are distributed and heterogeneous. These atomic services available in these environments, do not directly or fully meet all the requirements and the needs of users. Moreover, these high-level services may involve the interaction of ubiquitous services owned and/or controlled by different structures or domains (i.e. multi-domain environment). In this work, we studied the problems related to the aggregation of atomic ubiquitous services in cooperations and compositions in an ambient multi-domain environment in order to meet users' needs. This study concerns the semantic and behavioral interoperability of high-level composite services and their formal specification. This latter, is based on the Basic Constructive Description Logic, namely, BCDL0 formal model. This work contributes by realizing a semantic framework for the design and formal verification of cooperative processes in the interactive theorem prover Isabelle/HOL. The proposed semantic framework consists of an extensible cooperation ontology, a sound formal specification language of ubiquitous services and a components for mapping the formally proved cooperatives processes to the targeted infrastructures

Le but de cette thèse est de dégager un cadre sémantique formel approprié supportant l'interopérabilité dedifférents formalismes déjà utilisés pour décrire et déployer un service Web. En d’autres termes, nouscontribuons au développement d’un formalisme mathématique rigoureux permettant de décrire un service Webcomplexe susceptible de changer pendant l’exécution et de coordonner avec les autres services de façonadaptative. Pour atteindre cet objectif, les étapes de description, de sélection et de composition ont constitué lestrois majeures problématiques étudiées dans cette thèse.Pour ce faire, nous avons proposé dans un premier temps, à travers l’utilisation du cadre sémantique formel K lelangage K-WSDL; un langage de description de services Web doté d’une sémantique opérationnelle en terme derègles de réécriture qui peut être exécutable et analysable sous Maude. Nous avons introduit, dans un secondtemps, l’approche WS-Sim basée sur la théorie des catégories qui évalue l’équivalence comportementale entreservices en représentant chaque service par une catégorie et en établissant des liens formels (foncteur) entre elles.Enfin, nous avons présenté le modèle RMop-ECATNet (Refined Meta Open ECATNet ) : un modèle dédié à laspécification formelle de la composition des services Web et fruit du raffinement du modèle Mop-ECATNetproposé par [LB14]. Nous avons étendu et enrichi ce dernier aux trois niveaux : structurel, comportemental etimplémentation. / The aim of this thesis is to provide a suitable formal semantic framework that supports interoperability ofdifferent formalisms already used to describe and deploy a Web service. In other words, we contribute to thedevelopment of a rigorous mathematical formalism to describe a complex Web service that may change duringexecution and coordinate with other services adaptively. To achieve this goal, the steps of description, selectionand composition constitute the three major issues studied in this thesis.We proposed so, initially, through the use of the K semantic framework the K-WSDL : a Web servicesdescription language endowed with an operational semantics in terms of rewriting rules which can be executedand analyzed in Maude. We introduced, in a second step, WS-Sim, a new approach based on the category theorywhich evaluates the behavioral equivalence between services by representing each service by a category and byestablishing formal links (functor) between them. Finally, we present RMop-ECATNet (Refined Meta OpenECATNet): a formal model for the specification of services composition. product of the refinement of the Mop-ECATNets model, introduced initially by [LB14]. We extended and enriched this model at three distinct levels:at the structural, behavioural level and implementation levels.

A l'heure du numérique, la quantité d'objets connectés ne cesse de croître et de se diversifier. Afin de supporter cette complexité croissante, nous avons souhaité apporter un maximum d'automatismes à l'Internet des Objets de manière à garantir une qualité de service (QoS) de bout en bout. Pour ce faire, un composant de service autocontrôlé est proposé pour intégrer l'objet dans l'écosystème digital. Grâce à la calibration de chaque service, qui permet la connaissance du comportement, une composition automatisée devient possible. Nous avons illustré la faisabilité de notre approche à travers un cas d'étude. Nous avons également montré comment les objets connectés peuvent s'assembler eux-mêmes, coopérant pour atteindre un objectif commun, tout en répondant aux exigences de QoS globales. / In the digital era, the number of connected objects continues to grow and diversify. To support this increasing complexity, we wanted to bring a maximum of automatisms to the Internet of Things in order to guarantee end-to-end quality of service (QoS). To do this, a self-controlled service component is proposed to integrate the object into the digital ecosystem. Thanks to the calibration of each service, which makes it possible to know the behaviour, an automated composition becomes possible. We have illustrated the feasibility of our approach on a case study. We also have shown how connected objects can assemble themselves, cooperating to achieve a common objective, while meeting global QoS requirements.

Serviceevolution erlaubt es, einen Service durch einen anderen Service zu verfeinern oder zu ersetzen. Der Austausch durch einen anderen Service sollte garantieren, dass alle oder ausgewählte Partner des Originalservices erhalten bleiben. In dieser Arbeit entwickeln wir einen Ansatz welcher einem Serviceentwickler helfen soll, Analyse- und Syntheseaufgaben für den Serviceaustausch so durchzuführen, dass jeder Partner eines gegebenen Services beim Austausch erhalten bleibt. Wir modellieren einen Kontrollfluss eines Services als Beschreibung der Reihenfolge von asynchron kommunizierenden Ereignissen mittels eines impliziten ungeordneten Nachrichtenspeichers. Weiterhin studieren wir den Verhaltensaspekt von korrekter Interaktion zwischen Services und konzentrieren uns auf zwei Varianten von Verklemmungsfreiheit als Korrektheitskriterien von Serviceersetzung. Der wichtigste Beitrag ist ein Ansatz zur Charakterisierung jedes möglichen Austausches eines gegebenen Services. Die zentrale Idee dieses Ansatzes ist eine systematische Untersuchung der Verbindung zwischen einem Service und all seiner Partner bzgl. eines gegebenen Korrektheitskriteriums. Wir nutzen diese Verbindung um von einem gegebenen Service einen kanonischen Partner und einen kanonischen Austausch bzgl. aller Partner zu synthetisieren. Ein Service welcher den kanonischen Austausch eines gegebenen Services verfeinert wird als Austausch des gegebenen Services angesehen, wenn die Menge all seiner Partner jeden Partner des gegebenen Services enthält. Mit dem kanonischen Austausch eines gegebenen Services identifizieren wir die Menge der möglichen austauschenden Services eines gegebenen Services bei der jeder exakt die gleichen Partner wie der gegebene Service hat. Einige Ergebnisse dieser Arbeit fundieren auf früheren Arbeiten zu Austausch und Korrektheit von Services und können daher mit diesen verbunden werden um schwierigere Analyse- und Syntheseaufgaben für den Serviceaustausch durchzuführen. / Service evolution allows one service to be refined into or substituted by another service. Substituting one service by another service should guarantee to preserve all or selected partners of the original service. In this thesis, we develop an approach that shall assist a service designer, such as a domain expert, to perform analysis and synthesis tasks on service substitution. We model a control flow of services that describes the ordering of asynchronously communicating events over an implicit unordered message buffer. We study the behavioral aspect of correct interaction between services and concentrate on two variants of deadlock freedom as correctness criteria of service substitution. The major contribution of this thesis is an approach for characterizing the set of all substitutes for a given service. We systematically investigate the relationship between a service and all its partners under a given correctness criterion and employ this relationship to synthesize from a given service its canonical partner and its canonical substitute with respect to all partners. A service that refines the canonical substitute for a given service is regarded as a substitute for the given service if the set of all its partners includes every partner of the given service. With the canonical substitute of a given service, we identify a specific subset of the set of all substitutes for the given service, each of which has exactly the same set of partners as that of the given service. Parts of the results in this thesis have been established upon previous works on service substitution and correctness of services. Consequently, we can also combine our results with the related existing techniques to perform more sophisticated analysis and synthesis tasks on service substitution.

Mit der stetigen Konsolidierung der Web Service Standards vollzieht sich in der Diskussion zu serviceorientierten Architekturen ein Wechsel weg von der Implementierung und dem Deployment von Services hin zum Service Management. Die Indikatoren: Anzahl der Standardisierungsanfragen und die Menge großer Forschungsprogramme in diesem Bereich sind evident für einen wachsenden Bedarf an Managementmethoden für die Abbildung von Geschäftsanforderungen auf Servicekompositionen. Die Verwendung von semiformalen Modellen sowie die verteilte Entwicklung von SOA Services machen eine an Konventionen orientierte konstruktive Einschränkung der Freiheitsgrade bei der Prozess- und Servicemodellierung notwendig. In dieser Arbeit wird eine generische Methode vorgestellt, welche durch die Einführung von „Beschreibungsrahmen“ (Description Kits) sowohl eine Einschränkung der Modellierungsfreiheit in Bezug auf natürlichsprachliche Aspekte in fachkonzeptuellen Modellen erlaubt, als auch eine restriktive Benutzung bestehender Modellierungssprachen ermöglicht. Als Anwendungsfall wird die Konfiguration serviceorientierter Architekturen diskutiert. - (Die Dissertation ist veröffentlicht im Logos Verlag Berlin GmbH, http://www.logos-verlag.de, ISBN: 978-3-8325-2402-9) / With Service-oriented Architectures (SOA) companies are facing a paradigm shift towards services as the key unit of their enterprise architectures. An exploitation of the potential of Service-oriented Architectures is up to the applicability of semi-formal business models for a transformation into service compositions. However, several conceptual shortcomings prevent semi-formal models from being a suitable resource of an automated transformation process. Problems result from a multitude of modeling aims, objects, and procedures. Enhancements in order to solve these problems require both systematic preparation, and a methodical approach. This thesis provides a modeling method for business process-oriented SOA design using a meta-model based approach. An integrated modeling environment gives an overview of business requirements and allows appropriate assignment of SOA services to the business functions at the same time. The research refers to the example of process-oriented analysis and optimization of administrative procedures in German universities.

Mit der stetigen Konsolidierung der Web Service Standards vollzieht sich in der Diskussion zu serviceorientierten Architekturen ein Wechsel weg von der Implementierung und dem Deployment von Services hin zum Service Management. Die Indikatoren: Anzahl der Standardisierungsanfragen und die Menge großer Forschungsprogramme in diesem Bereich sind evident für einen wachsenden Bedarf an Managementmethoden für die Abbildung von Geschäftsanforderungen auf Servicekompositionen. Die Verwendung von semiformalen Modellen sowie die verteilte Entwicklung von SOA Services machen eine an Konventionen orientierte konstruktive Einschränkung der Freiheitsgrade bei der Prozess- und Servicemodellierung notwendig. In dieser Arbeit wird eine generische Methode vorgestellt, welche durch die Einführung von „Beschreibungsrahmen“ (Description Kits) sowohl eine Einschränkung der Modellierungsfreiheit in Bezug auf natürlichsprachliche Aspekte in fachkonzeptuellen Modellen erlaubt, als auch eine restriktive Benutzung bestehender Modellierungssprachen ermöglicht. Als Anwendungsfall wird die Konfiguration serviceorientierter Architekturen diskutiert. - (Die Dissertation ist veröffentlicht im Logos Verlag Berlin GmbH, http://www.logos-verlag.de, ISBN: 978-3-8325-2402-9) / With Service-oriented Architectures (SOA) companies are facing a paradigm shift towards services as the key unit of their enterprise architectures. An exploitation of the potential of Service-oriented Architectures is up to the applicability of semi-formal business models for a transformation into service compositions. However, several conceptual shortcomings prevent semi-formal models from being a suitable resource of an automated transformation process. Problems result from a multitude of modeling aims, objects, and procedures. Enhancements in order to solve these problems require both systematic preparation, and a methodical approach. This thesis provides a modeling method for business process-oriented SOA design using a meta-model based approach. An integrated modeling environment gives an overview of business requirements and allows appropriate assignment of SOA services to the business functions at the same time. The research refers to the example of process-oriented analysis and optimization of administrative procedures in German universities.

The increasing number of smart systems inevitably leads to a huge number of systems that potentially provide independently designed, autonomously operating services. In near-future smart computing systems, such as smart cities, smart grids or smart mobility, independently developed and heterogeneous services need to be dynamically interconnected in order to develop their full potential in a rather complex collaboration with others. Since the services are developed independently, it is challenging to integrate them on-the-fly at run time. Due to the increasing degree of distribution, such systems operate in a decentralized and volatile environment, where central management is infeasible. Conversely, the increasing computational power of such systems also supersedes the need for central management. The four identified key problems of adaptable, collaborative Smart Service Systems are on-demand composition of complex service structures in decentralized environments, the absence of a comprehensive, serendipity-aware specification, a discontinuity from design-time specification to run-time execution, and the lack of a development methodology that separates the development of a service from that of its role essential to a collaboration. This approach utilizes role-based models, which have a collaborative nature, for automated, on-demand service composition. A rigorous two-phase development methodology is proposed in order to demarcate the development of the services from that of their role essential to a collaboration. Therein, a collaboration designer specifies the collaboration including its abstract functionality using the proposed role-based collaboration specification for Smart Service Systems. Thereof, a partial implementation is derived, which is complemented by services developed in the second phase. The proposed middleware architecture provides run-time support and bridges the gap between design and run time. It implements a protocol for coordinated, role-based composition and adaptation of Smart Service Systems. The approach is quantitatively and qualitatively evaluated by means of a case study and a performance evaluation in order to identify limitations of complex service structures and the trade-off of employing the concept of roles for composition and adaptation of Smart Service Systems.:1 Introduction 1.1 Motivation 1.2 Terminology 1.3 Problem Statement 1.4 Requirements Analysis 1.5 Research Questions and Hypothesis 1.6 Focus and Limitations 1.7 Outline 2 The Role Concept in Computer Science 2.1 What is a Role in Computer Science? 2.2 Roles in RoleDiSCo 3 State of the Art & Related Work 3.1 Role-based Modeling Abstractions for Software Systems 3.1.1 Classification 3.1.2 Approaches 3.1.3 Summary 3.2 Role-based Run-Time Systems 3.2.1 Classification 3.2.2 Approaches 3.2.3 Summary 3.3 Spontaneously Collaborating Run-Time Systems 3.3.1 Classification 3.3.2 Approaches 3.3.3 Summary 3.4 Summary 4 On-Demand Composition and Adaptation of Smart Service Systems 4.1 RoleDiSCo Development Methodology 4.1.1 Role-based Collaboration Specification for Smart Service Systems 4.1.2 Derived Partial Implementation 4.1.3 Player & Context Provision 4.2 RoleDiSCo Middleware Architecture for Smart Service Systems 4.2.1 Infrastructure Abstraction Layer 4.2.2 Context Management 4.2.3 Local Repositories & Knowledge 4.2.4 Discovery 4.2.5 Dispatcher 4.3 Coordinated Composition and Subsequent Adaptation 4.3.1 Initialization and Planning 4.3.2 Composition: Coordinating Subsystem 4.3.3 Composition: Non-Coordinating Subsystem 4.3.4 Competing Collaborations & Negotiation 4.3.5 Subsequent Adaptation 4.3.6 Terminating a Pervasive Collaboration 4.4 Summary 5 Implementing RoleDiSCo 5.1 RoleDiSCo Development Support 5.2 RoleDiSCo Middleware 5.2.1 Infrastructure Abstraction Layer 5.2.2 Knowledge Repositories and Local Class Discovery 5.2.3 Planner 6 Evaluation 6.1 Case Study: Distributed Slideshow 6.1.1 Scenario 6.1.2 Phase 1: Collaboration Design 6.1.3 Phase 2: Player Complementation 6.1.4 Coordinated Composition and Adaptation at Run Time 6.2 Runtime Evaluation 6.2.1 General Testbed Setup and Scenarios 6.2.2 Discovery Time 6.2.3 Composition Time 6.2.4 Discussion 6.3 The ›Role‹ of Roles 6.4 Summary 7 Conclusion 7.1 Summary 7.2 Research Results 7.3 Future Work

La thèse est consacrée à des problématiques d’algorithmique et de complexité sur deux sujets. Le premier sujet s’intéresse à la composition comportementale des services web. Ce problème a été réduit à la simulation d’un automate par le produit fermé d’un ensemble d’automates. La thèse étudie dans sa première partie la complexité de ce problème en considérant deux paramètres : le nombre des instances considéré de chaque service et la présence des états hybrides : état à la fois intermédiaire et final dans un automate. Le second sujet porte sur les systèmes de fermeture et s’intéresse au calcul de l’extension maximale d’un système de fermeture ainsi qu’à l’énumération des clefs candidates d’une base implicative. On donne un algorithme incrémental polynomial qui génère l’extension maximale d’un treillis codé par une relation binaire. Puis, la notion de key-ideal est définie, en prouvant que leur énumération est équivalente à l’énumération des clefs candidates. Ensuite, on donne un algorithme qui permet de générer les key-ideal minimaux en temps incrémental polynomial et les key-ideal non minimaux en délai polynomial. / This thesis investigates complexity and computational issues in two parts. The first concerns an issue related to web services composition problem: Deciding whether the behaviour of a web service can be composed out of an existing repository of web services. This question has been reduced to simulating a finite automata to the product closure of an automata set. We study the complexity of this problem considering two parameters; the number of considered instances in the composition and the presence of the so-called hybrid states (states that are both intermediate and final). The second part concerns closure systems and two related issues; Maximal extension of a closure system : we give an incremental polynomial algorithm that computes a lattice's maximal extension when the input is a binary relation. Candidate keys enumeration : we introduce the notion of key-ideal sets and prove that their enumeration is equivalent to candidate keys enumeration. We then give an efficient algorithm that generates all non-minimal key-ideal sets in a polynomial delay and all minimal ones in incremental polynomial time.