TU Darmstadt / ULB / TUprints

Decentralized establishment of consistent, multi-lateral collaborations

Wombacher, Andreas (2006)
Decentralized establishment of consistent, multi-lateral collaborations.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Dissertation - PDF
diss_wombacher.pdf
Copyright Information: In Copyright.

Download (1MB) | Preview
[img]
Preview
CV - PDF
CurriculumVitae.pdf
Copyright Information: In Copyright.

Download (15kB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Decentralized establishment of consistent, multi-lateral collaborations
Language: English
Referees: Neuhold, Prof.Dr. Erich ; Aberer, Prof.Dr. Karl
Date: 3 February 2006
Place of Publication: Darmstadt
Date of oral examination: 26 August 2005
Abstract:

Multi-lateral collaborations are based on the interaction of several parties. In particular, each party contributes different tasks to the execution of the collaboration. The coordination of these different tasks, that is, the handling of the dependencies between the different tasks, is known as a workflow. When this coordination ensures a successful interaction between the different parties the workflow is called consistent, guaranteeing deadlock-freeness. Currently, a multi-lateral collaboration is set up by people meeting and discussing the collaboration, specifying the workflow (also called the global workflow) and checking its consistency. Afterwards the global workflow is split into parts (also called local workflows) performed by the individual parties. Following this top-down approach, the combination of the local workflow guarantees consistency of the global workflow. Applying a bottom up approach, that is, deriving global properties from local ones is known to be hard in distributed systems. Thus, the issue is to provide an approach which can determine global consistency based on local consistency decisions. Recent technologies such as Service Oriented Architecture (SOA) support decentralized and loosely coupled applications. In particular, parties make the provided functionality available as a service, which is maintained and controlled completely independent of a centralized coordinator. Further, the loose coupling supports the late binding of services, that is, a service requestor may decide at run-time which service provider to use for that particular collaboration. As a consequence of these decentralized decisions and the lack of a centralized coordinator, the top-down approach is not applicable to SOA, but requires a bottom up approach. Deciding consistency of a global workflow in a decentralized way requires additional local information which is provided by the method proposed in this thesis. In particular, information on parameter constraints and execution sequences between local workflows has to be exchanged and propagated through the collaboration to gather sufficient information. It is shown that this propagated information suffices to determine global workflow consistency in a decentralized way. Further, Web Services are used as a concrete technology supporting the SOA paradigm and the theoretical results are applied to this technology as a proof of concept to illustrate the applicability of the approach presented. The approach can be applied to synchronous or asynchronous communication models. While there already exist approaches for asynchronous communication models, there are none available for the synchronous case. Therefore, a formal model for synchronous communication is introduced which is called annotated Finite State Automata. This model extends standard Finite State Automata by annotating states with logical expressions to differentiate between mandatory and optional automata transitions. An optional transition can be illustrated by a party providing the option to receive one of two messages, where the interacting party may use one of the options. Optional transitions represent standard automata semantics. However, a mandatory transition can be illustrated by a party sending either one of two messages, where the receiving party is required to support both options, because supporting only a single option results in a deadlock if the sender selects the other option. This formal model is introduced and discussed in detail for bilateral and multi-lateral collaborations. In particular, the propagation of parameter constraints and execution sequences are defined based on this model and the construction of the corresponding global workflow is introduced. For the asynchronous communication model, Workflow Nets are used as a formal model based on an existing approach to constructing the corresponding global workflow. However, since the computational complexity of Workflow Nets prevents satisfactory application of the propagation definitions, the execution sequences of the Workflow Nets involved are represented as annotated Finite State Automata and thus allow handling of the synchronous and asynchronous communication model based on a single formal model, that is, annotated Finite State Automata. Based on the common formal model, it can be shown that the propagation of parameter constraints and execution sequence constraints result in a fixed point, where further propagation will not change the local workflow any further. Based on this fixed point, it can be shown that if all parties decide locally that the workflow is consistent then the global workflow is also consistent. Therefore, the final consistency decision is based on the consensus of the parties' local consistency decisions. The approach is implemented within the Web Services framework. In particular, a partial mapping of the Web Service process specification language (Business Process Execution Language for Web Services (BPEL)) to annotated Finite State Automata is provided. Based on this mapping an extension of standard service discovery, considering process descriptions in terms of BPEL, is implemented. Further, the relevant operations for annotated Finite State Automata are implemented. Finally, in order to be able to apply the approach presented, a decentralized collaboration establishment approach is introduced.

Alternative Abstract:
Alternative AbstractLanguage

Multi-laterale Kollaborationen basieren auf Interaktionen zwischen mehreren Parteien. Im Besonderen trägt jede Partei unterschiedliche Funktionen zu der Ausführung der Kollaboration bei. Die Koordination dieser unterschiedlichen Funktionen ist auch unter dem Begriff Workflow bekannt. Falls die Koordination eine erfolgreiche Interaktion zwischen den verschiedenen Parteien gewährleistet, dann bezeichnet man einen Workflow als konsistent, d.h. eine blockadenfreie Ausführung des Workflows ist garantiert. Heutzutage wird eine multi-laterale Kollaboration durch Personen etabliert, die sich treffen, die Kollaboration besprechen, den Workflow spezifizieren (dieser wird auch als globaler Workflow bezeichnet) und ihn auf Konsistenz hin prüfen. Nach dieser Prüfung wird der globale Workflow in Teile - so genannte lokale Workflows - aufgeteilt, die dann von den einzelnen Parteien ausgeführt werden. Dieser top-down Ansatz gewährleistet, dass die Kombination der lokalen Workflows die Konsistenz des resultierenden globalen Workflows garantiert. Wendet man einen bottom-up Ansatz an, d.h. leitet man globale Eigenschaften von lokalen ab, so ist dies wesentlich schwerer zu bewerkstelligen, wie man aus dem Bereich der verteilten Systeme her kennt. Daher ist die Herausforderung einen Ansatz bereitzustellen, der globale Konsistenz auf Basis lokaler Konsistenzentscheidungen herleiten kann. Aktuelle Technologien wie z.B. Service Orientierte Architekturen (SOA) unterstützen dezentralisierte und lose gekoppelte Anwendungen. Im Besonderen machen Parteien ihre bereitgestellten Funktionen als Services verfügbar, die unabhängig von einem zentralisierten Koordinator gewartet und kontrolliert werden. Weiterhin unterstützt die lose Kopplung das späte Binden von Services, d.h. die Partei, die einen Service anfordert, kann zur Laufzeit entscheiden, welchen Serviceanbieter sie für eine spezielle Kollaboration nutzten will. Auf Grund dieser dezentralen Entscheidungen und des fehlenden zentralen Koordinators ist der top-down Ansatz im Umfeld von SOA nicht anwendbar und erfordert daher den bottom-up Ansatz. Die Entscheidung über die Konsistenz eines globalen Workflows in einer dezentralisierten Weise erfordert zusätzliche lokale Informationen, die durch die vorgestellte Methode verfügbar werden. Im Besonderen werden Informationen über Parameter-Einschränkungen und Ausführungssequenzen zwischen lokalen Parteien ausgetauscht und durch die Kollaboration propagiert. Es wird gezeigt, dass die propagierten Informationen ausreichen, um globale Workflow Konsistenz in einer dezentralisierten Weise herzuleiten. Weiterhin wird die Methode auf Web Services, als eine konkrete Technologie basierend auf SOA, angewendet und die Methode prototypisch implementiert. Die Implementierung dient als "Proof of Concept" und illustriert die Anwendbarkeit des vorgeschlagenen Ansatzes. Der Ansatz kann auf synchrone und asynchrone Kommunikationsmodelle angewendet werden. Es existieren Ansätze für asynchrone Kommunikationsmodelle, wogegen es keine Ansätze für synchrone Kommunikationsmodelle gibt. Daher wird ein formales Model für synchrone Kommunikation eingeführt, das als annotierte Finite State Automata bezeichnet wird. Dieses Model erweitert Standard Finite State Automata durch die Annotation von Zuständen mit logischen Ausdrücken, um zwischen optionalen und verbindlichen Automaten Übergängen zu unterscheiden. Ein optionaler Übergang kann durch eine Partei veranschaulicht werden, die anbietet eine von zwei Nachrichten zu empfangen, wobei die interagierende Partei eine dieser Optionen nutzen kann. Optionale Übergänge repräsentieren dabei Standard Automaten Semantik. Ein verbindlicher Übergang kann durch eine Partei veranschaulicht werden, die eine von zwei Nachrichten senden kann, wobei die empfangende Partei verpflichtet ist beide Optionen zu unterstützen. Unterstützt die empfangende Partei nur eine Option, so führt dies zu einer Blockade falls der Sender die falsche Option sendet. Das formale Model der annotierten Fintie State Automata wird eingeführt und sowohl bilaterale als auch multi-laterale Kollaborationen werden diskutiert. Insbesondere wird die Propagierung von Parameter-Einschränkungen und Ausführungssequenzen definiert und die Konstruktion des zugehörigen globalen Workflows eingeführt. Im asynchronen Kommunikationsmodel werden Workflow Nets als formales Model verwendet, da auf einen existierenden Ansatz zur Konstruktion des globalen Workflows zurückgegriffen werden kann. Da jedoch die Workflow Net Operationen eine hohe Komplexität haben, die eine erfolgreiche Anwendung der Propagierung verhindert, werden die Ausführungssequenzen der Workflow Nets als annotierte Finite State Automata repräsentiert. Auf diese Weise ist eine homogene Handhabung des synchronen und asynchronen Kommunikationsmodels in einer formalen Repräsentation, d.h. annotierte Finite State Automata, möglich. Basierend auf diesem gemeinsamen formalen Model wird gezeigt, dass die Propagierung von Parameter-Einschränkungen und Ausführungssequenzen in einem Fixpunkt resultiert, in dem eine weitere Propagierung keine Änderungen an lokalen Workflows herbeiführt. Basierend auf diesem Fixpunkt wird gezeigt, dass die lokale Konsistenzentscheidung aller Parteien die Konsistenz des korrespondierenden globalen Workflows garantiert. Daher kann die Konsistenzentscheidung nun auf dem Konsens der lokalen Konsistenzentscheidung der einzelnen Parteien erfolgen. Der Ansatz wurde innerhalb des Web Services Umgebung implementiert. Insbesondere wurde eine partielle Abbildung der Web Service Prozessspezifikationssprache (Business Process Execution Language for Web Services (BPEL)) auf annotatierete Finite State Automata realisiert. Basierend auf dieser Abbildung wurde ein erweitertes Service Discovery entwickelt, das Prozessbeschreibungen (lokale Workflows) in BPEL Notation berücksichtigt. Weiterhin wurden die relevanten Operationen für annotierte Finite State Automata implementiert. Letztlich wurde eine dezentralisierte Erstellung von Kollaborationen eingeführt, um die Anwendbarkeit des vorgestellten Ansatzes zu zeigen.

German
URN: urn:nbn:de:tuda-tuprints-6529
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 17 Oct 2008 09:22
Last Modified: 08 Jul 2020 22:54
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/652
PPN:
Export:
Actions (login required)
View Item View Item