論文 / 著書情報
Article / Book Information
Title

FENECIA: failure endurable nested-transaction based execution ofcompositeWeb services with incorporated state analysis

Author

Neila Ben Lakhal, Takashi Kobayashi, Haruo Yokota

Journal/Book name

The VLDB Journal, Vol. 18, No. 1, pp. 1-56

発行日 / Issue date2009, 1

URL

http://www.springerlink.com/content/g546851225w35404/

権利情報 / Copyright

The original publication is available at www.springerlink.com.

Powered by T2R2 (Science Tokyo Research Repository)

The VLDB Journal manus ript No.
(will be inserted by the editor)

Neila BEN LAKHAL  Takashi KOBAYASHI  Haruo YOKOTAFENECIA: Failure Endurable Nested-transa tion based Exe utionof Composite Web Servi es with In orporated State Analysis

the date of re eipt and a eptan e should be inserted later

Abstra t Interest in the Web servi es (WS) omposition(WSC) paradigm is in reasing tremendously. A real shift
in distributed omputing history is expe ted to o ur when
the dream of implementing Servi e-Oriented Ar hite ture
(SOA) is realized. However, there is a long way to go toa hieve su h an ambitious goal. In this paper, we support theidea that, when hallenging the WSC issue, the earlier thatthe inevitability of failures is re ognized and proper failurehandling me hanisms are dened, from the very early stageof the omposite WS (CWS) spe i ation, the greater are
the han es of a hieving a signi ant gain in dependability.
To formalize this vision, we present the FENECIA (Failure

we introdu e graphi al and formal notations. These rules
provide the solid foundation needed to formulate the exe ution semanti s of a CWS in terms of exe ution orre tnessveri ation dependen ies. To ensure dependable exe utionof the CWS, we present in the se ond se tion of FENECIA
our ar hite ture THROWS, in whi h the exe ution ontrolof the resulting CWS is distributed among engines, dis overed dynami ally, that ommuni ate in a peer-to-peer fashion. A dependable exe ution is guaranteed in THROWS bykeeping tra k of the exe ution progress of a CWS and by
enfor ing forward and ba kward re overy. We on entratein the third se tion of our approa h on showing how the failEndurable Nested-transa tion based Exe ution of Compos- ure onsideration is trivial in a quiring more a urate CWS
ite Web servi es with In orporated state Analysis) frame- QoS estimations. We propose a model that assesses several
work. Our framework approa hes the WSC issue from dif- QoS properties of CWS, whi h are spe ied as WS-SAGAS
ferent points of view to guarantee a high level of dependabil- transa tions and exe uted in THROWS. We validate our proity. In parti ular, it aims at being simultaneously a failure- posal and show its feasibility and broad appli ability by dehandling-devoted CWS spe i ation, exe ution, and qual- s ribing an implemented prototype and a ase study.
ity of servi e (QoS) assessment approa h. In the rst se tion of our framework, we fo us on answering the need for Keywords Web servi es  omposition  dependability a spe i ation model tailored for the WS ar hite ture. To failure  distributed exe ution  transa tion model  QoS
this end, we introdu e WS-SAGAS, a new transa tion model.
WS-SAGAS introdu es key on epts that are not part of the
WS ar hite ture pillars, namely, arbitrary nesting, state, vi- 1 Introdu tion
tality degree, and ompensation, to spe ify failure-endurable
CWS as a hierar hy of re ursively nested transa tions. In With the urrent proliferation of Web servi es (WS), a onaddition, to dene the CWS exe ution semanti s, without siderable shift is expe ted to o ur in the way distributed
suffering from the hindran e of an XML-based notation, we omputing systems are integrated. The onventionally indes ribe a textual notation that des ribes a WSC in terms of tegrated systems are foreseen to be gradually repla ed indenition rules, omposability rules, and ordering rules, and the near future by distributed and loosely oupled servi esoriented systems. The key features that allow the WS te hnology to a omplish su h a shift are: a) It builds on a set
Neila BEN LAKHALTokyo Institute of Te hnology, Department of Computer S ien eof universally re ognized XML standards, espe ially WSDL
2-12-1 Oh-Okayama, Meguro-ku Tokyo, 152-8552 JAPAN(Web Servi e Des ription Language) [1℄, SOAP (Simple ObTel.: +81-3-5734-3505, Fax: +81-3-5734-3504
je
t A ess Proto ol) [2℄, and UDDI (Uniform Des ription
E-mail: neilade. s.tite h.a .jp
Dis overy and Integration) [3℄ to des ribe, dis over, and inTakashi KOBAYASHI  Haruo YOKOTA
voke any type of servi es in a networked environment. b) It
Global S ienti Information and Computing Centerhas
the potential to glue any systems together, no matter how
Tokyo Institute of Te hnology, Department of Computer S ien e
different they are. ) It redu es dependen y among ompo2-12-1 Oh-Okayama, Meguro-ku Tokyo, 152-8552 JAPAN
Tel.: +81-3-5734-3505, Fax: +81-3-5734-3504
nents to obtain less fragile systems with in reased responE-mail: ftkobaya,yokotag s.tite h.a .jp
siveness and ability to be frequently modied.

2

One issue that is gaining notable momentum in the resear h ommunity is WS omposition (WSC), whi h is used
to reate what is alled value-added servi es or omposite Web servi es (CWS) by taking a set of preexisting elementary WS, typi ally owned and managed by diverse entities, and weaving them together to build more powerful andfeature-ri h business pro esses. An example of CWS is anappli ation that books a ight, rents a ar, and makes a hotel
reservation to provide a omplete trip reservation pro ess.
There is a myriad of spe i ations available for omposing WS, exemplied by the emerging standards su h as
BPEL4WS (Business Pro ess Exe ution Language for Web
Servi es) [4℄ and industrial solutions su h as IBM's Emerging Te hnologies Toolkit ETTK [5℄ and Mi rosoft's .Net
[6℄. In addition, a ademi resear hers are making substantial resear h efforts, working on a whole panoply of WSC
strategies in luding dynami omposition (e.g., eFlow [7,8℄), de larative omposition (e.g., SELF-SERV [9,10℄), andsemanti omposition (e.g., SHOP2 [11℄). A areful investigation of the major part of the available solutions for WSC
reveals that only a very few ases are geared toward a distributed environment, su h as the SELF-SERV framework.
However, all the other approa hes, su h as BPEL4WS andeFlow, only support the integration of WS into a entralized
model onsisting of dedi ated entralized engine(s). They
have totally ignored the nature of the WS environment whereintera tion follows a peer-to-peer model and where ea h peer
WS owner provides a set of servi es that an be used to ompose a CWS.
The WSC te hnology is still regarded as immature: it requires onsiderable development before rea hing its apogee[12,13℄. In parti ular, the WSC te hnology has to over ome
a major obsta lethe widely re ognized unreliability of theInternetbe ause all the available WS rely heavily on theInternet to be deployed. Adding to the Internet unreliability
is a whole set of hara teristi s of the modern omputing environments (e.g., unpredi tability, heterogeneity, autonomy,
dynamism, omplexity, et .) in whi h the WS subsist, making the most unexpe ted failure a normal part of any WS.
Furthermore, with the assembly of several elementary WS
into a CWS to reate ri her fun tionalities, the failure frequen y is more important than ever.

Neila BEN LAKHAL et al.

WS-SAGAS: a CWS spe i ation model. The rst se tion of our approa h ta kles the WSC issue from a different viewpoint: instead of trying to avoid failures, we a ept
their inevitability and we propose a new CWS spe i ation
model that builds primarily on the transa tion on ept
widely re ognized by the database ommunity as a strongon ept for enhan ing reliability and availability [14℄. Spe ifi ally, we present a new transa tion model that we name
WS-SAGAS [1518℄ to apture the underpinning logi of the
CWS in transa tions. Our model is spe i ally tailored to t
the hara teristi s of the WS ar hite ture, thereby allowing
to over ome the onstraints imposed by the traditional transa tion model [14℄. In parti ular, WS-SAGAS spe ies the
CWS as a hierar hy of arbitrary nested transa tions and introdu es key features in luding state apture, vitality degree,
and ompensation me hanisms. These me hanisms are riti al to inform of and re over from any transient failure. We
build on these on epts to spe ify failure-endurable CWS
as a hierar hy of re ursively nested transa tions. In addition, to dene the CWS exe ution semanti s without suffering from the hindran e of an XML-based notation, we
des ribe a WSC in terms of Denition Rules (DR), Composability Rules (CR), and Ordering Rules (OR), and we introdu e graphi al and formal notations. These rules provide thesolid foundation required to formulate the exe ution semanti s of a CWS in terms of exe ution orre tness veri ation
dependen ies.
THROWS: a CWS exe ution ar hite ture. In the se ond
se tion of FENECIA, we propose a new ar hite ture, named
THROWS (Transa tion Hierar hy for Route Organization of
Web Servi es), for a highly dependable distributed exe u-tion of CWS. In THROWS [19,20℄, CWS exe ution ontrol
is hierar hi ally delegated among distributed engines; theseengines are dis overed dynami ally throughout the CWS exe ution progress and they intera t in a peer-to-peer fashion, thereby avoiding WS exe ution dependen e on a single authority, whi h an onstitute a potential single point of
failure. In THROWS, we a hieve failure apture and re overy, and ontrol of long-running and parallel transa tions byintrodu ing two key on epts: the Candidate Engines List
(CEL) and the Current Exe ution Progress (CEP).
QoS estimation and analysis model. In the third se tionof FENECIA, we fo us on another issue related to the qualIn this paper we advo ate that, when hallenging the itative aspe t of CWS: we verify to what extent the failureWSC issue, the earlier we a ept the inevitability of failures handling me hanisms we propose are suf iently strong toand make available proper failure-handling me hanisms a hieve a signi ant gain in dependability. during exe ufrom the very early stage of the CWS designthe greater tion. We present a novel model that hara terizes, estimates,
are the han es of a hieving a signi ant gain in dependabil- and analyzes several QoS properties of dynami ally exeity. To formalize this vision, we propose FENECIA (Failure uted CWS [21,17℄. In parti ular, we estimate the reliability
Endurable Nested-transa tion based Exe ution of Compos- and the exe ution time of the CWS. We on entrate on one
ite web servi es with In orporated state Analysis), in whi h important issue that has re eived little attention to date, that
we ta kle the WSC issue from different viewpoints to guar- is, onsidering the potential failures reper ussions on theantee a higher level of dependability. Our approa h aims CWS exe ution performan e estimates. We advo ate that a at being, simultaneously, a failure-handling-devoted CWS ounting for failures and their reper ussions on the effe tive
spe i ation, exe ution, and QoS assessment approa h. Our performan e of the CWS is parti ularly required in the WS
framework is depi ted in (Figure 7.1) and its ontributions ar hite ture, in view of the WS inherent tenden y to fail relare threefold:atively easily ( ompared to other omputing omponents).

FENECIA

Contrary to most of the urrent approa hes dealing with
QoS estimations in the WS ontext, whi h rely on the QoS
information advertised by the WS providers, our model omputes QoS estimates on the basis of the CWS exe ution observation.
Approa h validation. To he k the feasibility of our approa h, we present a prototype that we implemented [18,22℄
and that spe ies CWS as a hierar hy of re ursively nested
WS-SAGAS transa tions and simulates their exe ution in
THROWS ar hite ture. In addition, we report a ase study
that demonstrates the appli ability of our proposal [21℄.
By bringing together the se tions des ribed above: i) We
build on the strength of the WS ar hite ture-enabling standards. ii) We ombine a number of arefully sele ted features: the transa tion-based spe i ation and exe ution, thestate-guided exe ution failure monitoring, the failure-aware
QoS estimation, and the exe ution observation-driven QoS
analysis. iii) Finally, we introdu e the dedi ated failure handling and re overy strategy, and we provide a solid foundation for the FENECIA approa h to be ome a omprehensive methodology for the development of highly dependable
CWS .
The remainder of this paper is organized as follows. Se tion 2 des ribes the type of failures we onsider in this paper. Se tion 3 des ribes the key requirements that a transa tion model for the WS ontext must satisfy. Se tion 4 is an
overview of the evolution of the transa tion on ept. Se tion 5 des ribes our WS-SAGAS transa tion model. Se tion 6 des ribes our ar hite ture, THROWS. Se tion 7 introdu es our QoS model. Se tion 8 des ribes our validation andhe ks the appli ability of our proposal. Se tion 9 des ribes
related work. Finally, Se tion 10 on ludes our paper andgives a few tentative suggestions for future work.
2 Fault Model3

du ed by updates. The intera tion faults an be ategorized
as transient faults or permanent faults. We onsider permanent faults beyond the s ope of this paper.
2.1 Failure Modes
A omplete understanding of possible failure modes helps
determine the me hanisms for fault toleran e. In this paper,
we onsider failure modes en ountered by the system users,
spe i ally timing-related failures where the time of arrival,or the duration of the information delivered, at the servi e
deviates from the expe ted duration implemented by the system fun tion. These failures are environment-related failures
and are asso iated with WS rashes and timeouts; they areommonly hara terized as silent failures be ause the system servi e is no longer available to users. At the omposition level, spe ial monitoring is required to handle these failures. This lass of failure is handled by performing either aforward re overy or a ba kward re overy without requiring
any external intervention.
The other ategory of failures en ountered by systemusers is ontent-related failures, su h as WS exe ution exeptions, WS programmed ex eptions, ex eptions propagatedfrom other parti ipant WS, and fault messages re eived from
SOAP alls to WS. We onsider ontent-related failures tobe beyond the s ope of this paper; dealing with them is omplex be ause WS providers dene WS differently.
3 A Transa tion Model for WS Context: Key
Requirements
We identify the key requirements that a transa tion model
for CWS must satisfy. A number of ontributions have added
a transa tional support for CWS su h as WS-transa tion [25℄and WS-CAF [26℄. Although available solutions are mostly
for stati ally omposed WS, we target a dynami CWS. After identifying the different requirements that a transa tionmodel for dynami CWS must satisfy, we provide a stateof-the art summary of the on ept of transa tions in databasete hnology to identify previously proposed on epts that may
help to in rease dependability.

The fault model and the failure modes we identied were
inspired by a failure taxonomy for the parti ular ase of WS
ar hite ture developed in [23℄, whi h in turn is based on theseminal work of [24℄.
A fault model is a model of the types of faults that ano ur in a system while it is running. The widely re ognized
spe i ities of the modern IT environment in whi h WS
subsist (e.g., heterogeneity, omplexity, and autonomy of R EQUIREMENT 1. A generi model that an ombine difthe parti ipating systems and of their underlying platforms, ferent transa tional semanti s: WS interleaved in a CWS
versatile ommuni ations proto ols and dynami manage- tends to be hosted by different providers. It is most likely
ment poli ies, un ertainties about system boundaries, et .) that their providers are using non ompliant transa tion supmake the system subje t to all the lasses of faults atego- ports (if they provide any). Moreover, it is not possible torized in [24℄. The lasses of faults of interest are physi al ompel the WS providers to make the same transa tion model
faults in luding all fault lasses that affe t hardware, inter- available. To this end, a transa tion model for the WS ona tion faults in luding all external faults, and development text must be suf iently generi to a ommodate different
faults in luding all fault lasses o urring during develop- transa tional semanti s in the same model. Furthermore, it
ment. However, in multitier CWS, whi h span multiple in- must add the required transa tional semanti s to the WS, if
tera ting systems, intera tion faults, whi h o ur during use, they do not exist. BPEL [4℄ is a typi al example of a WSC
have the greatest impa t. Examples of faults in this lass are spe i ation that denes only one type of transa tional selost/ orrupted messages, pro ess rashes, and faults intro- manti for all the WS interleaved in the same CWS.

4

The sagas model [27℄ was used to dene the required
transa tional support for stati CWS in BPEL. In BPEL, theonly way to handle a failure is by ompensation; the ase
where it is impossible or unne essary to dene a ompensator for a parti ular saga is not addressed. It is true that failure atomi ity is guaranteed be ause if any a tivity fails theoverall pro ess is ompensated. However, we argue that the
support of other transa tional behaviors in the same model
improves the han es of CWS exe ution ompleting su essfully. Other required transa tional behaviors in this situation are: (i) envisaging alternative me hanisms to ompensation if ompensation is not an option; (ii) having re ourse
to ompensation only as a last resort, when there is no meansof saving some part of the pro ess progress; (iii) in luding
idempotent tasks that need no ompensation.

Neila BEN LAKHAL et al.

R EQUIREMENT 4. A model that an guarantee orre t anddependable exe ution: Many spe ied details of the CWS

relate to the dened exe ution orre tness restri tion methods. In parti ular, we ite serializability [30℄, widely a epted
as the ornerstone of database orre tness, as unsuitable.
Our justi ation is that serializability is very rigid and imposes restri tions that are not required (or feasible) in the
WS ontext. For example, the shared resour e ondition is
not satised be ause we are no longer dealing with transa tions to be serializable against only one database; the different pro esses des ribed as CWS are far more omplex thansimple write/read operations.
Several proposals, su h as quasiserializability for a multidatabase environment [31℄, have proposed solutions that,
although they relax the stri t serializability ondition, stilltarget on urren y ontrol and database integrity ontrol.
Nevertheless, for CWS, orre tness means ensuring thatR EQUIREMENT 2. A model that an support different inter- the semanti s of the CWS are orre t against the pro essa tion patterns: The logi underpinning business pro esses predened semanti s (i.e., pro ess logi and omponents ortends to be versatile and semanti ally varying. Consequently, ders). Therefore, serializable exe ution is not required in thein the same transa tion, we may have to or hestrate elemen- same way as in a onventional database [32℄. An importanttary WS in different ways and in line with different ontrol approa h, whi h indeed was already used for ensuring orow patterns (e.g., join, split, syn hronize, et .). However, re t exe ution of CWS, is by spe ifying a set of A eptablea major part of the proposed transa tion models only sup- Terminal States (ATS) [33,34℄.
This approa h was initially proposed for transa tional
ports a on urrent or sequential intera tion within a transWorkow
systems and later extended to CWS. In this apa tion. To over ome this limitation, the Workow ommuproah,designers
have a ru ial role in determining whi hnity ontributions are of interest. In parti ular, well-knownWorkow Patterns are those proposed in the seminal work is the orre t exe ution, in terms of ATS. We argue that ATS[28℄. This olle tion of patterns has been used to evaluate the is a powerful approa h that ts well for CWS with a entralfun tionality of ommer ial produ ts and standards support- ized and stati exe ution, as in [34℄. However, for a dynami
ing the development of pro ess-oriented appli ations (e.g., and distributed exe ution, ATS is insuf ient as there is no
the METEOR proje t [29℄ and BPEL [4℄). This work serves entral entity that is responsible for verifying that the exe uas a reliable starting point for dening the required aggrega- tion veries, or violates, the predened ATS. Moreover, ATS
only veries termination dependen y and, even if the differtion patterns.
ent omponents of a CWS terminate in states in luded intheir ATS, there is no guarantee, or means of proving, theirexe ution order orre t. We require spe ial me hanisms to
R EQUIREMENT 3. A model that an guarantee the best mat h
enfor e that the exe ution order of the omponents of a CWS
between WS and CWS omponents: A well-known hara does
not deviate from the pres ribed order.
teristi of the WS realm is its unpredi tability; this hara teristi is not part of the equation in either the Workow area ortransa tion models. Both are designed for a omputing en- 4 Transa tion Con ept: State of the Art
vironment where modi ations are very rare. Moreover, thedifferent omponents, for either a transa tion (subtransa - We highlight features of several transa tion models that are
tions) or tasks for Workows, are predened, whi h totally interesting for dependability enhan ement. We explain foreliminates unpredi tability.
ea h feature/model why it an or annot be integrated in a
Returning to the WS ontext, unpredi tability introdu es transa tion model tailored for CWS.
a high probability of failure when WS are stati ally or hestrated. To over ome this limitation, it is required to deneseveral alternative WS for the same omponent so that if 4.1 Traditional Transa tion Modelthe exe ution using one fails, it an be reattempted using
others. Moreover, as WS tends to provide basi fun tionali- This model is undoubtedly the pre ursor of all the transa ties, it is very probable that one transa tion as a whole an- tion models that have been proposed. It refers to a transa not be satised by one WS alone. This introdu es another tion endowed with the ACID (Atomi ity, Consisten y, Isolarequirement for omponent/transa tion semanti s, ompo- tion, and Durability) properties [35℄. With these properties,
sition/de omposition, to fa ilitate and ensure that the best ea h transa tion is guaranteed to enfor e failure atomi ity
mat h is made. This requirement satisfa tion is partially ad- and serializability as a orre tness riterion. Ea h transa tion has a at stru ture.
dressed in this paper; for a full des ription, refer to [18℄.

FENECIA

Although the effe tiveness of the traditional transa tionmodel in onventional database appli ations, where transa tions are generally simple and of short duration, is irrefutable,
the unsuitability of its stri t ACID properties for the WS
ontext is lear. Maintaining stri t isolation and serializability auses a la k of fun tionality, exibility, and performan e.
This pre ludes the possibility of intertransa tion ooperationand long-running transa tions.
4.2 Advan ed Transa tion Models
Several advan ed transa tion models have been proposedin response to the inexibility of the traditional transa tionmodel (refer to [14℄ for a omprehensive des ription of someof these). We investigated the appli ability of some of thesemodels that inherently allow transa tion omposition (stru turing) an essential feature for a model for CWSand enompass on epts with re ognized ontributions in enhan ing dependability but not yet part of the WS ar hite ture.
The nested-transa tion model [36℄, whi h uses a serializable orre tness riterion, made a signi ant ontribution to
the database ommunity by: (i) extending the at transa tion
stru ture to a multilevel stru ture; (ii) introdu ing the onept of ontingent and nonvital subtransa tions; and (iii) allowing a higher degree of intratransa tion parallelism. All ofthese on epts are of onsiderable relevan e to WS ar hite ture be ause, rst, the on urrent exe ution of transa tion isan essential feature. Se ond, ontingent subtransa tions areeasily realizable be ause WS that share the same fun tionalities are numerous; onsiderable resear h effort is dire ted
toward a hieving this issue. Third, denition of nonvital subtransa tions is essential to in rease availability.
To deal with the problem of long-lived transa tion faults,
the on ept of ompensation was rst introdu ed in the sagas
model [27℄. A saga onsists of a set of ACID subtransa tions with a predened order of exe ution and a set of ompensating subtransa tions. If a long-lived transa tion fails,
it an be aborted and rolled ba k, and then retried. However, if a saga as a whole be omes irre overable and has toabort, appropriate ompensations are run to ompensate forthe ompleted parts of the transa tion (ba kward re overy),that is, semanti ally undoing the effe ts of the failed parts.
The other possibility in re overy is a forward re overy, thatis, the system needs to retry the same failed transa tion parts.
The ompensation ingredient here is of parti ular interest
be ause it an realize a exible fault-handling approa hahighly desirable hara teristi in the WS ontext, in view of
its high failure tenden y. However, the restri tion imposedby sagas that ea h subtransa tion must be su essfully ompensatable annot always be fullled. Therefore, alternative
me hanisms for non ompensatable tasks are required.
The nested-sagas transa tion model has been proposed
as an extension to the sagas model [37℄. It treats ommuni ation between transa tion steps as an essential feature in

5

the WS ontext. Ea h saga spe ies input and output ports,bound at run time to mailboxes (i.e., queue of messages).
Communi ation is a hieved using three different lasses ofpredened ommands: Bind, Send, and Re eive.
The Flex transa tion model was designed to allow more
exibility in transa tion pro essing [33,38℄. A exible transa tion is spe ied by dening a set of subtransa tions, a setof intratransa tion exe ution dependen ies, and a set of a eptable terminal states (ATS) dening the onditions forthe su ess of the exible transa tion. The Flex transa tionmodel goals are very similar to our goals be ause it targets a multidatabase system, whi h an be assimilated toa spe ial ase of the WS environment where the parti ipating systems are predened and annot dynami ally disappear without prior noti e. In parti ular, the way a exible transa tion is dened makes it the best andidate for
CWS, as it allows the designer to spe ify a set of fun tionally equivalent subtransa tions, ea h of whi h, when ompleted, a omplishes the task. Moreover, the ontribution of
the state and the intratransa tion exe ution dependen ies asso iated with ea h transa tion an over ome the stateless
WS and provide exible atomi ity and isolation, espe ially
if the subtransa tions support some form of ompensation.
It is also suitable for ontrolling and tra king the exe ution
progress in a distributed environment.
While these advan ed models differ in various forms,
they all share the same line of thinking: the stri t ACID
properties support is no longer a viable solution for a nontraditional database environment. In this sense, they exploit
appli ation-spe i semanti s to dene nonserializable orre tness riteria to spe ify and onstrain the behavior of thetransa tion omponents and their intera tions. As well as
these transa tion models, many others were also proposedfor databases (e.g., ooperative SEE transa tions [14℄, DOM
transa tions [14℄, et .) or by the Workow resear h ommunity. We limited our study to these models be ause they areat the base of many others that were proposed later.

5 WS-SAGAS Transa tion Model
We propose to adopt features of interest from the transa tion models des ribed above and to build on them to makeour transa tion model suf iently ri h to support any CWS
underpinning logi and to provide it with the required me hanisms to guarantee a dependable spe i ation of dynami
CWS exe uted in a peer-to-peer environment.
Spe i ally, we inherit the arbitrary nesting of transa tions, the forward re overy with exe ution retrial, the ba kward re overy ensured with ompensation me hanism, thevitality degree, the state, the Workow-like aggregation patterns, and the intratransa tion exe ution dependen ies toensure orre t exe ution.

6

Neila BEN LAKHAL et al.

in Process Pi [ ni , mi ] out

WS - SAGASi (ni ,1 Elements)
statei.astatei.1
inin

E 'i.1

Ei.1

out

...

(description )inoutput parametersout

E i .a . 1

in

E 'i.a.1...

atomicelement

Ei.ni , 1in

E 'i.nEi .a.ni ,2Nestingout( description )in

in

Ei.a.*.b.1(description )

out

...

in

E 'i.a.*.b.1...

Ei.a.*.b.ni . pout(description )out(Level 2 )E'i .a .ni ,2

...

...

(Level 1 )i .1statei .a .ni ,2in(description )

out

out

(description )

...

out

Nesting

i ,1WS - SAGASi.a.*.b (ni, p Elements)
statei .a .* .b .ni ,pstatei.a.*.b.1

compositeelement
compensating
element...

WS - SAGASi.a (ni, 2 Elements)
statei.a.1

control flow

in

out

(description )Legendinput parameters

Ei.a

in

statei.n...
Nestingout(Level p )E 'i.a.b.*.n

i,p

...

... ..
.

WS - SAGASi.a.*.b.*.c (ni ,m Elements)
statei .a .* .b .* .c .nstatei.a.*.b.*.c.1

...

...

i

in

in

Ei.a.*.b.*.c.1(description )Fig. 4.1

out

E 'i.a.*.b.*.c.1

...

in

i ,m iEi.a.*.b.*.c.ni , mi out(description )E'i.a.*.b.*.c.ni , miout

Nesting(Level mi )WS-SAGAS transa tion model: graphi al notation Gi of a pro ess Pi des ribed as a hierar hy of re ursively nested WS-SAGASA SSUMPTION 3. We assume the pro ess of andidate
WS dis overy, sele tion, and mapping, and that veri ationthat a ertain andidate WS and a ertain omponent fromA SSUMPTION 1. We assume we are dealing with business a CWS are semanti ally equivalent an be performed autopro esses that may need to ombine various transa tional mati ally. A very a tive area of resear h is measuring the
behaviors. That is, a pro ess puts together different a tivi- semanti and synta ti similarity between WS to ensure theties: several are idempotent and need not be undone (e.g., best mat h an be done. We onsider this issue beyond thedisplaying order information), several an be easily undone s ope of this paper, as we an apply any of the available proor ompensated for (e.g., adding produ ts to an order), and posals.
several others annot be (automati ally) undone be ause theymark a de ision, ommonly alled non ompensatable (e.g.,
A SSUMPTION 4. We assume the system designers havehe king out and ordering).
a omprehensive des ription of the business rules buried in
the pro ess-underpinning logi and they an use these rules
A SSUMPTION 2. We assume that there is no dependen y without ambiguity to dis ern the different transa tional bebetween su essive invo ations of the sele ted WS, if the haviors and their s ope (i.e., a CWS, a omponent from a
dynami WS dis overy and sele tion leads to sele ting the CWS, an aggregation of omponents, et .).
same WS,
5.1 General Assumptions

FENECIA7

5.2 Des ription of WS-SAGAS Model Salient Features
Our model introdu es the following features to spe ify theunderpinning logi of a pro ess (e.g., virtual travel agen y),
as a fault-tolerant and dynami ally exe uted CWS against apeer-to-peer environment:
5.2.1 Pro ess, Transa tion, and Element

In (W S-SAGASi ` W S-SAGASi a ), the symbol ` indiates that W S-SAGASi is dened at the top of the subtransa tion W S-SAGASi a . That is, the parent element of the subtransa tion W S-SAGASi a must be Ei a , one of the elements
aggregated in W S-SAGASi .
A hierar hy of WS-SAGAS forming a pro ess ontains
a parent WS-SAGAS, plus zero or more hildren; the hildren
an be atomi elements or omposite elements, parents ofother WS-SAGAS.
We guarantee the uniqueness of an element identier bykeeping the identier of the subtransa tion it appertains toand on atenating it to a unique identier for the element.
More formally, let Ei a be one of the elements from the uppermost transa tion W S-SAGASi and i:a its identier; i
is the index of its parent WS-SAGAS. We emphasize that the
number of :00 in the identier indi ates the nesting level, andthe last digit (i.e., a for Ei a ) indi ates the order. We assume
that a is dened in [1::jWS-SAGASi j℄ where jW S-SAGASi j
is the ardinality (i.e., the number of assembled elements)of the subtransa tion W S-SAGASi and is equal to ni 1 . Similarly, it is equal to ni 2 for W S-SAGASi a forming the se ond nesting level, and equal to ni m for the nesting level
mi ontaining W S-SAGASi a  b  . To generalize, we use in
W S-SAGASi a  b the symbol  to indi ate that there exists
a subtransa tion that has as a parent the element Ei a  b andthat omes in one of the nesting levels after nesting level 1,
whi h ontains the element Ei a . In i:a:  :b the symbol is repla ed to dene the WS-SAGAS a tual identier. We
assume W S-SAGASi a  b is the nesting level p where p < miand mi orresponds to the last nesting level in Pi . We denotethe last subtransa tion in the hierar hy, whi h orresponds
to the nesting level mi by W S-SAGASi a  b  ; its rst element is denoted Ei a  b  1 and its last element is denoted
Ei a  b  n .
:

:

:

:

To allow a dynami pro ess omposition, instead of spe ifying the underpinning logi of a pro ess using a set of preexisting WS woven together into a stati CWS, we introdu e the on ept of an Elementrepresented by a re tanglein (Figure 4.1)and use it as a unit in the omposition ofa pro ess as a hierar hy of re ursively nested WS-SAGAS
transa tions.
The same element an be simultaneously a omponent
from a WS-SAGAS and a parent of other elements in another WS-SAGAS. Therefore, it is alled a omposite element and we represent it as a blue re tangle. Alternatively,
an atomi element is only embedded in a WS-SAGAS andis represented as a white re tangle.
On exe uting a pro ess, WS are dynami ally dis overed,and andidates are sele ted and mapped either to the different elements or to WS-SAGAS, onsidering the WS availability. In this paper we limit the WS sele tion and mappingto the atomi elements. However, our approa h supports the
mapping to entire WS-SAGAS. This issue is detailed in [18℄.
The ontrol ow between the different elements spe ies theordering relation between the different elements and is represented by dire ted edges. Finally, the data ow spe ies
how the data produ ed by an element are transferred to another element and are represented by the mapping between
the different input and output boxes; we do not onsider thisissue in this paper and we will address it in our future work.
More pre isely, we adopt the following notation of a pro- 5.2.2 Vitality Degree
ess, illustrated also by (Figure 4.1):
To add exibility to the way failures as ade through a proPi [ni ; mi ℄ : W S-SAGASi(ni 1 elements) (nesting level 1)
ess, depi ted as a hierar hy of WS-SAGAS transa tions,` W S-SAGASi a (ni 2 elements) (nesting level 2) we distinguish vital from nonvital elements. The vitality degree of an element is denoted by a supers ript set to` :::v for vital and to v̄ for nonvital. The vitality degree` W S-SAGASi a  b (ni p elements) (nesting level p) obeys these assumptions: A vital element (denoted Eivk ) must be exe uted su ` :::essfully (i.e., it has to ommit) for its parent transa tion
to ommit.
` W S-SAGASi a  b  (ni m elements)(nesting level mi )v̄(5.1)  A nonvital element (denoted Ei k ) may abort without
preventing its parent transa tion from ommitting.
A pro ess (denoted Pi ) is assumed to have a unique identi-  Aborting a vital element Eivk indu es aborting the wholeer i as a subs ript, where i ranges over the set of naturaltransa tion it appertains to if there is no alternative WS
numbers  to designate different pro esses. Ea h pro ess is
to retry it.
assumed to have ni elements distributed over mi nesting lev-  Aborting a nonvital element Eiv̄k does not ree t on theels. In the hierar hy of WS-SAGAS forming the pro ess, we
exe ution of the transa tion it appertains to; the pro ess
denote the uppermost WS-SAGAS W S-SAGASi . Note that
ould omplete su essfully although not all its ompowe keep the same subs ript for the orresponding pro ess.
nent elements were ommitted. Doing so is expe ted toNote also that W S-SAGASi is the only WS-SAGAS in thein rease availability and to de rease the probability ofhierar hy that has no parent.
overall pro ess failure o urring.
:

:

;

;

:

;

i

: : : : :

: : :

: : :

:

: : :

: : : : :: : : : : :: : : : : : i;m
i

;

:

: : :

;

;

:

: : : : :

;

i

:

:

:

8

Neila BEN LAKHAL et al.

We des ribe below the denition of the vitality degree of a
we annot make a de ision unless we atta h a state to
pro ess Pi depi ted as a hierar hy of re ursively nested WSea h element. We an then derive the urrent state of the
SAGAS transa tions. In the remainder of this paper, an elewhole pro ess. More importantly, we an dedu e whether
ment's supers ript is omitted and the notation (Ei k ) without
the exe ution progress is orre t against the pro ess prespe ifying the vitality degree is used for an element when
spe ied semanti s and ordering.
not relevant or interesting. The distin tion between a vitalelement (Eivk ) and a nonvital element (Eiv̄k ) is only given At any time, the state of every element Ei k denoted statei k(in Figure 4.1)keeps the same identier as the element it iswhen a spe ial onsideration is required.
atta hed to. The state of an element is assumed to be ex lusively in one of the six states dened below, if the element
5.2.3 Transa tional Behavior
is ompensatable (see Figure 5.1 (a) and (b)):
Every atomi element Ei k has a transa tional behavior. The 1. Waiting: E is not yet submitted for exe ution and isiktransa tional behavior of an element is losely related to thestill waiting for the exe ution progress to rea h its level.
nature of its fun tional semanti s and is determined prin i- 2. Exe uting: E is effe tively being exe uted.
ik
pally by the designers to des ribe how the element failure 3. Failed: E has
en ountered a failure.
ik
an be handled. The transa tional behavior of an element 4. Aborted: E has re eived a request to abort itself andik
an be one of the transa tional behaviors des ribed below:
has obeyed it.
 Compensatable: The fun tional semanti s of the ele- 5. Committed: Ei k has su essfully terminated and wasommitted.
ment an be undone.
 Non ompensatable: The fun tional semanti s of the 6. Compensated: Ei k has been ompensated for.
element annot be undone (automati ally) on e done.
If an element isnon ompensatable, the set of states that
Two other transa tional behaviors are impli itly supported model the element's internal behavior is redu ed to ve statesby our model: retriable and idempotent elements. We by eliminating the ompensated state (see Figure 5.1 ( )assume all the vital elements are retriable with differ- and (d)). A vital element is assumed to be retriable,
ent semanti ally equivalent WS and that the nonvital ele- and there is therefore a dire ted edge between the failed
ments are not retriable be ause their fulllment is optional. and exe uting states in Figure 5.1, (a) and ( ).
An idempotent element is one that has no effe t (e.g., read
For an element to transfer from one state to another, a
operation); we treat this as a ompensatable element that transition ondition has to be evaluated. When it is veried,
is undone by running an empty ompensator.
several a tions may be triggered. Of the different a tions,
The hoi e of potential andidate WS for a parti ular el- one a tion makes the state of the element hange from oneement must onsider the required transa tional behavior for state to another.
that element. When an atomi element is ompensatable,
For a ompensatable element E , to transit from thewe represent its ompensating element just below it with a state waiting to the state exe utingi,kwe assume the veriround- ornered re tangle (see Figure 4.1). Assume that the ability of the ondition that indi ates that at least one WS
element Ei 1 is ompensatable: we denote its ompensat- bearing the same semanti fun tionalities as the element musting element Ei0 1 . Similarly, a omposite element is om- be sele ted. Only when the sele ted WS is mapped to the elpensated by the different elements aggregated in its orre- ement does the element's state be omes exe uting.
sponding WS-SAGAS: in (Equation 5.1), Ei a is a omposite
Depending on the allo ated WS exe ution progress andelement represented by the subtransa tion W S-SAGASi a and the progress of other elements in the same WS-SAGAS, theit an be ompensated by ompensating W S-SAGASi a . We exe uting state an transit to aborted, if the WS exe udes ribe this in detail below.
tion must be an eled, or it an transit to either the ommittedor the failed states; this depends on whether the sele ted
5.2.4 State
WS a hieved the element's obje tives or not.
Assume that the state of a ompensatable element was
We atta h to ea h atomi element from a WS-SAGAS trans- set to failed. Subsequently, depending on the element's via tion a state for the following reasons.
tality degree, the pro essing differs:(i) To de ide how to advan e a pro ess exe ution, (i.e., toa) When the element is vital, another andidate WS
de ide whether to delegate the exe ution ontrol to other that bears the same semanti fun tionalities is sele ted andelement(s) or to resume it), it is essential to know the the exe ution is retried with this new andidate by hanging
exe ution progress of ea h element separately.
the element state ba k to exe uting; su ess of exe ution(ii) At a ertain point of the exe ution of a pro ess, the pre- of the new WS means su ess of the element and its state isspe ied obje tives may be a hieved. In this ase, the set to ommitted. However, if an element is retried a numpro ess is onsidered to be su essfully ompleted and ber of times with different WS and all the attempts are unan be ommitted. Be ause we onsider a distributed su essful and it is no longer possible to retry the exe ution,model, where there is no entral monitor that has all for any predened reason, then the element's state remains
the required information about the exe ution progress, failed, and a ba kward re overy is triggered.
:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

FENECIA

9

start

start

Initiate()

Initiate()

waiting

waitingStart()

executingAbort()
Fail()Start()

executingexecutingexecutingabortedfailedend(a) State transition diagram of avital compensatable element
Fig. 5.1

Commit()Abort()
Fail()

Retry()

Abort()

compensatedwaitingStart()

Compensate()end

waiting

Fail()

committed

start
Initiate()

Start()

Abort()

Retry()

failedabortedCommit()start
Initiate()

committed
Compensate()

failedabortedabortedfailedcommitted

committed
end

compensated(b) State transition diagram of anon-vital compensatable element

Commit()Fail()
Commit()(c) State transition diagram of avital non-compensatable element

end(d) State transition diagram of anon-vital non-compensatable element

State transition diagram for elementsb) The other possible ase is when we have a nonvital 5.2.6 WS-SAGAS Notations
element. If the rst andidate WS exe ution failed, the element's state is set to Failed, no exe ution retrial is attempted, and the exe ution of the whole WS-SAGAS is re- An investigation of most of the urrent CWS spe i ation
sumed, as if the element was su essful.
languages and approa hes showed that there are three main
The main differen e in pro essing a ompensatable ategories of notations adopted to depi t a CWS: (a) The
and a non ompensatable element be omes lear when an rst ategory uses an XML-based notation; BPEL [4℄ andelement is in the ommitted state and the exe ution of an- WebTransa t [39,40℄ are typi al examples. (b) The se ond
other vital element from the same WS-SAGAS annot be ategory opts for a graphi al notation for more expressiveretried so a ba kward re overy is ne essary. In su h a ase, ness and to over ome the omplexity of an XML-based noall the ompensatable elements in the ommitted state are tation; they typi ally use a standardized modeling notation to
des ribe CWS. Examples are state harts and UML modelsompensated and their state then be omes ompensated.
The ase of non ompensatable elements in luded in a typi al example is SELF-SERV [41℄or they dene aa WS-SAGAS requires spe ial onsideration be ause the is- proprietary notation, if the standard notations are not sufsue of mixing ompensatable and non ompensatable om-  iently ri h to a ommodate all the desired semanti s oftheir approa hes, e.g., eFlow [8℄. ( ) The third ategory prefers
ponents in the same transa tion is a dif ult problem.
In [38℄, the authors introdu ed a ommit proto ol to en- formal notations su h as p - al ulus or other pro ess algesure the ompensatable omponents are ommitted before bras be ause of their on iseness and power to analyze thethe ommitment of the non ompensatable omponents. semanti s and orre tness of the model [42℄.
The global ommit/abort de ision is determined by the outIn WS-SAGAS, we advo ate the use of three notations
ome of the non ompensatable omponents. If they abort,
all of the ompensatable omponents are ompensated. In be ause we are strongly onvin ed that one notation alone isour model, we extend this proto ol and we use mainly the inadequate to express all the semanti s of an approa h andstate on ept to allow the exe ution of a hierar hy of re ur- may not be suitable for different users. First, instead of ansively nested WS-SAGAS more exibly. A detailed dis us- XML-based notation, we propose a textual notation that an
be used to generate automati ally an XML-based notation
sion of this issue is in the following se tion.
of the CWS, when later implementing the system. Our textual notation is mu h less error prone, less omplex, more
5.2.5 Failure Re overy
human readable, and more easily modiable. The most important feature of our notation is that we exploit it to spe ify
The WS-SAGAS denes a ompensating element for ea h and onstrain the behavior of the different elements in a proelement, when possible. There are two hoi es when an el- ess and the intera tions between them. In addition, to omement fails to ommit (e.g., allo ated WS failure): the rst plement our textual notation and to dene a ommon solid
is to attempt the element exe ution retrial, whi h is a vari- foundation for omparison with other formal approa hes,
ant of the sagas forward re overy. However, the differen e is we propose a formal notation. We also dene a proprietarythat the same element is reattempted but with another WS. graphi al notation and we use this to illustrate a running
If the rst hoi e is not possible, then the se ond hoi e is example, be ause the standardized notations, su h as UML
ba kward re overy, in whi h the WS-SAGAS offers either diagrams, do not en ompass all the semanti s we required
to ompensate or to abort the elements to bring the overall for our model. Finally, to have a omprehensive notation of
CWS ba k to a onsistent state. We elaborate on this point a CWS, our three notations an be ombined or used sepain greater detail later in this se tion.
rately.

10

Neila BEN LAKHAL et al.

State i.k+1
inState i.k...

E i.k out

State i.kState i.k+1
in E i.k+1

...

Ei.k

...

E i.k+1 ...
..
.

out
out

in

...

E i.k out

E i.k+j

Ei.k out
..
.

State

in

E i.l

...

.
.
.

...

Ei.k+j out

State i.kinλtimes

E i.l
λ=1
λ

E i.k+j out(e) RendezVous pattern(f) Exclusive merge pattern

State i.k

Ei.k out.
.
.
State i.k+j

State i.l

Exclusivemerge

Statei.k+ji.k+j(d) Switch pattern

State i.l
Selective
merge

inλtimesEi.k+j out...

E i.k out...

State i.k+1

E i.l
Iterateλ =| S(E i.l)pre|(g) Selective merge patternFig. 5.2

Ei.k out

Statei.l
Rendezvous..
.

in E i.k+j

E i.k+j ...

State i.kStatei.k+jinState i.k+j

State i.k.
.
.

SwitchSelection(c) Selection pattern...

E i.k+1

E i.k out...

(b) Parallel pattern
State j.k+1
inin E i.k+1

State i.kState i.k+j(a) Sequence pattern

State i.kState i.k+1

in E i.k+1 out

λ Times(h) Iterative pattern

WS-SAGAS aggregation patterns

5.2.7 WS-SAGAS Aggregation Patterns

To dene the aggregation patterns, we propose building on
existing work on Workow patterns and on an analysis ofexisting Workow languages reported in [28℄. The following
motivated our hoi e: a) Control ow dependen ies en ountered in Workow modeling omply with the WS ontext,
be ause the situations they apture are also relevant in thisdomain. b) Existing languages for WSC, su h as BPEL and
BPML, were built on the basis of languages for Workow
modeling [43℄; therefore, we have a ommon basis for omparing our work with these approa hes. ) It is possible forour model to in orporate different aggregation patterns into
the same stru ture, whi h was not allowed with advan edtransa tion models proposed previously. By in orporating
the transa tion on ept with the different aggregation patterns we enable a exible and dependable WSC [18℄.
The analysis of existing Workow languages allowed us
to identify the relevant patterns ne essary to model the logi
of any pro ess, no matter what it is. We identied eightpatterns: sequen e, parallel, sele tion, swit h, rendezvous,sele tive merge, ex lusive merge, and iterative (see Figure5.2) [17,18℄. In [28℄, the authors introdu ed 20 patterns,
but we limited our study to eight of these and we deliberately ex luded the others (su h as the an ellation patterns or the state-based patterns) be ause those eight patterns, when ombined with the ompensation, the state, andthe vitality degree, are suf ient to express any pro ess that
our approa h an support. Existing Workow languages provided either a graphi al notation or an XML-like notation ofthese patterns and, to the best of our knowledge, there is no
standard notation for su h aggregation patterns. We have already identied the limitations of XML-like notation and des ribed why we prefer to dene our textual notation. We ontinue with the same line of thinking and propose a pro ess
algebrai approa h to formalize the des ription of our aggregation patterns. Instead of an informal notation, we propose
using pro ess algebras (PAs) be ause we are dealing withaggregation patterns that have semanti s and the orre tnessof their semanti s needs to be veried. PA ontributions inthis dire tion make them an interesting andidate.

FENECIA

11

5.3 WS-SAGAS Notation
The underpinning logi of a pro ess Pi , depi ted as a hierar hy of re ursively nested WS-SAGAS, is denoted by a 3tuple h i ; i ; i i formed by a textual notation ( i ), a graphi al notation ( i ), and a formal notation ( i ).

TGF
G

F

T

an element. The set of CR identies the relation of omposability between the different elements and WS-SAGAS(e.g., whi h WS-SAGAS is omposed of/ omposing whi h
WS-SAGAS/elements). Finally, the set of OR identies theordering ondition that every relation of omposability between the elements and pro ess must verify.

Denition 5.1 (Denition Rule of an Element )Let Ei k be an Atomi element from W S-SAGASi . DR(Ei k )is an ordered tuple that provides relevant information of an
A textual notation of a pro ess Pi (denoted i ) is formed Ei k , namely its name, des ription, state, vitality degree, transwith three different sets of Rules identied by the system a tional behavior, operation with its orresponding input
designers using the pro ess logi des ription: the set of Def- and output parameters, and its QoS attributes. We added only
inition Rules (DR), the set of Composability Rules (CR), and those attributes we onsidered to be fundamental in omposthe set Ordering Rules (OR).
ing WS; extending the DR expression with other attributes is
The DR,CR, and OR share the same tuple-like notation possible. We use the following notation of a DR of an elebut their semanti s differ be ause: (i) Ea h DR gives relevant ment, whi h is a spe ialization of the generi DR notation
information of an entity that either relates to the CWS spe - for an entity des ribed above:i ation (e.g., a pro ess, an element, a omponent, et .) orintervenes in the CWS exe ution (e.g., a WS, a oordinator,
DR(Ei k ) :hname; des ription; behavior; state;et .). (ii) Ea h CR spe ies the relation between the differtype; vitality; (operation  (in; out )); qosi ;ent entities dened by the different DR (i.e., how the entities
are ombined, how the entities intera t with ea h other, et .). where:(iii) Ea h OR denes the ondition that the relation between- name is the name of the element.
the different entities dened by the CR must verify (i.e., un- des ription is a on ise des ription of the element's
der whi h ondition entities are ombined, under whi h onmain semanti fun tionality.
dition entities intera t with ea h other).
behavior is the transa tional behavior of the element.
We propose the following tuple-like generi notations toThisattribute veries the ondition:dene a DR, a CR, and an OR:T

5.3.1 Des ription of Textual Notation ( i )

T

:

:

:

:

DR(Entityu) : hAttribute1; :::iDR(Entityv) : hAttribute2; :::iDR(Entityw) : hAttribute3; (Attribute4; Attribute5); :::iCR(Entityw) ! hEntityu; Entityvi
OR(Entityw) ! hEntityu op Entityvi ;where:
 Attribute is the relevant information about an Entity.
We dene the multipli ity of ea h attribute to indi ate
the Attribute o urren e number, that is, the number oftimes we may nd the attribute; we dene four formsof an attribute's multipli ity: i) The notation Attribute1
indi ates that Entityu may dene zero or several valuesof Attribute1. ii) The notation Attribute2 indi ates that
the Entityv must dene at least one value of Attribute2.
iii) The notation Attribute3 indi ates that this attributeis optional and at most one value an be provided. iv) An
attribute name with nothing next to it similarly to the attribute Attribute4 indi ates that one value only is to beprovided. v) Finally, Attribute4 and Attribute5 are assoiated and this is indi ated by the parentheses.
 CR(Entityw) indi ates that Entityw denes a omposability relation between Entityu and Entityv.
 op is the ondition that the omposability relation between Entityu and Entityv must dene.
Spe i ally, we dene DR to provide relevant information
about three different entities: a pro ess, a WS-SAGAS, andDR(Ei:k ):behavior 2 f ompensatable;
non- ompensatableg :- state des ribes the exe ution progress of the element.
- vitality is the vitality degree of the element. This attribute veries the ondition:
DR(Ei:k ):vitality 2 fvital; nonvitalg :- type is the element granularity: an element that has no
hildren is atomi . Otherwise the element is a parent ofa WS-SAGAS and its type is omposite.
- operation indi ates that an element may dene several values of operation, but at least one.
- in and out  are the different input and output parameters of the element.
- The different input and output parameters are asso iatedwith their orresponding operation by using parentheses; we may dene at least one operation, but input andoutput parameters are optional. For example, we may
have (operation1 (in1 ; in2 ; out1 )); (operation2 ()), for anelement with two operations, one of whi h is a void fun tion that takes no argument.
- qos are the different QoS attributes of the element,
whi h are estimated when the element is exe uted. We
denote this by qos tuples of attributes; for example, we
may have qos =< qos1 ; qos2 ; qos3 > to des ribe an element where we are interested in three parti ular QoS attributes: the exe ution time, the reliability, and the ost.

12

Neila BEN LAKHAL et al.

For ea h atomi ompensatable element Ei k verifying(DR(Ei k ):behavior = Compensatable and DR(Ei k ):type =Atomi ), we dene a ompensating element (denoted Ei0 k ).
This element is invoked if a failure later in the exe ution ofEi k makes it ne essary.
The o urren e of element Ei0 k after element Ei k restoresthe system to a state that is an a eptable approximation ofits state before the start of the exe ution. For every ompensating element, we may dene the denition rule of a ompensating element (exa tly DR(Ei0 k )), in the same way wedened it for an element.
:

:

:

:

:

:

:

:

- vitality is a redu tion of a tuple formed by ni 2 vitality
degrees, one for every atomi element aggregated in
W S-SAGASi a . We redu e this ni 2 -tuple to a one-value
tuple. If there is at least one vital element in a WSSAGAS, the overall WS-SAGAS is vital. However, a
WS-SAGAS is nonvital if all of its omposing elements are nonvital. These requirements are formulated
below:
 DR(W S-SAGASi a ):vitality = nonvital iff
f8Ei a 2 W S-SAGASi a j` 2 [1::ni 2 ℄g we have:(DR(Ei a ):vitality = nonvital ).
 DR(W S-SAGASi a ):vitality = vital iff
f9Ei a 2 W S-SAGASi a j` 2 [1::ni 2 ℄g that veries:(jDR(Ei a ):vitality = vital).
- behavior is a ni 2 tuple formed by the transa tional behaviors of the atomi elements in W S-SAGASi a . Its expression is:
;

:

;

:

:

: :`

;

: :`

:

Denition 5.2 (Denition Rule of a WS-SAGAS)
Let W S-SAGASi a be a subtransa tion formed by ni 2 elements and having as a parent the omposite element Ei afrom W S-SAGASi (see Equation 5.1).
DR(W S-SAGASi a ) is an ordered tuple that provides relevant
information on W S-SAGASi , spe i ally its name, des ripn[2tion, state, vitality degree, transa tional behavior, and QoS
attributes. The values of several attributes are dedu ed from DR(W S-SAGASi a ):behavior (DR(Ei a ):behavior) :=1
the attributes in the omposing elements of the WS-SAGAS.
:

: :`

:

;

;

: :`

:

;

:

:

i;

:

: :`

`

DR(W S-SAGASi:a ) : hname; des ription; behavior;state; vitality; qosi ;where:- Finally, qos are the different QoS attributes we onsider; we derive these on the basis of the qos attributesof the elements that appertain to the WS-SAGAS. We
des ribe how below.

Denition 5.3 (Set of Denition Rule of a Pro ess)
- name is the name identier of the WS-SAGAS.
- des ription is a on ise des ription of the WS-SAGAS; The set of DR that denes a pro ess Pi is derived below based
it ombines the des ription of the different elements that on the expression of a pro ess in (Equation 5.1):
appertain to this WS-SAGAS and veries:
iab ni a [b [DR(W S-SAGASi a ): des ription DR(E¶ )
DR(Pi )[ni ; mi ℄ DR(W S-SAGAS ): : : : : : i;mi: : : : :

:

n[2

`=

i;

`=

1



(DR(Ei:a:` ):des ription) : DR(W S-SAGASi ):DR(W S-SAGASi:a ):state 

i;

`=

i;

i;

;

n[2

¶ =i:1i:[n1DR(E¶ ))
¶ =i:1:n 2
S (DR(W S-SAGAS ) i:a[DR(E¶ ))i:a
¶ =i:a:1:b:n
S (DR(W S-SAGAS i:a):[DR(E¶ ))
i:a::b¶ =i:a::b:1:: :nS (DR(W S-SAGAS i:a:):b[
DR
(
E
)
:
i:a::b::¶¶ =i:a::b:: :1- state des ribes the exe ution progress of the subtransa tion W S-SAGASi a It is an ni 2 -tuple formed by the statesof the elements omposing W S-SAGASi a :
:

`

i



i; p

(DR(Ei:a:` ):state) :1

We assume that only the state of the vital elements affe ts the overall WS-SAGAS ommitment's de ision. In
addition, all the ompensatable elements must wait for
the non ompensatable elements from the same subtransa tion (i.e., nesting level) to be able to ommit theirwork. By putting together these two assumptions, we an
redu e the state of a WS-SAGAS to the set of states ofthe elements that verify the onditions:



i;m
i

Denition 5.4 (Composability Rule of a WS-SAGAS)
The next step in our modeling approa h is dening the Composability Rules (CR), essential in dening the nesting andomposition dependen y between the different WS-SAGAS.
A typi al CR of a WS-SAGAS is the spe ialization of then[2entity CR des ribed above. Below we des ribe the CR of
DR(W S-SAGASi a ):state  (DR(Ei a ):state) with: W S-SAGASi a , the se ond nesting level omposed of ni 2 el=1
ements:DR(Ei a ):vitality = Vital andCR(W S-SAGASi a ) ! hEi a 1 ;  ; Ei a n 2 i :DR(Ei a ):behavior = Non ompensatable :
i;

:

: :`

:

;

`

: :`

: :`

:

: :

: : i;

FENECIA

13

Denition 5.5 (Set of Composability Rules for a Pro ess)
In the different OR, op stands for operator and it deWe dene the set of CR for the pro ess shown in (Figure 4.1) pends on the ontrol ow that des ribes the pro ess in termsand (Equation 5.1):of elements and their exe ution ordering through different
onstru tors (e.g., sequen e, hoi e, parallelism, and syni a [b 
hronization).
CR(Pi )[ni ; mi ℄ (CR(W S-SAGAS ))Considering how business pro ess logi tends often to=iinvolve
omplex behaviors and apabilities, whi h are stru S CR(W S-SAGASi )tured in different ways, we need to enri h WS-SAGAS with
CR(W S-SAGASi a ) a set of onstru tors that broadens its potential s ope and
S CR(W S-SAGASi a  b ) 
make it suf iently ri h to sustain any business pro ess, no
S CR(W S-SAGAS
matter how omplex; this remains an ongoing problem in theiab ) ;area of transa tion models. The different operators are thewhere:
eight different aggregation patterns we dened on the basis! hEi 1 ;  ; Ei a ;  ; Ei n 1 i
CR(W S-SAGASi )of the seminal work in [28℄. To ll the gap aused by the absen e of a standard textual notation of the different patterns,! hEi a 1 ;  ; Ei a n 2 i
CR(W S-SAGASi a )we build on the formal notations and PAs.
::
: : : : :

`

`

:

: : :

: : : : :

:

:

: :

:

: i;

: : i;::::

CR(W S-SAGASi:a::b )! hEi a  b 1  Ei a  b n i

:
:
:

:
:
:

: : : :;;

F

5.3.2 Des ription of Formal Notation ( i ): : : : i; p

PAs [44℄ are formal des ription te hniques to spe ify software systems, parti ularly those formed from on urrent andommuni ating omponents. Numerous PAs have been proDenition 5.6 (Ordering Rule of a WS-SAGAS)
posed; well-known PAs are Milner's Cal ulus for CommuThe step that omes after identifying the different CR is the ni ating Systems (CCS) [45℄, Hoare's Communi ating SeOrdering Rules (OR) denition. The most important feature quential Pro esses (CSP) [46℄, and all their extensions, su hof this step is that ea h rule builds on the pro ess's prede- as the p - al ulus and LOTOS [44℄. These PAs dene typned semanti s to dene and restri t the exe ution depen- i ally simple onstru tions to des ribe dynami behavior,
den ies between the different elements/WS-SAGAS form- ompositional modeling, operational semanti s, behavioral
ing a pro ess (i.e., the orre t exe ution orders). For a WS- reasoning by model he king, and pro ess equivalen e.
SAGAS, if no OR is expli itly dened, then the order of thedifferent elements order is inter hangeable. Below we dePAs omply with the WSC issue be ause they allow des ribe the OR of W S-SAGASi a representing the se ond nest- s ription of formally dynami pro esses. In addition, their
ing level and omposed of ni 2 elements:
predened onstru ts are adequate to spe ify CWS, due totheir inherent omposability property [42℄.
OR(W S-SAGASi a ) ! hEi a 1 op  op Ei a n 2 i :Denition 5.7 (Set of Ordering Rules of a Pro ess)
There are a large number of existing PAs; the most adWe dene the different OR of the WS-SAGAS subtrans- equate formalism an be determined based on the desireda tions nested in the pro ess depi ted in (Figure 4.1) and expressiveness orientation. The en oding proposed in any of(Equation 5.1):
i a [b 
the PAs an be smoothly translated into any other standard
PA.
(OR(W S-SAGAS ))OR(Pi )[ni ; mi ℄ 
We hose to build on the Compensating CSP [47℄, a vari=i
ant of the CSP PA, be ause it already supports ompensaS OR(W S-SAGASi )tion
and reasoning for long-running transa tions. The atomi
OR(W S-SAGASi a ) 
events of CSP are used to model the elements of a WSS OR
W S-SAGASi a  b ) 
SAGAS; several atomi elements an be ombined using the
S OR((WS-SAGASi a  b  ) ;operators provided by the CSP language to support sequen ing, hoi e, and parallel omposition. In addition, to supwhere:
port failed transa tions, ompensation operators are inher!hEi 1 op  op Ei n 1 i
OR(W S-SAGASi )ited from the Compensating CSP. Finally, to allow more ad!hEi a 1 op  op Ei a n 2 ivan ed ombinations to support other aggregation patterns
OR(W S-SAGASi a )that WS-SAGAS requires to formalize the eight aggregation
:
:
:
:
:
:
patterns it dened but that CSP does not dene, we introdu ea set of advan ed aggregation operators.
OR(W S-SAGASi a  b ) !hEi a  b 1 op  op Ei a  b n i
CR(W S-SAGASi:a::b:: ) ! hEi:a::b:: :1 ;  ; Ei:a::b:: :n

i;m
i

i

:

:

;

:

: :

: : i;: : : : :

`

`

:

: : :

: : : : :

:

:
:
:

:

: :

: : :

: : : :: i;

: : i;: : : : i; p:::

OR(W S-SAGASi:a::b:: )!hEi:a::b:: :1 op  opEi:a::b:: :ni;mi

In formalizing WS-SAGAS, we des ribe a syntax in thespirit of CSP dened by the following grammar in BNF-like
i :notation:

14

Neila BEN LAKHAL et al.

G

5.3.3 Des ription of Graphi al Notation ( i )Pi F W S-SAGASi ` W S-SAGASi: (nesting)W S-SAGASi F [Ei:k ℄; [Ei:k+1 ℄(sequen e)j [Ei:k ℄ jj [Ei:k+1 ℄(parallel)j [Ei:k ℄ ? [Ei:k+1 ℄(arbitrary ordering)j [Ei:k ℄  ([Ei:k+1℄ jj [Ei:k+2 ℄) (sele tion)j [Ei:k ℄ C ([Ei:k+1 ℄ jj [Ei:k+1 ℄) (fork/ hoi e)j ([Ei:k ℄ jj [Ei:k+1 ℄)^[Ei:k+2 ℄ (join)j ([Ei:k ℄ ? [Ei:k+1 ℄)  [Ei:k+2 ℄ (sele tive merge)j ([Ei:k ℄ ? [Ei:k+1 ℄)  [Ei:k+2 ℄ (ex lusive merge)j l [Ei:k ℄(iteration)( ompensating pair) :[Ei:k ℄ F Eiv:k  E 0 vi:k j Eiv̄:k  Ei0:k v̄

where:

Our proposed graphi al notation of WS-SAGAS is shown in(Figure 5.2).
5.4 WS-SAGAS Transa tion Model: Exe ution Semanti s
and Corre tness
To eliminate ambiguities, to allow analysis and further reasoning regarding our transa tion model, and to fa ilitate its
omparison with other models, it is ne essary to dene ourmodel operational semanti s and orre t exe ution. Be ause
we are onsidering a peer-to-peer exe ution model, the useof stri t serializability poses severe limitations that are una eptable. The des ription of a pro ess in terms of DR, CR,
and in parti ular OR, partly ontributes to avoiding in onsisten ies be ause the different OR allow denition of theorre t ontrol ow in a pro ess.

the semanti s of ea h element are respe ted, Pi designates a pro ess and we represent it as a hierar- whenToeaensure
h element exe uted, in parti ular its nesting, transhy of re ursively nested WS-SAGAS by adopting the a tional behavior, and vitality degree, we build on the state
notation (W S-SAGASi ` W S-SAGASi  );on ept and dene several types of dependen ies that must W S-SAGASi  is the lowermost nested subtransa tion and holdbetween the different elements ombined in the samei  is to be repla ed by the subtransa tion identier;pattern; we term these intrapattern dependen ies. These de [Ei k ℄, [Ei k 1 ℄, and [Ei k 2 ℄ are elements from W S-SAGASi penden ies formulate the required onditions for a pattern to
:

:

:

:

:

+

:

+

where an element en losed between [ and ℄ an be a ommit and des ribe how failure re overy is performed. Beompensating pair of a vital or a nonvital element, ause every WS-SAGAS ombines elements following difif the element is dened as ompensatable;
patterned operational semanti s, to dene a orre t [Ei k ℄and [Ei k+1 ℄ represent the sequential onstru tion that ferent
WS-SAGAS on the basis of the different intrapattern depenombines two elements: [Ei k ℄ is exe uted rst, and only den ies, we des ribe another form of dependen ies, alled
when [Ei k ℄ terminates su essfully an [Ei k ℄ be exe uted; intra-WS-SAGAS dependen ies, that formulate the required
 [Ei k ℄ jj [Ei k+1 ℄ is a parallel omposition of two elements; onditions for a WS-SAGAS to ommit and des ribe how [Ei k ℄ ? [Ei k+1 ℄ represents the operator for onstru ting failure re overy is performed.
the exe ution of elements where the exe ution order isarbitrary; it an be in parallel, sequentially, or a ombiFinally, we formulate the onditions for orre t exe unation of these two;tion of a pro ess in terms of intrapro ess dependen ies by [Ei k ℄  ([Ei k+1 ℄ jj [Ei k+2 ℄) represents the sele tive hoi e taking as a basis the intra-WS-SAGAS dependen ies formuof [Ei k ℄, whi h sele ts whi hever of [Ei k+1 ℄ and/or [Ei k+2 ℄ lated for ea h WS-SAGAS appertaining to the hierar hy ofis to be enabled; [Ei k ℄ C ([Ei k+1 ℄ jj [Ei k+2 ℄) represents a parti ular ase of WS-SAGAS in the pro ess.
the sele tive hoi e operator be ause only one of [Ei k+1 ℄5.4.1 WS-SAGAS Pattern Exe ution Semanti sand [Ei k+1 ℄ is to be enabled; ([Ei k ℄ jj [Ei k+1 ℄)^[Ei k+2 ℄ represents where the elements Let W S-SAGAS be a subtransa tion from a hierar hy formia[Ei k ℄ and [Ei k+1 ℄ are syn hronized at a parti ular rening
a
pro
ess
P
i (Equation 5.1). W S-SAGASi a ombines a
dezvous point and must wait for ea h other to exe ute
olle
tion
of
elements
dened in CR(W S-SAGASi a ). This
the element that omes dire tly after them;S ([Ei k ℄ ? [Ei k+1 ℄)  [Ei k+2 ℄ represents where [Ei k ℄ and olle tion of elements is equal to i =a ina21 E .
We dene W S- pattern as the set of possible patterns de[Ei k+1 ℄ onverge but without syn hronization at a parti ular rendezvous point; the element that omes dire tly ned by ombining the CSP-like notation and the Workow
after them (i.e., [Ei k+2 ℄) is a tivated every time either of patterns:
these two elements rea hes the rendezvous point;
W S- pattern : fsequen e(; ); parallel (jj); arbitrary(?);
 ([Ei k ℄ ? [Ei k+1℄)  [Ei k+2 ℄ is a spe ial ase of (([Ei k ℄ ?
sele tion(); swit h(C); iterative(l ); rendezvous(^);[Ei k+1 ℄)  [Ei k+2 ℄); the differen e is that the rst elesele tivemerge(); ex lusivemerge()g :ment that terminates its exe ution a tivates the exe utionof [Ei k+2 ℄;The different patterns, with their dened operators, are used
 l [Ei k ℄ is l iteration of [Ei k ℄.
to write the set of OR, as des ribed above in this se tion.
:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

: : i;

:

:

:

`

:

:

:

:

:

:

:

:

:

:

:

:

: :

`

FENECIA

15

Depending on the pattern's semanti s, the operator of a
ing the elements that have to be aborted in luded in thepattern an be prexed (, C, l ), postxed (^, , and ),
pattern.
or inxed (;, jj, and ?). We dene for ea h pattern a s opethat delimits the elements within the rea h of that pattern S EQUENCE PATTERN ([Ei a k ℄; :::; [Ei a k+ j ℄)Si a k + j
and that should verify its semanti s.
We assume in what follows that the s ope of ea h pat- By =i a k E (Figure 5.2 (a)) we denote a set of elements
t extern in ludes only atomi elements between Ei a k and Ei a l , aggregated in a sequen e pattern. To ensure the Sorre
i k+ jeution
ofasequene,
weassume
that
among
E,
where the subs ripts of these two elements verify k < l <=i a k
there
must
exist
only
one
vital
non
ompensatableeleni 2 . The end of one s ope and the start of another is de ided
when a postxed or a prexed operator is en ountered in an ment. Where more than one vital non ompensatable elOR. Overlapping of elements between onse utive s opes ement is in luded in the sequen e, splitting the sequen e intois allowed. The ase of omposite elements is onsidered several sequen es is envisaged. Assuming thatv the vital
non ompensatable element in question is Ei a ¶ , it must
below in the des ription of the nesting semanti s.
We assume there is an entity that ontains the different verify the following onditions:DR, CR, and OR of the entire pro ess. On every exe ution ofDR(Ei a ¶ ):behavior = non- ompensatable andevery element of a pro ess, the element's state in this entity
DR(Ei a ¶ ):vitality = vital :is updated.
The entity that ontains all this information is transferred
The a tivation of the exe ution of ea h element requires
between elements (i.e., an engine or an authority responsible
thetermination of ea h dire t prede essor. More formally,
for the exe ution of the element) as the exe ution pro ess
letE
be an element verifying f` 2 [i:a:k :: i:a:k + j℄g; the exadvan es. We also assume that ea h element keeps a opyeution
of E requires the su essful termination of its dire tof this entity until the end of the pro ess instan e exe ution.
prede
essor,
if it is vital (i.e., DR(E v 1 ):state = Committed),
Therefore, any element an know the set of elements thatandtheterminationof its prede essor, even with a failure
ome after and before it.
(i.e.,
DR(E v̄ 1 ):state = Failed), if it is nonvital.
To des ribe the patterns' semanti s, we dene for ea h
The ommitment of the sequen e of elements depends
pattern several types of dependen ies that formulate the onv
onE
i a ¶ ; more formally, the intra ommitment dependen yditions that the elements in the pattern must satisfy to a tivate, ommit, interrupt, ompensate, or abort the pattern of this pattern is spe ied as:exe ution. The on ept of dependen ies is strongly related  intra (sequen e) veri ation requires that (C ONDITION
to the on ept of state. We dene ve types of dependen y.
S1) and (C ONDITION S2) are valid:
Ea h dependen y is denoted by intrasupers ript ( pattern), where(C ONDITION S1.) The sequen e an attempt to ommit
the supers ript is repla ed with an abbreviation of the typeiff DR(Ei a ¶ ):state = Committed.
of dependen y and the pattern is dened in W S- pattern:(C ONDITION S2.) If the previous ondition is valid, thenthe sequen e an be ommitted iff
 intraa ( pattern) is an intrapattern exe ution a tivation
dependen y and des ribes the ondition(s) that must be
8E j` 2 [i:a:k :: i:a:k + j℄ verifying: DR(E ):vitality =veried for the elements ombined in the pattern to startvital; we have: DR(E ):state = Committed:
exe ution.
 intra ( pattern) is an intrapattern exe ution ommitment If the set of elements ombined in the sequen e does not endependen y that des ribes the ondition(s) required forompass any vital non ompensatable element, then thethe pattern to be su essfully terminated.
intra
ommitment dependen y veri ation requires satisfa  intrai ( pattern) is an intrapattern exe ution interruption tion only of (C ONDITION S2).
dependen y that des ribes the ondition(s) where, if verIf (C ONDITION S2) is not veried, that is:ied, the exe ution of the whole pattern is in a situation
where forward re overy is insuf ient to suppress a fail9E j` 2 [i:a:k :: i:a:k + j℄ that veries: DR(E ):state =ure and a ba kward re overy is required.
Failed and DR(E ):vitality = vital:
When intrai ( pattern) is valid, depending on the patternexe ution progress and from its omposing elements, an then the two onditions we dene below, (C ONDITION S3)
intrapattern exe ution ompensation dependen y and/or and (C ONDITION S4), are evaluated. Subsequently, a ba kintrapattern exe ution aborting dependen y is/are trig- ward re overy is triggered in the same way whether a sequen e in ludes a vital non ompensatable element orgered.
 intra p ( pattern) is an intrapattern exe ution ompensa- not.
tion dependen y that formulates the ondition(s) that, if
An extreme situation is when the set of elements omveried, ensure the onsisten y of the exe ution by trig- bined in the sequen e are ompensatable and nonvital;
gering a ompensation me hanism.
in su h a ase, even if all the elements fail, the pattern intra intraa( pattern) is an intrapattern exe ution aborting de- interruption dependen y is dedu ed and it has no effe t onpenden y that formulates the ondition(s) where, if veri- the overall WS-SAGAS, be ause a nonvital WS-SAGASed, the onsisten y of the exe ution is ensured by abort- su ess is not riti al for the overall pro ess ommitment.
: :

: :

: :

`

: :

`

: :

: :

:

`

;

: :

: :

: :

`

`

`

`

: :

: :

`

`

`

`

`

`

: :

`

16

Neila BEN LAKHAL et al.

Assume that the element Eiva ¶ was attempted a number When intra p (sequen e) is veried, the sequen e exe utionof times with different WS but none of those attempts was is:
su essful; this me hanism is a tually a forward re overy
where an element is reattempted with different WS. In this
v
v
v
v
0v
0v
ase, the element is assumed to have failed and a ba kward[Ei a k ; Ei a k+1 ; :::; Ei a ¶ ; :::; E i a k+ j ; ::::; E i a k+1 ; E i a k ℄re overy is triggered, whi h implies the veri ation of theintrainterruption dependen y of this sequen e pattern; more
We assume that the exe ution of every ompensating eleformally:
ment, su h as E 0 vi a k+1 , is su essful and does not fail. Its ex intrai (sequen e) veri ation requires that (C ONDITION e ution is performed by exe uting a previously mapped WS
that an reverse the effe ts of the WS that was mapped toS3) is valid:v(C ONDITION S3.) The exe ution of the sequen e pat- Ei a k+1 . The failure of ompensation is onsidered beyond
thes ope of this paper be ause it remains an unresolved
tern is interrupted iff DR(Ei a ¶ ):state = Failed isomplexissue.
veried.
: :

: :

: :

: :

: :

: :

: :

: :

: :

: :

Depending on the exe ution progress of all the other eleS
ments in the sequen e (i.e., i =k+i aj k E Ei a ¶ ), the veri ation of intrai (sequen e) may trigger an intrapattern ompensation dependen y, an intrapattern aborting dependen y, orboth. More formally:

PARALLEL PATTERN ([Ei a k ℄; ([Ei a k+1 ℄jj:::jj[Ei a k+ j℄)) is
the notation of this pattern. Let (Ei a k )su be the set of all
the elements that are dire tly ordered after Ei a k and that arepresumed to be exe uted on urrently, and (Ei k )su be asubset that only ontains the subset of elements that is exe intraa(sequen e) denotes an intrapatterni aborting depen- uted effe tively. The ontent of (Ei k )su depends on theden y in a pattern; it requires that intra (sequen e) was aggregation pattern semanti s (Figure 5.2(b)). For a parallel pattern, all the elements in (Ei a k )su must be a tivatedveried and that (C ONDITION S4) is valid:(C ONDITION S4.) The intrapattern aborting dependen y after Ei a k . This means that: (Ei a k )su = (Ei a k )su .
The a tivation of the exe ution of the elements in the set
holds and there are elements in the sequen e that ver(E
ify:
i a k )su requires that Ei a k su essfully terminates its
exe
ution
(i.e., DR(Eiva k ):state =Committed), where it is
9E j` 2 [i:a:k :: i:k + j℄ we have : DR(E ):state = vital. Otherwise, it may terminate in any other state, without affe ting the exe ution progress.
Exe uting and DR(E ):vitality = vital:
Assume that the set (Ei a k )su ontains one or sevThe veri ation of (C ONDITION S4) implies that the valid- eral vital non ompensatable elements. For this pattern
ity of intraa (sequen e) and that all the elements that veried to ommit, a spe ial syn hronization me hanism needs to be(C ONDITION S4) are aborted.
added to inform the different elements of the progress of theothervital non ompensatable elements in the same pat intra p (sequen e) denotes an intra ompensation
depen- tern. The syn hronization me hanism must guarantee thatden y in a pattern; it requires that intrai (sequen e) was either all or none of the vital non ompensatable eleveried and that (C ONDITION S5) is valid:ments are ommitted.
(C ONDITION S5.) The intrapattern ompensation depenThe ommitment of this pattern depends on the vitalden y is satised and there are elements in the senon ompensatable elements' exe ution progress.
quen e that verify:
More formally, the intrapattern ommitment dependen yintra( parallel ) is spe ied as:
E 2 j` 2 [i:a:k :: i:k + j℄; we have: DR(E ):state =Committed and DR(E ):vitality = vital:
 intra ( parallel ) veri ation requires that (C ONDITION
P1) and (C ONDITION P2) are valid:
The veri ation of (C ONDITION S5) implies that the valid(CONDITION P1.) The set of elements an attempt topity of intra (sequen e) is veried and that all the elements
ommit iffthat veried (C ONDITION S5) are ompensated for.
8
Ei a ¶ 2 (Ei a k )su g verifying:>
To explain ompensation performan e, assume that we< f8
DR(Ei a ¶ ):behavior = non- ompensatable andhave the following sequen e from W S-SAGASi a ; we noteDR>
: (Ei a ):vitality = vital; we have:that an element pla ed between [℄ is a tually a ompensatable
DR(Ei a ¶ ):state = Committed:
element:
:

`

`

: :

: :

: :

Q

: :

: :

: :

S

: :

Q
S

: :

S

: :

S

:

:

: :

: :

Q

: :

: :

: :

`

`

S

`

`

: :

`

`

: :

S

: :

: :

:

: :`
: :

sequen e : [Eiv:a:k ℄; [Eiv:a:k+1 ℄; :::; Eiv:a:¶ ; :::; [Eiv:a:k+ j ℄The exe ution of the different elements veries:

8Ei a jk  ¶ DR(E ) state = Committed and8Ei a j¶  k + j DR(E ) state = Exe uting
: :`

: :`

`<

<`

;

`

;

:

`

:

(C ONDITION P2.) If the previous ondition is valid, thenthe parallel pattern an be ommitted iff
8Ei a 2 (Ei a k )su and DR(Ei a ):vitality = vital;
we have: DR(Ei a ):state = Committed:
: :`

S

: :

: :`

: :`

FENECIA17

If the set of elements

S (Ei a k )does not en ompass any
vital non ompensatable element, then the intrapatternommitment dependen y veri ation requires only the satisfa tion of (C ONDITION P2).
: :su

 intra p( parallel ) denotes an intrapatternompensationi

dependen y; it requires that intra ( parallel ) was veried
and that (C ONDITION P5) is valid:(Condition P5.) The intrapattern ompensation dependen yholds and we have:8>< 9Ei a 2 (Ei a k )su that verify:

If (C ONDITION P2) is not veried, that is:
9Ei a 2 (Ei a k )su verifying:

S
v

: :`

: :

DR(Ei:a:` ):state = Failed;then the onditions, (C ONDITION P3) and (C ONDITION
P4), have to be evaluated, and subsequently, a ba kward reovery is triggered orresponding to the denition below fora parallel pattern that ombines vital non ompensatableelements.
An extreme situation is when all the elements in the set(Ei a k )su are nonvital.
Even if all the elements fail, the intrapattern ommitment
dependen y is dedu ed and the failure of this WS-SAGAS
has no effe t on the overall pro ess, as a nonvital WSSAGAS su ess is not ru ial for the overall pro ess ommitment.
Assume that one or more elements from the set of vital
non ompensatable elements were attempted a number oftimes with different WS but none of those attempts was su essful. Similar to the sequen e pattern, these elements are
assumed to be failed and a ba kward re overy is triggered,
whi h implies the veri ation of the intrapattern interruption
dependen y of this parallel pattern; formally:

S

S

: :`

: :

 intrai ( parallel ) veri ation requires that (C ONDITION

P3) is valid:(C ONDITION P3.) The exe ution of the parallel patternis interrupted iff
8 v< 9Ei a ¶ 2 (Ei a k )su that veries:
DR(Ei a ¶ ):behavior = non- ompensatable;: we have:DR(Ei a ¶ ):state = Failed:: :DR(Ei:a:` ):behavior = ompensatable;DR>: (Ei:a:` ):state = Committed, andDR(Ei:a:` ):vitality = vital:

The veri ation of (C ONDITION P5) implies that the validity of intra p ( parallel ) is veried and that all the elementsthat veried (C ONDITION P5) are ompensated for. We des ribe below how ompensation is performed: Assume thatthe only vital non ompensatable element is Eiva ¶ and it
has failed. Assume also that:
8Ei a 2 (Ei a k )su Ei a ¶ , we have: DR(Ei a ):vitality= vital and DR(Ei a ):behavior = ompensatable:
: :

S

: :`

: :

: :`

: :

: :`

If the exe ution progress of these elements veries:
8Ei a 2 (Ei a k )su Ei a ¶ , we have:
: :`

S

: :

: :

DR(Ei:a:` ):state = Committed:

then, when intra p ( parallel ) is veried, the ompensation
order is:vv

[Ei:a:k ; ((Ei:a:k+1

jj Eiva ¶ jjE vi a k j ); (E 0vi a k j jj jjE 0vi a k 1 ))
:::

:::

: :

: :

+

: :

+

:::

: :

+

We assumed that Eiva k is vital and ompensatable. We
emphasize that this element an be nonvital; however, it
must be ompensatable. Otherwise, a ba kward re overy
would not be possible, be ause a non ompensatable element's
effe ts, on e ommitted, annot be undone. If the underpinning pro ess logi requires a parallel pattern with Ei a k nonompensatable, a plausible solution is to insert an idempotent
between Ei a k and the set of elements to be exe uted
Depending on the exe ution progress of all the other on uron
urrently.
rent elements ombined in the same pattern, the veri ationiof intra ( parallel ) may trigger an intrapattern ompensation
dependen y, an intrapattern aborting dependen y, or both. S ELECTION PATTERN ([Ei a k ℄  ([Ei a k+1 ℄jj:::jj[Ei a k+ j℄)).
Formally:
This pattern is a spe ial ase of the parallel pattern, whereatleast one and at most all the elements from (Ei a k )sua intra ( parallel ) denotes an iintrapattern aborting depen- ould
be sele ted. After exe uting the element Ei a k , a sele den y; it requires that intra ( parallel ) was veried andtion
onditionis evaluated to hoose from the set of its dire tthat (C ONDITION P4) is valid:suessors(Ei a k )su . Building on the assumption of equal(C ONDITION P4.) The intrapattern aborting dependen yholds and there are elements in (Ei a k )su that ver- probabilities for the different hoi es, Ei a k an hoose from( (Ei a k )su ), the power set of(Ei a k )su , whi h is theify:
set of all subsets of (Ei a k )su (Figure 5.2( )).
The exe ution ommitment, interruption, aborting, and9Ei a j 2 (Ei a k )su we have: DR(Ei a ):state = ompensation
obey the same dependen ies dened for the
Exe uting and DR(E ):vitality = vital:
parallel pattern. The only differen e is that the hosen set of
The veri ation of (C ONDITION P4) implies the validity of elements from ( (Ei a k )su ) must verify the onditions:intraa ( parallel ). It entails that all the elements that veried (Ei a k )su  (Ei a k )su
and(Ei a k )su , 0/ :(C ONDITION P4) are aborted.

S

: :

: :

: :

: :

: :

: :

: :

: :

: :

: :

Q
: :

S

: :`

S

: :

PQ

: :

Q

: :

: :

Q

Q

: :

: :

: :

: :`

`

S

: :

PQ
Q

: :

: :

S

: :

: :

18

Neila BEN LAKHAL et al.

S WITCH PATTERN ([Ei a k ℄ C ([Ei a k+1 ℄jj : : : jj[Ei a k+ j ℄)).
Similarly, this pattern is a spe ialization of the Sele tion pattern (see Figure 5.2(d)). It differs in that only one element
an be hosen from (Ei a k )su , the set of elements thatomes dire tly after Ei a k . Similarly, by dening (Ei a k )su
as the subset hosen from ( (Ei k )su ), it must verify thefollowing onditions:(Ei a k )su  (Ei a k )su ;(Ei a k )su , 0/ andj (Ei a k )su j = 1 :On every element termination, Ei a l is a tivated again.
Let (Ei a l )pre be the subset hosen from ( (Ei a l )pre )and let l = j (Ei a l )pre j. In this ase, l represents the upper bound of the interval of time the element Ei a l an bea tivated.
As (Ei a l )pre an ombine vital and nonvital elements, the ondition for the a tivation of the exe ution of
Ei a l varies be ause a su essful termination for a vitalelement is equivalent to a ommitment; nevertheless, for anonvital element it an be any other state. More formally:
Assume that at least one of the elements in (Ei a l )pre is
The exe ution ommitment, interruption, abortion, andvital, that is, the following ondition is veried:ompensation obey the same dependen ies dened for theparallel pattern.
: :

Q
: :

S
S

Q

: :

: :

S

: :

PQ

S

: :

S

S

PQ

: :

: :

: :

S

: :

:

: :

: :

:: :

: :

: :

: :

: :

S

: :

f9E¶ 2 S (Ei a l ) jDR(E¶ ) vitality = vitalg
: :

:

pre

R ENDEZVOUS PATTERN (([Ei a k ℄jj : : : jj[Ei a k+ j ℄)^[Ei a l ℄).
Assume that (Ei a l )pre is the set of elements that are the di- If the above ondition is veried, the a tivation ondition
re t prede essors of the element Ei a l . This pattern restri ts for Ei a l is veried and its exe ution is started every time thethe ommitment of a set of elements exe uted in parallel following ondition is valid:
as follows: all the vital elements in (Ei a l )pre must be
ommitted for Ei a l to start exe ution. Therefore, the eleE¶ 2 (Ei a l )pre jDR(E¶ ):vitality = vital
ment Ei a l a tivation requires that the intra ( parallel ) dewe have: DR(E¶ ):state = ommitted :penden y of the elements in (Ei a l )pre is veried. Whenintra ( parallel ) is veried, Ei a l exe ution starts.
To ensure onsistent exe ution, Ei a l needs to know the arThe ommitment of this pattern depends on Ei a l progress; dinality l of (Ei a l )pre . This an be dedu ed by referring to
the intrapattern ommitment dependen y is formulated as OR's ontent. An in remental ounter needs to be in reased
follows:
on every a tivation of Ei a l . When this ounter rea hes l ,thepattern ommitment is veried. The intrapattern om intra (rendezvous) veri ation requires that (C ONDITION mitment
dependen y is formulated as follows:
R1) is valid:(C ONDITION R1.) The exe ution ommitment an be  intra (sele tive merge) veri ation requires (C ONDITION
dedu ed iff :SM1) to be valid:
(C
ONDITION SM1.) The pattern ommitment an be dev
DR(Ei a l ):state = ommitted or
du ed iff :v̄
DR(Ei a l ) :state = failed;
8
Assume that Ei a l is ompensatable and vital, and a fail- < DR(E v ):state = ommitted orial
ure that ould not be resolved by a forward re overy o DR(Ei a l )v̄ :state = failed (i.e., be ause Ei a l an be vitalurred. In su h a ase, a ba kward re overy must be trig- : or not); and the ounter rea hed l :gered. A ba kward re overy me hanism requires undoing
the effe ts of all the elements in (Ei a l )pre . However, thismay not be possible in the ase where we have (Ei a l )pre If (C ONDITION SM1) is veried, a ba kward re overy is
triggered. The ba kward re overy in ludes all the elements
verifying the following ondition:in(Ei a l )pre . Depending on their vitality degree and ex
9E¶ 2 (Ei a l )pre verifying:e ution progress, an intrapattern ompensation dependen yDR(E¶ ):behavior = non- ompensatable
and/or abortion dependen y may be triggered, the same asthat dened for the previous parallel pattern. However, a
In this paper, we assume that in this pattern, (Ei a l )pre in- riti al situation may o ur when Ei a l is a tivated l times
ludes only ompensatable elements.
and some of these a tivations fail and require a ba kward
re overy. In su h a situation, in onsisten ies o ur, espeS ELECTIVE M ERGE PATTERN (([Ei a k ℄?:::?[Ei a k+ j ℄)  ially if Ei a l is non ompensatable. To deal with this situa[Ei a l ℄). Consider the ase where two or more elements ome tion, we assume that Ei a l and all the elements in(Ei a l )pre
together but without syn hronization. Assume no elements are non ompensatable and in the rst failure of Ei a l , theare ever exe uted in parallel (Figure 5.2(g)).
whole pattern failure is dedu ed and a ba kward re overy
Let (Ei a l )pre = fEi a k ; :::; Ei a k+ j g be the set of all the is performed. Ei a l is ompensated rst, then the different
elements that are the dire t prede essors of the element Ei a l . elements in (Ei a l )pre are either ompensated or aborted,
The exe ution of Ei a l annot be a tivated unless either of in view of their exe ution progress. This is performed underthe elements appertaining to (Ei a l )pre has terminated.
the same onditions as formulated for the parallel pattern.

Q

: :

: :

: :

: :

: :

Q

: :

: :

S

: :

Q

: :

: :

: :

: :

S

: :

: :

: :

: :

: :

: :

: :

: :

: :

Q

Q

Q

: :

: :

S

: :

: :

: :

Q

: :

: :

: :

: :

: :

: :

: :

S

: :

: :

Q

: :

: :

: :

: :

: :

Q

: :

S

: :

: :

FENECIA19

 5.4.2 WS-SAGAS Patterns Corre t Stru turing

E XCLUSIVE M ERGE PATTERN (([Ei:a:k ℄? ::: ?[Ei:a:k+ j ℄)[Ei:a:l ℄)) is a point in a WS-SAGAS where the exe ution of

We dene a set of aggregation patterns that ombines a olle tion of elements in different ways. A WS-SAGAS is dened by onne ting a number of patterns in order to satisfy
a parti ular business rule logi . Putting together different
patterns permits the denition of a wide range of pro essunderpinning semanti s. However, some of these pattern ombinations may lead to in onsisten ies in the ontrol ow. To
avoid this, we need to differentiate the permissible pattern
ombinations from the pattern ombinations that may ausein onsisten ies. Moreover, we need to dene the orre t order of ombination. To this end, be ause the pro ess logi
is en ompassed in the different OR it denes, we need to Assume that (Ei a l )pre ontains only vital elements: dene
the permissible ombinations that we use to say if an(C ONDITION EM1.) The a tivation of the exe ution of OR is orre t or if it has onsisten y oni ts.
Ei a l requires that only one vital element has been
Let pattern1 and pattern2 be two patterns to be denedommitted and it is the rst to be ommitted; more in W Spattern andthat have overlapping s opes (i.e., they
formally:ome one after the other and have overlapping s ope of el8
ements); to obtain a orre tly stru tured WS-SAGAS, the< 9DR(Eiva ):state = ommitted anddesigner must observe several restri tions:v
v
8E 2 (Ei a l )pre fEi a g, we have:: DRi(aE¶v ):state If pattern1 = parallel , then pattern2 an be either a, ommitted:
ia
rendezvous pattern or a sele tive merge pattern.
 Assume that (Ei a l )pre ontains only nonvital elements: If pattern1 = swit h, then pattern2 an be only an exlusive merge pattern.
(C ONDITION EM2.) The a tivation of the exe ution of If pattern1 = sele tion, then pattern2 an be either a
Ei a l requires that only one nonvital element has
sele tive merge pattern or an ex lusive merge pattern.
terminated and it is the rst to do so; more formally:8
5.4.3 WS-SAGAS Subtransa tions Exe ution Semanti s< 9DR(Eiv̄a ):state 2 f ommitted,failed,aborted,
ompensatedg and 8Eiv̄a ¶ 2 (Ei a l )pre fEiv̄a g;: we have: DR(E v̄ ):state 2 fexe uting; waitingg: Every WS-SAGAS forms a olle tion of elements assemia¶
bled following different aggregation patterns. Therefore, theUpon satisfa tion of either of the above onditions, the exe- exe ution of the WS-SAGAS depends on the exe ution ofution of Ei a l an be started. The ommitment of this pat- the different patterns it omposes. We formulate the exeution semanti s of a WS-SAGAS in terms of intra-WStern depends on Ei a l progress.
SAGAS dependen ies and we dene four types of dependen intra (ex lusive merge) veri ation requires that the fol- ies. Let W S-SAGASi a be a subtransa tion and patterni a its
lowing ondition, (C ONDITION EM1), is valid:ordered set of patterns des ribed by OR(W S-SAGASi a ). Let(C ONDITION EM1) The pattern ommitment an be de- pattern be the rst pattern in pattern , and pattern
i a1
ia
ia
du ed iff :the last pattern.

intraa (W S SAGASi a ) is an intra-WS-SAGAS a tivation
DR(Eiva l ):state = ommitted or
dependen y. It pla es onditions on the different intrapatDR(Ei a l )v̄ :state = failed;tern dependen ies formulated for the different patterns in
If Ei a l is ompensatable and vital and a failure that an- patterni a . Let patterni a1 and patterni a2 be two onse unot be handled using forward re overy o urs, the same as- tive patterns from W S-SAGASi a . For patterni a2 exe ution
sumption made for the rendezvous pattern applies for failure to be a tivated, patterni a1 must have terminated its exe ution. We do not restri t the termination to a su essful omhandling.
mitment be ause a pattern an be a olle tion of nonvital
I TERATIVE PATTERN ([Ei a k ℄; l [Ei a k+1 ℄) is a point in a elements.
intra (W S-SAGASi a ) is an intra-WS-SAGAS ommitment
WS-SAGAS exe ution where the exe ution of a parti ular
dependeny. It pla es onditions on the different intrapatelement Ei k+1 must be repeated l times (Figure 5.2(h)).
terndependenies formulated for the different patterns in
The number of iterations depends on the pro ess semanti s.
patterni a . A WS-SAGAS an ommit if all the patterns that
This pattern is a spe ial ase of the sele tive merge pattern;
the only differen e is when (Ei a l )pre is a set that ontains ontain at least one vital element are ommitted. More forintra (W S-SAGASi a ) is valid iff :only one element. It follows that the pro essing is the same mally,
as for the sele tive merge pattern, if we repla e Ei a k by
8 patterni a 2 patterni a where 9Eiva ¶ 2 patterni a ;(Ei a l )pre and Ei a k+1 by Ei a l .
we have: intra ( patterni a ) is veried.

two or more elements onverge but without syn hronization (see Figure 5.2(f)). In ontrast to the sele tive merge
pattern, this pattern assumes that only one element is exeuted and its exe ution su ess triggers the dire t su essor
Ei a l only on e. (Ei a l )pre ontains the elements within thes ope of this pattern and is where any of them may trigger
the exe ution of Ei a l ; we assume that all the elements from
(Ei a l )pre have the same probability of triggering the exeution of Ei a l .
A tivation of the exe ution of Ei a l requires the veri ation of either of the two following onditions:

Q

: :

Q

: :

: :

: :

: :

: :

Q

: :

: :

Q

: :`

: :

: :

: :`

: :`

Q

: :

: :

: :`

: :

Q

: :

: :`

: :

: :

: :

:

:

:

:

:

: t

:

: :

: :

:

: :

:

:

:

:

:

: :

: :

:

:

S

S

:

: :

:

: :

: :

: :

: :

:

`

:

: :

: `

:

`

20

Neila BEN LAKHAL et al.

If any of the patterns in W S-SAGASi a that ontain at least
one vital element were interrupted by a failure and a ba kward re overy was triggered, then the WS-SAGAS failure isdedu ed. More formally, intrai (W S-SAGASi a ) is valid iff
9 patterni a 2 patterni a where 9Eiva ¶ 2 patterni a ;we have: intrai ( patterni a ) is veried:
:

:

: `

:

: `

: :

: `

Assume that patterni a1 and patterni a2 are two onse utive
patterns from W S-SAGASi a , and patterni a2 is verifying theabove ondition. Therefore, intrai (W S SAGASi a ) is veriedand it requires that all the patterns in patterni a have to reover.
Every pattern a tivates impli itly the intrapattern interruption dependen y of its prede essor when its own intrapattern interruption dependen y is veried and terminated.
This is ensured by every su essive pattern having overlapping s opes.
:

:

:

:

:

:

5.4.4 WS-SAGAS Nesting Semanti s

5.4.5 Pro ess Exe ution Semanti s

We assume a peer-to-peer exe ution model of a pro ess Pi
depi ted as a hierar hy of re ursively nested WS-SAGAS,
whi h in turn are olle tions of aggregated elements. We denote a pro ess exe ution instan e by Pix where x is ranging in[1::a ℄ and a designates the number of invo ations of the proess. The exe ution of a pro ess instan e assumes a dynami
WS dis overy and andidate sele tion. For ea h pro ess exe ution instan e, we have a set of DR, a set of OR, and a setof CR : DR(Pix )[ni ; mi ℄, CR(Pix )[ni ; mi ℄, and CR(Pix )[ni ; mi ℄.
A su essful termination of a pro ess exe ution instan e
is rea hed when all the vital WS-SAGAS forming the hierar hy are su essfully ommitted and that the invo ation
order of the olle tion of elements forming the hierar hy of
WS-SAGAS is orre t against the pres ribed order. Moreformally, the following onditions are satised: inter (Pix ) is veried and OR(Pix )[ni ; mi ℄ respe ted the same pres ribed order dened in OR(Pi )[ni ; mi ℄.

In the des ription of all the patterns semanti s, we assumedxthat all the elements were atomi . However, we have de- intra (Pi ) is an intrapro ess ommitment dependen y. It puts
ned our pro ess with multinesting levels where an element onditions on the different intra-WS-SAGAS dependen ies
an be at the same time part of one WS-SAGAS and par- formulated for the different WS-SAGAS in Pi . A pro ess an
ent of another WS-SAGAS. The element Ei a is in luded in ommit if all the xvital WS-SAGAS are ommitted. Moreformally, intra (Pi ) is valid iff:
W S-SAGASi and therefore it is regarded as atomi elements
in the same nesting level, that is, f8E 2 CR(W S-SAGASi )8W S-SAGAS 2 Pi verifying DR(W S-SAGAS ):vitality =fEi a gg, E does not know that Ei a is omposite. That is, if vital; we have: intra(WS-SAGAS ) is veried:the exe ution progress of the elements in W S-SAGASi rea hes
the omposite element Ei a the exe ution of W S-SAGASi a If any of the vital WS-SAGAS in Pi were interrupted byis triggered. However, for the other elements in W S-SAGASi , a failure and a ba kward re overy was triggered, then the
we assume that the exe ution delegation is totally transpar- whole WS-SAGAS failure is dedu ed. A failure is as aded
ent in the sense that the other elements in W S-SAGASi are up and down the hierar hy. More formally, intrai (Pi ) is valid
only waiting for the exe ution of the element Ei a .
iff:
On the other hand, Ei a is the parent of the subtransa - 
9W S-SAGAS 2 Pi verifying DR(W S-SAGAS ):vitality =tion W S-SAGASi a . Consequently, the ommitment of Ei a invital; we have: intra (WS-SAGAS ):W S-SAGASi is equivalent to the intra (W S-SAGASi a ). Therefore, in the intra ommitment dependen y of every patternthat has Ei a in its s ope, we have to repla e the ondition:
5.5 Illustrative Example
DR(Ei a ):state = ommitted byintra (W S-SAGASi a ) is veried. Similarly, all the intrainterruption, intra ompensation, and intra-abortion depen- We spe ify the trip reservation pro ess P1 using our dened
den ies for ea h pattern, in luding a omposite element textual, graphi al, and formal notations. The travel itinerary
reservation pro ess P1 [n1 ; m1 ℄ is des ribed as a hierar hy ofwithin its s ope, should be revised likewise.
WS-SAGAS
omposed of n1 = 6 elements distributed overIn the same way, another form of exe ution dependen ym= 2 nesting levels. The rst level is W S-SAGAS1 that2
is required to guarantee that the nesting relation betweenv
the WS-SAGAS forming a pro ess is respe ted. We intro- ombines n1 1 elements: a tripv information registration (E1 1 ),element (E1 2 ), a hotel reservation element
du e another form of dependen y, inter-WS-SAGAS nesting a ight-bookingv ), and a ar rental element(E(E1v̄ 4 ). The se ond nesting
13
dependen y to ensure that ommitment of W S-SAGASi dev
pends on W S-SAGASi a and that failures of W S-SAGASi a level is W S-SAGAS1 3 that has as a parent vE1 3 that ombinesn1 2 elements: a reserve room element (E1 3 1 ) and a reserve
should also be as aded to W S-SAGASi . More formally:
restaurant
element (E1v̄ 3 2 ). To ea h atomi element, a omLet W S-SAGAS and W S-SAGAS¶ be two subtransa is dened: E1v01 is the ompensating eletions in Pi (i.e., ` and ¶ are dened in [i::i:a:  :b:  : ℄). pensating velementv0 is the ompensating
ment
of
E
,
E
element of E1v 2 , E1v03 1
11
12
There is an inter-WS-SAGAS nesting dependen y between
is the ompensating element of E1v 3 1 , E1v̄03 2 is the ompenW S-SAGAS and W S-SAGAS¶ , we note:nsating element of E1v̄ 3 2 , and E1v̄04 is the ompensating eleinter (W S-SAGAS ; W S-SAGAS¶ ) iff:
f9E¶ 2 CR(W S-SAGAS )j DR(E¶ ):type = ompositeg. ment of E1v̄ 4 .
:

`

:

`

`

:

`

`

:

:

:

:

:

`

:

`

`

:

:

:

:

;

:

:

:

:

:

:

:

:

;

: :

: :

`

:

:

:

:

: :

`

`

: :

`

:

:

: :

: :

FENECIA

21

DR(W S-SAGAS1 ) : hname = WS-SAGAS1 ;Travel reservation process (P1)

14
[
:

in

v

des ription =v

P1 [2,6]1

out(travel reservation)state =

WS-SAGAS1

in

in

E1.2 out

v

v'

E1.2
E

out

(travel information)

Rendezvous

E
E1.1

v

E1.4 out

in

E1.4
E

(reserve hotel)

WS-SAGAS1.3

State1.3.1
inState1.3.2

v

E1.3.1 out

in(reserve room)out(reserve restaurant)

'
v'
v

v'

E1.3.1E

Startv

E1.3.2 out

inE1.3.2
E

in

End

out

Fig. 5.3

pro ess

DR(E¶ :behavior)i :CR(P1 )[n1 ; m1 ℄  CR(W S-SAGAS1 )[E element
State statev vitality degree(text) description

input data
output data

Composite element

Atomic element¶ =1:1

Composability Rules:

flow
Legend[
1:4

DR(E1v:1 ) : hname = E1:1 ; des ription = travel
information ; type = atomi ; state = Waiting;vitality = vital; operation1 ((in1 = destination ;in2 = depart ; in3 = return ; in4 = name);(out1 = destination; out2 = depart;out3 = return;out4 = name));qos1 = reliability; qos2 = exe utionTime i :v'

Ev1.3 outinDR(E¶ :state); vitality = vital;out(rent car)State 1.3v'

behavior =State1.4(book flight)

E 1.1 out

¶ =1:1v

in¶ =1:1:

State1.2

State1.1

14[DR(E¶ :des ription);

Compensating element

WS-SAGAS graphi al notation: example of a trip reservation

CR(W S-SAGAS1:3 ) :CR(W S-SAGAS1 ) ! hE1v:1 ; E1v:2 ; E1v:3 ; E1v̄:4 i
CR(W S-SAGAS ) ! hE v ; E v̄ i :
1:3

1:3:1

1:3:2

Ordering Rules:

OR(P1 )[n1 ; m1 ℄  OR(W S-SAGAS1 )We assume that a potential user of the pro ess has to provide his desired destination, his desired departure and returndates, and his name. As QoS attributes, we assume that weare only interested in knowing the exe ution time and thereliability.

[

OR(W S-SAGAS1:3 ) :OR(W S-SAGAS1 ) ! hE1v:1 ; (E1v:2 jjE1v:3 )^E1v̄:4 i
OR(W S-SAGAS ) ! hE v ; E v̄ i :
1:3

1:3:1

5.5.2 Graphi al Notation:
5.5.1 Textual Notation:

1:3:2

G1

(Figure 5.3) is an illustrative example of how a trip reservation pro ess P1 is spe ied using the WS-SAGAS transa tion model graphi al notation.

T1

The textual notation of P1 is formed by the triplet ombining
the list of DR, the list of CR, and the list of OR, as des ribed 5.5.3 Formal Notation: 1
below.
Denition Rules:
The formal notation of the pro ess P1 is des ribed below
using the syntax, in the spirit of CPS, that we dened:

F

DR(P1 )[n1 ; m1 ℄ 

13
[
:

`=



DR(W S-SAGAS` )1

 DR(W S-SAGAS1 )
[

[

1:3:2

¶ =1:1[
1:4¶ =1:1

DR(W S-SAGAS1:3 )P1 = W S-SAGAS1 ` W S-SAGAS1:3
W S-SAGAS = [E v ℄; ([E v ℄jj[E v ℄^[E v̄ ℄)DR(E¶ )1

DR(E¶ )[

1:3:2

¶ =1:3:1

1:1v= (E1:1

v̄
(E

1:4


DR(E¶ )W S-SAGAS1:3
:

1:2
:

1:4

:

 E v̄0 ))

v
= [E

1:3

 E1v01 ); (((E1v 2  E1v02 )jjE1v 3 )^
1:4

:

:

v̄

1:3:1 ℄; [E1:3:2 ℄v= (E1:3:1

 E1v03 1 ); (E1v̄ 3 2  E1v̄03 2 )
: :

: :

: :

:

22

Neila BEN LAKHAL et al.

trols and that provides the required fun tionalities from theelement Ei k . Therefore, the engine is responsible of the invo
ation, exe ution and ompletion, failure information, and
6.1 Motivations
re overy of Ei k .
An engine allo ated to an element Ei k is denoted as eipk
The FENECIA approa h dened the WS-SAGAS model todes ribe how a business pro ess is spe ied. However, the and it ontrols a WS denoted as wsipk , where the subs ript
WS-SAGAS remains only a spe i ation be ause it dealt i:k is kept the same as the element to whi h it is allo ated
only with modeling and did not onsider the evident need of and the supers ript  p is a unique identier ranging over
a CWS ena tment model to have a omprehensive methodol- [1::jCEL(Ei k )j℄, with jCEL(Ei k )j the ardinality of CEL.
ogy that ta kles the WSC issue from all its different aspe ts.
We assume that there are two types of engines. The rst
To this end, in the FENECIA approa h, we investigated the type of engine is allo ated to atomi elements and is reissue of CWS exe ution.
sponsible for the invo ation, exe ution and ompletion, failTypi ally, a CWS an be organized in either a entral- ure information, and re overy; we all this type engine exized or a distributed fashion. We refer to the exe ution mode e utor and we denote it as eeipk . The se ond type of engines
as entralized when a single oordinator or engine, su h as is responsible for omposite elements. An engine allo atedthe BPWS4J engine, exe utes a CWS developed, for exam- to a omposite element ontrols an overall WS-SAGAS;
ple using BPEL4WS [4℄. In ontrast to a distributed model we all this the engine oordinator and we denote it as e ipa .
where data are transferred dire tly between two points, in a
Assume that for a parti ular value q of p in eeipk , the enentralized model all data must go through the oordinator.
q
the element Ei k . Then, in
The oordinator may thereby be ome a performan e bottle- gine eei k ommitted su essfully
q
su
h
a
s
enario,theengineee
isresponsible
for generating
ne k and onstitute a single point of failure. In addition, alik
the
CEL
of
the
dire
t
su
essorsoftheelement
it ontrols;
lowing a large amount of irrelevant data to traverse the oordinator may overload the network and ause poor s alability this is how the exe ution progresses in THROWS. However,if the engine fails, then a forward re overy an be attemptedand signi ant performan e degradation.
To ope with the revealed inadequa y of the exe ution of if there are other engines in the CEL; otherwise, a ba kward
CWS with a entralized ontrol in FENECIA, we opted for re overy is triggered.
The CEP, using the state on ept dened in WS-SAGAS
a distributed model and we present THROWS ar hite ture,andwith every element being updated with every state hange,
whi h is an a ronym for a Transa tion Hierar hy for Route
Organization of Web Servi es, where the omposition exe- allows for information about failures to be olle ted and theution ontrol is distributed [19℄ over multiple engines, ea h ba kward re overy me hanism to be realized, as des ribedallo ated to an element from a pro ess depi ted as a hierar- in WS-SAGAS. On the other hand, the CEL allows an inhy of re ursively nested WS-SAGAS transa tions. Rather rease in the han es for the exe ution of a CWS ommit
than ommuni ating through a entral authority, the engines by realizing the forward re overy me hanism, des ribed inommuni ate dire tly with ea h other to transfer data and WS-SAGAS. In the future, both the CEL and CEP, be auseof their ontents, an serve as a solid base for investigating
delegate exe ution ontrol when required.
and analyzing the reasons for failures that have o urred ifthey are stored in a history that olle ts the exe ution logs ofdifferent
CWS.
6.2 General Assumptions and Des ription of THROWS
To
returnto the engine oordinator, assume that Ei a is a
Ar hite ture
omposite element from the pro ess des ribed by (EquaWhen the exe ution progress rea hes Ei a , an enIn THROWS ar hite ture, the exe ution ontrol of a pro ess tion 5.1).
p
Pi depi ted as hierar hy of re ursively nested WS-SAGAS is gine e i a is allo ated to Ei a . Be ause Ei a is pthe parent of theallo ated to dynami ally dis overed engines. To ensure high subtransa tion W S-SAGASi a , the engine e i a has to initiate
availability of distributed exe ution of the CWS, we make the exe ution of W S-SAGASi a .
available on ea h engine side the following information: theThe parti ularity of e ipa as engine oordinatoris that
CEL (Candidate Engines List) and the CEP (Current Exe u- it has no unique WS under its ontrol; therefore, it does nottion Progress).
invoke any WS. Instead, it has to generate the CEL of the
In THROWS, for ea h atomi element Ei k from a sub- rst element in W S-SAGASi a , that is, CEL of Ei a 1 . Then,transa tion W S-SAGASi , a CEL is generated by sear hing for an engine eeipa 1 is sele ted and the exe ution pro eeds until
WS that have apabilities satisfying the element Ei k fun - it rea hes the last element in W S-SAGASi a ; we assume thistionalities. To ea h dis overed WS, an engine is allo ated, element is Ei a n 2 and it is allo ated to an engine eei a n 2 .
and together, they are stored as a ouple, engine-ws, in the This engine, when it terminates the exe ution of the element,
CEL of the element Ei k , denoted as CEL(Ei k ). That is, CEL(Ei kreturns)
exe ution ontrol to the engine parent of the entire
is an ordered set of engine-ws ouples, and every time an subtransa tion W S-SAGASi a , that is, to the engine oordielement is to be exe uted, CEL(Ei k ) is generated and an nator e ipa . The engine oordinator e ipa resumes exe ution
engine-ws ouple is allo ated. When allo ated to exe ute a termination of element Ei a by updating the state of Ei a inparti ular element Ei k , the engine exe utes the WS it on- line with the overall state of W S-SAGASi a .
6 THROWS Ar hite ture

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

: :

: :

:

:

: : i;::: : i;

:

:

:

:

:

:

:

:

:

FENECIA

23

We des ribe the oordination between engine oordinator and engine exe utor below in this se tion.
In des ribing our exe ution ar hite ture, we only onsider the ase where all the elements in a pro ess Pi areompensatable. The ase of a pro ess that in ludes one
or more non ompensatable elements is addressed in our
future work.
In sear hing for WS that mat h an element's fun tionalities, we assume only simple mat hing based on the element's predened operations in its DR and the WS des ription in luded in its WSDL. We onsider only simplied onditions that an be developed in a future work. We assume
that we an determine easily and automati ally whether a
WS and an element are semanti ally equivalent. To date, assessing the similarity of WS to a hieve the best mat h is ana tive area of resear h. We an apply one of the available
proposals ranging from keyword-based methods to ontologies and reasoning algorithm-enri hed methods. We onsider the applied WS dis overy and sele tion methods beyond the s ope of this paper.

Denition 6.2 (Engine Coordinator (e ipa )) An engine oordinator (denoted e ipa ) is allo ated to ontrol the exe ution
progress of a omposite element Ei a aggregated in a subtransa tion W S-SAGASi and the parent of another subtransa tion W S-SAGASi a . Be ause an engine is an entity that relates to the CWS exe ution, we dene it using the following
spe ialization of the generi DR introdu ed in the pre eding
se tion:
:

:

:

:

p
DR(e i:a ) = hname; des ription; CR(W S-SAGASi:a )i ;where:- name is ne essary to identify the engine oordinator;- des ription is a on ise des ription of the fun tionalities of the engine e ipa . It veries::pDR(e i:a ):des ription  DR(W S-SAGASi:a ):des ription- CR(W S-SAGASi a ) has the same ontent as CR spe iedin the pre eding se tions. This ontent is required for theengine oordinator to know the elements it is responsiblefor invoking. In parti ular, as des ribed above, e ipa has
to generate the CEL of the rst element in W S-SAGASi a ;therefore, it requires full knowledge of CR(W S-SAGASi a ).
:Denition 6.1 (Engine Exe utor (eeipk )) An engine exe utor eeipk is allo ated to ontrol the exe ution of a WS W Sipk
that provides apabilities satisfying the fun tionalities of aparti ular atomi element Ei k from a W S-SAGASi .
Denition 6.3 ( The Candidate Engine List of an Atomi
Be ause an engine is an entity that relates to the CWS Element (CEL(Ei k ))) For ea h atomi element Ei k fromexe ution, we dene it using the following spe ialization of W S-SAGASi we dene CEL as the list of andidate engines
the generi DR introdu ed in the pre eding se tion:
potentially enabled to exe ute Ei k (i.e., they ontrol the exe ution of WS providing the same semanti s as Ei k ). GenDR(eeipk ) = hname; des ription; wsdlLink; e ip ;erating CEL is the responsibility of the dire t prede essor(operation  (in; out ))i ;of the element, that is, when the exe ution of Ei k by a ertain engine eeqi k is ommitted. Then, the engine exe utor
where:
eeqi k must allo ate the exe ution ontrol to another engine to- name is ne essary to identify the engine exe utor;- des ription is a on ise des ription of the apabilities progress the pro ess exe ution by generating the CEL of its
dire t su essor; we assume it generates CEL(Ei k+1 ), andof the WS ontrolled by the engine eeipk ;thenit sele ts an engine eeipk+1 and delegates the exe ution- wsdlLink is the lo ation of the WSDL of the WS onontrol to that engine.
trolled by the engine eeipk ;Depending on the element it ontrols (i.e., order in the- (operation  (in; out )) are the different operations that
WS-SAGAS's
OR), an engine may have to generate onlypa parti ular WS W Si k an provide with their orrespondone
CEL, many CELs, or it may not have to generate any.
ing input and output parameters;- every rst and last engine exe utor ontrolling the rst
In addition, generating the CEL of a parti ular element
and last element in a subtransa tion, respe tively, must
might
be the responsibility of only one engine, or it mightknow the engine oordinator that ontrols the subtransbe
theresponsibility of several engines. We show in whata tion they relate to.
follows
that distinguishing one ase from another depends
This is required be ause the WS-SAGAS exe ution starts
ontheontentof OR(W S-SAGASi ):by re eiving the ontrol from the engine oordinator, andwhen the exe ution of the last element terminates, this 1. (Ei k op (Ei k+1 op Ei k+2 op : : : op Ei k+ j )) where every
element has to inform the oordinator of its termination
prexed operator veries op 2 fjj; ; Cg: In this ase, theand of its exe ution results. However, be ause a WSengine responsible for exe uting the element Ei k on nSAGAS exe ution may be subje t to failure and interishing su essfully Ei k has to generate the CELs of all
rupted before rea hing the last element, ideally we mustthe elements in (Ei k )su (the subset of elements homake this information available in all the elements. Moresen for exe ution from all the dire t su essors of Ei k ).
pre isely, in (Equation 5.1), assume that e ip is the engine
If we assume that eeqi k is the engine that was allo ated tooordinator that initiated the exe ution of the subtransEi k and has ommitted it, then the generated CELs of alla tion and that was allo ated W S-SAGASi ; then, in every
the elements in (Ei k )su is denoted CEL( (Ei k )su ),engine exe utor ontrolling an element from W S-SAGASi ,and the set of the sele ted engines (ea h for ea h element
we have the information e ip made available.
from (Ei k )su is denoted (eqi k )su ;
:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

S

:

:

:

:

S

:

S

:

S

:

S

:

:

24

Neila BEN LAKHAL et al.

2. ((Ei k opEi k+1 op Ei k+2 op : : : op Ei k+ j ) op Ei l ) where
every postxed operator veries op 2 f^; ; g : In
this ase, CEL(Ei l ) is generated by the engine(s) responsible for exe uting the element(s) in (Ei l )pre (the subset of elements being exe uted from all the dire t predeessors of Ei l ); if we assume eeipl to be the engine sele ted to exe ute Ei l , then this set of engines is denotedp(eei l )pre ;3. As dened in (Equation 5.1), Ei n 1 is the last element inthis WS-SAGAS and does not have to generate any CEL.
We use the following notation for CEL(Ei k ):


q
1
2
CEL(Ei k ) = DR(eei k ); DR(eei k ); :::; DR(eei k ); ::: (6.1)
;
:

:

:

:

S

:

:

S

:

:

:

:

:

: i;

:

generate REL(Ei a ), whi h is a list of repli a engines. Thisavoids failure, be ause if one of the engines in REL(Ei a )fails, another engine takes harge of the exe ution instead of
the failed engine. The information in the different engines isontinuously updated to avoid having any obsolete information. Moreover, any update/information that rea hes any of
the repli a engine oordinators in REL(Ei a ) is transparently
broad ast to all the others. We use the following notation for
REL(Ei a ):


q
1
2
REL(Ei a ) = DR(e i a ); DR(e i a ); :::; DR(e i a); ::: (6.2)
:

:

:

:

:

:

:

:

where:
 the number of repli a engines in REL(Ei a ) is variableand depends on the designer's judgment;
where:qDR(e i a ) is assumed to be the DR of the repli a en the number of dis overed engines in CEL(Ei k ) is varigine oordinator that was allo ated to Ei a , whi h wasable and depends on WS availability.
q
not subje t to a failure, and whi h ontains the last up DR(eei k ) is assumed to be the DR of the engine exe utor
dated information on erning the exe ution progress ofthat was allo ated to Ei k and was su essful in its exeW
S-SAGASi a .
ution. Every time the exe ution of an element Ei k fails,
it is allo ated a new engine from the CEL(Ei k ), dened Denition 6.5 (The Current Exe ution Progress (CEP))
with DR(eeipk ) and p 2 [1::jCEL(Ei k )j℄.
We dene the on ept of CEP to keep tra k of the exe ution
ursively
Be ause ea h nonvital element has to be attempted progress of a pro ess, depi ted as a hierar hy of rep
only on e, the ardinality of the different CELs of all the nested WS-SAGAS. When an engine exe utor eei k exe utes
nonvital elements from W S-SAGASi must verify the on- an atomi element Ei k , every hange in that element's state
has to be ree ted on the opy of the CEP, stored lo ally
dition:on the engine exe utor eeipk side. The CEP ontent is madev̄v̄v̄f8Ei k jEi k 2 W S-SAGASi : jCEL(Ei k )j = 1g
available on ea h engine (exe utor and oordinator).
On every engine exe utor, only one type of CEP opy is
However, be ause the su essful ommitment of all the vital
available.
Consider the pro ess depi ted in (Equation 5.1),
elements is essential, the probability of their su ess must be
where
a
opy
of CEP of W S-SAGASi , whi h is stored on thein reased by generating CELs verifying the ondition:engine exe utor eeipk , is formulated as:
f8Eivk jEivk 2 W S-SAGASi : jCEL(Eivk )j > 1g!
!
p
It is possible that throughout the exe ution of the different CEP(W S-SAGASi ;eei k ) : DR(Ei 1 ) op  op DR(Ei k ) op
instan es of the same element, an engine generates a CEL!(E ) op  op DR!(E ) ;that ontains multiple andidate engines and that in almost op DR
ia
in 1
all exe ution instan es, the element exe ution was ommitted by the rst allo ated engine.
where:
Consequently, the time spent in generating the CEL on!
stitutes an overhead. It is required to determine for ea h  DR(Ei k ) is dened as the A tive DR of the element Ei k :it is equal to the DR of the element Ei k to whi h an atelement the most suitable value of the ardinality of CEL,
tributeengine is added, indi ating the name of the urwhi h allows the element to be su essfully terminated, but
rentlyallo
ated engine to the element; this notation isin addition, avoids the risk of having to trigger a re overy
used
to
indi
ate that the element Ei k is allo ated to enonly be ause there is no available andidate engine. This angine eeipk . The last value of the attribute engine is the
be possible by onsidering and analyzing the exe ution hisvalue of the engine that either ommitted the element or
tory of the different elements.
failed to ommit it. !
Denition 6.4 ( The Repli a Engines List of a Composite  initially, the attribute DR(Ei k ):engine is set to null in
Element (REL(Ei a ))) The REL of a omposite element is
all the elements' a tive DR in CEP.
dened in the same way as an atomi element. However,  Ei 1 and Ei n 1 are, respe tively, the rst and the last eleit does not require any WS dis overy or sele tion. The main
ment of the subtransa tion W S-SAGASi .
differen e is that an REL ontains the repli as from the same  op is the operator that onne ts the different element
engine oordinator. That is, assume a omposite elementwith op 2 fjj; ; ; ?; C; ^; ; ; g . Depending on the
Ei a is the parent of a W S-SAGASi a in Pi . When the exeonsidered operator, it an be prexed (e.g., l , C, and ),
ution ontrol rea hes Ei a , instead of generating a CEL, bepostxed (e.g.,^, , and ), or inxed (e.g.,jj and ;).
ause this element is omposite it makes its prede essor(s)
:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

: i;

:

:

:

:

:

:

:

:

:

:

:

: i;

FENECIA

25
ecip
CEP(WS - SAGASi , ecip )in Process Pi [ ni , mi ] out

in

Ei.1

in

out

Ei.a

in

(description)

E 'i.1

...

in
out

...

atomicelement
compositeelement

...

out

in

engineexecutorenginecoordinator

in

in

in

CEL( Ei.a.2 )

...

...

...

out

in

Ei.a.*.b.ni . p(description)

E 'i.a.b.*.ni , p

...

...

...

statei.a.*.b.*.c.1

Ei.a.*.b.*.c.1

out

...

in

E 'i.a.*.b.*.c.1

CEP (WS - SAGAS i.a , ecip.a )i,2eeip.a.ni,2
CEP(WS - SAGASi .a , eeip.n )

...

i,2

ecip.aCEP (WS - SAGASi.a.u , ecip.a.u )CEP (WS - SAGAS i.a , eeip.a.1 )

...

...

CEP (WS - SAGAS i .a , ecip. a.u )

...

..

...
CEP (WS - SAGASi.a .*.b.*.c , eei.pa.*.b.*.c.n )i , mieeip.a.*.b.*.c.1

Ei.a.*.b.*.c.ni , mi out(description)out

CEP(WS - SAGASi. a , eeip.n )CEP (WS - SAGAS i , ecip.a )CEL( Ei.a.u +1 ) CEL( Ei.a.u.1 )CEP (WS - SAGAS i.a.u , ecip.a.u )

out

i ,1

ecip

CEP (WS - SAGAS i.a , ecip.a.u )

...

i ,1

CEP (WS - SAGAS i , eeip. n )...

ecip.a.u

CEP(WS - SAGASi.a , eeip.a.1)

ecip.aeeip.nCEL( Ei.a+1 ) CEL( Ei.a.1 )eeip.a.1

out

E 'i.a.n2

WS - SAGASi.a.*.b.*.cstatei.a.*.b.*.c.ni .mi(description)

CEL( Ei.2 )CEP (WS - SAGASi , eeip.1 )statei.a.*.b.ni . p

E 'i.a.*.b.1...

CEP/CELout...

WS - SAGASi.a.*.b

Ei.a.*.b.1(description)

Ei.a.n2(description)

...

...

ecip

CEP (WS - SAGAS i.a , ecip.a )instatei.a.*.b.1

compensating
elementout

E 'i.ni .1(description)(description)

E 'i.a.1

out

ecip.aCEP (WS - SAGAS i , ecip.a )statei.a.n 2

Ei.a.1in

Ei.ni , 1

ineeip.1
CEP (WS - SAGAS i , eeip.1 )WS - SAGASi.astatei.a.1
inout

statei.ni ,1(description)

Legendcontrol flow
input
parameters
outputparameters

...

i ,1

CEL( Ei.1 )WS - SAGAS i
statei.astatei.1

CEP(WS - SAGAS i , eeip. n )CEP(WS - SAGASi , ecip )out

ee ip.a .*.b .*.c .n...

CEP (WS - SAGASi.a.*.b.*.c , eeip.a.*.b.*.c.1 )i ,m i

CEP (WS - SAGASi.a .*.b.*.c , eei.pa.*.b.*.c.n )i ,m i

CEL( Ei.a.*.b.*.c.2 )E'i.a.*.b.*.c.ni ,miCEP (WS - SAGAS i.a.*.b.*.c , eeip.a .*.b.*.c .1 )WS-SAGAS transa tion model exe ution in THROWS ar hite ture: ontrol delegation and CEP ex hange between engine oordinatorand engine exe utor

Fig. 6.1

Be ause we onsider a hierar hy of nested WS-SAGAS, wehave different CEP expressions, one for every nesting level.
More pre isely, onsider the pro ess in (Equation 5.1). Pi isformed with mi nesting levels. Therefore we have mi different CEP, one for ea h WS-SAGAS.
Be ause we onsider a peer-to-peer exe ution model, theonly onne tion point between two subtransa tions in two
onse utive nesting levels, su h as W S-SAGASi in nestinglevel 1 and W S-SAGASi a in level 2, is the engine oordinator responsible for the omposite element Ei a , parent of
W S-SAGASi a and part of W S-SAGASi . The important roleof an engine oordinator be omes apparent here be ause every engine exe utor is the onne tion point level and onstitutes, similar to the bridge that delegates the exe ution ontrol from one level to another.
Assume that the engine oordinator e ipa was allo atedto the omposite element Ei a from W S-SAGASi . On being
allo ated to exe ute the element Ei a , this engine re eives
a opy of CEP(W S-SAGASi ; eeipa 1 ) from its dire t predeessor (i.e., assume it is an engine eeipa 1 allo ated to anelement Ei a 1 ).
Be ause Ei a is omposite, the engine oordinator e ipa
has to initiate the exe ution of W S-SAGASi a ; therefore, it
has to generate a CEL of Ei a 1 and must provide it with theopy of CEP(W S-SAGASi a ; e ipa ). Therefore, on e ipa , wehave two CEPs: the rst is CEP(W S-SAGASi ; eeipa 1 ) andthe se ond is CEP(W S-SAGASi a ; e ipa ). In this way we anstart the exe ution of another nested level. The ontent of
CEP(W S-SAGASi a ; e ipa ) is des ribed in the same way asp
CEP(W S-SAGASi ; eei a 1 ).
::When the exe ution of W S-SAGASi a terminates, e ipa
has to resume exe ution ontrol. On re eiving a opy of
CEP(W S-SAGASi a ; eeipa n 2 ), it dedu es its own state on thebasis of the exe ution progress of the whole WS-SAGAS
and has to generate a CEL for Ei a+1 its dire t su essor in
W S-SAGASi sele t an engine, and allo ate exe ution ontrol to it; assume the allo ated engine is eei a+1 , if Ei a+1 is
atomi . In this ase, engine e ipa sends to eei a+1 a opy of
CEP(W S-SAGASi ; e ipa ) (see Figure 6.1).
:::: : i;

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

6.3 Collaboration between Peer Engines and Web Servi es
To exe ute a WS-SAGAS, the engines in THROWS ar hite ture ommuni ate by the different messages that we dene. All the messages are sent in a peer-to-peer fashion, thatis, from the sour e to the destination without going throughany entral entity, as they would for entralized exe ution.
Consequently, performan e bottlene ks should de rease.
In what follows, the distin tion between an engine exe utor or oordinator is only made when the pro essing differs.

:

: :

:

:

:

:

:

:

:

:

:

6.3.1 Conversation between Peer Engines:

Messages ex hanged between peer engines ontain:(i) The urrent exe ution progress (CEP): After an engine
is hosen to be in harge of a parti ular element, it has to
be informed of the CEP ontent (last-updated version).

26

Neila BEN LAKHAL et al.

To guarantee that the ne essary information for any potential re overy is still available, we assume that the CEP
ontent is preserved in the side of every engine until theend of all the WS-SAGAS exe utions.
Therefore, even if a message sent between two engines is
dis arded or does not rea h its destination for any reason(e.g., network broken, time out), it is possible to submit itagain. We note that CEP ontains the exe ution ontext(e.g., input/output variables, servi es invo ation results)
ne essary for ea h WS invo ation.

(ii) The exe ution start signal, abortion request, and ompensation request: These messages enable a syn hronizedtransa tional exe ution of CWS. However, they are notsuf ient. We also need spe ial syn hronization messages to ontrol delegation of the exe ution ontrol between engines to prevent ra e onditions o urring, andimproper ontrol ow signals may be triggered, leading
to possible in onsisten ies.
Considering that in our ar hite ture, we are onstrained by a
distributed and loosely oupled environment, the distributed
two-phase ommit proto ol (2PC) annot apply, be ause theAtomi ity property and the lo king me hanisms on whi h it
is founded are not required and a entral monitor's existen e
is undesirable.
There are a number of proposed proto ols for distributedand loosely oupled environments, in luding BTP [48℄, WStransa tion [25℄ with WS- oordination [49℄, and WS-CAF[26℄. Not all the available WS support the same proto ol,
so instead of using any of these proto ols, for exibility
in THROWS ar hite ture we introdu ed the predelegation
phase, the syn hronization phase, the peer-engines waiting
period, and the engine-ws waiting period: The predelegation phase: During this phase, a rst entity(one or more engines) agrees that it will release exe ution ontrol while a se ond entity (one or more engines)
agrees that it is ready to a ept delegation of the ontrol. This phase is ne essary at the beginning of ea h element exe ution. Introdu ing su h a phase redu es thepotential for an ellations (e.g., engine not ready) and
improves the probability of su essfully ompleting theomposite WS exe ution. The rst entity sends a ontrol
delegation request and it is assumed to re eive a ontrol
delegation agreement from the se ond entity.
 The syn hronization phase: This phase follows dire tly
after the predelegation phase where one or more elements has to be exe uted in parallel. To ensure this, different engines, on re eiving a start signal propagated bytheir dire t ommon prede essor, start the exe ution simultaneously.
 Peer engines waiting period: This is the estimated periodof time, after whi h the engine does not re eive any onrmation or agreement, so the message for ontrol delegation ignores that engine and hooses another engine
from the CEL as a new andidate for ontrol delegation;
then, the predelegation phase is repeated.
 Engine-web servi e waiting period: It is most likely thatan engine exe utor ontrolling a WS, for an unknown

start
Generate (CEL(Ei.k))[CEL (Ei.k) not Empty]

WaitingEngine:=e1i.kStatei.k:=Executing
Commit()Update(CEP)[start_signal received] [Finish_Signal received]
State:=Committed
Execute(Ei.k, e1i.k)
Update(CEP)
Finish()Abort()[abort_request received]
Statei.k :=Aborted
Update(CEP)

Executingerror()[failure detected]
Statei.k:= Failed
AbortedUpdate (CEP)
Propagate (failure)

Finish()Failed[vital]Allocate()[CEL(Ei.k) not empty]
Engine:=e2i.kStatei.k:=Executing Committed
Update(CEP)
Execute(Ei.k,e2i.k)[vital][non-vital]
Allocate()[CEL(Ei.k) Empty] Resume(Successors)
Finish(Ei.k)
Back_Recovery()Compensate()
Finish()[compensate_request received]
end
State
:=CompensatedFinish()i.kGenerate(CEL(successors)) Update(CEP)
Finish()CompensatedState transition diagram of an atomi
ment exe uted in THROWS ar hite ture

Fig. 6.2

ompensatable ele-reason (e.g., failure) does not re eive a response message
from the WS for a time; in some ases, the waiting time,as an answer time may even tend to be innite, whi h
is una eptable. To avoid this, a similar situation to theabove o urs. We dene this as the engine-ws waiting
period. It avoids the engine exe utor waiting eternallyfor an answer that may never ome: if the WS fails to respond after the engine-ws waiting period has elapsed andno information was re eived of the exe ution progressof the WS, then the engine exe utor must onsider itself
failed and a re overy must be triggered.

6.3.2 Conversation between an Engine Exe utor and a WS:

The different messages that are used to ommuni ate between an engine exe utor and a WS are dened a ording
to the WS exe ution progress and they are hiey of two
forms:
 The engine exe utor sends a noti ation of exe ution
start to ask the WS it ontrols to start exe uting. At thesame time it provides the WS with the ne essary input
data for its exe ution.
 When a WS nishes exe uting, it noties the engine exe utor of its own exe ution results. In this ase also, theengine-ws waiting period, whi h has to be estimated, isessential to avoid the engine exe utor nding itself eternally waiting for an answer that may not arrive. Therefore, after the engine-ws waiting period has elapsed, theengine exe utor has to be informed of the WS exe ution's progress. If no answer is re eived, it implies that
the WS has failed.

FENECIA

27

6.4 Des ription of THROWS Ar hite ture Fun tionality
The WS-SAGAS transa tion model supports the spe i ation of a pro ess in different ways following different dened aggregation patterns. For these different patterns, weneed to des ribe how they are to be exe uted. In the following, we show how the state and vitality degree on epts
play a ru ial role in determining how the exe ution is toprogress, and espe ially, in distinguishing su essful fromfaulty situations, in informing of failures, and in re overingfrom failures. In des ribing the fun tioning of THROWS arhite ture, we mostly des ribe sequential and parallel WSSAGAS. Other patterns an be dedu ed in the same way, beause we have dened the exe ution semanti s of ea h pattern in detail in the previous se tion. (Figure 6.2) shows thedifferent transition rules that THROWS denes to make anatomi ompensatable element's state hange from one
state to another. The diagram is for vital and nonvitalelements.

level, that is, W S-SAGASi . The rst step is to generate the
CEL of the element appearing rst in the rst pattern; in thease of W S-SAGASi , CEL(Ei:l ) is generated, an engine is allo ated, the predelegation phase is performed, and a opy ofpp
CEP(W S-SAGASi ; e i ) is passed to eei:1 and the exe utionof the WS-SAGAS starts.
We des ribe below the internal fun tioning of a WSSAGAS: the exe ution of patterns that only ontain atomi
elements. Then, we des ribe how the exe ution is delegatedbetween different nesting levels.
6.4.2 Sequen e Pattern Exe ution ([Ei:k ℄; [Ei:k+1 ℄)We des ribe the general exe ution model of a sequen e pattern aggregating only ompensatable atomi elements.
We assume that an engine exe utor eeipk has been allo atedto the element Ei k . Depending on the exe ution progress,
different s enarios may o ur:::

1. Element Ei k ommitment: In this s enario we assume
that the exe ution of wsipk ontrolled by eeipk was su essful. The su essful exe ution must be ree ted on
the CEP ontent (to omply with our proposed notationof an engine that uses p to designate any engine and q
to designate an engine that was su essful, we use eeqi kinstead of eeipk ). Therefore, the engine eeqi k has to update
the lo ally stored opy of CEP; spe i ally, the state of
the element is to be modied as follows::

6.4.1 Initiating the Exe ution of a Pro ess Pi

The entire pro ess Pi exe ution is initiated by an engine oordinator e ip . To ensure that it does not onstitute a single
point of failure, we assume that we have REL(Pi ), a repli aengine oordinator list that ontains several repli as of e ip .
A pro ess running on a server side is responsible for taking a user request for a parti ular pro ess and for reating
REL(Pi ), and starting the exe ution with one of the repli aengine oordinators; we assume here that it is e ip . More preisely, below is the ontent of REL(Pi ):


q
p
1
REL(Pi ) = DR(e i );  ; DR(e i );  ; DR(e i );  (6.3):
Every repli a in REL(Pi ) ontains the CEP of the overall pro ess and the CEP of the WS-SAGAS for whi h theengine oordinator is responsible. That is, in e ip we haveboth, CEP(Pi ; e ip ) and CEP(W S-SAGASi ; e ip ); CEP(Pi ) is
formed as follows:
CEP(Pi ; e ip ) :CEP(W S-SAGASi ; eeip:1 )[CEP(W S-SAGASi:a ; eeip:a:1 )CEP(W S-SAGASi:a::b ; eeip:a::b:1 )

:
:
:

[

:

:

:

:

q !
CEP(W S-SAGASi ; eei:k ):DR(Ei:k ):state := Committed :The exe ution results are used to update the output parameters of the element:q !
CEP(W S-SAGASi ; eei:k ):DR(Ei:k ):operation:out :=DR(eeqi:k ):operation:out :Afterwards, the engine exe utor has to delegate exe ution ontrol. To this end, it generates CEL(Ei k+1 ) andhooses an engine exe utor to whi h it must delegate theexe ution ontrol; we assume here that the engine eeipk+1
was allo ated to exe ute Ei k+1 . We note that the exe ution of Ei k+1 by eeipk+1 is the exe ution of a WS wsipk+1
ontrolled by eeipk+1 . The WS wsipk+1 to be mapped toEi k+1 must satisfy the following three onditions:
:

:

:

:

:

:

:

:

:

:
:
:

[

:

p
CEP(W S-SAGASi:a::b:: ; eei:a::b:: :1 ) :p
CEP(Pi ; e i ) means that the CEP opy is stored on enginepe i . Similarly, CEP(W S-SAGASi:a ; eeip:a:1 ) is stored on engine eeip:a:1 , CEP(W S-SAGASi:a::b ; eeip:a::b:1 ) is stored on engine eeip:a::b:1 , et (see Figure 6.1).

The engine oordinator initiates the pro ess exe ution by
starting the exe ution of the WS-SAGAS at the rst nesting!
CEP(W S-SAGASi ; eeqi:k ):DR(Ei:k+1 ):des ription =CEL(Ei:k+1 ):DR(eeip:k+1 ):des ription :(the fun tionalities of the element meet the WS apabilities)!
CEP(W S-SAGASi ; eeqi:k ):DR(Ei:k+1 ):operation:in =p
CEL(Ei:k+1 ):DR(eei:k+1 ):operation:in :(the input parameters of the element and of the WS are ompliant)
CEP(W S-SAGASi ; eeqi:k ):DR(Ei:k+1 ):operation:out =CEL(Ei:k+1 ):DR(eeip:k+1 ):operation:out :!

(the output parameters of the element and of the WS are ompliant)

28

Neila BEN LAKHAL et al.

On e these onditions are satised, the two engines starta predelegation phase in whi h one engine agrees to delegating ontrol while the other agrees to having ontrol
delegated to it. When eeqi k re eives the agreement notiation from eeipk+1 , it nalizes the delegation by updating and sending the CEP ontent to the allo ated engine:::!
CEP(W S-SAGASi ; eeqi:k ):DR(Ei:k+1 ):engine := eeip:k+1 :We emphasize that whether or not Ei k was vital does
not affe t the fun tioning of the engine for a su essful
exe ution.
2. Vital Element Eivk+1 Failure: We assume that ex eptional
behavior (e.g., unavailable, timed out, error message) of
the WS wsipk+1 pre luded the engine eeipk+1 from su essfully ommitting the element Eivk+1 . Consequently,
the element Eivk+1 exe ution attempt by the engine eeipk+1
is onsidered to have failed and the following steps mustbe performed to re over to a onsistent state, be ause theelement's su ess is ru ial for the overall subtransa tionsu ess. First, the engine eeipk+1 has to update its lo ally
stored opy of CEP with the latest progress in exe ution
as follows:

4. Vital Element Eivk+1 Ba kward Re overy: If it happensthat (jCEL(Eivk+1 )j = 0), the exe ution retrial is impossible and a ba kward re overy is ne essary. To this end,
all the other elements from the same WS-SAGAS thatare ordered before Eivk+1 and have already ommitted areompensated for, that is, all the vital and nonvital elements that verify the following onditions:
:

:

:

!
CEP(W S-SAGASi ; eeqi:k ):DR(Ei:`j`2[1::k℄ ):state = Committed ;:are ompensated for by exe uting for ea h element its
ompensating element. We emphasize that a ompensation me hanism is triggered by a ompensation request
propagated for all the engines of the elements that verify
the above ondition. In addition, we note that the ompensation request propagation is handled as des ribed
below.
5. Element Ei k Compensation: On re eiving a ompensation request, an engine rst he ks if it has any prede essor to whi h it must, similarly, propagate a ompensation
request. Se ond, it has to ompensate the exe ution of
the element for whi h it is responsible.
That is, if we onsider the ase of the engine eeqi k , responsible for the element Ei k (appli able to the ase of!
CEP(W S-SAGASi ; eeipk+1 ):DR(Eivk+1 ):state := Failed :vital and nonvital), the engine eeqi k sear hes for a
WS that satises the fun tionalities of Ei0 k , the ompenSe ond, a opy of the lo ally stored CEP is sent as a failsating element of Ei k .
ure noti ation message to the engine responsible for theexe ution of the prede essor of Eivk+1 , that is, to engine
Here, we assume that a WS wsqi k was dis overed. Theqeei k , so that it takes harge of the failure re overy proengine eeqi k exe utes the WS wsqi k . On ompleting wsqi kess. Depending on the ardinality of CEL(Eivk+1 ) either
exe ution, eeqi k updates CEP and propagates it with thea forward re overy (i.e., trying to advan e the exe ution
ompensation request to the engines on erned:
pro ess with an attempt at an exe ution retrial) or a ba k!
ward re overy (i.e., to re over the CWS to a onsistent
CEP(W S-SAGASi ; eeqi k ):DR(Ei k ):state := Compensated :qstate) is to be performed by eei k .
3. Vital Element Eivk+1 Forward Re overy: After being noThe engine that nds that it has no prede essor engine istied of Eivk+1 exe ution failure by eeipk+1 (i.e., re eivpresumably the engine responsible for the rst element
ing a opy of CEP in whi h the element Eivk+1 state was
Ei 1 . This engine exe utor has only to ompensate the elset to Failed), the engine eeqi k he ks the ardinality
ement Ei 1 . Finally, the overall WS-SAGAS of this levelof CEL(Eivk+1 ) to determine whether trying a forward
failure is al ulated. The engine exe utor eeqi p , responsire overy, by allo ating another engine in order to reatble for the element Ei 1 , after ompensating the element
tempt the exe ution of Eivk+1 , is feasible or not.
Ei 1 must propagate the failure information up the hierarhy to perform a ba kward re overy in other terminatedWhen (jCEL(Eivk+1 )j , 0) is veried, it means that other
WS-SAGAS. To this end, it sends its last updated opy of
WS satisfying the element Eivk+1 required fun tionalities
CEP(W S-SAGASi ; eeqi 1 ) to the engine oordinator onare available. Therefore, exe ution retrial is possible: theqptrolling the element parent of the W S-SAGASi . In thisengine eei k sear hes for the engine ranked next to eei k+1
p+1
ase, it propagates the opy to e qi . We des ribe belowv
in CEL(Ei k+1 ); here we assume it is the engine eei k+1 .
in this se tion how an engine oordinator handles thisThis engine is allo ated to reattempt the exe ution of theq
failureinformation.
v
element Ei k+1 ; the lo ally stored ontent of CEP in eei k
6.
NonvitalElement Eiv̄k+1 Failure: Assume that the dire t
is updated as follows:su essor of Eiv̄k is the nonvital element Eiv̄k+1 . In this!
qp+1ase, even if the engine eeipk+1 allo ated to Eiv̄k fails, it is
CEP(Pi ; eei k ):DR(Ei k+1 ):engine := eei k+1 :not ne essary to attempt a re overy be ause its su ess is
Subsequently, a predelegation has again been performed
optional. However, the engine eeipk+1 ontinues the exep
+1
ution as if the element was ommitted by updating thewith the new engine eei k+1 , the CEP ontent, with the
CEP and performing the ontrol predelegation phase as
required ontext data for effe tively starting the exe uusual.
tion, is ommuni ated.
:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

0

:

:

:

:

:

0

0

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

FENECIA

29

6.4.3 Parallel Pattern Exe ution (Ei:k ; (Ei:k+1 jj:::jjEi:k+ j ))The main differen e with the exe ution of a sequen e of WSSAGAS is that the engine allo ated to the element Ei k weassume here it is engine eeqi k on nishing exe uting Ei k
has to generate the CEL of the set of elements to be exeuted in parallel, that is, the elements from Ei k+1 to Ei k+ j ,as noted above (Ei k )su . Similarly, eeqi k generates CEL for
all the elements in (Ei k )su . If we assume that the CEL
generation and the engine allo ation steps were done, wehave the CEP updated as follows:
:

:

:

S

:

S
:

2. Failure of one or more vital elements: One or morevital elements in (Ei k )su verify the following ondition:
 v
9Ei j Eiv 2 (Ei k )su and!` 2 [k + 1::k + j℄ :CEP(W S-SAGASi ; eeip ):DR(Ei ):state = Failed :

S

:`

:

!
CEP(W S-SAGASi ; eeqi:k ):DR(Ei:k+ j ):engine := eeip:k+ j :

S

:

S

:`

S

:`

:

:

:`

:`

If the above ondition is veried, rst, all the engines
ontrolling the elements verifying the above ondition
have to ex hange opies of their lo ally stored CEP ontents. At the end of this update, all the engines ontrolling vital elements in (Ei k )su have the same opyof CEP.
Se ond, depending on the pattern used to make the different elements in (Ei k )su onverge to a single point,
a set of elements from (Ei k )su has to generate theCEL(s) for the element(s) that omes dire tly after them.
If we assume that Ei l is the ommon su essor, then theelements in (Ei k )su have to ooperate in generating
the CEL(Ei l ) by taking the union of the different CEL(s)generated by ea h of their engines.
Finally, we note that only the results of the exe ution of
the vital elements were onsidered be ause the othernonvital elements' su ess or failure does not affe t
the others' progress.

S

S

S

:

:

:

:

S

:

:

If a similar situation o urs, then the failed engine(s) has
to inform its dire t prede essor, here eeqi k , of the failure(s). As des ribed above, eeqi k tries to perform a failure re overy. The main differen es reside in that, rst,
the failed engine(s) also have to inform the on urrent
engines ontrolling the other elements to avoid ompromising the subtransa tion exe ution by making the others wait forever.
Se ond, if a ba kward re overy is ne essary, it is most
likely that the exe ution of one or several elements from(Ei k )su is still in progress. As a result, the ompensation me hanism des ribed above is not appli able.
It is essential to abort all the elements that verify the following ondition by stopping their exe ution:

S

:

:

:`

:

:
:
:

:

:

:

:

q !
p
CEP(W S-SAGASi ; eei:k ):DR(Ei:k+1 ):engine := eei:k+1!
CEP(W S-SAGASi ; eeqi:k ):DR(Ei:k+2 ):engine := eeip:k+2

S

S

:`

:

Be ause starting the exe ution of the elements pertaining
to (Ei k )su must be syn hronized, a syn hronization phasehas to be introdu ed.
The syn hronization phase omes dire tly after the predelegation phase nishes. It aims at ensuring that the engine eeqi k , after re eiving the delegation agreements from theother, different engines, simultaneously propagates a startsignal. In addition, be ause a signi ant delay in re eiving
the delegation agreement messages an seriously ompromise the CWS exe ution, we use the peer-engine waiting
period, as already spe ied. After it has elapsed without reeiving the a knowledgment message from one of the engines, eeqi k must sele t another andidate engine. When theelements in (Ei k )su are being exe uted, three situations
are most likely to o ur:
1. Simultaneous Commitment of all the Vital Elements: All
the vital elements in (Ei k )su have been su essfully
ommitted, that is, they verify the following ondition:
 v
8Ei j Eiv 2 (Ei k )su and!` 2 [k + 1::k + j℄ :CEP(W S-SAGASi ; ee1i ):DR(Ei ):state = Committed :

:`

:



:

9Eiv j Eiv 2 S (Ei k )and ` 2 [k + 1::k + j℄ :
su
:
:`
:`
!
CEP(W S-SAGASi ; ee1i:` ):DR(Ei:` ):state = Exe uting :To abort all the elements that verify the above ondition,qeei k has to propagate an abort request to all their alloated engines. Ea h engine that re eives an abort request
responds by immediately stopping its exe ution and updating its lo ally stored CEP opy, then sends it to eeqi k .
After all the different engines have properly handled there eived abort request, the CEP ontent stored on eeqi kside is: v
9Ei j Eiv 2 (Ei k )su and!` 2 [k + 1::k + j℄ :q
CEP(W S-SAGASi ; eei k ):DR(Ei ):state = Aborted :
:

:

:

:`

:`

S

:

:`

:

3. One or more vital elements are still exe uting while
the others have already ommitted: At least one vitalelement in (Ei k )su veries the following ondition:
 v
8Ei j Eiv 2 (Ei k )su and!` 2 [k + 1::k + j℄ :CEP(W S-SAGASi ; eeqi ):DR(Ei ):state = Exe uting :
:`

:`

S
S

:

:

:`

:`

In this ase, two s enarios are possible:
 S enario 1: The engine(s) responsible for the ommitted element(s) informs, as des ribed above, theon urrent engine(s) of their ommitment(s) and generates the CEL of the su essor(s), if they exist. However, they wait for the termination of the element(s)that is/are still being exe uted to agree on the CEL
and to hoose the engine to allo ate to the su essor(s), so that a predelegation phase is performed toeffe tively start exe uting the su essor(s).
 S enario 2: The ommitted elements' engines informthe on urrent engines of their ommitment and enter a latent state while waiting for the remaining unnished elements' ommitment.

30

Neila BEN LAKHAL et al.

A omparison of the two s enarios shows that in (S enario 1) the time spent by the on urrent engines in generating the CEL(s) of the su essor(s) et an be mean-

ingless if one of the still exe uting engines fails. On theother hand, if all the remaining elements were ommitted, then the time spent in a latent state by the different
engines in (S enario 1) is an overhead.

6.4.4 Exe ution Control Delegation between an Engine
Exe utor and an Engine Coordinator

Assume that Ei a is a omposite element from W S-SAGASi .
If the exe ution progress of W S-SAGASi rea hes the element
Ei a , that is, the element Ei a 1 terminates its exe ution then,eeqi a 1 has to delegate the exe ution ontrol as des ribedabove.
The parti ularity here is that when eeqi a 1 he ks for aprede essor, the CEP ontent reveals that the next element
to be exe uted is Ei a and it is omposite. Consequently,
the engine exe utor eeqi a 1 generates an REL not a CEL,
the generated REL being REL(Ei a ). Then, an engine oordinator is sele ted; let this engine be e ipa . The exe utionof W S-SAGASi is suspended waiting for the element Ei a to
be exe uted by e ipa . As des ribed at the beginning of thisse tion, e ipa starts exe ution of W S-SAGASi a in exa tly thesame way as the engine oordinator e ip starts the exe utionof W S-SAGASi .
::izes the exe ution in the way des ribed above. Every WSSAGAS termination is as aded up in the hierar hy until theuppermost level ontrolled by the engine oordinator e ip is
rea hed. Then, this engine nalizes the overall pro ess exe ution by requesting from every other engine oordinator
the last updated opy of the CEP of the subtransa tion for
whi h it was responsible.
When all the opies have been olle ted, the lo ally stored
opy of the overall pro ess CEP is updated and pro ess termination is dedu ed.
6.4.7 Interruption of the Exe ution of a WS-SAGAS with a
Failure:Assume that the exe ution of W S-SAGASi a was interrupted
by a failure of one of its onstituent vital elements andthat the forward re overy me hanism was unable to overome the failure. As a last resort, a ba kward re overy is performed as des ribed in the exe ution of a sequen e/parallel
pattern.
When the failure message (i.e., CEP(W S-SAGASi a ), withthe state of one element set to failed), rea hes the engine
responsible for the rst element in W S-SAGASi a in thisase this engine is eeqi a 1 this element performs a ba kward re overy for the element it ontrols and propagates thefailure information up in the hierar hy. All it has to do isto send the updated opy of CEP(W S-SAGASi a ; eeqi a 1 ) to
the parent of the engine oordinator ontrolling the parentof W S-SAGASi a . In this ase, a opy rea hes e ipa and, be6.4.5 Exe ution Termination of a WS-SAGAS Transa tionause it he ks the CEP ontent, a failure is dedu ed. Subsequently,
a ba kward re overy is triggered: e ipa initiates a
Assume that the exe ution of W S-SAGASi a was terminatedand the exe ution rea hed the last element Ei a n 2 , whi h ba kward re overy in W S-SAGASi by hanging the state of
the element Ei a as follows:
was exe uted by the engine exe utor eeqi a n 2 . eeqi a n 2 he ks
CEP(W S-SAGASi ; e ipa ):DR(Ei a ):state := failed:the lo ally stored CEP, CEP(W S-SAGASi a ; eeqi a n 2 ), for elements not yet exe uted. The result is that all the elements The failure of Ei a is handled in the same way as des ribedin W S-SAGASi a have nished already.
above by ompensating all the ommitted elements in the
Therefore, it has to inform the engine oordinator re- transa tion W S-SAGASi and aborting the other elements stillsponsible for the parent element of W S-SAGASi a that the exe uting. When the failure message rea hes the uppermost
exe ution was terminated. To this end, it sends a opy of level, that is, the engine e p , this engine propagates the failiqp
CEP(W S-SAGASi a ; eei a n 2 ) to the engine e i a .
ure down the hierar hy to all the WS-SAGAS that were terThe engine e ipa dedu es the element Ei a 's state from the minated before the W S-SAGASi a failure (i.e., all the WSre eived CEP(W S-SAGASi a ; eeqi a n 2 ). More pre isely, as- SAGAS lower in the hierar hy must also be re overed).
sume we dedu ed from CEP(W S-SAGASi a ; eeqi a n 2 ):statethat:
DR(W S-SAGASi a ):state = ommitted, then e ipa updates 7 Composite Web Servi es QoS Modeling and Analysis
the state of the element Ei a in CEP(W S-SAGASi ; e ipa ) as
We des ribe the third part of the FENECIA approa h: asfollows:
sessing the QoS of CWS depi ted as WS-SAGAS and exp
e uted following THROWS ar hite ture. Our hief aims in
CEP(W S-SAGASi ; e i a ):DR(Ei a ):state := ommitteddening a QoS model are that, rst, it allows veri ation
Then, the exe ution is ontinued as des ribed above.
of the des ribed CWS as WS-SAGAS are reliably serving
their purpose, when exe uted, by a hieving a high level ofdependability. Se ond, it allows greater improvement of the6.4.6 Exe ution Termination of a Pro ess
quality of exe ution in the future by favoring the more reOn every termination of a WS-SAGAS, the last engine re- liable WS and dis arding the WS that are most likely to besponsible for the last element in the subtransa tion nal- the stage failures.
:

:

:

:

:

:

:

:

:

:

: :

:

:

:

:

:

:

:

:

: : i;: : i;:: : i;:::: : i:::::: : i:

:

:

:

:

:

: : i:::: : i:

:

:

:

:

:

: :

FENECIA

Moreover, we aim to use the QoS estimation and analysis as a basis for improving the WS-SAGAS stru ture. To
this end, our model hara terizes, estimates, and analyzes
several QoS properties, namely the exe ution time and thereliability [17,21℄, on the basis of the past exe utions olle ted in a history, and takes into onsideration the failure
reper ussions.
7.1 Preliminaries
We give an overview of the QoS on epts we are on ernedwith be ause the QoS on ept in itself is broad. It has been
applied to many areas and, depending on the area of appliation, its denition varies.
Some dene it as a set of user-per eivable attributes,
whi h des ribe a servi e and the way it is per eived [50,51℄. We are not on erned with this form of QoS be ause
it has been widely addressed and was the subje t of onsiderable resear h efforts in the area of WSC. Several studies
have fo used on the dynami sele tion of the provider [5254℄ and on semanti WS des ription to improve the sele tion
[55℄. These studies are lassied under the umbrella of maximizing user satisfa tion.
A more appropriate denition of the QoS we treat in the
FENECIA approa h is the system property that onsists ofa set of quality requirements on the olle tive behavior of
one or more obje ts, su h as the information transfer rate,
the laten y, the system failure probability, et . [50,56℄. That31

 Most of the urrent approa hes dealing with QoS estimates in the WS ontext rely on the QoS information advertised by the WS owners/providers, whi h may be not
up to date or subje t to manipulation by the providers.
To over ome this limitation, we ompute the QoS estimations on the basis of the CWS exe ution observation,
where the observation results are olle ted in a history. In
doing so, we believe that more a urate estimates an bea quired be ause we do not rely on the providers' data.
 A major part of the work done up until now onsiders only situations where the CWS do not fail. As a result, the estimates obtained are very often regarded as
too optimisti be ause they do not a ount for any failure (information, re overy) and their reper ussions. In
our model we a ount for failures and their reper ussions on the effe tive performan es of the CWS be ause
this is parti ularly required in the WS ar hite ture, inview of the WS inherent tenden y to fail relatively easily (relative to other omputing omponents). Typi alauses of failure in lude: non ompliant WS hara teristi s (e.g., transa tional supports, management poli ies,
a ess rights) and obvious Internet limitations (e.g., laten y, time-out, se urity).
 Finally, be ause WS are generally stateless, tra king the
failures and determining their lo ations is almost impossible. To over ome this limitation, the notion of state that
we initially introdu ed in WS-SAGAS is used. Introdu ing the state on ept is expe ted to ontribute in a quiring more a urate information on the lo ation of failures
and to be used later to improve the CWS QoS.

is, this ategory of QoS assessment hiey targets estimating
a number of QoS properties for later analysis by the systemdesigners to verify to what extent the CWS are ef iently
serving their purpose during exe ution (i.e., are the introdu ed fault-toleran e me hanisms working properly? Are 7.3 Exe ution Time Chara terization
the sele ted WS adequate?).

In our QoS model, we rst estimate the exe ution time ofea h atomi element Ei k for a subtransa tion W S-SAGASi
from a hierar hy of nested WS-SAGAS forming a pro ess
7.2 Motivation
Pi . Then, we des ribe the derivation of the equivalent estiThe issues guiding us toward introdu ing su h a model are mate for the entire W S-SAGASi and the entire pro ess. Our
QoS model builds heavily on the observation of the past insummarized below.
vo ations of the pro ess and on olle ting these observations
 Most of the proposed approa hes that address the esti- in a history. Be ause the exe ution follows the THROWS
mation of the QoS issue, rst, make use of either math- ar hite ture, the history ontent is hiey formed from theemati al modeling or simulation tools [5760℄. Se ond, different opies of CEP stored in the different engines' logs
they typi ally provide a global view of the range of vari- that ooperated to exe ute the whole pro ess. By enfor ing
ation of the estimates of ertain properties of the CWS as the poli y, all the opies of the different CEPs stored lo allya whole, or their estimates are only appli able for stati on the different engines must be kept until the end of ea h
CWS, whi h make them inappli able for both THROWS pro ess invo ation; at the end we have information about theand WS-SAGAS for dynami omposition. However, pro- pro ess life y le and of all its onstituent elements. Moreviding more detailed estimations, espe ially in the ase over, applying the same poli y to all the different CELs anof omplex CWS, is required more and more. To fulll be very interesting as ea h CEL, in itself, is a history of thethis requirement, our QoS model for CWS is oriented engine-ws ouples attempted. With both the CEP and thetoward a quiring more pra ti al and detailed estimates CEL ontents, tra king failures' lo ations and determinaof the QoS of ea h element, and derives equivalent esti- tions of the engine-ws ouples that fail readily an, in themates for the overall CWS;
future, signi antly improve the quality of exe ution.
:

32

Neila BEN LAKHAL et al.

the time taken by the WS to pro ess its sequen e of a tivities
and of the laten y (exa tly L(eeqi k ; wsqi k ))the time ne esBe ause ea h atomi element is mapped dynami ally to a sary to send a request and re eive a response:
WS, we investigate rst the issue of estimating the exe ution
T (Eivk )opt = T (Eivk ; eeqi k ; wsqi k )(7.1)
time of an elementary WS, whi h has been addressed previqqq= S(wsi k ) + L(eei k ; wsi k )ously on several o asions. Spe i ally, we refer to [60,57℄
in whi h the authors dened the exe ution time taken by awith: 1  q  jCEL(Eivk )jsingle WS invo ation with the sum of the three following
In the spe ial ase of a nonvital element, the exe ution
onstituents:
is attempted only on e; onsequently the equation (7.1) is The servi e time S(WS) is the time that the WS takes transformed as follows:
to perform its task.
 The message delay time M(WS) is determined by the
T (Eiv̄k )opt = T (Eiv̄k ; ee1i k ; ws1i k )(7.2)
size of the message being transmitted/returned and the111
load on the network through whi h the message is sent.
= S(wsi k ) + L(eei k ; wsi k ) The waiting time W(WS) is the delay aused by thev̄
with: jCEL(Ei k )j = 1
load on the system where the WS is deployed.
This model does not omply with our approa h be ause we Denition 7.2 (The Probable Exe ution Time (prob))v
target a dynami and fault-tolerant exe ution. However, the We dene the Probable Exe ution Time(denoted T (Ei k ) probv )E
above model is, rst, only for CWS with one-to-one stati as the estimate of the time spent by an atomi elementv ) , itok
in
being
exe
uted
effe
tively,
whi
h
is
equal
to
T
(
E
opt
WS-element mapping. Se ond, it does not take into a ountik
any eventual failure and how it may intervene in varying the whi h we add the time ne essary for re overing from failperforman es. These two reasons pre lude it from being di- ures that the same instan e of the WS-SAGAS as a whole
re tly appli able in the FENECIA approa h, without further has en ountered (see Equation (7.3)).
extensions.
T (Eivk ) prob = T (Eivk )opt + RP(Eivk ) + R(Eivk );(7.3)
In hara terizing the exe ution time, we build on theabove model and introdu e the Optimisti Exe ution Time where:
and Probable Exe ution Time where the former is limited- T (Eivk )opt is the time to exe ute the WS wsipk ontrolled
to the orre t exe ution situations and where the latter onby the engine exe utor eeipk . We note that p ranges oversiders all the possible exe ution situations (i.e., ommitted[1::jCEL(Eivk )j℄ and that, for a parti ular value q of p, theexe ution, failed exe ution, ompensated exe ution, aborted
exe ution of Eivk was ommitted. Where Eivk was retried
exe ution, et .) of a fault-tolerant CWS. Distinguishing bewith all the engines in CEL(Eivk ) and the exe ution failed
tween these two variants provides more a urate estimates
for all of them, then T (Eivk )opt is assumed to be equal toto a ount for the failure reper ussions on the delivered per0 and T (Eivk ) prob is equal to the time spent in performing
forman es.
a forward re overy by retrying Eivk several times (exa tly
jCEL(Ev ivk )j times).
Denition 7.1 (The Optimisti Exe ution Time(opt))v
We dene the Optimisti Exe ution Time (denoted T (Ei k )opt ), - RP(Ei k ) is the time spent by Eivk in informing of its
own failure or in being informed about others' failure.
as the time spent by the dynami ally mapped engine exe utorv
PR(Eivk ) is detailed more in the following denition.
WS ouple in exe uting the vital element Ei k . This de- R(Eivk ) is the total period of time spent in performing
nition onsiders only the best ase where the exe ution isv
a forward re overy every time the element Eivk failed,ommitted when Ei k is mapped to the rst-ranked ouple
to whi h we add the time spent by Eivk in performing aengine exe utor-WS in the orresponding CEL.
v
ba kward re overy, if it happens that any of the elements
We note here that any atomi element Ei k an be mapped
exe uted in parallel with it, or the elements that ome
at runtime to more than one engine exe utor-WS, at most exvvv
dire
tly after it fail. R(Eivk ) is onsidered in greater detaila tly jCEL(Ei k )j, the ardinality of CEL(Ei k ), with [1::jCEL(Ei k )j℄below.
ranging over p, and every time the element Eivk is to be exep
uted it is allo ated an engine exe utor eei k ( ontrolling theDenition 7.3 (The Failure Re overy Preparation Time)
WS wsipk ). If we assume that for a parti ular value of p we We dene the failure re overy preparation time of an atomi
note q, Eivk exe utions by eeqi k ommitted su essfully, then element (RP(E v )) as the time ne essary to notify of a failik
Eivk was attempted by q engines from CEL(Eivk ) (q veries: ure, or to send a re overy (abort/ ompensation) request. Allv
q  jCEL(Ei k j); in all these exe ution attempts, (q 1) ex- the messages are one-way SOAP messages that ontain thee utions were nished by failures. That is, we an say that last updated opy of CEP. Depending on the failure lo ation
Eivk was retried q times, and that the qth exe ution delegated (i.e., the element itself or another element from the sameto the engine eeqi k ( ontrolling the WS wsqi k ) was su essful. pro ess) and on the elements state and vitality degree, theWe dene T (Eivk )opt by the following equation(7.1) where dened expression of the failure re overy preparation timeq
T (Eivk )opt is the sum of the exe ution time (exa tly S(wsi k )) varies as follows:
7.3.1 The Exe ution Time of an Atomi Element

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

FENECIA33

 In the rst ase, Eivk was ommitted by an engine exe utor eeqi k after being reattempted q 1 times; on every failure by an allo ated engine eeipk , it has to inform
its dire t prede essor by sending a failure information
message to eqi k 1 (i.e., it an be an engine exe utor oroordinator), thereby the notation I (eeipk ; eqi k 1 ). If theelement is nonvital, performing a forward re overy is
not required:
:

:

:

:

:

!

 In the fourth ase, Eivk was attempted by all the engines
in its CEL (i.e., it was reattempted CEL(Eivk ) times) but,unfortunately, it failed in all the retried times; therefore,
the overall WS-SAGAS failure is dedu ed.
This ase is not appli able to a nonvital element beause its failure does not entail overall pro ess failure::::jCEL(E )j ! v):DR(Ei k ):state =Case 4: : CEP(W S-SAGASi ; eei kv

i:kCase 1: : CEP(W S-SAGASi ; eeqi k ):DR(Ei k ):state =Committed

q 1

åp I eeipk eqik
(

:

=1

;

1 ) (vital):

RP(Eiv̄:k ) = 0 (nonvital)
 In the se ond ase, Eiv:k was ommitted by an engine exe utor eeqi:k and was reattempted q 1 times; however,

the overall WS-SAGAS failed be ause of the failure ofanother element that was exe uted later in the pro ess.
If we assume the failed element to be Eiv j , with ( j > k)(handled in the same way whether it is omposite or
atomi ), then the engine allo ated to Eivk re eives a ompensation request from the engine responsible for Eiv j(CR(eip j ; eeqi k ) is the time spent in ex hanging su h amessage):
:

:

:

:

:

!
Case 2: : CEP(W S-SAGASi ; eeqi:k ):DR(Ei:k ):state =CompensatedjCEL(E )jåp I eeipk eqikv

RP(Eiv:k ) =(element ommitted / WS-SAGAS ommitted)

RP(Eiv:k ) =Failed(vital element failed/WS-SAGAS failed)

:

:

:

:

i:k

(

:

=1

;

1)

:

Denition 7.4 (The Failure Re overy Time)We dene the failure re overy time(exa tly R(Eivk )) as thetime required for Eivk to re over from its own failures andfrom the failure of other elements. We note that an element
failure an trigger at most the ardinality of its CEL forward
re overies; however, it an be subje t to only one ba kward
re overy, triggered by another element. The expression ofR(Eivk ) is dened by the following equation::::

For Eivk
Ba k Eivkå pjCEL E jv
For Ei k
T Eivk eeipk wsipk
å pjCEL E j
R(Eiv:k ) =
(

:

1

(

:

(

:

)+

(

:

:

)

(7.4)

)

)
i:k

)=

1

(

v

(

v

i:k

;

;

:

)

Ba k(Ei ) = xor(Comp(Eiv:k ); Abort (Eiv:k )) For(Eivk ) is the total time spent in retrying Eivk by theother engine-ws ouple from CEL(Eivk ) every time the(element ommitted/WS-SAGAS failed)allo ated engine fails to ommit Eivk .
q 1v̄
RP(Eivk ) =I (eeipk ; eqi k 1 ) + CR(eip j ; eeqi k ) (vital)  For(Ei k ) is always equal to 0 for a nonvital element
be ause its exe ution is not retried even if it fails.
p=1
 Ba k(Eivk ): In a ba kward re overy, the me hanism to bepv̄
1
RP(Ei k ) = CR(ei j ; eei k ) (nonvital)
applied depends on the omposition spe i ation model;
the more widely used te hniques are rolling ba k, abort In the third ase, while the element Eivk is being exe uted
ing, and ompensation. In the FENECIA approa h, theby an engine exe utor eeri k (i.e., it was reattempted r 1
ba kward re overy time is the time ne essary to trigger
times), the overall pro ess failed be ause of the failureaba kward re overy me hanism by aborting all the elof another element that was exe uted later in this WSv
ementsstill exe uting and ompensating all the already
SAGAS. If we assume the failed element to be Ei j , withommittedelements. Therefore, the entity Ba k(Eivk ) anv
j > k, the engine allo ated to Ei k re eives an abort rebe equal to the Compensation time(Comp(Eivk )) if anquest from the engine responsible for Eiv j (the time spentotherelement from the same pro ess that omes after Eivk
in ex hanging su h a message is denoted AR(eip j ; eeri k )):failed and triggered a ba kward re overy when Eivk had
already ommitted; alternatively, it is equal to the Abort!
Case 3: : CEP(W S-SAGASi ; eeri k ):DR(Ei k ):state =time(Abort (Eivk )) if another element from the same proAborted
ess that is exe uted on urrently with Eivk failed andr
triggered a ba kward re overy while Eivk is still being(element still exe uting with eei k /pro ess failed)
exe
uted.
r 1
p
q
p
r
v

Dependingon lo ation of the failure (of the element itI (eei k ; ei k 1 ) + AR(ei j ; eei k ) (vital)
RP(Ei k ) =
self
or
of
other
elements) and on the element's state andp=1
vitalitydegree,thedened expression of R(Eivk ) in Equap
RP(Eiv̄k ) = AR(ei j ; eeri k ) (nonvital)tion (7.4) varies as follows:
:

:

:

å

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

å

:

:

:

:

:

:

:

:

34

Neila BEN LAKHAL et al.

!
Case 1: : CEP(W S-SAGASi ; eeqi:k ):DR(Ei:k ):state =Committed(element ommitted / WS-SAGAS ommitted)

R(Eiv:k ) =

q 1

:

q 1

åp For Eivk på T Eivk eeipk wsipk
(

=1

:

)=

(

=1

R(Eiv̄:k ) = 0 (nonvital)

;

:

!

:

;

:

) (vital)

Case 2: : CEP(W S-SAGASi ; eeqi k ):DR(Ei k ):state =::Compensated(element ommitted/WS-SAGAS failed)

R(Eiv:k ) =q 1

å For Eivk Comp Eivk
(

p=1

:

)+

(

:

) (vital)

R(Eiv̄:k ) = Ba k(Eiv̄:k ) = Comp(Eiv̄:k ) (nonvital)!

Case 3: : CEP(W S-SAGASi ; eeri k ):DR(Ei k ):state =::Aborted(element still exe uting with eeri:k /WS-SAGAS failed)

R(Eiv:k ) =åp For Eivk Abort Eivk
r 1

(

=1

)+

:

(

:

) (vital)

R(Eiv̄:k ) = Ba k(Eiv̄:k ) = Abort (Eiv̄:k )(nonvital)jCEL(E )j ! v):DR(Ei k )Case 4: : CEP(W S-SAGASi ; eei k
v

i:k

:

:

:

state = Failed(element failed/WS-SAGAS failed)jCEL(E )jåp For Eivkv

R(Eiv:k ) =

i:k

(

=1

:

The expression Õ means that the exe ution time is derived
a ording to the aggregation pattern that onne ts the different elements that we dened in (Table 7.1). By deriving theexe ution time of every WS-SAGAS in the hierar hy in thesame way as for W S-SAGASi a , we an derive the expression
below for the exe ution time of the whole pro ess:)

7.3.2 The Exe ution Time of a WS-SAGAS and of a Pro ess

T (Pi ) prob = (i:a::b:: :n

Õi

1

`= :

i;m
i

T (E` ) prob jDR(E` ):type = atomi ) :We emphasize that the estimate of the exe ution time
obtained by ombining the exe ution time of the different
elementsdoes not in lude the time spent in the oordination/ onversation between peer-engines, that is, the timespent in the exe ution ontrol delegation (predelegation phaseand syn hronization phase) or the time spent in CEP ommuni ation, that is, the time spent in propagating the synhronization signals. Se ond, it does not in lude the timespent in generating the CEL=REL and the time spent in updating CEP. Any of these different times fall into the ategory of ontrol delegation time. We dene in what follows
how the ontrol delegation time is estimated in our approa h.
In general, it an be in orporated in: (i) the time taken by aone-way SOAP message, (ii) the time taken by a two-way
syn hronous SOAP message (request/response), or (iii) thetime taken by an update/sear h query.
Denition 7.5 (The Control Delegation Time)
The ontrol delegation time is the time between the momentof termination of the exe ution of one or many elements bya rst entity (i.e., one or more engines) and the moment ofstarting the exe ution of one or more elements by a se ond
entity (i.e., one or more engines). It typi ally in ludes thetime ne essary to generate the CEL=REL and sele t the engine(s), the time spent in the predelegation and syn hronization phases, and the time spent in updating and ommuni ating the CEP ontent.
Depending on the WS-SAGAS OR, the ontrol delegation an be: (a) from one engine (exe utor or oordinator)
eqi k to another engine (exe utor or oordinator) eipk+1 (i.e.,eqi k and eipk+1 ontrol a sequen e of elements) (see ase 1).
q(b) from one engine (exe utor or oordinator) ei k to the set
qof engines (ei k )su allo ated to ontrol the set of elements(Ei k )su (see ase 2). ( ) from many engines (exe utor oroordinator) (eipl )pre ontrolling the set of elements (Ei l )preto the engine (exe utor or oordinator) eipl allo ated to Ei l(see ase 3). (d) from many engines (exe utor or oordinator) to many engines (exe utor or oordinator); this ase an
be dedu ed by ombining the se ond and third ases.

The exe ution time of a WS-SAGAS W S-SAGASi is derived
from the estimates of the exe ution time of the different elements it ombines. Be ause these elements might be or hestrated in different ways to stru ture the CWS, we proposedening an expression that estimates the exe ution time for
ea h of the different aggregation patterns that WS-SAGAS
dened (see Table 7.1).
Be ause WS-SAGAS are re ursively nested, the exe ution time of the uppermost WS-SAGAS in the hierar hy isequal to the exe ution time of the entire pro ess. The expression to estimate the exe ution time of a WS-SAGAS
Case 1 :( one engine / one engine)
W S-SAGASi is derived as follows:D(eqi k ; eipk+1 ) = GS(eqi k ; CEL(Ei k+1 )) + PC(eqi k ; eipk+1 ) ;T (Pi ) prob = T (W S-SAGASi ) prob
T (W S-SAGASi ) prob = T (W S-SAGASi a ) prob
where:in 1
 D(eqi k ; eipk+1 ) is the time to delegate the exe ution onT (E ) prob jDR(E ):type = atomi ) :+(trol between the engine eqi k and engine eipk+1 ;
=i 1
:

:

:

S

:

S
S

:

:

:

S

:

:

:

:

:

:

:

:

:

:

:

Õ
: i;

`

:

`

`

:

:

:

:

FENECIA

35

Pattern

Notation

Probable exe ution time

Sequen e(Ei:k ; Ei:k+1 )T (Ei:k ) prob + T (Ei:k+1 ) prob + D(eeqi:k ; eeip:k+1 )Parallel(Ei:k ; (Ei:k+1

Sele tion(Ei:k (Ei k+1 jjEi k+2 jj:::jjEi k+ j ))T (Ei:k ) prob + max(T (S (Ei:k )su ) prob ) + max(D(eeqi:k ; S (Ei:k )su ))Swit h(Ei:k

C (Ei k+1 jjEi k+2 jj : : : jjEi k+ j ))T (Ei:k ) prob + T (S (Ei:k )su ) prob + D(eeqi:k ; S (eeqi:k )su )Rendezvous((Ei:kjjEi k+1jj jjEi k+ j )^Ei l )max(T (S (Ei l )pre ) prob ) + T (Ei l ) prob + max(D(S (eeipl )pre ; eeipl ))Sele tive merge((Ei:k ? ::: ? Ei:k+ j ) Ei l )Ex lusive merge((Ei:k ? ::: ? Ei:k+ j ) Ei l )Iterative(Ei:k ; l Ei:k+1 )jj jjEi k+ j ))
:::

:

:

:

j

=1

:

:

:::

=1

`

:

:

j

T (Ei:k ) prob + max(T (Ei:k+` ) prob ) + max D(eeqi:k ; eeip:k+` )

:

:

:

`

:

:

:

:

max(T (S (Ei l )pre ) prob ) + jS (Ei l )pre jT (Ei l ) prob + max(D(S (eeipl )pre ; eeipl ))

:

:

:

T (S (Ei:l )pre ) prob + T (Ei:l ) prob + D(S

:

:

:

:

p
p
(eei:l )pre ; eei:l )T (Ei:k ) prob + l T (Ei:k+1 ) prob + D(eeqi:k ; eeip:k+1 )The probable exe ution time expressions of WS-SAGAS patterns

Table 7.1

 GS(eqi k ; CEL(Ei k+1 )) is the time spent in generating ei- the observation results of these past invo ations(a ). In Equather CEL(Ei k+1 ) or REL(Ei k+1 ) and in sele ting an en- tion (7.5)), T (Ei k )1opt is the Optimisti Exe ution Time ofgine, we assume that the sele ted engine is eipk+1 ;Ei k when invoked for the 1st time:qp PC(ei k ; ei k+1 ) is the predelegation phase duration andpp
W (ei k ; wsi k ) = max(T (Ei k )1opt ; : : : ; T (Ei k )aopt ) : (7.5)
the time spent in updating and ommuni ating the CEP
ontent.
:

:

:

:

:

:

:

:

:

:

S (eqik ) ) = GS(eqik CEL(S (Ei k ) ))+qqPC(ei k S (ei k ) )
:

su

;

:

su

:

:

;

:

:

su

Case 3 :(many engines / one engine)D(

S (eipl ) eipl ) = GS(S (eipl ) CEL(Ei l ))+PC(S (eipl ) eipl )
:

pre ;

:

:

pre ;

:

:

pre ;

:

:

Denition 7.6 (The Engine-WS Waiting Period)
We dene the engine-ws Waiting Period to avoid the situation where an engine eipk allo ated to an element Ei k waits
eternally for an answer from a WS wsipk that might neverome, if the WS fails to respond. After the engine-ws Waitpping Period (exa tly W (ei k ; W Si k )) has elapsed and no information has been re eived of the exe ution progress of the
WS wsipk , then the engine eipk must onsider itself failed anda re overy has to be triggered. The question is how to determine W (eipk ; wsipk ), in ase the element Ei k ) has not yet been
attempted.
Usually, WS providers advertise the pro essing time of
their provided WS or offer methods to inquire about it. This
ould be used here to ompute an initial estimate of the entity W (eipk ; wsipk ). Later, when the element is invoked a number of times, W (eipk ; wsipk ) an be estimated on the basis of
:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

7.4 Reliability Property Chara terization

Case 2 :( one engine / many engines)qD(ei:k ;:In this se tion, we des ribe the QoS of a CWS in terms of
reliability. It is widely re ognized that the way the reliability
is dened and assessed is spe i to the domain onsideredbut, in general, the reliability on ept is always kept somehow losely related to the system behavior and its failure
history.
In our approa h, in hara terizing the reliability dimension, we introdu e a new ategory of reliability, named reliability tenden y, that builds heavily on the state on ept
atta hed to ea h element from a pro ess, depi ted as a hierar hy of nested WS-SAGAS. Our proposal was motivatedby the reliability and the state on epts being very losely
related and that the element's ontribution to the overall proess reliability estimation varies from one state to another.
To this end, we propose olle ting the pro ess past invoation in a history (i.e., the different opies of CEP stored inevery engine exe ution log).
Later, the olle ted history is used to analyze thoroughly
the different elements' behavior when exe uted by tra kingtheir different states and by how and when they transit between different states. To estimate the reliability tenden y,
the pro ess exe ution history is used to derive for ea h element the element's Terminal States Set (TSS), the element's
State Tenden y Set (STS), and the State Reliability Contribution (SRC).

36

Neila BEN LAKHAL et al.

Denition 7.7 (The Terminal States Set (TSS))
Ea h atomi element Ei k , after being invoked for exe ution as a omponent from a subtransa tion W S-SAGASi , has
a Terminal State (exa tly T S(Ei k )) with whi h its invo ation
is terminated. If the element Ei k is allo ated to an engine
exe utor eeipk , every progress in the element's exe ution isree ted on the lo ally stored opy of CEP on the engine's
eeipk side by updating the attribute state in CEP of the element Ei k . When the element's exe ution is nished, the element's TS is updated as follows:Denition 7.9 (The State Reliability Contribution (SRC))
We assume that from one TS to another, the ontribution toreliability differs: terminating the exe ution of an atomi
element Ei k in the Failed state negatively affe ts the reliability, ontrary to the Committed state, whi h would ontribute positively by in reasing the reliability. A ordingly,
we dene this on ept as the State Reliability Contribution(exa tly SRC) of a parti ular TS. We assume that a transition
from one TS to another makes the SRC stronger if it is toward a state denoting exe ution su ess, and it is ontributing negatively and making the SRC weaker if it is toward a!
p
T S(Ei k ) := CEP(W S-SAGASi ; eei k ):DR(Ei k ):state :state denoting a faulty exe ution. The denition of the SRC
After a invo ations of the same pro ess Pi , for ea h ele- of ea h state depends greatly on the environment hara teristi s onsidered (e.g., number of TS, possible states, states
ment, a Terminal State Set (exa tly T SS(Ei k )) is formed.
The T SS(Ei k ) is a set of 2-tuples where the o urren e transitions, et ). Initially, the different SRC an be allo ated
number of ea h 2-tuple is asso iated with ea h terminal state a value based on the designer's judgment (i.e., when the deas a TS after a invo ation of the element Ei k . If we assume signer wishes to emphasize the more error-prone elements, athat there are b possible TS, and ea h TS T S(Ei k )x is asso- stronger SRC values to the faulty TS an be assigned). Typiated with a number of o urren es o x , as x ranges over i al values of the SRC of the TS of WS-SAGAS are as follows:[1::b ℄, then T SS(Ei k ) is formulated as follows:
:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

f(SRC(Waiting) = 0) (SRC(Failed) = -1) (SRC(Aborted) = -0.5)(SRC(Committed) = 1) (SRC(Compensated) = +0.5)g;

T SS(Ei:k ) = f(T S(Ei:k ) ; o11xx ); :::;); :::; (TS(Ei:k ) ; obb )g(T S(Ei:k ) ; o
with:
o x=a
1xb

;

;

;

å

The ardinality of T SS(Ei k ) depends on the different
possible TS of the element. In the FENECIA approa h, aompensatable atomi element at a given moment an bein one of the following states::

However, in some systems, making the human intervene todene the different SRC may not be desirable be ause thesystem is to be ompletely automated. In su h a ase, making the system able to dene automati ally the different SRC
and to revise them when required is ne essary. We will address this issue in future work.

Denition 7.10 (Element Reliability Tenden y (RT))
The on ept of Reliability Tenden y of an atomi element
Committed, Compensatedg
Ei k (exa tly RT (Ei k )) is derived from its T SS and the difAs we follow a transa tional exe ution, the Exe uting state ferent SRC values, as shown in Equation (7.6).
annot be a T S; therefore, b veries:(b = 5) and the TS ofo x :SRC(T S(Ei k )x )åany element an only be in:TS(E ) 2TSS(E )(7.6)
T S(E ) 2 fWaiting,Failed,Aborted,Committed,Compensatedg RT (Ei k ) =DR(Ei:k ):state 2 fWaiting, Exe uting, Failed, Aborted,

:

:

:

i:k

i:k
T SS(Ei:k ) is denoted as follows:

x

:

i:k

jT SS(Ei k )j:Denition 7.11 (Pro ess Reliability Tenden y)
Any pro ess Pi depi ted as a hierar hy of nested WS-SAGAS
an be formed by both vital and nonvital elements. Be4
5(Committed; o); (Compensated; o)gause the failure of a nonvital element is not handled in5
thesame way as the failure of a vital element and inveswith:o x = a tigating the reasons for failure of the nonvital elements
x =1
is se ondary, we propose onsidering only the vital elements to estimate the overall pro ess RT and ignoring theDenition 7.8 (The State Tenden y Set (STS))
After a invo ations of an atomi element Ei k , at least one nonvital elements.
Therefore, the RT of a pro ess Pi formed by ni elements
Terminal State (T S(Ei k )) from the different possible TS tends
to have the largest o urren e number. We introdu e the on- where n0i elements are vital and distributed between mi
ept of State Tenden y Set (exa tly ST S(Ei k )), as the set that nesting levels is estimated by the following formula:ontains the TS that has the largest o urren e number after
a invo ations of an element.
That is, ST S(Ei k ) must verify the ondition ST S(Ei k )  RT (Pi ) = RT (W S-SAGASi )iab nT SS(Ei k ); that is, ST S(Ei k ) is the set of TS tuples that are
RT (E )jDR(E ):vitality = vital /n0i :=in luded within the TSS T SS(Ei k ) of Ei k and that has the=i1largest o urren e number, after a invo ations of Ei k .

T SS(Ei:k ) = f(Waiting; o12); (Failed; o); (Aborted; o

3

);

å

:

:

:

:

:

:

å

: : : : : : i;m
i

:

:

:

:

`

:

`

`

FENECIA

37

Process Pi

Textual description of the process
underpinning logic

legendinout

identify
definition rules

input data
output data

Process execution
history storage

QoS estimateselement execution log

Multiple DR, CR,
or OR of anelement/processengine

CEP/CELPi

DR(P )i
DR(E )i.k
DR(E i.k+1)
...

CR(P)
i
...

OR(P)
i
...

Atomic element
Composite element
Compensating element
Flow between elements

identify vital/non vital elements, composite/atomic
elements, compensating elements etc.
make WS SAGAS diagram

identify
composability
rules

identify
ordering rules

Start
End

State

i.k+1

relation/operation that uses one part to generatesecond part

WS-SAGASi

WS-SAGAS specification flow

Ei.k+1

Peer engines flow/execution related flow
Web service/engine flow
Failure related flow

State i.k
...

Ei.k

...

State

i.k

QoS estimation/analysis related flow

E
i.k+2

update definition ruleswith QoS estimates

allocate toallocate to

generate CEP
generate CELs

Inform about failure
recovery request
1
engine ee i.kcollect execution log

Ei.k execution log...

collect execution log

Ei.k+1 execution log

engine ee1i.k+1

Ei.k+2 execution log

CEL(Ei.k+2)

E i.k +2execution log
updateengine ee1i.k+2
1
CEP(Pi,eei.k+2
)

...

...

Estimate QoS of element
QoS of Ei.k

QoS of Ei.k+1

QoS of Ei.k+2

Optimistic execution time
Probable execution time
STS,TSS
Reliability tendency

Optimistic execution time
Probable execution time
STS,TSS
Reliability tendency

Optimistic execution time
Probable execution time
STS,TSS
Reliability tendency

CEL(Ei.k+3)

Invocate\control
WSs discovery/
selection...

CEP(Pi,,ee1i.k+1)

send CEP
delegate control
synchronize

CEL(Ei.k+1)

Process Pi execution history

Ei.k+1 execution log

CEL(Ei.k+3)

CEP(Pi ,ee1i.k )...

updateWS-SAGAS specificationcollect execution log

Ei.k execution log
updateallocate to

WSs discovery/
selection

WSs discovery/
selection

Derive QoS of process Pi
analyse QoS estimates
QoS of Pi

Invocate\control

wsi.k1

ws1i.k+2

Invocate /control

...

...

1
wsi.k+1

Optimistic execution time
Probable execution time
STS,TSS
Reliability tendency

UDDI registries

WS-SAGAS execution in THROWS architecture
Fig. 7.1

QoS assessment and analysis

FENECIA Framework

target, we translate all the FENECIA models and elements(i.e., the textual notation of a WS-SAGAS, THROWS ar hiBelow we des ribe two axes of validation for our FENE- te ture CEP, CEL, and REL on epts, and QoS model atCIA framework models and artifa ts. In the rst part of our tributes) into an XML-based language. Our proposed XMLvalidation, we present a prototype that provides an imple- based spe i ation language is dened and expressed a mentation of our exe ution ar hite ture's (THROWS) main ording to a well-formed stru ture, the XML S hema defun tionalities. The prototype implementation is intended to s ription (XSD). An XML-based des ription of a WSC serves
show that the failure re overy-oriented features that THROWS as an input to our prototype as we show below in this se tion.
The prototype implementation is heavily based on thear hite ture provides are feasible with the urrent WS te hJava programming language and on a set of WS enabling
nologies.
In the se ond part of our validation, we show the ap- te hnologies. In the remainder of this se tion, we des ribe
pli ability of our failure-aware QoS estimation and analysis our implementation and we sket h a ase study and reportmodel. To this end, we provide a ase study of using our on its exe ution. We used a simplied version of the travel
model for a real-world example of CWS assembled using itinerary reservation s enario des ribed in the se tions above,with only one nesting level (i.e., all elements are assumed toJopera [61,62℄, a visual WSC tool.
be atomi ).
8 FENECIA Framework Validation

8.1 Prototyping
As in our prototype we target a fully automati WSC. We
have to des ribe the semanti s of the models and elements of
our FENECIA framework in a learer and unambiguous waythat an be easily automated or transformed into any platform spe i ode for automati exe ution. In a hieving this

8.1.1 Implementation Environment Choi es andMotivations

Our prototype implements a logi ally distributed prototypeof THROWS ar hite ture to exe ute CWS spe ied as WSSAGAS and des ribed using our XML-based language.

38

We have made extensive use of Java threads and of anumber of syn hronization me hanisms to allow the on urrent exe ution of engines. Although a physi ally distributed
prototype appears more suitable, the ir umstan es we ite
below pre luded us from implementing su h a system:

Neila BEN LAKHAL et al.

webservc
iesmanager

webservc
iesrepostiory
budli

webservc
iebud
li er
n
i vokedepolywebservc
iedepol yerwebservc
iecal
engn
ie

webservc
ieregsitrer

updatewebservc
ie The urrent progress in WS ar hite ture in terms of seCEPmanager
descrpi toincommunciate
manti ally equivalent WS availability is very limited as
there are few UDDI registries in operation (maintained
regs
iter
updateCELmanager
by IBM, Mi rosoft, et .). Moreover, these registries arestill very small and most of their entries do not work
UDDrIegs
itry
searchor do not orrespond to any real servi e. Furthermore,most of the UDDI registries in pla e today are private
Simplied on eptual ar hite ture for our prototype modeled
registries operating inside ompanies or maintained by a in UML with omponent diagram
set of ompanies privately. Therefore, they are not of use
to us.
 The urrent unpredi tability of the WS environment, whi h 8.1.2 Des ription of Implementation Tools
makes WS appear and disappear on daily basis, makes
the dynami WS dis overy pro ess very likely to fail in We have made extensive use of the different APIs provided
all attempts. This may onsiderably impair our results by Sun's JWSDP 1.2 (Java Web Servi es Developer Pa k)[63℄. Of the te hnologies that JWSDP ontains, we haveand may even make exe ution impossible.
 Even if we assume that a wide range of WS equivalents, hiey used the Java API for XML Registries (JAXR) within terms of fun tionalities, was provided, fully automati the Registry Server for building, deploying, and publishingand dynami WS dis overy and sele tion remains an un- the WS we used. All the WS that we needed for our sysresolved issue with very few solutions. Even large en- tem were built and deployed in an XML registry that folterprises agree that manual WS dis overy and sele tion lowed the UDDI spe i ation (version 1.2). We used JAXR
remains the most ef ient approa h and that automated to a ess this XML registry. To build the different WS, we
dis overy of WS requires a urate des riptions of the used Java API for XML-based RPC (JAX-RPC). The WS
fun tionality of WS and an approa h to nding WS based invo ation and its ontext ommuni ation is done impli itlyon the fun tionality they provide. This remains infea- using syn hronous SOAP messages over HTTP. Moreover,sible be ause it is not possible for a servi e lient to all the ommuni ations between the different modules usedhave full knowledge of the exa t form and meaning of SOAP with Atta hments API for Java (SAAJ). Depending
all the servi e's WSDL in advan e, and this for all the on the CWS exe ution stage, the ex hanged SOAP messages
may en apsulate different forms of XML do uments. Those
WS hosted on different providers.
XML do uments were parsed using JAXP and manipulatedwith JDOM and DOM.
These onditions, and in parti ular the last, have dire ted our
hoi e toward building our private UDDI registry and publishing our own WS lo ally in this registry. In building our 8.1.3 Des ription of Prototype Components
WS, we deliberately reated a WS that shares the same semanti s and syntax (as represented by their WSDL message The implementation featured omponents des ribed in thedenitions); thereby, an automati WS dis overy and sele - on eptual ar hite ture model of Figure 8.1. We implemented
tion an be performed su essfully, the all to the servi e two main modules, the Web Servi es Manager and the Ensu eeds, and no unexpe ted results an be returned. Our gine. Ea h Engine en apsulates two submodules, the CEPManager and the CEL Manager. Ea h Manager has two
prototype features the following fun tionalities:
main fun tions, an information update and retrieval fun tion
and a ommuni ation fun tion, that is, sending and re eiving
 Of the eight different aggregation patterns we dened in SOAP messages.
WS-SAGAS, our prototype supports only three: the seT HE W EB S ERVICES M ANAGER: This implements thequen e, parallel, and rendezvous patterns. Adding all the different fun tions that relate to WS reation, deployment,
different patterns to have a full-featured implementation and invo ation. It onsists of the following three submodis feasible.
ules: (1) the Servi es Builder, whi h hiey uses JAX-RPC
 In our prototype, we only onsider the ase of pro esses API and several other tools (e.g., ws ompile, wsdeploy) toformed by ompensatable elements alone.
generate the WS endpoints, their lients, and their WSDL In our prototype, we onsider a pro ess with only one do uments; (2) the Servi es Deployer, whi h deploys thenesting level; therefore, we have only one engine oor- built WS in a Web ontainer (we used TOMCAT); (3) the
dinator that starts the overall pro ess exe ution and that Servi es Register, whi h is responsible for registering theis responsible for terminating the pro ess.
different WS in our private UDDI registry.
Fig. 8.1

FENECIA<fnc:eelmentADRtype="fasle"vta
ityil="vtai"ldescrpi on
ti ="trpi _niformaon
ti "behaeelmentID="E_1.1"engnieID="nu"l><fnc:statevaule="wantig"/><fnc:operaon
ti operaon
ti ID="operati<fnc:paramparamID="departDate"ajnuary12</fnc:param><fnc:paramparamID="desntiaontiparamtype="niout">
ajpan</fnc:param><fnc:paramparamID="returnDate"february12</fnc:param><fnc:paramparamID="customerNam
paramtype="niout">
Ahmed</fnc:param></fnc:operaonti ></fnc:eelmentADR>

39

voi r="compensatabel"on1">paramtype="niout">"

paramtype="niout">e"Ex erpt from the simplied trip reservation pro ess: different
elements' attributes with the values affe ted

Fig. 8.2

T HE E NGINE: Our prototype implements two types ofengine: engine oordinator and engine exe utor. The numberof instantiated engines depends on the number of elements
and the number of nesting levels of a pro ess. The main differen e is that an engine oordinator is not responsible for
a WS invo ation. Both of the two forms of engines ontaintwo submodules, the CEL Manager and the CEP Manager,
and the en apsulated fun tions are the same: (1) CEL manager: The main fun tion of this omponent is to generate
the CEL of the next element(s) to be exe uted. To this end, it
sends a query with the element des ription (available in thea tive denition rule of the element in CEP) to the UDDI
registry to sear h for WS with fun tionalities mat hing thedes ription and whi h are published in the registry. On reeiving a response to the dis overy query, a new engine exe utor is allo ated and a new engine DR added to the CELfor ea h WS dis overed. This module is also used to sele tan engine exe utor from a CEL do ument. (2) CEP Manager: This mainly updates and monitors the CEP do ument
stored on the engine to whi h it appertains. Typi ally, an update operation hanges an element's state when a new SOAP
message is re eived, for example, a message that tells that
the WS exe ution was su essful.
8.1.4 Detailed Des ription of Typi al Exe ution Steps of a
Pro ess in our Prototype

We des ribe the different steps of the exe ution of a simplied version of the trip reservation pro ess that we used in
the se tions above.
1. C USTOMER REQUEST SUBMISSION . The exe ution
starts when a ustomer inputs his request (the destination,
the departure date, the return date, and his name). Submitting the request entails saving the entered values in the CEP
do ument. The trip request is simulated by assigning a tualvalues to the different elds in the XML do ument. (Listing 8.2) is an ex erpt from the initial CEP do ument of the
pro ess dened in our XML language.

-Theseelctedeelmentsi :E1.1Desc:trpi parael
thsi CEPnumberofetslsi :4driCELsi :E1.1
Organziaon
ti Querystrnigsi trpi
ServcieQuerystrnigsi trpi
Createdconnecon
ti toregsitry
Gotregsitryservcieandquerymanager
Orgname:trpi organziercompanyOrgdescrpi onti :trpi reservaon
ti :hoteal ndaripalnectiketbooki
Orgkeydi :f9e4f93d-2bf9-e4f9-7297-2864692ad619
Contactname:NealiBENLAKHAL
Phonenumber:(012)345-678
EmaAdli dress:neali.benalkha@
l Voyager.com
Servciename:Trpi Servcie
Servciedescrpi on
ti :trpi servcieTunsiai
AccessURI:htpoc:/l ahlost:8080/trpi a-jxrpc/tri
name:JapanTrpi Servcie
Servciedescrpi on
ti :trpi servcieJapan
AccessURI:htpoc:/l ahlost:8080a/jpantrpi a-jxrp
2
WSname=Trpi Servcie
WSname=JapanTrpi Servcie
WSURI=htpoc:/l ahlost:8080/trpi a-jxrpc/trpi
WSURI=htpoc:/l ahlost:8080a/jpantrpi a-jxrpca/j
WSbnidnig=trpi Informaon
ti
WSbnidnig=Trpi IF
WSbnidnig=Strnig_1
WSbnidnig=Strnig_2
WSbnidnig=Strnig_3
WSbnidnig=Strnig_4
WSbnidnig=ajpantrpi Informaon
ti
WSbnidnig=JapanTrpi IF
WSbnidnig=Strnig_1
WSbnidnig=Strnig_2
WSbnidnig=Strnig_3
WSbnidnig=Strnig_4
Trpi Servciehtpoc:/l ahlost:8080/trpi a-jxrpc/trpi
JapanTrpi Servciehtpoc:/l ahlost:8080a/jpantrpi a-j-GENERATEDCELcontaniedniefli:
C:\ecpilse-SDK-2.1.1-wni32\ecpilse\workspace\THROWw
l th
i :nonengwth
i carenta(opl onti a)lpServcie

ca/jpantrpi

pantrpi

xrpca/jpantrpi
S4\E1.1\CEL.XML

Fig. 8.3 Ex erpt from the messages output on the Java exe ution onsole to monitor the exe ution progress. In this part, a WS dis overy is
performed by querying the UDDI registry for WS to the element E1 1 ;two WS are found and their binding information is used to generate a
CEL with two engine elements.
:

This CEP do ument is updated and handled by the different engines throughout the pro ess exe ution. By the end of
its exe ution, the CEP do ument ontains information about
the exe ution su ess (e.g., ight booked, hotel ti ket reserved, ar reserved) or failure (e.g., no available ight).
2. Element sele tion and CEL generation The engine
oordinator e 11 runs on the server side. When it re eives a
new CEP do ument it starts pro essing by parsing the XML
do ument and sele ting a urrent element, that is, the rst
element to be exe uted. In the CEP do ument of Listing of(Figure 8.2), the rst element is the elementID = E 1:1.
The fun tion of going through this CEP do ument for sele ting elements is atta hed to the CEP Manager module.
After an element is sele ted, a CEL do ument is generated. This is the responsibility of the CEL Manager: whi hre eives, as input from the CEP Manager, a des ription ofan element (here, des ription = trip information).
The des ription is used to reate a query that is sent to
the UDDI registry for sear hing WS that eventually meetthe des ription provided.

40<fnc:CEL><fnc:engnieExecutorDRengnieCoordniator="ec_1-1
engnieExecutorID="ee_1.1-1"wsdescrpi on
ti ="wsdLlnik="htpoc:/l ahlost:8080/trpi a-jxrpc<fnc:operaon
ti operaon
ti ID="trpi Informaonti<fnc:paramparamID="Strnig_1"paramtype<fnc:paramparamID="Strnig_2"paramtype<fnc:paramparamID="Strnig_3"paramtype<fnc:paramparamID="Strnig_4"paramtype</fnc:operaon
ti ></fnc:engnieExecutorDR><fnc:engnieExecutorDRengnieCoordniator="ec_1-1
engnieExecutorID="ee_1.1-2"wsdescrpi on
ti ="wsdLlnik="htpoc:/l ahlost:8080a/jpantrpi -j<fnc:operaon
ti operaon
ti ID="ajpantrpi Inform<fnc:paramparamID="Strnig_1"paramtype<fnc:paramparamID="Strnig_2"paramtype<fnc:paramparamID="Strnig_3"paramtype<fnc:paramparamID="Strnig_4"paramtype</fnc:operaon
ti ></fnc:engnieExecutorDR></fnc:CEL>

Neila BEN LAKHAL et al.

"
Trpi Servcie"/trpi ">">="niout"/>="niout"/>="niout"/>="niout"/>"
JapanTrpi Servcie"
axrpca/jpantrpi ">
aon
ti ">
="niout"/>="niout"/>="niout"/>="niout"/>

Ex erpt from the CEL of the element E 1:1 from the trip reservation pro ess

Fig. 8.4

We show in (Listing 8.3) the progress of the exe ution ofthis step in terms of messages output on the Java onsole.
3. Web servi es dis overy and sele tion To ensure interoperability of the engine (here onsidered as the JAXR
lient) and the UDDI registry implementation, the SOAP
messages that ontain the query (and its orresponding results) are handled ompletely unseen using SAAJ. Sear hing
the UDDI registry for WS results in a list of all the organization(s) that ontain(s) WS we are interested in (i.e., they
have apabilities that meet the fun tionalities of the urrent
element E 1.1). When we query the UDDI registry, the result is all the organizations with the name that ontains thestring trip.
4. CEP generation The retrieved information, as a resultof the query, is parsed for details about the organization(s)and the servi es it/they provide(s) and is used to generate
the CEL do ument (refer to Listing 8.4) for the automati ally generated CEL do ument for the element E 1:1. To
ea h WS, an engine exe utor is allo ated, that is, a new engine exe utor ID engineid is dynami ally reated and stored
in the CEL Do ument oupled with the WS information as
an engine denition rule (see Listing 8.4 and Listing 8.3 for
the CEL do ument ontent).
After terminating the CEL do ument generation, a andidate engine exe utor is sele ted and the CEP Manager updates the CEP do ument. Here, the sele ted engine exe utor
is engineExe utorID = ee 1:1 1.
5. CEP update and ontrol delegation When preparing
the ne essary data for effe tively allo ating the exe ution
ontrol to the engine exe utor ee 1:1 1, the CEP do ument is en apsulated and sent as a SOAP message. Simultaneously, a new thread engine ee 1:1 1 is reated, the reeived CEP do ument is stored lo ally, and a response issent ba k to e 1 1 notifying that the SOAP message wasre eived and the exe ution laun hed.

theparameterdi :desntiaon
ti hasthevaulea:jpan
theparameterdi :departuredatehasthevaulea:jn1
theparameterdi :returndatehasthevaule:feb12
theparameterdi :namehasthevaule:Ahmedsi an

si anniputparameter2si anniputparametersi anniputparameter
niputparameter

niput:[desntiaonti ,departuredate,returndate,namewsEndpoint
address=htpoc:/l ahlost:8080/trpi a-jxrpc/trpi Mr/M
niformaon
ti wererecevied
successfuyl*Yourdesrieddesn
tiaon
ti sia:jpan*Yourchosendeparturedatesia:jn12*Yourchosenreturndatesi :feb12
success]output:[]startrunnnig
sAhmed,yourtrpi

Fig. 8.5 Ex erpt from the messages output on the Java exe ution onsole to monitor the exe ution progress. In this part, the WS allo ated
to element E 1:1 and ontrolled by engine ee 1:1 1 is invoked and asu ess message
returned.

6. Control delegation nalization and WS invo ation
preparation After re eiving the exe ution ontrol, the engine exe utor ee1 1 1 updates in the CEP do ument the stateof E 1:1 from Waiting to Exe uting, and extra ts from the
CEP do ument the values of the parameters with whi h the
WS will be invoked (see Listing 8.5).
7. WS invo ation The engine exe utor invokes the WS
lient. The JAX-RPC runtime is responsible for re eiving
this WS invo ation message within the lient all and for
passing it to the WS endpoint. In addition, when the WSnishes exe uting, it passes the results to the JAX-RPC runtime. Likewise, the latter takes are of handing over theseresults to the CEP Manager.
At this point, depending on the WS exe ution progress,
two s enarios an o ur: the WS failure or su ess. Be ause
we implemented the WS, their failure probability was low.
The exe ution often terminated with su ess so to show how
failure handling is performed we for ed WS failure (i.e.,
fault inje tion). In what follows, we rst des ribe the aseof a s enario in whi h the WS exe ution was su essful (seeListing 8.5).
In this pro ess instan e exe ution, the WS sends ba k theresult of its exe ution to the engine exe utor, whi h uses thisto update the CEP do ument to add the WS exe ution result
and to add the required hange in the exe ution progress. In
the ase of the engine exe utor ee 1:1 1, the only update
is hanging the element E 1:1's state from Exe uting toCommitted.
The next step is to pro eed with the exe ution of the
pro ess as the urrent element exe ution is ommitted. To
this end, the engine exe utor ee 1:1 1 nds that there are
two elements, elementID = E 1:2 and E 1:3, that areassembled in a parallel aggregation pattern. The CEL do uments of these elements are generated and the engine exe utor pro esses as des ribed above and allo ates the engines exe utors (ee 1:2 1 and ee 1:3 1), respe tively.
The CEP do ument is updated with the new allo ated engines (see Listing 8.6).
:

FENECIA</fnc:CEP>..
<fnc:eelmentADRtype="fasle"vta
ityil="vtai"ldescrpi on
ti ="trpi _niformaon
ti "behaeelmentID="E_1.1"engnieID="ee_1.1<fnc:statevaule="commited"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="book_giflht"behavoi r=eelmentID="E_1.2"engnieID="ee_1.2<fnc:statevaule="wantig"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="book_hote"lbehavoi r="eelmentID="E_1.3"engnieID="ee_1.3<fnc:statevaule="wantig"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="rent_car"behavoi r="coeelmentID="E_1.4"engnieID="nu"l><fnc:statevaule="wantig"/>.
<fnc:composabtyiliRuels><fnc:composabtyiliRuel OF="WS-SAGAS_1"><fnc:membermemberID="E_1.1"/><fnc:membermemberID="E_1.2"/><fnc:membermemberID="E_1.3"/><fnc:membermemberID="E_1.4"/></fnc:composabtyiliRuel></fnc:composabtyiliRuels><fnc:ordernigRuels><fnc:ordernigRuel><fnc:sequenceIN="WS-SAGAS_1"><fnc:membermemberID="E_1.1"/></fnc:sequence><fnc:paraelIN
l ="WS-SAGAS_1"><fnc:membermemberID="E_1.2"/><fnc:membermemberID="E_1.3"/></fnc:parael>l<fnc:rendezvousIN="WS-SAGAS_1"><fnc:membermemberID="E_1.2"/><fnc:membermemberID="E_1.3"/></fnc:rendezvous><fnc:sequenceIN="WS-SAGAS_1"><fnc:membermemberID="E_1.4"/></fnc:sequence></fnc:ordernigRuel></fnc:ordernigRuels></fnc:CEP>

41

REQUEST:voi r="compensatabel"1">

tyil="vtai"l"compensatabel"1">

tyil="vtai"lcompensatabel"1">

tyil="nonvtai"lmpensatabel"

Ex erpt from the simplied trip reservation pro ess: the exeution progress an be monitored by the hange in the state. Here, therst element was exe uted and ommitted su essfully whereas the exe ution of the two following elements is about to start as engines areallo ated to both.
Fig. 8.6<SOAP-ENV:Enveol pe
xmlns:SOAP-ENV="htp:/schemas.xmlsoap.org/soap/env<SOAP-ENV:Body><driectory>..</driectory><fnc:CEP>.
<fnc:eelmentADRtype="fasle"vta
ityil="vtai"ldescrpi on
ti ="trpi _niformaon
ti "behaeelmentID="E_1.1"engnieID="ee_1.1<fnc:statevaule="commited"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="book_giflht"behavoi r=eelmentID="E_1.2"engnieID="ee_1.2<fnc:statevaule="commited"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="book_hote"lbehavoi r="eelmentID="E_1.3"engnieID="ee_1.3<fnc:statevaule="commited"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="rent_car"behavoi r="coeelmentID="E_1.4"engnieID="ee_1.4<fnc:statevaule="faelid"/>.
</fnc:eelmentADR>.
/fnc:CEP></SOAP-ENV:Body></SOAP-ENV:Enveol pe>

eol pe/">voi r="compensatabel"1">

tyil="vtai"l"compensatabel"1">

tyil="vtai"lcompensatabel"1">

tyil="nonvtai"lmpensatabel"
1">

Ex erpt from the simplied trip reservation pro ess: the exeution progress an be monitored with the hange in the state. All threevital elements were exe uted and ommitted su essfully whereas theexe ution of the last nonvital elements failed.
Fig. 8.7

the andidate engine to exe ute the element elementID =E 1:4 by merging their CEL do uments and sele ting anengine, ee 1:4 1, to exe ute it. Subsequently, ee 1:4 1
suspends ee 1:2 1 and ee 1:3 1, and pro eeds with its
exe ution.

Up to this point in the urrent pro ess exe ution, all theelements exe uted had a vitality degree attribute in the CEPThe CEP Manager omponent from the engine ee 1:3
do ument equal to vital. For that purpose, when they fail,
1 sends the CEP do ument to both of the new engines. The their failure is riti al and auses the whole WS-SAGAS to
exe ution pro ess start is almost the same as that des ribed whi h they appertain to fail, as des ribed below in des ribfor ee 1:1 1. The main differen e is that that two elements ing a pro ess instan e that failed.
elementID = E 1:2 and elementID = E 1:3 are assembled in a parallel pattern and they must wait for ea h
If the WS atta hed to ee 1:4 1 fails while being exother as they are also assembled in a rendezvous pattern (see e uted by ee 1:4 1, then this implies that the failure of
Listing 8.6). Consequently, we divided the exe ution pro ess E 1:4 is ignored and the entire WS-SAGAS exe ution prointo two phases; when every thread engine nishes a phase, eeds, and the state of the element E 1:4 is set to Failed.
it informs the other engine. The rst phase is dedi ated to the
WS invo ation and the se ond phase to preparing for ontrol
As this element is the last element (i.e., parsing the lodelegation, in ase the WS invo ation is su essful.
ally stored CEP do ument and looking for an elements hild
By the end of the exe ution of both of the elements E 1:2 from the same omposite WS returns an empty list), then theand E 1:3, the engines ee 1:2 1 and ee 1:3 1 generate su ess of the entire WS-SAGAS and of the whole pro ess
the CEL do ument of their su essors (here elementID = example is dedu ed by sending the lo ally stored CEP do E 1:4: ea h engine generates CEL do ument by itself and ument to the engine oordinator of the whole WS-SAGAS;
the resulting CEL do ument is a ombination of the two do - here e 1:1 re eives the CEP do ument en apsulated in auments. The engines ee 1:2 1 and ee 1:3 1 agree on SOAP message (see Listing 8.7 for an ex erpt).

42

Neila BEN LAKHAL et al.

RESPONSE:<?xmlversoi n="1.0"encodnig="UTF-8"?><soap-env:Enveol pe
xmlns:soap-env="htp:/schemas.xmlsoap.org/soap/env<soap-env:Header/><soap-env:Body><Response>OKCEPsi receviedcorrec</soap-env:Body></soap-env:Enveol pe>

eol pe/">ytl</Response>

Fig. 8.8 SOAP message en apsulating aonrmation message to indi ate that a CEP do ument was delivered orre tly<fnc:CEPeelmentnb="4"engniecoordniatorID="ec_1-1"
ws-sagasID="WS-SAGAS_1">.
<fnc:ws-sagasADRnesn
tigelve=l "1"eelmentnb="4"
behavoi r="compensatabel"descrpi oti
ws-sagasID="WS-SAGAS_1"type="true<fnc:statevaule="commited"/>.
<fnc:eelmentADRtype="fasle"vta
ityil="vtai"ldescrpi on
ti ="trpi _niformaon
ti "behaeelmentID="E_1.1"engnieID="ee_1.1<fnc:statevaule="commited"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="book_giflht"behavoi r=eelmentID="E_1.2"engnieID="ee_1.2<fnc:statevaule="commited"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="book_hote"lbehavoi r="eelmentID="E_1.3"engnieID="ee_1.3<fnc:statevaule="commited"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="rent_car"behavoi r="coeelmentID="E_1.4"engnieID="ee_1.4<fnc:statevaule="faelid"/>.
</fnc:eelmentADR>.
/fnc:CEP></SOAP-ENV:Body></SOAP-ENV:Enveol pe>

nesntigelve=l "1"n="trpi _process""vta
ityil="vtai"l>voi r="compensatabel"1">

tyil="vtai"l"compensatabel"1">

tyil="vtai"lcompensatabel"1">

tyil="nonvtai"lmpensatabel"
1">

Ex erpt from the simplied trip reservation pro ess. Here,all three vital elements were exe uted and ommitted su essfully
whereas the exe ution of the last nonvital elements failed. The stateof the overall WS-SAGAS is dedu ed on the basis of the state of thevital elements.

Fig. 8.9

8.1.5 Pro ess Instan e Exe ution Termination<fnc:eelmentADRtype="fasle"vta
ityil="vtai"ldescrpi on
ti ="trpi _niformaon
ti "behaeelmentID="E_1.1"engnieID="ee_1.1<fnc:statevaule="faelid"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="book_giflht"behavoi r=eelmentID="E_1.2"engnieID="nu"l><fnc:statevaule="wantig"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="book_hote"lbehavoi r="eelmentID="E_1.3"engnieID="nu"l><fnc:statevaule="wantig"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="rent_car"behavoi r="coeelmentID="E_1.4"engnieID="nu"l><fnc:statevaule="wantig"/>.
</fnc:eelmentADR>

voi r="compensatabel"1">

tyil="vtai"l"compensatabel"tyil="vtai"lcompensatabel"tyil="nonvtai"lmpensatabel"Fig. 8.10 Ex erpt from the simplied trip reservation pro ess; here therst element was exe uted by the engine ee1 1 1 and a failure o urred.
:rst WS (i.e., re eived response ontains failure instead of
su ess) andidate to element elementID = E 1:2 in order to make the engine onsider the WS as failed. Thereby,
the engine ee 1:1 1 needs to dedu e its own failure and todelegate the exe ution ontrol to the previous engine thread.
For that, the urrent engine ee 1:1 1 updates the urrent element elementID = E 1:1 state to Failed and will ommuni ate the CEP do ument to its dire t prede essor. As itwas responsible for the very rst element in the urrently
exe uted WS-SAGAS, it must inform the the engine oordinator e 1:1 be ause that is the engine that has ontrol
delegated to it.
Listing of Figure 8.10 is an ex erpt from the CEP do ument that ee 1:1 1 sends to e 1:1. On re eiving thisdo ument in a SOAP message, e 1:1 handles the failure byattempting a forward re overy. First, the engine is updated(the element E 1:1 state is set to waiting), the engineid
is set to null, and an attempt to sele t another andidate
engine from the CEL do ument is performed.

In response to the re eived CEP do ument (see Listing 8.7
for an ex erpt), the engine oordinator e 1:1 sends the SOAP
message in (Listing 8.8) and resumes exe ution ontrol.
The engine oordinator e 1:1 terminates the exe ution 8.1.7 Forward Re overy in the Exe ution of a Pro essof the pro ess instan e and dedu es the overall pro ess su - Instan eess be ause all the vital elements were ommitted. The
last version of the CEP do ument is then available on this Be ause we have made available for ea h element two anengine (see Listing 8.9 for an ex erpt).
didate engines, the engine oordinator e 1:1, when parsing
the CEL do ument of element E 1:1 des ribed in Listing 8.4,
8.1.6 Exe ution of a Example Pro ess with Failurends a se ond andidate engine: engine ee 1:1 2. It folHandlinglows that a forward re overy is possible; e 1:1 updates the
CEP do ument with the new sele ted andidate engine andThis pro ess example was subje t to a WS failure. Here, the exe ution is resumed with ee 1:1 2 as des ribed for
we intentionally modied the ontent of the response of the ee 1:1 1 (see Listing 8.11).

FENECIA<fnc:CEPeelmentnb="4"engniecoordniatorID="ec_1-1"
ws-sagasID="WS-SAGAS_1".>.
<fnc:eelmentADRtype="fasle"vta
ityil="vtai"ldescrpi on
ti ="trpi _niformaon
ti "behaeelmentID="E_1.1"engnieID="ee_1.1<fnc:statevaule="wantig"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="book_giflht"behavoi r=eelmentID="E_1.2"engnieID="nu"l><fnc:statevaule="wantig"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="book_hote"lbehavoi r="eelmentID="E_1.3"engnieID="nu"l><fnc:statevaule="wantig"/>.
</fnc:eelmentADR><fnc:eelmentADRtype="fasle"vtaidescrpi on
ti ="rent_car"behavoi r="coeelmentID="E_1.4"engnieID="nu"l><fnc:statevaule="wantig"/>.
</fnc:eelmentADR>

43
nesn
tigelve=l "1"

Quoting process (P2)State1

voi r="compensatabel"
2">

in

v

CWS2

out

(stock quoting)tyil="vtai"l"compensatabel"State2.1
in

tyil="vtai"lcompensatabel"v

E2.1 outIn

Rendezvous

State2.2
in

tyil="nonvtai"lmpensatabel"State2.4

State2.3(retrieve stock quote)inv

E2.3 outinv

E2.4 out

out(multiply rate by quote) (convert to European currency)

Ev2.2 out

(retrieve currency exchange rate)

Start

in

input data
flow

End

LegendEx erpt from the simplied trip reservation pro ess; here,the rst element was allo ated to a new engine.

out

output data

E element
State statev vitality degree(text) description

Fig. 8.11

Atomic element

Composite element(a) pro ess depi ted using our graphi al notation

8.2 QoS Model Appli ability Veri ation

The previous se tion fo used on showing that our failure
Unreachable
re overy-devoted WSC spe i ation and exe ution strategy
is feasible only to some extent with the urrent level of WS
Initialte hnology. Our prototype ould not be used to validate our
QoS model unless spe ial me hanisms and modules, dedi ated to taking a log of ea h pro ess instan e exe ution
Waitingin terms of exe ution time and hange in state, need to be
added. We intend to add su h modules in our future work
Suspendedby olle ting the different CEP and CEL opies in a history.
In this paper, to validate our QoS model, we use data generFailed
Running
ated using JOpera [61℄ [62℄, a rapid omposition tool offering a visual language and an exe ution platform for building
distributed appli ations from reusable servi es with a CWS
depi ting a quoting pro ess. Our hoi e of JOpera was inFinisheduen ed by its pra ti ability and its similarity to our FENEAborted
CIA approa h in introdu ing the state on ept. However, theJOpera tool is for stati CWS with entralized exe ution. By(b) state transition diagram from [61℄using JOpera, we simultaneously show our proposal's appliability and give a foretaste of what it is like to use it with
Quoting pro ess
other systems.
As a pro ess instan e is exe uted in Jopera, the exe ution
progress is expressed in terms of state. The exe ution of a
WS in Jopera, when the pro ess is invoked for exe ution, two elements are invoked in a parallel WS-SAGAS pattern
and they join subsequently in a rendezvous pattern. A third
follows the state diagram of (Figure8.12(b)).
element E2v 3 integrates the results obtained from the previous two elements. Finally, a fourth element E2v 1 onverts the
8.2.1 Pro ess Des ription
sto k quote from Euro to the urren y of any of the 12 Europarti ipating ountries and ba k. The quoting pro ess P2 is
We onsider a pro ess P2 that retrieves quotes in a desired depi ted using the WS-SAGAS graphi al notation in (Figurren y for a user-provided sto k symbol. The pro ess we ure 8.12(a)). However, we are obliged to delegate exe ution
dened ombines four WS that we sear hed manually and ontrol to a entralized authority, whi h is responsible for
we used from xmethods.net [64℄. This pro ess ombines four exe ution and failure re overy of all the elements and forvital elements. The rst element quotes sto k pri es E2v 1 the WS dis overy and mapping to the elements, whi h isand the se ond performs a urren y onversion E2v 2 ; these performed stati ally, be ause this is how JOpera is built.
Fig. 8.12

:

:

:

:

44

Neila BEN LAKHAL et al.

instancenumber

E 2v .1
E 2v .2
E 2v .3
E 2v .4
WS - SAGAS 2v

#1
1.102
1.202
1.222
2.313
4.737

#2
0.981
1.151
2.343
1.161
4.655

#3
2.544
2.564
2.104
6.309
10.977

#4
1.282
0.991
0.010
0.000
1.292

#5
1.031
1.182
20.9000.000
22.082

#6
0.160
0.160
0.000
0.000
0.160

#7
0.902
1.172
0.010
2.592
3.774

#8
1.022
1.181
0.010
1.062
2.253

#9
1.001
9.704
0.000
0.000
9.704

#10
5.859
5.879
0.000
0.000
5.879

#11
31.42531.3950.000
0.000
31.425(a) The observed exe ution time (se .) of the four Web servi es allo ated to the elements and of the overall sto k quoting pro ess depi ted
as a WS-SAGAS
instancenumber

E 2v .1
E 2v .2
E 2v .3
E 2v .4
WS - SAGAS 2v#1
Fnisihed
Fnisihed
Fnisihed
Fnisihed
Fnisihed#2
Fnisihed
Fnisihed
Fnisihed
Fnisihed
Fnisihed#3
Fnisihed
FaelidUnreachabel
Unreachabel

Faelid#4
Fnisihed
Fnisihed
FaelidFaelidFaelid#5
Fnisihed
Fnisihed
Faelid#6
FaelidFaelidUnreachabel

Unreachabel

Unreachabel

FaelidFaelid#7
Fnisihed
Fnisihed
Fnisihed
Fnisihed
Fnisihed#8
Fnisihed
Fnisihed
Fnisihed
Fnisihed
Fnisihed#9
Fnisihed
Faelid#10
FaelidFaelid#11
FaelidFaelidUnreachabel

Unreachabel

Unreachabel

Unreachabel

Unreachabel

Unreachabel

FaelidFaelidFaelid(b) The observed terminal states of the four Web servi es allo ated to the elements and of the overall sto k quoting pro ess depi ted as a
WS-SAGAS
Fig. 8.13

Results of quoting pro ess exe uted instan es

sidered, how the exe ution time is estimated varies a ording to whether a failure has o urred or not.
We invoked the sto k quoting pro ess 11 times (a = 11).
S CENARIO 1. In this s enario, we onsider the ase of
The results from the invo ations in terms of exe ution time instan es where the pro ess P2 exe ution is terminated in the
and Terminal States, respe tively, for ea h element and for Finished state and where no failure o urred; for example,
the overall pro ess are shown in (Figure 8.13) and (Fig- see instan e ℄1 in (Figure8.13). The following equation isure 8.14). The reasons for failures during the running of the dened on the basis of our proposed model to estimate thepro ess instan es are: (i) The Internet onne tion failed dur- Probable Exe ution Time of W S-SAGAS2 :ing the SOAP message roundtrip (e.g., instan e ℄10). (ii) The
24
WS timed out be ause of a network onne tion failure (e.g.,
T (E ) prob jDR(E ):type = atomi )T(P2 ) prob = (instan e ℄5). (iii) The WS returned a failure message be ause=2 1of data in onsisten y (e.g., instan e ℄9).
v
v
v
= max(T (E2 1 ) prob ; T (E2 2 ) prob ) + T (E2 3 ) probv
+T (E2 4 ) prob
(8.1)
8.2.2 Pro ess Exe ution and Data Colle tion

Õ:`

8.2.3 Exe ution Time Estimation and Analysis

Before stating our exe ution time estimate analysis, note thatin Figure 8.13 if only the results of the rst table are onsidered the only information obtained is the exe ution time
range of the different omponents. There is no way to tellwhether a failure took pla e or the reasons behind the riti alvariation in the exe ution time between instan e ℄6 instan e℄11. However, even without further analysis, onsidering theexe ution progress in terms of state helps to show that failures have o urred and helps estimate the omponent(s) thatis/are behind the failures ( ells highlighted in gray in the twotables in Figure 8.13).
To analyze thoroughly the obtained data olle ted fromexe uting the sto k quoting pro ess listed in Figure 8.13(a),we onsider different s enarios. The differentiation into s enarios allows us to emphasize the effe ts of failures on theobserved exe ution time. As shown in the two s enarios on-

`

`

:

:

:

:

:

For instan e ℄1, the expression of 8.1 is transformed as follows:
T (P2 )1prob = T (E2v:2 )1opt + T (E2v:3 )1opt + T (E2v:4 )1opt

Note that T (P2 )1prob is used to designate the Probable Exe ution Time of P2 , when invoked. The symbol Õ was introdu ed to indi ate that the exe ution time is derived a ording to the aggregation pattern that onne ts the different
elements that we dened. In addition, this symbol onsiders
only atomi elements, whi h is the type for all the elementsin the sto k quoting pro ess.
In addition, note that the entity ontrol delegation timein the estimation of the probable exe ution time of a proess is ignored be ause the JOpera tools provide no means
to inquire about it.

FENECIA45

Be ause no failure o urred when instan e ℄1 was exeuted, we have:
T (E2v:1 )1opt = T (E2v:1 ; ws12:1 )1
T (E2v:2 )1opt = T (E2v:2 ; ws12:2 )1
T (E2v:3 )1opt = T (E2v:3 ; ws12:3 )1
T (E2v:4 )1opt = T (E2v:4 ; ws12:4 )1

RP(E2v:1 )1 + R(E2v:1 )1 = 0
RP(E v )1 + R(E v )1 = 0
2:2

2:2

2:4

2:4

RP(E2v:3 )1 + R(E2v:3 )1 = 0
RP(E v )1 + R(E v )1 = 0This s enario onsidered only the ase of pro ess instan es
with no failure; therefore, in our model the expression that
relates to the failure re overy time estimates are irrelevant.
S CENARIO 2. In this s enario, we onsidered the aseof one of the instan es in whi h a failure o urred. The exeution retrial of the failed element was not possible be ause
there were no other available WS to reattempt it. As a result,a ba kward re overy was ne essary. In the following expression, we followed the ase of instan e ℄5 in whi h the WS
ws12 3 , allo ated to E2v 3 , has failed. The expression of 8.1 istransformed as follows:::

T (P2 )5prob = max(T (E2v:1 )5prob ; T (E2v:2 )5prob ) + T (E2v:3 )4probv 5+ T (E2:4 ) prob
(8.2)

Be ause a failure o urred when instan e ℄5 was exe uting
the element E2v 3 , we have::

T (E2v:1 )5prob = T (E2v:1 ; ws12:1 )5 + RP(E2v:1 )5 + R(E2v:1 )5
T (E2v:2 )5prob = T (E2v:2 ; ws12:2 )5 + RP(E2v:2 )5 + R(E2v:2 )5
T (E2v:3 )5prob = T (E2v:3 ; ws12:3 )5 + RP(E2v:3 )5
T (E2v:4 )5prob = 0
R(E v )5 = Ba k(E v )5
2:1

2:1

R(E2v:2 )5 = Ba k(E2v:2 )5

the SRC of the Failed state to make its effe ts noti ed veryqui kly. In addition, we atta hed to the Unrea hable state a
median value be ause in this ase the element exe ution was
about to start but it did not be ause its a tivation ondition
was not red; therefore, it requires the designer's attention
to he k why su h a situation o urred.
Typi al interpretations of these results are:
 First, both E2v 3 and E2v 4 tend not to su eed in their exe utions in 9:1% of ases be ause of their own failures(i.e., in 9:1% of ases their exe utions terminate in the
Failed state). For example, instan e ℄5 and instan e℄4 failed be ause failures ourred, respe tively, at E2v 31(ws2 3 failed to send ba k its response and a time-out o urred) and at E2v 4 (a network failure prohibited ws12 4
re eiving its input).
 Se ond, the elements E2v 3 and E2v 4 tend not to start theirexe utions and to terminate in the Unrea hable state in
36:4% and 45:5% of the total invo ations, respe tively.
An element state is set to the Unrea hable state when
the ondition asso iated with the start of its exe ution isevaluated as false. In su h a ase, its exe ution is skipped[62℄. In the ase of E2v 3 and E2v 4 , their onditions werenot red be ause their prede essors failed (e.g., in instan e ℄9, E2v 2 failed).
 Finally, elements E2v 1 and E2v 2 have a strong tenden y
to nish in the Failed state: up to 27:3% for E2v 1 and
36:4% for E2v 2 . Their frequent failures ause overall omposition failure. Therefore, the reasons behind the frequent failures of E2v 1 and E2v 2 need to be investigated.
Moreover, other WS bearing the same fun tionalities as
E2v 1 and E2v 2 need to be sear hed. Lastly, revising the
CWS stru ture (i.e., order of elements, invo ation onditions) has to be planned, if other andidate WS show no
improvements in the quality of exe ution of the pro ess.
:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

8.2.4 Reliability Estimation and Analysis

From the results of the invo ations of the quoting pro ess(Figure8.13), we determined the T SS, ST S, and RT of thedifferent elements of the omposition (see Figure 8.14).
The estimates of the Reliability Tenden y (RT ) of the different elements are shown in (Figure 8.14).

8.3 Validation Results Dis ussion

In the introdu tion to this paper, we advo ate that perfe tawareness of inevitability of failures in the WS ontext anda failure-handling-devoted omposite Web servi es modeling, exe ution, and analysis strategy are required to realize
In determining these estimates, dening the different State a greater gain in dependability. In this se tion, we have valReliability Contributions (SRC) of ea h Terminal State was idated that laim. We have he ked the appli ability of ourrequired. In this ase study, we allo ated as initial values for proposed ideas and shown that they are feasible and an be
the Terminal States Finished, Failed, and Unrea hable implemented using the available WS enabling te hnologies
the SRC of +1:0, 1:0 and +0:5, respe tively. Our motiva- (e.g., WSDL, UDDI, and SOAP), to a limited extent. In ourtion behind assuming su h values is that, when a negative prototype, we only implemented part of the omplete FENESRC value is assumed, the variation in the overall reliabil- CIA approa h features be ause a full-featured implementaity of the estimate an be more important. Therefore, that a tion is dif ult to realize with the urrent state of WS te hfailure is taking pla e an be more readily highlighted by at- nology, as des ribed above. A full implementation requires
tra ting the designer's attention to the element with the more a more mature WS te hnology, parti ularly regarding dyriti al reliability estimate. To realize this, we atta hed to nami WS dis overy and sele tion, solutions that onsider
the Finished state a more neutral value, be ause we are the semanti and synta ti aspe t of WS are needed.
more interested in failures; we atta hed a negative value to46

Neila BEN LAKHAL et al.

Terminal States Set (TSS)v(E2.1,WS12.1 ) {(Finished,72.7%), (Failed,27.3%), (Unreachable,0%)}
v

1

v

1

v

1

(E2.2,WS 2.2 ) {(Finished,63.6%), (Failed,36.4%), (Unreachable,0%)}(E2.3,WS 2.3 ) {(Finished,54.5%), (Failed,9.1%), (Unreachable,36.4%)}(E2.4,WS 2.4 ) {(Finished,45.5%), (Failed,9.1%), (Unreachable,45.5%)}

Fig. 8.14

State Tendency Set (STS){(Finished,72.7%)}

Reliability Tendency (RT)(72.7%*1+27.3%*(-1)+0%*0.5)/3=15.1%{(Finished,63.6%)}

9.1%{(Finished,54.5%)}

21.2%{(Finished,45.5%), (Unreachable,45.5%)}

19.7%

Reliability tendency(RT(CWS2))

16.3%

Quoting pro ess: TSS, STS, and RT

In parti ular, in this prototype implementation, we haveshown that the different me hanisms dened by WS-SAGAS
are feasible. Spe i ally, by des ribing a pro ess in termsof elements and by removing any exe ution-related details,
su h as binding ea h element to only one WS, a higher dependability level an be a hieved by realizing forward reovery. This annot be said of other available WSC languages, notably BPEL where when a fault o urs at one stati ally bound WS; BPEL pro esses handle the fault by a ompensation handler invoked to ompensate for the faulty a tivity. Although BPEL adds some reliability support, de laring a pro ess failed should nevertheless be the last resortand envisaging forward re overy with dynami WS dis overy and binding is more promising; otherwise, the WS ar hite ture offering the possibility of swit hing easily from one
provider to another is useless.
In our prototype des ription, we have also shown how
the WS-SAGAS pro ess denitions and, in parti ular, theway ea h DR en apsulates information about an element an
be used as the pro ess exe ution runs for dynami WS disovery and mapping. The des ription of an element and its
operation provided with its parameters is used to reate aquery that is sent to WS registries for sear hing WS thateventually meet the des ription. We emphasize that our des ribed method for element-WS mat hmaking is intentionally simplied be ause we onsider WS dis overy and sele tion issues beyond the s ope of this paper. Assessing thesimilarity of WS to a hieve the best mat h is an a tive areaof resear h, so we may apply one of the available proposals, su h as the keyword-based methods and ontologies andreasoning algorithm enri hed methods. Therefore, the proess exe ution an transparently resume without interruption
and, even when a dynami ally mapped WS fails, instead of
stopping the overall exe ution, as in BPEL, a forward reovery an be transparently attempted by automati ally allo ating another WS. In addition, equivalently to BPEL, ourmodel supports ba kward re overy be ause a ompensating
element is provided to ea h element.
In addition, we have also shown the broad s ope of theappli ability of our QoS model and that our failure-aware
QoS analysis approa h, with the state in orporation, an provide step-by-step information about the exe ution progress,

whi h an help to tra k the lo ation of failures and explain
the reasons for failures.
In many of the available WSC languages, exempliedby BPEL, mapping between WS and partners is set when a
pro ess is invoked, and this mapping is xed for all the exe utions. As the pro ess runs, there is no means of knowing
the exe ution progress, be ause WS are generally statelessand BPEL provides only a orrelation-based stateful intera tion that only allows identifying instan es. Another me hanism is required to identify the progress of the intera tingparts as the pro ess runs, and to derive the pro ess instan es
progress. This is exa tly the ru ial role of the state on ept
introdu ed in our proposal. Tra king the exe ution progressby keeping a log of all the CEPs, whi h are updated on every hange in any of the element states, provides a stepby-step exe ution progress of all the pro ess instan es that
we an analyze to investigate failures' reasons or lo ations.
We have shown how this an be done when we applied ourstate-guided failure analysis approa h to data olle ted using Jopera.
Finally, the ase study allowed us to show that in estimating the exe ution time, onsidering all the possible exeution situations and building on the state on ept an help
designers to a quire detailed data about the failure lo ation
and auses more easily, without having to use any omplex
modeling formalisms. Moreover, the data derived from theexe ution history (i.e., state tenden y sets, terminal statesset) are more pra ti al and straightforward be ause no simulation systems are required for analysis. On the basis of su hdata, system designers an more readily lo ate error-prone
omponent(s), reasons for failure an be more easily investigated, and eventually, the pro ess overall stru ture an bealtered to improve performan e, if required. However, in our
proposal, to rea h its full potential, we need to use a morerobust real-time monitoring tool that an, besides measuring
and olle ting the total response time of a pro ess invo ation, distinguish between a faulty and a su essful invo ation, measure separately the SOAP messages roundtrip time
and the WS exe ution time, and measure the ontrol delegation time. Several WS monitoring tools are already available
but, to the best of our knowledge, they are only for elementary WS or for stati ally omposed WS; the ase of dynami ally exe uted omposite WS has not yet been onsidered.

FENECIA

47

9.1 WSC Approa hes

isfa tion. However, our approa h is oriented more toward
allowing the system designers to assess the system quality,
analyze it, and eventually produ e some improvements.

A number of alternative approa hes have been suggested
by several authors to aggregate individual WS to produ e
a new CWS, enabled even to en apsulate the underpinninglogi of omplex business pro esses. However, large parts of
the available solutions are oriented toward omparing the semanti s of the interleaved servi es and he king their ports'
ompatibility.
The most important feature that distinguishes our approa h from others is that we onsidered the dependability
issue in all the different stages of the WSC pro ess, that is,from the spe i ation, to the exe ution, to the QoS assessment.
The WSC platform StarWSCoP (Star Web Servi es Composition Platform) [65℄ is very losely related to our work
and it follows a similar approa h to ours be ause it fo uses
on dynami omposition. It provides a servi e exe ution information library that stores tra e information of CWS exe ution; in our approa h, this library is equivalent to thehistory that olle ts the observed exe ution progress of the
CWS instan es (i.e., the opies of CEP).
Another similarity with our approa h is that in StarWSCoP, the authors developed the notion of a wrapper for ea hWS, whi h is very similar to the engine notion, be ause it isalso used to a t as a proxy of the WS; others ommuni atewith the wrapper instead of the WS. The wrapper initiates,
freezes, and ontinues the WS a ording to the requests sentby the requester. However, the wrapper does not have any
predened me hanism to handle potential failures su h as
those we dened in our approa h, where ea h engine, beside
onversing with the WS it wraps, also ommuni ates withdifferent engines in a peer-to-peer fashion to progress theexe ution and to handle failures, whi h is ompletely absent
in the StarWSCoP approa h. Furthermore, ea h wrapper implements different managers to deal with the se urity, transport, and data type mismat h issues. We re ognize that seurity is a very important dependability attribute, espe iallyin the ontext of WS. However, be ause the te hniques forse urity assessment are still rudimentary in the WS ar hite ture, se urity is not addressed in this paper. Considering theexe ution aspe t, our approa h is more s alable than StarWSCoP be ause exe ution ontrol in StarWSCoP is alloated to a entralized engine whereas in our approa h it isdistributed among different engines to avoid the possibilityof bottlene ks and of having a single point of failure.
For QoS estimation and analysis, the StarWSCoP approa h estimates real-time QoS metri s of the CWS by extending WSDL to support QoS metri s, su h as ost, time,and reliability. The dened QoS metri s are very simplisti
ompared to ours: they do not onsider the reper ussions offailures and the authors do not state how reliability is estimated. In addition, the real-time QoS estimations are used
to he k if a parti ular CWS ts the user's predened QoS
requirements, whi h means that StarWSCoP targets user sat-

Similarly, we also onsider two other approa hes where
the CWS is reated dynami ally by des ribing the fun tionalities of interest that omponents should have without referen ing any spe i WS. The rst is eFlow, a platform developed by HP [7,8℄; the se ond approa h is SELF-SERV, aframework developed by the University of New South Wales[41,10,9℄. In the eFlow platform, the denition of a servi e
node en loses a servi e sele tion rule written in a parti ular
query language. When invoking the servi e node, the ruleis exe uted to sele t a spe i servi e. Con erning SELFSERV, it exploits the on ept of servi e ommunity, a ontainer of alternative servi es. At runtime, a ommunity delegates any requests it re eives to one of its urrent members. The eFlow platform ontrasts with our approa h beause it works with a entralized s heduler. As with starWSCoP, it may suffer from s alability problems and no QoS
model is expli itly supported. On the other hand, SELFSERV uses an approa h similar to ours: a distributed exe ution system where oordinators (i.e., software omponents
hosted by WS providers) may ontrol a set of WS, rather
than only one. Although the SELF-SERV strategy avoids
having a single point of failure, to exe ute a CWS the different oordinators need to manage routing tables, stati ally
generated from the oordinators' pre ondition and post ondition states transition tables; a large amount of data needs
to be ex hanged among oordinators. Doing so may easily provoke failures of the oordinators be ause of bottlene ks. To the best of our knowledge, the SELF-SERV strategy does not provide any me hanisms for handling similar
situations. On the other hand, in our approa h, the CEP onept, equivalent to the oordinators' routing tables in SELFSERV, allows a dynami de ision of the exe ution ontrol
delegation of the engines based on the CWS different omponents exe ution states; however, the advantage is that aminimal amount of data is ex hanged, ompared with SELFSERV. Furthermore, an engine is allo ated only if it is ingood ondition. Moreover, exe ution retrial and ompensation me hanisms are provided in ase of failure, whi h annot be said of SELF-SERV. Note that the notion of ommunity in SELF-SERV differs greatly from the notion of
CEL in our approa h be ause there is no dened poli y tohandle the ase where one or more omponent servi es thatform a ommunity fail. Therefore, onsidering extending theomposition model to integrate transa tional semanti s, as in
our approa h, is very interesting for SELF-SERV. However,an unresolved issue remains and needs to be addressed forour approa h/SELF-SERV: how to de ide on the size of theommunity/CEL to in rease the han es of su essful exeution. Here, the idea of using the history of past exe utionsof a CWS an be used to dynami ally optimize an ongoingexe utiona ording to a given set of parameters, su h as
time, pri e, and QoSand to de ide the suitable number of
CELs available in view of the su ess per entage of the different WS invoked in the different CWS instan es.

9 Related Work and Dis ussion

48

One of the most profound features that is of great importan e for designing and developing dependable omposite
servi es is transa tion support. WS are well known for being
autonomous, heterogeneous units, where ea h WS provider
has its own management poli ies; su h hara teristi s make
implementing CWS with a transa tion support more difult, but essential. Very few proposals ontain transa tion
support in their omposition. [39,40℄ introdu es a framework alled WebTransa t, whi h provides the ne essary infrastru ture to build reliable CWS.
WebTransa t is omposed of a multilayered framework.
It uses WSDL to des ribe the WS fun tionalities and adds
a Web Servi es Transa tion Language (WSTL) on top of
WSDL, enhan ing it with fun tionalities fa ilitating omposite WS by des ribing transa tion support for a WS. As in
our approa h, WebTransa t denes different types of transa tion behavior. However, it supports ompensation and retriability behaviors and introdu es virtual- ompensatable behavior for operations whose underlying system supports 2PC
and pivot behavior for the operations, whi h are neither ompensatable nor retriable.
However, the main differen es between our approa h and
WebTransa t are, rst, the WS are stati ally integrated in
WebTransa t by the developer who plays the role of WS integrator. However, this is not a exible method of WS integration. Se ond, the WebTransa t framework is mainly for
integrating WS that have (and expose) their own lo al transa tion support; however, this ondition is not always veriable be ause not all WS have transa tion support and presumably, if they do, not all are ompliant with ea h other,or are limited only to the above suggested transa tion support of WebTransa t. This is what made us onsider ompletely ignoring transa tion support that the different WS
may provide and to de ide to offer/append at a higher level
the same transa tion support at the omposition WS level
instead. Currently in our approa h, WS-SAGAS supports
ompensatable, non ompensatable, retriable, vital, and nonvital behaviors. Finally, our approa h an omplement the
WebTransa t framework be ause our QoS model an be very
important in auditing and analyzing the WS exe ution to improve the quality and ef ien y of the mediator servi e omposition given that QoS assessment is not yet addressed in
Webtransa t.
In [66℄, an approa h to sele ting servi es based on theirsemanti s as well as their quality, as judged by users, is
proposed. To this end, a query language based on DAML
that a ommodates several essential query and manipulation
templates is developed. The users'/providers' estimations of
the QoS may be in orre t and/or biased by the users' subje tivity. In our approa h, we do not rely on the users'/providers'
QoS rating; instead, designers observe the CWS exe ution
and olle t the exe ution results in a history to use later as abasis to estimate the QoS properties.
In [67,58℄, the authors introdu e a QoS-aware middleware for CWS. They fo us on a dynami and quality-driven
approa h to sele t omponent servi es for a omposite servi e. Multiple QoS riteria, su h as pri e, exe ution time,

Neila BEN LAKHAL et al.

and reliability, are onsidered. They propose a global planning approa h to optimize the overall QoS using linear programming te hniques. Their approa h is effe tive with respe t to rea hing QoS optimality. However, their omplex
Workow patterns, su h as using bran hing and frequent
loop iterations, seems to make their approa h less ef ientand in reasingly omplex for business pro esses. Furthermore, potential failure reper ussions on the global QoS havenot been onsidered. Moreover, reliability is mapped dire tly
to the reliability of ea h WS individual. Reliability is dened
as the probability that a request to a parti ular WS re eivesa orre t response within a maximum expe ted time frame.
This method of hara terizing the reliability is not extendable to dynami ally assembled CWS.
Similarly to our approa h, the authors of [68,57,69,70℄
have proposed building new CWS that are QoS-optimized
and have either dened their own QoS models or been inspired by other models. However, all these approa hes are
only appli able for stati ally aggregated CWS. In addition,
the authors of [57,59,69,70℄ have investigated different QoS
dimensions, su h as time, ost, reliability, and delity. However, they have not onsidered how the different states andeffe ts of failure ause the QoS estimates vary. To hara terize the reliability dimension, their proposed models are derived from a more general work [59℄, in whi h the dis retetime stable reliability model proposed in [71℄ is followed to
des ribe the reliability of tasks in the Workow ontext:R(t ) = 1

(system failure rate + pro ess failure rate) :This equation is only appli able for stati CWS as it only
gives a global idea of the reliability estimates of a omponent. Our approa h for reliability estimation goes further beause it obtains more detailed estimates with the possibilityof knowing what omponent(s) was/were behind the onsiderable variation in the overall reliability estimates and thereason (i.e., failure).
9.2 Standards and Commer ial Platforms
WS are be oming an important part of mainstream IT. Every day, it seems, a new a ronym is introdu ed and added
to the mass of a ronyms ranging from SOAP to UDDI to
WSDL. Moreover, ongoing massive standardization efforts
seek to enable CWS; these in lude, among others, businesspro ess modeling languages su h as WSCI, WSFL (WebServi es Flow Language), and, most re ently, BPEL4WS[4℄, whi h have been developed to model CWS. Of these,
only BPEL4WS onsiders failure handling but it offers only
limited support be ause it introdu es fault handlers to spe ify the a tions to be taken when a WS exe ution fails. However, these fault handlers are dened in a way similar to theex eption-handling te hniques exploited in programming languages. Moreover, the handlers are dedi ated to trying to reover from the effe ts of the failed servi e but they do not
attempt to investigate the auses behind the failure, as we doin our approa h.

FENECIAIn addition, other existing standards, su h as BTP [48℄,
the WS-Transa tion [25℄ proposed by IBM, and WS-TXM(from WS-CAF framework) [26℄ by Sun dene models to
support transa tions between loosely oupled systems in the
WS ontext. They dene models for entralized and peerto-peer transa tions, whi h support a two-phase oordination of WS. These standards build on extended transa tionalmodels to spe ify how different WS are oordinated. The
different entities have to agree a priori on the transa tionmodel. Consequently, they inherit the advan ed transa tionalmodels' la k of fun tionality and performan e when used
in appli ations that involve dynami omposition of heterogeneous servi es in a peer-to-peer ontext [72℄. Hierar hial QoS Markup Language (HQML), Web Ontology Language (OWL-S), and Web Servi e Level Agreement language (WSLA) are examples of spe i ations that have addressed the need for a QoS model.
The ommon point of these spe i ations is that they des ribe the QoS of WS. For example, DAML-S has in luded
onstru ts that spe ify several QoS parameters, namely, thequality rating and the degree of quality. However, these spe i ations have not supplied any pre ise hara terization of
the different parameters and they are only suitable for WS
and not for ompositions.
Finally, examples of ommer ial platforms that deal with
WS automation in lude Mi rosoft's .NET and BizTalk tools
and IBM's WebSphere. These appli ations provide support
for SOAP, WSDL, and UDDI onne tivity. However, to thebest of our knowledge, they provide little or no support forCWS.
9.3 Conventional Composite Systems
Making several entities work in tandem to rea h a ommon goal is not a new hallenge in itself, be ause it has
been widely addressed for de ades in several areas, in luding Workow management systems, software engineering,
and arti ial intelligen e. Many argue that when onsidering CWS, it is important to take into a ount, and use experien e and knowledge from, these losely related areas [73,43℄, be ause the main differen e is that omposition in WSar hite ture hiey aims at taking XML-based standards andthe Internet as starting points to rea h the same goal. In the
different parts of our approa h, we promote the same idea
be ause we were inspired by several works in related areas,
spe i ally in the area of Workow te hnology and software
engineering.
In dening the different aggregation patterns for the CWS
spe i ation model, we hose to build on Workow patterns
to dene the different WS-SAGAS aggregation patterns beause the typi al ontrol ow dependen ies en ountered inWorkow modeling arguably apply as well in the ontext
of CWS, be ause the situations they apture are noti eably
similar. In [43℄, the authors showed that the Workow patterns apply to existing CWS languages su h as BPEL4WS
and BPML. Our approa h builds on the state on ept that49

was used well in the ontext of software engineering to dene QoS models, where many mathemati al te hniques havebeen developed. The models that are losely related to ourapproa h are the stru tural models of reliability [74℄ and theMarkov reward models [75℄, whi h form the basis of all performability models. In the former, a state diagram that depi ts the system behavior is used.
Based on Markov hain properties, the transition between
states is assumed to be a Markov pro ess. This means thatthe omponents to be exe uted in the next state depend only
on the omponents of the urrent state and the omponentsof the next state do not depend on the history of the urrent
state. In the latter, the system is assumed to be modeled as aMarkov pro ess with a nite state spa e, and a reward rate
(performan e measure) is asso iated with ea h state.
Our approa h omplements these models be ause we use
the state on ept to dene in the same way the behaviorof the different omponents in terms of transition between
different states; we augment this by making the state onept play an important role in enhan ing failure information, dening the QoS estimates, and analyzing the QoS estimates. On the other hand, our approa h differs in its simpli ity from these proposals and from other te hniques proposedin [76,77℄, whi h are supported by underlying modeling formalisms (e.g., blo k diagrams, Markov hains, Petri-nets,
logi s, et .), be ause the a quired estimates are easily analyzed, whi h is not the ase of the te hniques above, widely
known for requiring onsiderable expertise and effort. Veryoften, the designers are not eager to build su h models beause of their inherent omplexity. Finally, the models obtained are not straightforward to interpret so further simulations have to be performed.

10 Con lusions
In this paper, we introdu e FENECIA, our framework for
CWS spe i ation, exe ution, and QoS assessment. Our approa h puts forward the view that WS/CWS failures are notex eptional situations, as often laimed, but takes a radi ally
different view by a epting that failures are inevitable for
any WS/CWS. In addition, our approa h emphasizes thatwhen earlier failures are taken into onsideration, by dening in advan e proper failure-handling me hanisms, there
are greater han es of seeing a CWS perform with greater
dependability. To a hieve this vision, our work's main ontributions are summarized below.
First is the onstru tion of WS-SAGAS, whi h provides
the framework required to build a transa tion model spe ifi ally tailored to t the hara teristi s of the WS ar hite ture, thereby allowing movement away from the onstraints
imposed by the traditional transa tion model. WS-SAGAS
inherited several interesting features from previously proposed transa tion models, spe i ally, arbitrary nesting, relaxed ACID properties, state, vitality degree, forward andba kward re overy, and ompensation.

50

Neila BEN LAKHAL et al.

We demonstrate how these on epts, whi h were adapted and availability a riti al issue. To deal with this issue, wefrom onventional omposite systems, need to be ome part propose generating the CEL dynami ally, where a list of dyof the WS ar hite ture pillars to provide major ontributions nami ally dis overed WS-engine ouples is ranked. Morein dependability enhan ement.
over, the CEL on ept allows the exe ution retrial with alWe also show how our model provided a powerful on- ternative andidates. Be ause CEL are dynami ally generstru t for extending other approa hes to support WSC more ated, engine sequen es of invo ation annot be known beexpressively, with an in reasing level of exibility and de- forehand. Here, we propose the CEP on ept so that the exependability, by dening a textual notation that is as free as ution ontrol delegation between engines an be performed
possible from programming onstru ts and as expli it as pos- by keeping tra k of the exe ution progress.
sible. This would allow it to be easily understood and upWe also introdu e a model to assess the QoS of CWS. In
dated, whi h annot be said of the syntax of other exist- our model, rather than relying on the QoS information advering proposals, whi h are heavily based on XML. Further- tised by the different WS providers (whi h may be not up tomore, our textual notation that des ribes a CWS in terms date), we estimate the QoS properties on the basis of CWS
of denition rules (DR), omposability rules (CR), and or- exe ution observations, whi h are olle ted in a history thatdering rules (OR) is parti ularly useful for us to dene our onsists of the different opies of CEP and its different uptransa tion model operational semanti s and orre t exe u- dated opies. Se ond, we onfer paramount importan e totions. Be ause we onsider a peer-to-peer exe ution model, the failure reper ussions on the CWS performan es; in fa t,
the use of stri t serializability, adopted in traditional trans- not only were orre t exe ution instan es examined to estia tion models, is inadequate. The des ription of a pro ess mate the QoS and later analyze it, but also our model wasin term of DR, CR, and in parti ular, OR, ontributes partly oriented toward onsidering the system in all of its possible
to avoiding in onsisten ies, be ause the different OR allow states (e.g., orre t, faulty, re overable, exe utions). By dodenition of the orre t ontrol ow in a pro ess. To ensure ing so, we intend to make our model apable of ree ting thethe semanti s of ea h element are respe ted when it is ex- real state of the typi al ase of CWS, with their inherent tene uted, parti ularly the nesting, transa tional behavior, and den y to fail rather easily ompared with others. Third, wevitality degree, we build on the state on ept and we dene use the on ept of element state, initially introdu ed in WSseveral forms of dependen y that must hold between the dif- SAGAS, so that the more error-prone elements an be more
ferent elements ombined in the same pattern, the same WS- readily lo ated. Finally, our model does not use any omplex
SAGAS, and in the same pro ess; we all these intrapattern modeling te hniques, thus making it dire tly usable without
dependen ies, intra-WS-SAGAS dependen ies, and intrapro- requiring a dif ult learning urve.
ess dependen ies.
Our method illustrates how onferring paramount imporWe have atta hed a graphi al syntax to our model to tan e to failure reper ussions on the CWS performan es an
exploit the per eptual apabilities of designers by allowing turn the observed failures throughout a pro ess exe ution
them to apture the models at different levels of detail, whereas y le from a dif ulty to a benet. We demonstrate in ourother solutions either dene no graphi al notation or advo- ase study how the history of exe ution of faulty pro ess inate the use of state- harts for ease of use, although they may stan es an serve as solid basis for analyzing the robustness
not allow expression of all their models' semanti s.
of fault-toleran e me hanisms by tra king failures to ndthemost error-prone element in a pro ess. We also show
From WS-SAGAS for WSC dependable spe i ation asa hierar hy of re ursively nested transa tions omes our se - how su h observations are used to restru ture the pro ess
ond ontribution toward dening an exe ution environment denition to a hieve better quality of exe ution and how ourthat supports the abstra t on epts suggested by WS-SAGAS, exible pro ess denition in terms of DR, CR, and OR supwhi h we named THROWS ar hite ture. The exe ution of port su h a method.
WSC, depi ted as WS-SAGAS, is made possible by the onWe demonstrate that the abstra t on epts and artifa ts
uen e of several novel ideas. First, most existing WSC sys- dened by FENECIA an be implemented to some extent intems only support the integration of WS in a entralized a prototype in the ontext of a resear h proje t. While ourmodel, onsisting of dedi ated entralized engine(s). They prototype implementation suffers from te hnologi al limihave totally ignored the inherent nature of the WS environ- tations, it does demonstrate that our proposal is within thement where intera tion follows a peer-to-peer model and realm of feasibility. The possibility of implementing a fully
where ea h peer WS owner provides a set of servi es that edged implementation of this work will depend greatly on
omprise CWS. We take a radi al approa h and propose the evolution speed of the servi e industry and resear h.
an ar hite ture where the exe ution ontrol is hierar hi ally
The FENECIA approa h proposal allows us to realizedelegated to distributed engines dis overed dynami ally. Ex- that basi on epts that exist in onventional omposite syse uting the CWS in a distributed fashion allows us to avoid tems, namely the element state and, more generally, the omhaving a single point of failure and to split the messages that ponent behavior, need to be made available for WS as they
the entral authority is required to manage among the dis- an assist greatly in obtaining information about the exe utributed engines.
tion and in adding improvements. Moreover, in onventional
In addition, be ause WS are in essen e loosely oupled, omposite systems, where the same omponents are onintegrating them into a CWS makes the system reliability ne ted, only stati omposition strategies were available.

FENECIA

However, in the WS ontext, throughout the different partsof our approa h, we show that su h a solution is not viable,
and a dynami omposition strategy is far more preferable.
However, to realize fully a dynami omposition strategy,
mu h remains to be done in the WS ar hite ture be ause it
still suffers signi antly from being heavily based on the Internet.
In the ase of some business pro esses where failures
are not permissible (e.g., banking), effe tive realization of
the FENECIA vision, besides making the failure re overy
me hanism possible, requires proper failure avoidan e me hanisms, whi h may onstitute an interesting extension to ourpresent work. In addition, at present the CWS exe ution in
FENECIA is done independently by different engines, where
the engines are volatile (i.e., on ea h CWS invo ation, new
CEL are built to avoid using WS that are no longer available or obsolete). Making the different engines nonvolatile
and assigning QoS attributes to the different engines to estimate their performan e an lead to a more optimized exe ution, be ause the more reliable engines are sele ted. Later, amore elaborate model of ollaboration between the different
engines an be developed. Finally, be ause there is a wide
range of toolkits supporting WS development, another interesting resear h dire tion will be nalizing the implementedonguration of WS-SAGAS for THROWS, experimentallymeasuring its performan e, and omparing it with others.
Part of this resear h was supported by CREST of
JST (Japan S ien e and Te hnology Agen y), a Grant-in-Aid for S ienti Resear h on Priority Areas from MEXT of the Japanese Government (#16016232 and #18049026), and the 21st Century COE Program Framework for Systematization and Appli ation of Large-s ale
Knowledge Resour es.

A knowledgements

Referen es
1. W3C.
Web servi es des ription language (wsdl).
http://www.w3.org/TR/wsdl, 2005.
2. W3C.
Simple obje t a ess proto ol (soap).
http://www.w3.org/TR/soap, 2005.
3. W3C. Universal des ription, dis overy, and integration (uddi).
http://www.uddi.org, 2005.
4. IBM, BEA Systems, Mi rosoft, SAP AG, and Siebel Systems.
Bpel4ws business pro ess exe ution language for web servi es,
2005.
5. IBM. The emerging te hnologies toolkit (ettk), 2005.
6. Mi rosoft.
Mi rosoft web servi es strategy.net.
http://www.mi rosoft. om/net/, 2005.
7. Fabio Casati, Ski Ilni ki, Li-Jie Jin, Vasudev Krishnamoorthy, andMing-Chien Shan. eow: A platform for developing and managing omposite e-servi es. In AIWORC '00: Pro eedings of theA ademia/Industry Working Conferen e on Resear h Challenges,
page 341. IEEE Computer So iety, 2000.
8. Fabio Casati, Ski Ilni ki, Li jie Jin, Vasudev Krishnamoorthy, andMing-Chien Shan. Adaptive and dynami servi e omposition ineow. In B. Wangler and L. Bergman, editors, CAiSE '00: the12th international Conferen e on Advan ed information Systems
Engineering, volume 1789 of LNCS, pages 1331, London, June

05 - 09 2000. Springer-Verlag.
9. Quan Z. Sheng, Boualem Benatallah, Marlon Dumas, and Eileen
Oi-Yan Mak. Self-serv: A platform for rapid omposition of web

51
servi es in a peer-to-peer environment. In VLDB, pages 1051
1054, 2002.
10. Boualem Benatallah, Quan Z. Sheng, and Marlon Dumas. The
self-serv environment for web servi es omposition. IEEE Internet Computing, 7(1):4048, Jan. 2003.
11. Dan Wu, Bijan Parsia, Evren Sirin, James A. Hendler, and Dana S.
Nau. Automating daml-s web servi es omposition using shop2.
In The Semanti Web - ISWC 2003, Se ond International Semanti
Web Conferen e, Sanibel Island, FL, USA, volume 2870 of Le ture Notes in Computer S ien e, pages 195210. Springer, 2003.
12. Nikola Milanovi and Miroslaw Malek. Current solutions for web
servi e omposition. IEEE Internet Computing, 8(6):5159, 2004.
13. N. J. Davies, D. Fensel, and M. Ri hardson. The future of web
servi es. BT Te hnology Journal, 22:118130, Jan. 2004.
14. Ahmed K. Elmagarmid. Database transa tion models for advan ed appli ations. Morgan Kaufmann, San Mateo, California,
1992.
15. Neila Ben Lakhal, Takashi Kobayashi, and Haruo Yokota. Wssagas:a transa tion model for reliable web servi es omposition
spe i ation and exe ution. DBSJ letters, 2(2):720, O t. 2003.
16. Neila Ben Lakhal, Takashi Kobayashi, and Haruo Yokota. Distributed ar hite ture for reliable exe ution of web servi es. Te hni al Report DBWS2003 2B, IEICE, 2003.
17. Neila Ben Lakhal, Takashi Kobayashi, and Haruo Yokota. Reliability and performan e estimation for enri hed ws-sagas. In WIRI
'05: Pro eedings of the International Workshop on Challenges in
Web Information Retrieval and Integration, In onjun tion withICDE2005, pages 5463, Tokyo, Japan, Apr. 2005. IEEE Com-

puter So iety.
18. Neila Ben lakhal, Takashi Kobayashi, and Haruo Yokota. Dependability and exibility entered approa h for omposite web servi es modeling. In 14th International Conferen e on Cooperative
Information Systems (CoopIS2006), volume 4275(OTM2006) of
LNCS, pages 163182, Montpellier, Fran e, Nov. 2006.
19. Neila Ben Lakhal, Takashi Kobayashi, and Haruo Yokota.
Throws: An ar hite ture for highly available distributed exe utionof web servi es ompositions. In IEEE 14th International Work-

shop on Resear h Issues on Data Engineering: Web Servi es for
E-Commer e and E-Government Appli ations (RIDE'04), pages

103110, Boston, USA, Mar h 2004. IEEE.
20. Neila Ben Lakhal, Takashi Kobayashi, and Haruo Yokota. A simulation system of throws ar hite ture with ws-sagas transa tionmodel. DBSJ Letters, 3(1):8992, June 2004.
21. Neila Ben Lakhal, Takashi Kobayashi, and Haruo Yokota. A
failure-aware model for estimating and analyzing the ef ien yof web servi es ompositions. In PRDC '05: Pro eedings of the
11th Pa i Rim International Symposium on Dependable Computing (PRDC'05), pages 114124, Washington, DC, USA, 2005.

IEEE Computer So iety.
22. Neila Ben Lakhal. A framework for modeling, exe uting, andanalyzing dependable transa tional Web servi es ompositions.
Phd.thesis, Tokyo Institute of Te hnology, Tokyo, Japan, 2007.
23. A. Gorbenko, V. Khar henko, P. Popov, A. Romanovsky, and
A. Boyar huk. Development of dependable web servi es out of
undependable web omponents. Te hni al Report 863, Universityof New astle upon Tyne, S hool of Computing S ien e, O t 2004.
24. Jean-Claude Laprie and Brian Randell. Basi on epts and taxonomy of dependable and se ure omputing. IEEE Transa tions
on Dependable Se ure Computing, 1(1):1133, 2004. FellowAlgirdas Avizienis and Senior Member-Carl Landwehr.
25. F. Cabrera and et al.
Spe i ation: Web servi estransa tion (ws-transa tion).
http://www106.ibm. om/developerworks/webservi es/library/ws-transpe /,2002.
26. Ora le Fujitsu, IONA and Arjuna Te hnologies Sun.
Web servi es omposite appli ation framework(ws- af).
http://www.arjuna. om/standards/ws- af/, 2003.
27. He tor Gar ia-Molina and Kenneth Salem. Sagas. In SIGMOD
Conferen e, pages 249259, 1987.

52

Neila BEN LAKHAL et al.

28. W.M.P. van der Aalst, A.H.M.ter Hofstede, B. Kiepuszewski,
and A.P. Barros. Workow patterns. Distributed and Parallel
Databases, 14(1):551, 2003.
29. A. Sheth, K. Ko hut, and J. Miller. Meteor proje t pageat large s ale distributed information systems (lsdis)laboratory.
http://lsdis. s.uga.edu/proj/meteor/meteor.html.
30. Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, and Irving L.
Traiger. The notions of onsisten y and predi ate lo ks in a
database system. Commun. ACM, 19(11):624633, 1976.
31. W. Du and Ahmed Elmagarmid. Quasi serializability: a orre tness riterion for global on urren y ontrol in interbase. In VLDB
'89: Pro eedings of the 15th international onferen e on Verylarge data bases, pages 347355, San Fran is o, CA, USA, 1989.

Morgan Kaufmann Publishers In .
32. Krithi Ramamritham and Panos K. Chrysanthis. A taxonomy oforre tness riteria in database appli ations. The VLDB Journal,5(1):085097, 1996.
33. Ahmed K. Elmagarmid, Yungho Leu, Witold Litwin, and Marek
Rusinkiewi z. A multidatabase transa tion model for interbase.
In Pro eedings of the 16th International Conferen e on Very Large
Data Bases, pages 507518, San Fran is o, CA, USA, August 1316 1990. Morgan Kaufmann Publishers In .
34. Sami Bhiri, Olivier Perrin, and Claude Godart. Ensuring required
failure atomi ity of omposite web servi es. In WWW '05: Proeedings of the 14th international onferen e on World Wide Web,
pages 138147, New York, NY, USA, 2005. ACM Press.
35. J. Gray and A. Reuter. Transa tion Pro essing: Con epts andTe hniques. Morgan Kaufmann, 1993.
36. J.E.B. Moss. Nested transa tions: an approa h to reliable distributed omputing. Cambridge, Massa husetts, 1985.
37. He tor Gar ia-Molina, Dieter Gawli k, Johannes Klein, Karl
Kleissner, and Kenneth Salem. Modeling long-running a tivities
as nested sagas. Data Engineering Bulletin, 14(1):1418, Mar h1991.
38. Mansoor Ansari, Linda Ness, Marek Rusinkiewi z, and Amit P.
Sheth. Using exible transa tions to support multi-systemtele ommuni ation appli ations. In VLDB '92: Pro eedings of the
18th International Conferen e on Very Large Data Bases, pages
6576, San Fran is o, CA, USA, 1992. Morgan Kaufmann Publishers In .
39. Paulo F. Pires, Mario R. F. Benevides, and Marta Mattoso. Mediating heterogeneous web servi es. In 2003 Symposium on Appli ations and the Internet (SAINT 2003), pages 344347, 27-31
January 2003 - Orlando, FL, USA.
40. Paulo F. Pires, Mario R. F. Benevides, and Marta Mattoso. Web,
Web-Servi es, and Database Systems, volume 2593 of Le ture
Notes in Computer S ien e, hapter Building Reliable Web Servi es Compositions, pages 5972. Springer, 2003.
41. Boualem Benatallah, Marlon Dumas, and Quan Z. Sheng. Fa ilitating the rapid development and s alable or hestration of omposite web servi es. Distributed and Parallel Databases, 17(1):5
37, Jan. 2005.
42. Gwen Salan, Lu as Bordeaux, and Mar o S haerf. Des ribing
and reasoning on web servi es using pro ess algebra. In ICWS
'04: Pro eedings of the IEEE International Conferen e on Web
Servi es (ICWS'04), page 43, Washington, DC, USA, 2004. IEEE

Computer So iety.
43. W.M.P.V.D. Aalst. Don't go with the ow: Web servi es omposition standards exposed. IEEE Intelligent Systems, 18(1):7276,
Mar h 2003.
44. J. A. Bergstra, A. Ponse, and S. A. Smolka. Handbook of Pro ess
Algebra. Elsevier, 2001.
45. R. Milner. Communi ation and on urren y. Prenti e-Hall, In .,Upper Saddle River, NJ, USA, 1989.
46. C.A.R.Hoare. Communi ating Sequential Pro esses. Prenti eHall, 1985.
47. Mi hael J. Butler, C. A. R. Hoare, and Carla Ferreira. A tra e
semanti s for long-running transa tions. In 25 Years Communiating Sequential Pro esses, pages 133150, 2004.
48. OASIS Committee. Business transa tion proto ol version 1.0,
2004.

49. F. Cabrera and et al.
Web servi es oordination.
http://www.ibm. om/developerworks/library/ws- oor/, 2002.
50. AT van Halteren. Towards an adaptable QoS aware middlewarefor distributed obje ts. Phd.thesis, University of Twente, Ens hede, the Netherlands, The Netherlands, 2002.
51. ITU/ISO. Open distributed pro essing referen e model, part 2:
Foundations, international standard. 10746-2 ITU-T Re ommendation X.902, 1995.
52. Christoph S huler, Roger Weber, Heiko S huldt, and Hans Jorge
S hek. Peer-to-peer pro ess exe ution with osiris. In Springer,
editor, International Conferen e on Servi e-Oriented Computing,volume 2910 of LNCS, pages 483498, Italy, De ember 2003.
53. Ulrike Greiner and Erhard Rahm. Quality-oriented handlingof ex eptions in web-servi e-based ooperative pro esses. In

Pro eedings of the GI-/GMDS Workshop on Enterprise Appliation Integration (EAI-04), Oldenburg, Germany, February 1213, 2004, volume 93 of CEUR Workshop Pro eedings. CEUR-

WS.org, 2004.
54. Markus Keidl, Stefan Seltzsam, and Alfons Kemper. Reliable
web servi e exe ution and deployment in dynami environments.
In Te hnologies for E-Servi es the fourth International Workshop(TES 2003), volume 2819 of Le ture Notes in Computer S ien e,
pages 104118. Springer, September 2003.
55. Mark H. Burstein, Jerry R. Hobbs, Ora Lassila, David L. Martin,
Drew V. M Dermott, Sheila A. M Ilraith, Srini Narayanan, Massimo Paolu i, Terry R. Payne, and Katia P. Sy ara. Daml-s: Web
servi e des ription for the semanti web. In First International
Semanti Web Conferen e, (ISWC 02), volume 2342 of Le ture
Notes in Computer S ien e, pages 348363. Springer, 2002.
56. Meyer B. Applying design by ontra t. IEEE Computer (Spe ial
Issue on Inheritan e and Classi ation), 25(10):4052, O tober
1992.
57. S. Chadrasekaran, J.A. Miller, G. Silver, I.B. Arpinar, and
A. Sheth. Composition, performan e analysis and simulation of
web servi es. Ele troni Markets: The International Journal of
Ele troni Commer e Business Media, 2003.
58. Liangzhao Zeng, Boualem Benatallah, Marlon Dumas, Jayant
Kalagnanam, and Quan Z. Sheng. Quality driven web servi es
omposition. In WWW '03: Pro eedings of the 12th international
onferen e on World Wide Web, pages 411421, New York, NY,
USA, 2003. ACM Press.
59. J. Cardoso, A. Sheth, J. Miller, J. Arnold, and K. Ko hut. Qualityof servi e for workows and web servi e pro esses. Journal of
Web Semanti s, 2004.
60. J. Cardoso and A. Sheth. Semanti e-workow omposition. Journal of Intelligent Information Systems, 2003.
61. Cesare Pautasso, Thomas Heinis, and Gustavo Alonso. Autonomi exe ution of web servi e ompositions. In ICWS '05: Proeedings of the IEEE International Conferen e on Web Servi es(ICWS'05), pages 435442. IEEE Computer So iety, 2005.
62. C.Pautasso. A Flexible System for Visual Servi e Composition.

PhD thesis, ETH, July 2004.
63. SUN.
Java web servi es developer pa k v1.2 (jwsdp).
http://java.sun. om/webservi es/, 2003.
64. xmethods. http://www.xmethods.net, 2004.
65. H. Sun, X. Wang, B. Zhou, and P. Zou. Resear h and Implementation of Dynami Web Servi es Composition, volume 2834, pages
457  466. Springer LNCS, 2003.
66. A. Soydan Bilgin and Munindar P. Singh. A daml-based repository for qos-aware semanti web servi e sele tion. In ICWS, pages
368375, 2004.
67. Zeng L.and Benatallah B., Ngu A., Dumas M., Kalagnanam J.,
and Chang H. Qos-aware middleware for web servi es omposition. IEEE Transa tions on Software Engineering, 30(5):311 
327, May 2004.
68. M.C. Gronmo, R.and Jaeger. LNCS, volume 3543, hapter ModelDriven Methodology for Building QoS-Optimised Web Servi e
Compositions, pages 68  82. Springer, Jan. 2005.
69. Amit P. Sheth, Jorge Cardoso, John A. Miller, Krzysztof J. Ko hut,and M. Kang. Servi e-oriented middleware. In Pro eedings of

FENECIA
The sixth World Multi onferen e on Systemi s Cyberneti s and Informati s(Invited Session on Web Servi es and Grid Computing),

volume 8, Orlando, FL, 2002.
70. J.Cardoso. Quality of Servi e and Semanti Composition of Workows. Ph.d. dissertation, Dep. of Computer S ien e, University ofGeorgia, Athens, GA., 2002.
71. E.C.Nelson. A statisti al basis for software reliability assessment.
Te hni al report, TRW Systems Report, Mar h 1973.
72. Nektarios Gioldasis and Stavros Christodoulakis. Utml: Uniedtransa tion modeling language. In third International Conferen eon Web Information Systems Engineering (WISE02), 0:115, 2002.
73. Wil M.P. van der Aalst, Marlon Dumas, and Arthur H.M. ter Hofstede. Web servi e omposition languages: Old wine in new bottles? euromi ro Conferen e, 00:298 305, Sept. 2003.
74. R.C. Cheung. A user-oriented software reliability model. IEEE
Transa tions On Software Engineering, 6(2):118, Mar h 1980.
75. M.A.Qureshi and W.H.Sanders. Reward model solution methods
with impulse and rate rewards:an algorithm and numeri al results.
Performan e evaluation, 1994.
76. H. Kobayashi. Modeling and Analysis: An Introdu tion to System
Performan e Evaluation Methodology. Addison-Wesley, 1978.
77. J-C. Laprie. Dependable omputing and faut toleran e: on epts
and terminology. In Pro . of the 15th int. Sym. on Fault-tolerant
Computing (FTCS-15), pages 211, 1985.

53