06067138

j

06067138 Li, Mu Li, Bo Huai, Jinpeng Reliability-aware automatic composition approach for web services. Sci. China, Inf. Sci. 55, No. 4, 921-937 (2012). 2012 Science China Press, Beijing; Springer, Heidelberg EN reliability web services synthesis problem synthesis model heuristic algorithm

doi:10.1007/s11432-011-4545-8

Summary: In this paper, we study the reliability-aware synthesis problem for composing available services automatically and guaranteeing that the composed result satisfies the specification, such as temporal constraints of functionality and reliability, centered on a synthesis model for a mediator of web services composition (CSM). This approach focuses on handling attributes and state relations and permitting users and services to operate over them, i.e., read/write their data values and compare them according to a dense state order. We show that the reliability-aware synthesis problem for the specification is EXPTIME-complete and we give an exponential-time algorithm (CSM-NSA) which for a given formula $\psi$ and a synthesis model, synthesizes available services in the library satisfying $\psi$ over the synthesis model (if they exist) or responds with ``not satisfiable'' (otherwise). The specification $\psi$ is a fragment of PCTL (probabilistic computation tree logic), obtained from ``ordinary'' CTL (computation tree logic) by replacing the EX, AX, EU and AU operation with their quantitative counterparts $\mathrm{X}^{>p }$, $\mathrm{X}^{=1}$, $\mathrm{U}^{>p }$, and $\mathrm{U}^{=1}$, respectively. As opposed to NSA, we provide a more effective algorithm to replace the NSA algorithm called CSM-HSA (heuristic synthesis algorithm). Though HSA is an incomplete algorithm, the answer is correct. The experiments show that the HSA algorithm solves the problem of reliability-aware service synthesis effectively and efficiently.