Correcting Deadlocking Service Choreographies Using a Simulation-based Graph Edit Distance

Niels Lohmann. Correcting deadlocking service choreographies using a simulation-based graph edit distance. In Marlon Dumas and Manfred Reichert, editors, Business Process Management, 6th International Conference, BPM 2008, Milan, Italy, September 1–4, 2008, Proceedings, Lecture Notes in Computer Science. Springer-Verlag, September 2008.


  • paper by Niels Lohmann

  • to be presented at BPM 2008 by Niels Lohmann


Many work has been conducted to analyze service choreographies to assert manyfold correctness criteria. While errors can be detected automatically, the correction of defective services is usually done manually. This paper introduces a graph-based approach to calculate the minimal edit distance between a given defective service and synthesized correct services. This edit distance helps to automatically fix found errors while keeping the rest of the service untouched. A prototypic implementation shows that the approach is applicable to real-life services.

Key words: Choreographies, graph correction, correction of services, verification of services, service automata, operating guidelines, BPEL


You can download the slides of the talk.

Case Study/Experimental Results

The presented experiments have been conducted with Rachel Version 1.00 using the following command:

rachel -a -o service.og -m matching

where is a service automaton and service.og is an operating guideline. You can download the example files used in the paper.

On an Apple MacBook (Intel Core 2 Duo, 2.16 GHz, 2 GB RAM, Mac OS X 10.5.2, g++ 4.0.1), we came to the following results:

Referenced Tools

  • Rachel (to calculate the edit distance between a service automaton and an operating guideline)

  • Fiona (to calculate the operating guideline for a service, and to synthesize a partner for a service)



Author = {Niels Lohmann},

Booktitle = {Business Process Management, 6th International Conference, BPM 2008, Milan, Italy, September 1--4, 2008, Proceedings},

Editor = {Marlon Dumas and Manfred Reichert},

Month = sep, Pages = {132-147}

Publisher = {Springer-Verlag},

Series = {Lecture Notes in Computer Science},

Title = {Correcting Deadlocking Service Choreographies Using a Simulation-Based Graph Edit Distance},

Volume = {5240},

Year = {2008}}