A controller synthesis framework for automated service composition. (English) Zbl 1441.93082
Summary: Nowadays, Web services allow interoperability among distributed software applications deployed on different platforms and architectures which in effect plays a major role in electronic businesses. Web services allow organizations to carry out certain business activities automatically and in a distributed fashion. However, in some circumstances, a single service is not able to perform a certain task and it becomes imperative to compose two or more services in order to complete it. Thus, a key research challenge in this field is the problem of automatic service composition. Several approaches exist that tackle the problem of automatic service composition, however, the task of generating provably correct Web service compositions still remains a challenging and complex task. In this paper, we develop a formal framework for modeling Web service compositions based on supervisory control theory (SCT) of discrete-event systems. We model services that exchange messages and exhibit nondeterministic behaviours. The objective is to synthesize a supervisor which interacts with a given set of Web services through messages to guarantee that a given specification is satisfied. A key novelty of this work is the application of control theory to service-oriented computing and the incorporation of run-time input into the supervisor generation process. First, we describe a novel supervisory control framework for automated composition of Web services. The framework employs labelled transition systems equipped with guards and data variables to model Web services and provides a technique to synthesize a controller. We model the interactions of services asynchronously and we use the guards and data variables to allow us to express certain preconditions which are then propagated from the system requirements through the overall composite service. Second, we develop a set of algorithms to generate a controller satisfying a given functional requirement also specified as a labelled transition system equipped with guards and data variables. Besides the standard disabling and enabling of events, the generated controller in our framework has the ability to enforce certain events based on run-time information to drive the system towards its goal. In addition, the controller is able to impose restrictions on the kind of data that can be sent or received by services. This includes the automatic generation of stronger guards or preconditions which impose restrictions on which path to take during execution. Lastly, we state a theorem capturing the existence of a controller and provide a proof to demonstrate the correctness of the proposed approach.
MSC:
| 93B50 | Synthesis problems |
| 93C65 | Discrete event control/observation systems |
| 93B05 | Controllability |
| 93-08 | Computational methods for problems pertaining to systems and control theory |
Keywords:
automatic service composition; supervisory control theory; controller synthesis; web services; discrete event systems; labelled transition systemsReferences:
| [1] | Abdullah A, Xining l (2013) An efficient I/O based clustering HTN in web service composition. In: International conference on computing, management and telecommunications (ComManTel), Ho Chi Minh City, pp 252-257 |
| [2] | Alves A, Arkin A, Askary S, Barreto C, Bloch B, Curbera F, Ford M, Goland Y, Guizar A, Kartha N, Kevin CL, Khalaf R, König D, Marin M, Mehta V, Thatte S, Rijn D, Yendluri P, Yiu A (2007) Web services business process execution language version 2.0, OASIS Standard. http://docs.oasis-open.org/wsbpel/2.0/OS/wsbpel-v2.0-OS.html. [Online; accessed 10 Mar 2017] |
| [3] | Andrews T, Curbera F, Dholakia H, Goland Y, Klein J, Leymann F, Liu K, Roller D, Smith D, Thatte S, Trickovic I, Weerawarana S (2003) Business process execution language for web services version 1.1. http://msdn.microsoft.com/en-us/library/ee251594(v=bts.10).aspx#feedback. [Online; accessed 10 Mar 2017] |
| [4] | Atampore F (2017) Towards provably correct services: automated service composition via supervisory control synthesis. Ph.D. thesis, School of Computing, Queen’s University, Ontario |
| [5] | Atampore F, Dingel J, Rudie K (2016) A controller synthesis framework for automated service composition. Tech. Rep. 2016-630, School of Computing, Queen’s University, Kingston, Ontario, Canada. http://sites.cs.queensu.ca/tr/ · Zbl 1441.93082 |
| [6] | Auer, A.; Dingel, J.; Rudie, K., Concurrency control generation for dynamic threads using discrete-event systems, Sci Comput Program, 82, 22-43 (2014) · doi:10.1016/j.scico.2013.01.007 |
| [7] | Balbiani P, Cheikh F, Feuillade G (2008) Composition of interactive web services based on controller synthesis. In: IEEE Congress on services - Part I. IEEE Computer Society, pp 521-528 |
| [8] | Bartalos, P.; Bieliková, M., Automatic dynamic web service composition: a survey and problem formalization, Comput Inform, 30, 4, 793-827 (2011) |
| [9] | Berardi D, Calvanese D, De Giacomo G, Hull R, Lenzerini M, Mecella M (2005a) Modeling data & processes for service specifications in Colombo. In: Proceedings of the open interop workshop on enterprise modeling and ontologies for interoperability (EMOI-INTEROP’05) co-located with CAiSE’05 conference. Portugal |
| [10] | Berardi D, Calvanese D, De Giacomo G, Hull R, Mecella M (2005b) Automatic composition of web services in Colombo. In: Proceedings of the thirteenth Italian symposium on advanced database systems, (SEBD). Brixen-Bressanone (near Bozen-Bolzano), Italy, pp 8-15 |
| [11] | Berardi, Daniela; Calvanese, Diego; De Giacomo, Giuseppe; Lenzerini, Maurizio; Mecella, Massimo, AUTOMATIC SERVICE COMPOSITION BASED ON BEHAVIORAL DESCRIPTIONS, International Journal of Cooperative Information Systems, 14, 4, 333-376 (2005) · doi:10.1142/S0218843005001201 |
| [12] | Berardi, D.; Cheikh, F.; Giuseppe, Gd; Patrizi, F., Automatic service composition via simulation, Int J Found Comput Sci, 19, 2, 429-451 (2008) · Zbl 1155.68014 · doi:10.1142/S0129054108005759 |
| [13] | Bertoli, P.; Pistore, M.; Traverso, P., Automated composition of web services via planning in asynchronous domains, Artif Intell: Int J, 174, 3-4, 316-361 (2010) · doi:10.1016/j.artint.2009.12.002 |
| [14] | Brand, D.; Zafiropulo, P., On communicating finite-state machines, J ACM, 30, 2, 323-342 (1983) · Zbl 0512.68039 · doi:10.1145/322374.322380 |
| [15] | Bucchiarone, Antonio; De Sanctis, Martina; Pistore, Marco, Domain Objects for Dynamic and Incremental Service Composition, Advanced Information Systems Engineering, 62-80 (2014), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg |
| [16] | Cassandras, C.; Lafortune, S., Introduction to discrete-event systems (2008), US: Springer, US · Zbl 1165.93001 |
| [17] | Christensen E, Curbera F, Meredith G, Weerawarana S (2001) Web services description language (WSDL), Version 1.1. http://www.w3.org/TR/wsdl. [Online; accessed 6-Jan-2017] |
| [18] | Crasso, M.; Rodríguez, Jm; Zunino, A.; Campo, M., Revising WSDL documents: why and how, Internet Comput IEEE, 14, 5, 48-56 (2010) · doi:10.1109/MIC.2010.81 |
| [19] | Diekmann R, Weidemann D (2013) Event enforcement in the context of the supervisory control theory, Miȩdzyzdroje, Poland |
| [20] | Domain WUW (2017) XML schema. https://www.w3.org/XML/Schema. [Online; Accessed 20 Aug 2017] |
| [21] | Dragert C, Dingel J, Rudie K (2008) Generation of concurrency control code using discrete-event systems theory. In: Proceedings of the 16th ACM international symposium on foundations of software engineering (SIGSOFT), vol FSE-16. ACM, New York, pp 146-157 |
| [22] | Erl, T., Service-oriented architecture: a field guide to integrating XML and web services (2004), New Jersey: Prentice Hall, New Jersey |
| [23] | Fabian M, Lennartson B (1996) On non-deterministic supervisory control. In: Proceedings of the 35th IEEE conference on decision and control, vol 2. IEEE, Kobe, pp 2213-2218 |
| [24] | Fayyad M, Kamel A, Salah A (2015) ACUAI framework for automatic composition of web services using gaming AI. In: Fifth international conference on digital information and communication technology and its applications (DICTAP). Lebanese University, Lebanon, pp 1-6 |
| [25] | Ferrein A, Schiffer S, Lakemeyer G (2009) Embedding fuzzy controllers in golog. In: IEEE International conference on fuzzy systems, FUZZ-IEEE’09. IEEE, Jeju Island, pp 894-899 |
| [26] | Fu X, Bultan T, Suc JJ (2004) Analysis of interacting BPEL web services. In: Proceedings of the 13th international conference on world wide web, (WWW ’04). ACM, New York, pp 621-630, DOI 10.1145/988672.988756, (to appear in print) |
| [27] | Gall TL, Jeannet B, Marchand H (2005) Supervisory control of infinite symbolic systems using abstract interpretation. In: Proceedings of the 44th IEEE conference on decision and control and european control conference (CDC-ECC ’05). IEEE Control Systems Society, Melia Sevilla, pp 30-35 |
| [28] | Gudgin M, Hadley M, Mendelsohn N, Moreau J, Nielsen HF, Karmarkar A, Lafon Y (2007) Simple object access protocol, Version 1.1. http://www.w3.org/TR/soap/. [Online; accessed 20 Aug 2017] |
| [29] | Hatzi, O.; Nikolaidou, M.; Vrakas, D.; Bassiliades, N.; Anagnostopoulos, D.; Vlahavas, I., Semantically aware web service composition through AI planning, Int J Artif Intell Tools, 24, 1, 1450,015 (2015) · doi:10.1142/S0218213014500158 |
| [30] | Hoffmann J, Bertoli P, Helmert M, Pistore M (2014) Message-based web service composition, integrity constraints, and planning under uncertainty: a new connection. Computing Research Repository, arXiv:1401.3470 · Zbl 1184.68072 |
| [31] | Honda K, Tokoro M (1991) An object calculus for asynchronous communication. In: Proceedings of the European conference on object-oriented programming (ECOOP), LNCS 512. Springer, Geneva, pp 133-147 |
| [32] | Jingjing, H.; Wei, Z.; Pesic, M.; Xing, Z.; Dongfeng, Z., Web service composition automation based on timed automata, Appl Math Inf Sci: Int J, 8, 4, 2017-2024 (2014) · doi:10.12785/amis/080460 |
| [33] | Kazhamiakin R, Marconi A, Pistore M, Raik H (2013) Data-flow requirements for dynamic service composition. In: Proceedings of the IEEE 20th international conference on web services. IEEE, Santa Clara, pp 243-250 |
| [34] | Khoumsi A (2013) A simple formal method to synthesize an orchestrator in web service composition. In: American control conference (ACC). USA, Washington, DC, pp 107-112 |
| [35] | Klusch M, Gerber A (2005) Semantic web service composition planning with OWLS-XPlan. In: Proceedings of the 1st international association for the advancement of artificial intelligence (AAAI) fall symposium on agents and the semantic web, Technical Report FS-05-01. AAAI Press, Arlington, pp 55-62 |
| [36] | Kumar, R.; Garg, V.; Marcus, Si, Predicates and predicate transformers for supervisory control of discrete event dynamical systems, IEEE Trans Autom Control, 38, 2, 232-247 (1993) · Zbl 0774.93003 · doi:10.1109/9.250512 |
| [37] | Marconi, A.; Pistore, M.; Traverso, P., Automated composition of web services: the ASTRO approach, IEEE Data Eng Bull Issues, 31, 3, 23-26 (2008) |
| [38] | McIlraith SA, Son TC (2002) Adapting golog for composition of semantic web services. In: Fensel D, Giunchiglia F, McGuinness DL, Williams MA (eds) Proceedings of the eights international conference on principles and knowledge representation and reasoning (KR-02). Morgan Kaufmann, Toulouse, pp 482-496 |
| [39] | Milner, R., Communication and concurrency (1989), Upper Saddle River: Prentice Hall International, Upper Saddle River · Zbl 0683.68008 |
| [40] | Miremadi S, Åkesson K, Lennartson B (2008) Extraction and representation of a supervisor using guards in extended finite automata. In: Proceedings of the 9th international workshop on discrete event systems, (WODES 08). IEEE, Gothenburg, pp 193-199 |
| [41] | Na-Lumpoon P, Fauvet MC, Lbath A (2014) Toward a framework for automated service composition and execution. In: 8th International conference on software, knowledge, information management and applications (SKIMA). Kathmandu, Nepal, pp 1-8 |
| [42] | Nath K, Dhar S, Basishtha S (2014) Web 1.0 to web 3.0 - evolution of the web and its various challenges. In: International conference on optimization, reliabilty, and information technology (ICROIT). IEEE, Faridabad, pp 86-89 |
| [43] | Nau, D.; Au, T.; Ilghami, O.; Kuter, U.; Murdock, Jw; Wu, D.; Yaman, F., SHOP2: an HTN planning system, J Artif Intell Res, 20, 1, 379-404 (2003) · Zbl 1058.68106 · doi:10.1613/jair.1141 |
| [44] | Niewiadomski A, Penczek W, Skaruz J (2014) A hybrid approach to web service composition problem in the planICS framework. In: Irfan A, Muhammad Y, Xavier F, Carme Q (eds) Mobile web information systems, lecture notes in computer science, vol 8640. Springer International Publishing, pp 17-28 |
| [45] | Papazoglou, Mp; Traverso, P.; Dustdar, D.; Leymann, F., Service-oriented computing: state of the art and research challenges, IEEE Comput, 40, 11, 38-45 (2007) · doi:10.1109/MC.2007.400 |
| [46] | Pathak, J.; Basu, S.; Lutz, Rr; Honavar, V., MOSCOE: an approach for composing web services through iterative reformulation of functional specifications, Int J Artif Intell Tools, 17, 1, 109-138 (2008) · doi:10.1142/S0218213008003807 |
| [47] | Peer, Joachim, A POP-Based Replanning Agent for Automatic Web Service Composition, Lecture Notes in Computer Science, 47-61 (2005), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg |
| [48] | Pistore M, Marconi A, Bertoli P, Traverso P (2005a) Automated composition of web services by planning at the knowledge level. In: Proceedings of the nineteenth international joint conference on artificial intelligence. Professional Book Center, Edinburgh, pp 1252-1259 |
| [49] | Pistore M, Traverso P, Bertoli P, Marconi A (2005b) Automated synthesis of composite BPEL4WS web services. In: Proceedings of the IEEE international conference on web services (ICWS’05). IEEE Computer Society, Orlando, pp 293-301 |
| [50] | Portchelvi, V.; Venkatesan, Vp, A goal-directed orchestration approach for agile service composition, Int J Inf Technol Comput Sci (IJITCS), 7, 3, 60-67 (2015) |
| [51] | Raik H, Bucchiarone H, Khurshid N, Marconi A, Pistore M (2012) ASTRO-CAptEvo: dynamic context-aware adaptation for service-based systems. In: Proceedings of the IEEE Eighth World congress on services, SERVICES ’12. IEEE Computer Society, Washington, DC, pp 385-392 |
| [52] | Ramadge, Pj; Wonham, Wm, Supervisory control of a class of discrete event processes, SIAM J Control Optim (SICON), 25, 1, 206-230 (1987) · Zbl 0618.93033 · doi:10.1137/0325013 |
| [53] | Rao J, Dimitrov D, Hofmann P, Sadeh NM (2006) A mixed initiative approach to semantic web service discovery and composition: SAP’s guided procedures framework. In: IEEE International conference on web services (ICWS’06). IEEE Computer Society, Chicago, pp 401-410 |
| [54] | Rodríguez, G.; Soria, A.; Campo, M., Artificial intelligence in service-oriented software design, Eng Appl Artif Intell, 53, 86-104 (2016) · doi:10.1016/j.engappai.2016.03.009 |
| [55] | Rodriguez-Mier P, Mucientes M, Lama M (2011) Automatic web service composition with a heuristic-based search algorithm. In: IEEE International conference on web services (ICWS). USA, Washington DC, pp 81-88 |
| [56] | Silva FO, Rosa PF (2006) The quest for the web services stack: a fast trip. In: Proceedings of the 6th international conference on web engineering, ICWE ’06. ACM, New York, pp 93-94 |
| [57] | Sirin, E.; Parsia, B.; Wu, D.; Hendler, J.; Nau, D., HTN planning for web service composition using SHOP2, Web Sem: Sci Services Agents World Wide Web, 1, 4, 377-396 (2004) · doi:10.1016/j.websem.2004.06.005 |
| [58] | Skogan D, Grønmo R, Solheim I (2004) Web service composition in UML. In: Proceedings of the eighth IEEE international enterprise distributed object computing conference, EDOC ’04. IEEE Computer Society, Washington, DC, pp 47-57 |
| [59] | Sohrabi, Shirin; Mcilraith, Sheila A., Optimizing Web Service Composition While Enforcing Regulations, Lecture Notes in Computer Science, 601-617 (2009), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg |
| [60] | Teixeira, M.; Malik, R.; Cury, J.; De Queiroz, M., Supervisory control of DES with extended finite-state machines and variable abstraction, IEEE Trans Autom Control, 60, 1, 118-129 (2015) · Zbl 1360.93401 · doi:10.1109/TAC.2014.2337411 |
| [61] | Wang Y, Nazeem A (2011) Artifact-centric business process synthesis framework using discrete event systems theory. Tech. rep., HP Laboratories |
| [62] | Wang Y, Lafortune S, Kelly T, Kudlur M, Mahlke S (2009) The theory of deadlock avoidance via discrete control. In: Proceedings of the 36th annual SIGPLAN-SIGACT symposium on principles of programming languages (POPL’09), New York, pp 252-263 · Zbl 1315.68073 |
| [63] | Wang, Yin; Cho, Hyoun Kyu; Liao, Hongwei; Nazeem, Ahmed; Kelly, Terence P.; Lafortune, Stéphane; Mahlke, Scott; Reveliotis, Spyros A., Supervisory Control of Software Execution for Failure Avoidance: Experience from the Gadara Project, IFAC Proceedings Volumes, 43, 12, 259-266 (2010) · doi:10.3182/20100830-3-DE-4013.00044 |
| [64] | Wang, P.; Ding, Z.; Jiang, C.; Zhou, M., Automated web service composition supporting conditional branch structures, Enterprise Inf Syst, 8, 1, 121-146 (2014) · doi:10.1080/17517575.2011.584132 |
| [65] | Wonham WM, Cai K (2019) Supervisory control of discrete-event systems. Springer International Publishing, pp XX-489 · Zbl 1405.93008 |
| [66] | Wonham, Wm; Ramadge, Pj, On the supremal controllable sublanguage of a given language, SIAM J Control Optim, 25, 3, 637-659 (1987) · doi:10.1137/0325036 |
| [67] | Wu Z, Ranabahu A, Gomadam K, Sheth AP, Miller JA (2007) Automatic composition of semantic web services using process and data mediation. Technical report, Kno.e.sis Center, Wright State University, Dayton, Ohio USA |
| [68] | Yang J, Zhou X, Wang J, Zhu X (2014) A novel method for web service composition based on extended BDI. In: IEEE 11th International conference on networking, sensing and control, (ICNSC’14). IEEE, Miami, pp 310-315, DOI 10.1109/ICNSC.2014.6819644, (to appear in print) |
| [69] | Zafiropulo, P.; West, C.; Rudin, H.; Cowan, D.; Brand, D., Towards analyzing and synthesizing protocols, IEEE Trans Commun, 28, 4, 651-661 (1980) · doi:10.1109/TCOM.1980.1094687 |
| [70] | Zhong, N.; Chen, J.; Ma, J.; Yao, Y.; Liu, J.; Huang, R.; Li, W.; Huang, Z.; Gao, Y.; Cao, J., WaaS-wisdom as a service, Intell Syst IEEE, PP, 99, 1-1 (2014) · doi:10.1109/MIS.2014.19 |
| [71] | Zhou, C.; Kumar, R., Control of nondeterministic discrete-event systems for simulation equivalence, IEEE Trans Autom Sci Eng, 4, 3, 340-349 (2007) · doi:10.1109/TASE.2006.891474 |
| [72] | Zou, G.; Lu, Q.; Chen, Y.; Huang, R.; Xu, Y.; Xiang, Y., QoS-aware dynamic composition of web services using numerical temporal planning, IEEE Trans Serv Comput, 7, 1, 18-31 (2014) · doi:10.1109/TSC.2012.27 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
