Publikationen zum Fachbereich Matching

Publikationen in Zeitschriften und Büchern

• Christian Stahl and Karsten Wolf. Deciding Service Composition and Substitutability Using Extended Operating Guidelines. Data Knowl. Eng., 68(9): 819-833, 2009.

  Abstract: We study the correct interaction between services using the following notion for correctness: there is no deadlock in the interaction of the services, and a given set of activities is not dead, that is, each activity in this set is executed in at least one run. The second condition has not been studied before. An operating guideline of a service P is an operational characterization of all deadlock-free interacting partners of P. In this paper, we present an extension of the concept of an operating guideline to characterize all correctly interacting partners of a service P. This extension can be used for answering at least the following two questions. First, given a service R, does R interact correctly with P? Second, given a service P', can P be substituted by P', that is, is every correctly interacting partner of P a correctly interacting partner of P', too?

  

• Niels Lohmann, Peter Massuthe, Christian Stahl, and Daniela Weinberg. Analyzing Interacting WS-BPEL Processes Using Flexible Model Generation. Data Knowl. Eng., 64(1): 38-54, January 2008.

  Abstract: We address the problem of analyzing the interaction between WS-BPEL processes. We present a technology chain that starts out with a WS-BPEL process and translates it into a Petri net model. On the model we decide controllability of the process (the existence of a partner process, such that both can interact properly) and compute its operating guideline (a characterization of all properly interacting partner processes). To manage processes of realistic size, we present a concept of a \emph{flexible model generation} which allows the generation of compact Petri net models. A case study demonstrates the value of this technology chain.

  

• Peter Massuthe and Karsten Wolf. An Algorithm for Matching Non-deterministic Services with Operating Guidelines. International Journal of Business Process Integration and Management (IJBPIM), 2(2): 81-90, 2007.

  Abstract: Interorganisational cooperation is more and more organised by the paradigm of services. Service-Oriented Architectures (SOA) provide a general framework for service interaction. SOA describe three roles of services, the service provider, the service requester and the service broker, together with the three operations publish, find and bind. We provide a formal method based on non-deterministic automata to model services and their interaction. In this paper, we restrict ourselves to finite and acyclic automata. We suggest operating guidelines as a convenient and intuitive artefact to realise the publish operation. In our approach, the find operation reduces to a matching problem between the requesters service and the published operating guidelines. If matching services are actually bound together, our approach guarantees deadlock-free interaction. In this paper, matching of deterministic as well as non-deterministic automata with operating guidelines is presented.

  

• Peter Massuthe and Karsten Wolf. Operating Guidelines for Services. Petri Net Newsletter, 70: 9-14, April 2006.

  Abstract: In the service-oriented architecture (SOA), we distinguish three roles of service owners: service providers, service requesters, and service brokers, and the three standard operations publish, find, and bind. We provide a formal method based on Petri nets to model services. We suggest operating guidelines as a convenient and intuitive artifact to realize publish. Then, the find operation reduces to a matching problem between the requester's service and the operating guideline.

  

• Peter Massuthe, Wolfgang Reisig, and Karsten Schmidt. An Operating Guideline Approach to the SOA. Annals of Mathematics, Computing & Teleinformatics, 1(3): 35-43, 2005.

  Abstract: Interorganizational cooperation is more andmore organized by the paradigm of services. The serviceoriented architecture (SOA) provides a general framework for service interaction. It describes three roles, service provider, service requester, and service broker, together with the three operations publish, find, and bind. We provide a formal method based on Petri nets to model services and their cooperation. We characterize well-behaving pairs of requester's and provider's services and suggest operating guidelines as a convenient and intuitive artifact to realize publish. In our approach, the find operation reduces to a matching problem between the requester's service and the operating guideline. Binding of a requester's and a provider's service is therefore guaranteed to result in a well-behaving cooperating service. At this time, the approach is limited to acyclic Petri nets.

  

Konferenzbeiträge und Beiträge auf Workshops

