• GANG XUE School of Software, Yunnan University, Kunming, Yunnan, China
  • JING LIU School of Software, Yunnan University, Kunming, Yunnan, China
  • LIWEN WU School of Software, Yunnan University, Kunming, Yunnan, China
  • SHAOWEN YAO School of Software, Yunnan University, Kunming, Yunnan, China


process partitioning, graph transformation based algorithm, typed directed graphs


Web service is an important technology for constructing distributed applications. In order to provide more complex functionalities, services can be reused by applying service composition. A service composition can be designed and implemented through a centralization or decentralization strategy. When observing the decentralized service composition, several researchers found out that this kind of compositions has its own advantages. These findings promote the development of approaches for designing, implementing and applying decentralized service compositions. Process partitioning is a topic about dividing a process into a collection of small parts. The technique is applicable to partitioning a process in a centralized service composition, and the result can provide support to constructing a decentralized service composition. This paper presents a technique of process partitioning. The technique can be used for constructing decentralized service compositions, and it provides a graph transformation based approach to reorganizing a process which is represented as a process structure graph. Compared to existing approaches, the technique can partition well-structured and unstructured processes. Some issues about decentralized service compositions and performance tests of service compositions are discussed in this paper. Experimental results show that, when compared with the centralized service composition, the decentralized service composition can have lower average response time and higher throughput in runtime environment.


Download data is not yet available.


Papazoglou, M. P., Traverso, P., Dustdar, S. and Leymann, F., Service-Oriented Computing: A

Research Roadmap. International Journal of Cooperative Information Systems, 2008, 17 (02). 223-

Dragoni, N., Giallorenzo, S., Lafuente, A. L., et al, Microservices: yesterday, today, and tomorrow.

eprint arxiv: 1606.04036, 2016. Available online: https://arxiv.org/abs/1606.04036.

Nadareishvili, I., Mitra, R., McLarty, M., and Amundsen, M., Microservice Architecture: Aligning

Principles, Practices, and Culture. O'Reilly Media, 2016.

Peltz, C., Web services orchestration and choreography. IEEE Computer, 2003, 36(10). 46–52.

OASIS Standard, Web Services Business Process Execution Language Version 2.0. 2007. Available

online: https://docs.oasis-open.org/wsbpel/2.0/wsbpel-v2.0.html.

W3C Standard, Web Services Choreography Description Language Version 1.0. 2005. Available

online: https://www.w3.org/TR/ws-cdl-10/.

Barker, A., Besana, P., Robertson, D. and Weissman, J. B., The Benefits of Service Choreography

for Data-Intensive Computing. in Proceedings of the 7th international workshop on Challenges of

large applications in distributed environments (CLADE '09), (Garching, Germany, June 09 - 10,

. 1-10.

Binder, W., Constantinescu, I. and Faltings, B., Decentralized Orchestration of Composite Web

Services. in Proceedings of 2006 IEEE International Conference on Web Services (ICWS '06),

(Chicago, Illinois, USA, September 2006). 869-876.

Nanda, M. G., Chandra, S. and Sarkar, V., Decentralizing Execution of Composite Web Services. in

Proceedings of the 19th Annual ACM SIGPLAN Conference on Object-Oriented Programming,

Systems, Languages, and Applications (OOPSLA '04), (Vancouver, BC, Canada, October 24-28,

. 170-187.

Atluri, V., Chun, S. A., Mukkamala, R. and Mazzoleni, P., A decentralized execution model for interorganizational

workflows. Distributed and Parallel Databases, 2007, 22 (1). 55 - 83.

Muth, P., Wodtke, D., Weissenfels, J., Dittrich, A. K. and Weikum, G., From Centralized Workflow

Specification to Distributed Workflow Execution. Journal of Intelligent Information Systems -Special issue on workflow management systems, 1998, 10 (2). 159-184.

Polyvyanyy, A., Structuring Process Models. PhD thesis, University of Potsdam, Germany, 2012.

Kiepuszewski, B., ter Hofstede, A. H. M. and Bussler, C., On structured workflow modelling. in

Proceedings of the 12th International Conference on Advanced Information Systems Engineering

(CAiSE '00). 431–445.

Ehrig, H., Ehrig, K., Prange, U. and Taentzer, G., Fundamentals of Algebraic Graph Transformation

(Monographs in Theoretical Computer Science. An EATCS Series). Springer, 2010.

Spivak, D. I., Category Theories for Sciences, 1st edition. The MIT press, 2014.

Löwe, M., Algebraic approach to single-pushout graph transformation. Theoretical Computer

Science, 1993, 109 (1-2). 181-224.

Müller, J., On Termination of Single-Pushout Graph Rewriting. Technical report 96-38, Technical

University of Berlin, 1996. Available online: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

Johnson, R., Pearson, D. and Pingali, K., The program structure tree: computing control regions in

linear time. in Proceedings of the ACM SIGPLAN 1994 conference on Programming Language

Design and Implementation (PLDI '94), (Orlando, Florida, USA, June 20 - 24, 1994). 171-185.

Flask-RESTful (open source software). Available online: https://flask-restful.readthedocs.io/en/


Flask (open source software). Available online: http://flask.pocoo.org/.

Apapche JMeter (open source software). Available online: https://jmeter.apache.org/.

Fdhila, W., Yildiz, U. and Godart, C., A flexible approach for automatic process decentralization

using dependency tables. in Proceedings of IEEE 7th International Conference on Web Services

(ICWS 2009), (Los Angeles, United States, 2009). 847-855.

Androutsopoulos, K., Clark, D., Harman, M., Krinke, J. and Tratt, L., State-based model slicing: a

survey. ACM Computing surveys, 2013, 45 (4). Paper No. 53.

Ferrante, J., Ottenstein, K. J. and Warren, J. D., The program dependence graph and its use in

optimization. ACM Transactions on Programming Language and Systems, 1987, 9 (3). 319-349.

Fdhila, W., Dumas, M., Godart, C. and Garciabanuelos, L., Heuristics for composite Web service

decentralization. Software and Systems Modeling, 2014, 13 (2). 599-619.