TY - JOUR
T1 - On the aggregation problem for synthesized Web services
AU - Deng, Ting
AU - Fan, Wenfei
AU - Libkin, Leonid
AU - Wu, Yinghui
PY - 2013
Y1 - 2013
N2 - The paper introduces and investigates the aggregation problem for synthesized mediators of Web services (SWMs). An SWM is a deterministic finite-state transducer defined in terms of templates for component services. Upon receiving an artifact, an SWM selects a set of available services from a library to realize its templates, and invokes those services to operate on the artifact, in parallel; it produces a numeric value as output (e.g., the total price of a package) by applying synthesis rules. Given an SWM, a library and an input artifact, the aggregation problem is to find a mapping from the component templates of the SWM to available services in the library that maximizes (or minimizes) the output. As opposed to the composition syntheses of Web services, the aggregation problem aims to optimize the realization of a given mediator, to best serve the usersʼ need. We analyze this problem, and show that its complexity depends on the underlying graph of the mediator: while it is undecidable when such graphs contain even very simple cycles, it is solvable in single-exponential time in the size of the specification (i.e., the total size of the input SWM, library and artifact) for SWMs whose underlying graphs are acyclic. We prove several results of this kind, with matching lower bounds (NP and PSPACE), and analyze restrictions that lead to polynomial-time solutions. In addition, we study the aggregation problem for nondeterministic SWMs (NSWMs). We show that the aggregation problem for NSWMs with various underlying graphs retains the same complexity as its deterministic counterparts. We also provide complexity bounds for determining whether SWMs and NSWMs terminate.
AB - The paper introduces and investigates the aggregation problem for synthesized mediators of Web services (SWMs). An SWM is a deterministic finite-state transducer defined in terms of templates for component services. Upon receiving an artifact, an SWM selects a set of available services from a library to realize its templates, and invokes those services to operate on the artifact, in parallel; it produces a numeric value as output (e.g., the total price of a package) by applying synthesis rules. Given an SWM, a library and an input artifact, the aggregation problem is to find a mapping from the component templates of the SWM to available services in the library that maximizes (or minimizes) the output. As opposed to the composition syntheses of Web services, the aggregation problem aims to optimize the realization of a given mediator, to best serve the usersʼ need. We analyze this problem, and show that its complexity depends on the underlying graph of the mediator: while it is undecidable when such graphs contain even very simple cycles, it is solvable in single-exponential time in the size of the specification (i.e., the total size of the input SWM, library and artifact) for SWMs whose underlying graphs are acyclic. We prove several results of this kind, with matching lower bounds (NP and PSPACE), and analyze restrictions that lead to polynomial-time solutions. In addition, we study the aggregation problem for nondeterministic SWMs (NSWMs). We show that the aggregation problem for NSWMs with various underlying graphs retains the same complexity as its deterministic counterparts. We also provide complexity bounds for determining whether SWMs and NSWMs terminate.
U2 - 10.1016/j.jcss.2013.01.007
DO - 10.1016/j.jcss.2013.01.007
M3 - Article
VL - 79
SP - 873
EP - 891
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
SN - 0022-0000
IS - 6
ER -