• Karsten Wolf, Christian Stahl, Janine Ott, and Robert Danitz. Verifying Livelock Freedom in an SOA Scenario. In Stephen Edwards and Walter Vogler, editors, Proceedings of the Ninth International Conference on Application of Concurrency to System Design (ACSD'09), Augsburg, Germany, July 2009. IEEE Computer Society.

  Abstract: In a service-oriented architecture (SOA), a service broker assigns a previously published service (stored in a service registry) to a service requester. It is desirable for the composition of the requesting and the assigned service to interact properly. While proper interaction is often reduced to deadlock freedom of the composed system, we additionally consider livelock freedom as a desirable property for the interaction of services. In principle, deadlock- and livelock freedom can be verified by inspecting the state space of the composition of (public views of) the involved services. The contribution of this paper is to propose a methodology to build that state space from pre-computed fragments which are computed upon publishing a service. That way, we shift computation time from the time critical request phase of service brokerage to the less critical publish phase. Interestingly, our setting enables state space reduction methods that are intrinsically different from traditional state space reductions.

  

• Wil M. P. van der Aalst, Arjan J. Mooij, Christian Stahl, and Karsten Wolf. Service Interaction: Patterns, Formalization, and Analysis. In Marco Bernardo, Luca Padovani, and Gianluigi Zavattaro, editors, Formal Methods for Web Services (SFM 2009), volume 5569, pages 42--88, April 2009. Springer-Verlag.

  Abstract: As systems become more service oriented and processes increasingly cross organizational boundaries, interaction becomes more important. New technologies support the development of such systems. However, the paradigm shift towards service orientation, requires a fundamentally different way of looking at processes. This survey aims to provide some foundational notions related to service interaction. A set of service interaction patterns is given to illustrate the challenges in this domain. Moreover, key results are given for three of these challenges: (1) How to expose a service?, (2) How to replace and refine services?, and (3) How to generate service adapters? These challenges will be addressed in a Petri net setting. However, the results extend to other languages used in this domain.

  

• Chistian Stahl and Karsten Wolf. An Approach to Tackle Livelock-Freedom in SOA. In Niels Lohmann and Karsten Wolf, editors, Proceedings of the 15th German Workshop on Algorithms and Tools for Petri Nets, AWPN 2008, Rostock, Germany, September 26--27, 2008, volume 380 of CEUR Workshop Proceedings, pages 69-74, September 2008. CEUR-WS.org.

  Abstract: We calculate a fixed finite set of state space fragments for a service P, where each fragment carries a part of the whole behavior of P. By composing these fragments according to the behavior of a service R we build the state space of their composition P \oplus R which can be checked for deadlocks and livelocks. We show that this approach is applicable to realize a ``find'' request by a service $R$ with a provided service P in SOA.

  

• Christian Stahl and Karsten Wolf. Covering Places and Transitions in Open Nets. In Marlon Dumas and Manfred Reichert, editors, Business Process Management, 6th International Conference, BPM 2008, Milan, Italy, September 1-4, 2008, Proceedings, volume 5240 of Lecture Notes in Computer Science, pages 116-131, September 2008. Springer-Verlag.

  Abstract: We present a finite representation of all services M where the composition with a given service N is deadlock-free, and a given set of activities of N can be covered (i.e. is not dead). Our representation is an extension of the existing notion of an operating guideline which only cared about deadlock freedom. We further present an algorithm to decide whether a service M matches with the extended operating guideline of N.

  

• Kathrin Kaschner, Peter Massuthe, and Karsten Wolf. Symbolische Repräsentation von Bedienungsanleitungen für Services. In Daniel Moldt, editor, 13. Workshop Algorithmen und Werkzeuge für Petrinetze (AWPN 2006), Proceedings, pages 54-61, September 2006. Universität Hamburg. Note: In German.

• Niels Lohmann, Peter Massuthe, Christian Stahl, and Daniela Weinberg. Analyzing Interacting BPEL Processes. In Schahram Dustdar, José Luiz Fiadeiro, and Amit Sheth, editors, Business Process Management, 4th International Conference, BPM 2006, Vienna, Austria, September 5-7, 2006, Proceedings, volume 4102 of Lecture Notes in Computer Science, pages 17-32, September 2006. Springer-Verlag.

  Abstract: This paper addresses the problem of analyzing theinteraction between BPEL processes. We present a technology chain that starts out with a BPEL process and transforms it into a Petri net model. On the model we decide controllability of the process (the existence of a partner process, such that both can interact properly) and compute its operating guideline (a characterization of all properly interacting partner processes). A case study demonstrates the value of this technology chain.

  

• Peter Massuthe and Karsten Wolf. An Algorithm for Matching Nondeterministic Services with Operating Guidelines. In Frank Leymann, Wolfgang Reisig, Satish R. Thatte, and Wil M. P. van der Aalst, editors, The Role of Business Processes in Service Oriented Architectures, number 06291 of Dagstuhl Seminar Proceedings, 2006. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany.

  Abstract: Interorganizational cooperation is more and more organized by the paradigm of services. Service-oriented architectures (SOA) provide a general framework for service interaction. SOA describe three roles of services, the service provider, the service requester, and the service broker, together with the three operations publish, find, and bind. We provide a formal method based on nondeterministic automata to model services and their interaction. In this paper, we restrict ourselves to finite and acyclic automata. We suggest operating guidelines as a convenient and intuitive artifact to realize the publish operation. In our approach, the find operation reduces to a matching problem between the requester's service and the published operating guidelines. If matching services are actually bound together, our approach guarantees deadlock-free communication. In this paper, matching of deterministic as well as nondeterministic automata with operating guidelines is presented.

  

• Axel Martens. Process Oriented Discovery of Business Partners. In Proceedings of 7th Intl. Conference on Enterprise Information Systems (ICEIS'05), Vol 3, Miami, Florida, May 2005. INSTICC.

  Abstract: Emerging technologies and industrial standards in the field of Web services enable a much faster and easier cooperation of distributed partners. With the increasing number of enterprises that offer specific functionality in terms of Web services, discovery of matching partners becomes a serious issue. At the moment, discovery of Web services generally is based on meta-information (e. g. name, business category) and some technical aspects (e. g. interface, protocols). But, this selection might be to coarse grained for dynamic application integration, and there is much more information available. This paper describes a method to discover business partners based on the comparison of their behavior ? specified in terms of their published Web service process models.

  

• Peter Massuthe and Karsten Schmidt. Operating Guidelines for Services. In Karsten Schmidt and Christian Stahl, editors, 12. Workshop Algorithmen und Werkzeuge für Petrinetze (AWPN 2005), Proceedings, pages 78-83, September 2005. Humboldt-Universität zu Berlin.

  Abstract: In the service-oriented architecture (SOA), we distinguish three roles of service owners:service providers, service requesters, and service brokers, and the three standard operations publish, find, and bind. We provide a formal method based on Petri nets to model services. We suggest operating guidelines as a convenient and intuitive artifact to realize publish. Then, the find operation reduces to a matching problem between the requester?s service and the operating guideline.

  

Technische Berichte

• Wolfgang Reisig. The Universal Net Composition Operator. Forschungsbericht, Humboldt-Universität zu Berlin, January 2009.

  Abstract: Petri nets are frequently composed of given nets. Literature suggests a lot of different composition operators, for different purposes and different classes of Petri nets. Formal definitions are frequently surprisingly technical, not matching the intuitively very elegant composition of Petri nets in the framework of their graphical representation. This paper suggests the universal net composition operator. This operator allows to specify any specific composition variant by very simple means, leaving all technical details to the operator, where they are treated once and for all. General properties of composition, in particular associativity, are inherited by all instantiations of the operator. We show the practical advantage of the universal composition operator by means of a lot of examples from various areas of Petri nets.

  

• Niels Lohmann, Peter Massuthe, and Karsten Wolf. Operating Guidelines for Finite-State Services. Informatik-Berichte 210, Humboldt-Universität zu Berlin, December 2006.

  Abstract: We introduce the concept of an operating guideline for an arbitrary finite-state service P, extending the work of [1, 2] which was restricted to acyclic services. An operating guideline gives complete information about how to correctly (in this paper: deadlock-free) communicate with P. It can further be executed or used for service discovery. An operating guideline for P is a particular service S that is enriched with annotations. S communicates deadlock-free with P and is able to simulate every other service that communicates deadlock-free with P. The attached annotations give complete information about whether or not a simulated service is deadlock-free, too.

  

• Peter Massuthe and Karsten Wolf. An Algorithm for Matching Nondeterministic Services with Operating Guidelines. Informatik-Berichte 202, Humboldt-Universität zu Berlin, 2006.

  Abstract: Interorganizational cooperation is more and more organizedby the paradigm of services. Service-oriented architectures (SOA) provide a general framework for service interaction. SOA describe three roles of services, the service provider, the service requester, and the service broker, together with the three operations publish, find, and bind. We provide a formal method based on nondeterministic automata to model services and their interaction. In this paper, we restrict ourselves to finite and acyclic automata. We suggest operating guidelines as a convenient and intuitive artifact to realize the publish operation. In our approach, the find operation reduces to a matching problem between the requester's service and the published operating guidelines. If matching services are actually bound together, our approach guarantees deadlockfree communication. In this paper, matching of deterministic as well as nondeterministic automata with operating guidelines is presented.

  

• Peter Massuthe, Wolfgang Reisig, and Karsten Schmidt. An Operating Guideline Approach to the SOA. Informatik-Berichte 191, Humboldt-Universität zu Berlin, 2005.

  Abstract: Interorganizational cooperation is more and more organized by the paradigm of services. The service-oriented architecture (SOA) provides a general framework for service interaction. It describes three roles, service provider, service requester, and service broker, together with the three operations publish, find, and bind. We provide a formal method based on Petri nets to model services and their cooperation. We characterize well-behaving pairs of requester?s and provider?s services and suggest operating guidelines as a convenient and intuitive artifact to realize publish. Then, the find operation reduces to a matching problem between the requester?s service and the operating guideline. Binding of a requester?s and a provider?s service is therefore guaranteed to result in a well-behaving cooperating service.

  

• Peter Massuthe and Karsten Schmidt. Matching Nondeterministic Services with Operating Guidelines. Informatik-Berichte 193, Humboldt-Universität zu Berlin, June 2005.

  Abstract: Abstract Interorganizational cooperation is more and more organizedby the paradigm of services. The service-oriented architecture (SOA) provides a general framework for service interaction. It describes three roles, service provider, service requester, and service broker, together with the operations publish, find, and bind. We provide a formal method based on nondeterministic automata to model services and their interaction. We suggest operating guidelines as a convenient and intuitive artifact to realize publish. In our approach, the find operation reduces to a matching problem between the requester?s service and operating guidelines. In this paper, matching of deterministic as well as nondeterministic automata with operating guidelines is presented.

  

Studien- und Diplomarbeiten

• Kathrin Kaschner. BDD-basiertes Matching von Services. Diplomarbeit, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, March 2006.

  Abstract: Moderne Software-Systeme werden zunehmend nach dem Paradigma der ServiceorientiertenArchitektur (SOA) aus unabhängigen Services zusammengesetzt, die definierte Funktionen zur Verfügung stellen und Nachrichten miteinander austauschen. Eine Möglichkeit zur Gewährleistung der reibungslosen Kommunikation besteht in der Bereitstellung einer Bedienungsanleitung durch den Service Provider, mit der der Service Broker anhand eines Prüfverfahrens - dem Matching - entscheiden kann, ob der Service eines Service Requesters zu dem angebotenen Service passt. Für die praktische Anwendung müssen Bedienungsanleitungen in geeigneter Weise kodiert werden. In der vorliegenden Arbeit werden dazu Binäre Entscheidungsdiagramme (BDDs) genutzt. Für das Matching wird der Service des Service Requesters durch einen Serviceautomaten modelliert, der seinerseits ebenfalls in eine BDD-Darstellung überführt wird. Darauf aufbauend wird schließlich ein Matching-Algorithmus entwickelt und seine Korrektheit bewiesen. Die Effizienz der Kodierung durch BDDs und die Funktionsweise des BDD-basierten Matching-Algorithmus wird an Beispielen gezeigt.

  

zurück zur Übersicht