論文――――――――――――――――――――――――――――――――――――
WS-SAGAS: Transaction Model for
Reliable Web-Services-Composition
Specification and Execution
Neila BEN LAKHAL♠ Takashi KOBAYASHI ♦Haruo YOKOTA ♥Recently, building reliable web services compositions
has triggered extensive research efforts. Considering thatweb services tend to be frequently updated or even todisappear unexpectedly, composition may fail easily
causing reliability decrease. To challenge reliability, inthis paper we propose WS-SAGAS, a transaction model
for a reliable specification of web services composition. A
composition is modeled as a hierarchy of arbitrary nested
transactions, executed in a distributed architecture, withproper failure detection and recovery mechanisms.

1. Introduction
Nowadays business processes are typically runningwithin a collection of largely distributed and loosely
coupled computing environments. Generally, suchbusiness processes need to be continually reconsidered to
fit to process changes. To cope with such environment
requirements, wide range of solutions were proposed.
Unfortunately, many of them have several limitations.
They mainly lack appropriate supports for correctness
and reliability enhancement in the presence of failure.
Addressing those issues is difficult because of the absenceof standards application.
Later on, with the emergence of XML-based
standards, followed by web services, researchers realizedthat those standards are strong enough to support suchrequirements. As a consequence, the trend is towards
deploying business processes by connecting elementary
web services. As an example of such trends, Open Grid
Services Architecture (OGSA) is proposed [5]. Despite
these standards help considerably to enhanceinteroperability, reliability is not yet well addressed. In
fact, with web services environment volatility anddynamism, it is most likely to happen that a component
service is updated or moreover it disappears suddenly. Insuch situation, it is necessary to provide proper failuresdetection and recovery mechanisms. This is fundamental
to avoid overall composition consistency review.
To achieve these requirements, augmenting web
services composition specification with the transaction
concept, as already revealed in other areas, seems to beadequate. Nevertheless, considering that web services arenaturally distributed i.e. hosted by different web services
providers, relying on these providers to support♠

Student Member Graduate School of Information Science andEngineering, Tokyo Institute of Technology
neila@de.cs.titech.ac.jp♦
Regular Member
Global Scientific Information andComputing Center tkobaya@cs.titech.ac.jp♥
Regular Member
Tokyo Institute of Technology,
GlobalScientific Information and Computing Centeryokota@cs.titech.ac.jp

1

DBSJ Letters Vol.2, No.2

transactions is not feasible. Thus, it becomes obvious thatdefining an accurate transaction model valid for the whole
composition is essential.
However there are many advanced transaction
models [2]. Applying directly already proposed models is
not acceptable because of web services particularity,
compared with usual software components.
Motivated with these concerns, in this paper we
propose WS-SAGAS, a new transaction model. Specifically
WS-SAGAS extends nested-sagas model [1] and enriches
it with “State” feature. State capturing allows
coordinating primarily autonomous web services in acomposition and helps to inform about web services
composition potential execution progress. Moreover, incase of potential failure occurrence, it will allow to detect
it and indeed to recover. Besides, in WS-SAGAS, weinherit also the “vitality degree” from other models suchas ConTract and Open Nested [2]. We expect the vitality
degree to reduce considerably failure possibilities andindeed increase composition availability. We justify thisas follow. Since originally a transaction succeeds only if allits components are successful, with vitality degree
introduction, only vital components success is required.
The remainder of the paper is organized as follows:
Section 2 gives an overview of WS-SAGAS transaction
model. Section 3 discusses the execution model of
WS-SAGAS in a distributed architecture, and explains it
in an illustrative example. Finally, Section 4 concludes thepaper and provides some remarks concerning future
works.

2. WS-Sagas Transaction Model
2.1 Transaction Paradigm Applicability
Considering that web services tend to be frequently
updated or even to disappear unexpectedly, composition
may fail easily, causing reliability significant decrease.
This makes web services rather different from usual
software components. Consequently, web services warranta particular transaction support especially shaped forthem. We discuss in what follow what kind of properties atransaction needs to satisfy to fit to web services context.
A traditional transaction is supposed to support fully
ACID properties, which is not acceptable for web services.
Our justifications are as follow. First, “Atomicity”
property full support is not required. Instead of deducing
a whole composition failure when one of its components
fails, it is more profitable to soften “Atomicity”, in otherwords, to take advantage of the transaction support that
services might formerly encompass e.g. compensation.
Moreover, it would be more efficient to choose anotherservice, which supports the same semantic. Actually, there
is a wide range of semantically equivalent web services
enabled to provide same functionalities in different ways.
Second, similarly “Isolation” and “Consistency” properties
should be relaxed because none of them is relevant. Sincecompositions might be long running, enforcing “Isolation”
affects negatively execution progress. This is because
parallel transactions communication is required in web
services context, since cooperation among transactions is
an essential feature. Besides, ensuring “Consistency”
enforcement means first, monitoring each web service
invocation and later, identifying the service(s), component

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――
5.

ProcessStart

End

Composition

in

out

WSC1
S2
S1
in

in

v

E1

in
out

v

E2

S4

out
in

S3

out
in

v

E3

in

nv

E4

out

out

2.3 WS-Saga Description
S3.2

S3.1
in

v

E3.1 outinnv

E3.2 out

out

Figure1. WS-SAGAS Description
from a composition, that might violate the whole
composition consistency. This is rather tedious and not
acceptable. Finally “Durability” property should be kept
because once a composition completes, its execution
results must be made persistent. As a result, thetraditional transaction model, with ACID properties
full-support, could not straightforwardly apply to web
services context but it needs to be extended.

2.2 Nested-Sagas Transaction Model
There are several advanced transaction models
proposed [2]. Seeing web services context requirements,
we investigated the applicability of the nested-transaction
model [3], sagas model and finally nested-sagas model [1].
In what follow a comparison between those three models:
1. Nested-sagas transactions can be recursively
defined. Thus they support an arbitrary level ofnesting contrary to the original sagastransactions, where nesting is limited to twolevels;2.
The original nested transaction model of [3]ensures atomicity and isolation of the wholetransaction. A sub-transaction failure isreflected on its parent. This is not conceivablebecause considerable amount of alreadyexecuted works would be lost;
3. Nested-sagas transaction model considers aboutcommunication mechanisms, an essential
feature in web service context. Each saga
specifies input and output ports bound at run
time to mailboxes i.e., messages queue.
4. Nested-sagas with already specified input andoutput ports can be more practically mapped to
web services since structures are somehow
identical;

2

Finally, compensating transaction provides
much more flexibility. Since it was primarily
proposed in sagas transaction model, it isworthy to build on nested-sagas instead of thenested-transaction model.
Guided by this comparison, we propose to inherit
features of interest from the nested-sagas model.
Specifically, arbitrary nesting level, relaxed ACID
properties and transaction compensation. We also inherit
the vitality degree feature, proposed in several advanced
transaction models [2]. Moreover, in order to satisfy
properly the transaction support described in 2.1, we also
propose to enrich it with state capturing feature that wewill describe in the following subsection.

out

WSC2

in

DBSJ Letters Vol.2, No.2

A ws-composition WSC is a collection of n elementsv
v
v
from a composition { E1, E2,…En }. As depicted in Figure
1., a composition is specified as an orchestration ofelements. Depending on the considered nesting level, thevsame element Ei is either assimilated
to an atomicv
element or to a ws-composition e.g. E3 is assimilated to
an atomic element in WSC1 specification while in WSC2v
specification,
it is composed of two elements E3.1
nv
and E3.2 .
An element
has a state Si and a vitality degree,nv
v
where “v” in Ei stands for Vital element and “nv” in Ei
stands for Not Vital element.
Definition I Element state Si
An atomic element is exclusively in one of the following
states:v
1. Waiting: If element Ei is not yet submitted forexecution and is waiting to;v
2. Executing: If element Ei is executing;v
3. Failed: If element Ei encounters a failure;v
4. Aborted: If element Ei receives a request to abort
itself;v
5. Committed: If element Ei has successfully
terminated and was committed andv
Ei
has been
6. Compensated: If elementcompensated.
An element execution is actually the execution of a web
service providing functionalities of interest. This service
execution control is delegated to an engine ei, alreadyallocated to the considered element. State change, as
described in Figure 2., is performed by that engine ei. The
state concept introduction is motivated with the following
concerns:
1. Since web services are originally without state,when they are executing as component of thesame composition, without the state concept
introduction, it will not be possible to know theexecution progress.
2.
In order to decide how to go forward in a WSC
execution i.e. decide to which element(s) todelegate the execution control or whether toresume the execution, it is essential to know theexecution progress of elements being executed.
Definition II Element Vitality Degreev
We introduce the vitality degree of an element Ei inorder to add flexibility in the way ws-composition failurev
is cascaded. We distinguish a vital element E i from a

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――v

DBSJ Letters Vol.2, No.2

Process

create(E i)[CEL(E i) <>empty]

Start

Waiting

inv

execute(E i,e i1 )[start_signal received]v
Ei.state=executing
Eiv.engine=e i1
update(CEP)

allocate()[CEL<>empty]v
Ei .engine=e i2v
Ei .state=executing
update(CEP)

Committed
compensate()[compensate_request received]
Evi.state=compensatedupdate(CEP)

finish()v
generate(CEL(E j))

E1 outnv

Aborting a vital element component of a
ws-composition will induce aborting the whole
ws-composition, if there is no alternative webservice to execute the same element.
Aborting a not-vital element
will not bereflected on its parent, thus a ws-composition
can complete successfully even though not allits components elements were committed.
Initially the vitality degree of all elements is bydefault set to vital.

3. WS-SAGAS Transactions Execution in
THROWS Distributed Architecture

3.1 THROWS Distributed Architecture Overview
In this section we describe how web services
composition, specified as WS-SAGAS transactions, will be
executed in a distributed architecture that we alreadyproposed and named THROWS. More details about
THROWS architecture are available in [4].
THROWS stands for “a Transaction Hierarchy for
Route Organization of Web Services”. Specifically
THROWS is a distributed architecture for web services
composition reliable execution where the control ishierarchically delegated among distributed engines
dynamically discovered, during the composition execution.
These distributed engines interact in a peer-to-peer way.
Each engine ei is responsible of the successfulv
execution of an element Ei that is, the execution of anavailable web service WSi. WSi is offering the samevfunctionalities, as element Ei requires.
THROWS achieves failure capturing and recovery
from failure by the “Candidate Engines List (CEL)”
concept and the “Current Execution Progress (CEP)”
concept. CEP and CEL are to be available on each engine
side. CEL is relative to an element from a composition. It
is the list of candidate engines enabled to execute it i.e.

Car rental

S2

in

Reserve hotel

in

in

v

E3 outnv

E4 out

out

S4

S3

finish()not-vital element Ei as follow:

3

in

v

E2 outAbortedFigure 2. Element State Transition Diagram

3.

in

in

v out

S1

finish()2.

Itineraryallocate()[CEL=empty]
Evi.state=failed
update(CEP)

Compensated1.

ou

Reserve ticket
Failedcommit()[finish_signal received]
Evi.state=committed
update(CEP)

End

WSC1

error()[failure detected]
Evi.state=failed
update(CEP)

ExecutingTripreservation

Figure 3. Trip Reservation Business Process
they control the execution of web services providing
semantics desired by that element.
CEL concept reinforces the composition reliability byproviding alternative execution routes for a same
WS-SAGAS transaction. Besides CEP keeps track of acomposition execution progress and allows execution
control delegation among engines. An engine, while
executing an element, every change in the element, as
described in Figure 2., has to be also reflected on CEP.

3.2

Illustrative Example

To ensure a better understanding of how web
services compositions are depicted as WS-SAGAS
transactions, we describe in what follow the case of a trip
reservation business process. To reserve a trip, a customer
needs to submit an itinerary that indicates desired
destination, departure and arrival time and date.
Airplane ticket and hotel reservation are crucial for thewhole process success. Car rental is considered as optional.
By using WS-SAGAS transaction model description, thetrip reservation business process will be specified as in
Figure.3. Initially, all the elements state is set to “waiting”,
with no engine allocated. The CEP of WSC1 is indicated asfollow:v
v
・ CEP (WSC
1) initial = {(E1, waiting, null), [(E2, waiting,vnvnull); (E3, waiting, null)], (E4, waiting,null)}
v
v
nv
v
whenv
The orderv of execution is E1<[E2; E3]<E4, i.e.
velement E1 is committed successfully, elements E2 and E3
executions are concurrently launched. To start executing
nvv
v
element E4, E2 and E3 successful completions arenvnecessary because both of them are vital. Contrary to E4,
considered as not vital i.e. if airplane ticket and hotel
reservation were successful but car rental failed, thewhole composition success can be deduced.
v
Suppose e11 is allocated to execute E1, i.e. to execute a
web vservice WS11 providing the same semantic vrequiredby E1. If engine e11 executed successfully WS11, E1 state is
updated to “committed”, e11 will check in CEP whetherv
there
is following elements, it will generate CEL of E2 andv
E3, as successors that need to be executed in parallel, andallocate e21 and e31 to execute respectively web services
WS21 and WS31. Finally it will update CEP as follows, andcommunicate it to e21 and e31.

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――vv

CEP (WSC1)11→21,31={(E1, committed, e11), [(E2,vvnv
waiting, e21); (E3, waiting, e31)], (E4, waiting, null)}Suppose that, while engine e21 was executing WS21, afailure occurs for any unpredicted reason such as WS21
unavailability e.g. this may occur since web services are
hosted on the web services providers side. Failure
recovery is performed as follows. e21 will inform its
predecessor engine(s), here e11, that it was unable toterminate successfully E2 execution i.e. will communicate
to engine e11 the CEP updated
as follows:vv
・ CEP (WSC1) 21→11 = {(E1, committed, e11), [(E2, failed,vnve21); (E3, executing, e31)], (E4, waiting, null)}
To avoid the whole composition failure, since elementvv
E2 execution is crucial for its success, i.e. vE2 is a vitalelement; e11 checks the content of CEL (E2) that it has
already generated. Two cases are conceivable:v
・ Case 1: CEL (E2)={e22, e23, e24}v
Engine e11 allocates e22 to execute E2. It also updates
CEP as follows and communicates it to engines e22 and e31.
As result, the execution retrial is enabled and failure is
avoided.
v
v
・ CEP(WSC1)11→22,31= {(E1, committed, e11), [(E2,nvv
waiting, e22); (E3, executing, e31)], (E4, waiting, null)}v
・ Case 2: CEL (E2)=emptyv
Engine e1 while checking CEL (E2) content, it finds
out that there are no other candidate engines, enabled tov
execute element E2. As result, WSC1 execution will beresumed. Executing elements will be requested to abort
and already committed elements will be compensated forvvi.e. E1 will be compensated for by engine e11, element E3
will be aborted by engine e31 and the executed part fromv
E2 before failure, will be compensated for.
・

4. Conclusion
In this paper, we proposed WS-SAGAS, a transaction
model for a reliable specification of web services
composition. In actual fact, concerned with web services
environment volatility and dynamism, an also with thefact that web services are in essence naturally hosted byindependent web services providers, we realized that, toenhance reliability, applying straightforwardly alreadyproposed transaction models is not possible. A
comparative study of several advanced transactions
models guided us to the nested-sagas transaction model,
from which we inherited several interesting features.
Specifically, arbitrary nesting level, relaxed ACID
properties and transaction compensation.
Besides, we inherited also the vitality degree notion.
It allowed us increasing the availability of composition
and indeed to reduce failures possibilities. Moreover, weenriched it with state capturing. This allowed us toenhance considerably composition reliability. In fact state
capturing enabled us to know a composition potential
execution progress and to detect failures.
In addition, we also described how web services
composition, modelled as WS-SAGAS transactions, can be
executed in a distributed architecture THROWS. We havetaken a trip reservation business process as anillustrative
example.
In
THROWS,
WS-SAGAStransactions reliable execution is ensured using CEL and
CEP concepts. Transactions are executed in a distributed

4

DBSJ Letters Vol.2, No.2

way; each transaction element is mapped to a web service,
allocated already to a distributed engine. Such execution
model allowed us to improve noticeably the system
performance. Moreover, WS-SAGAS transaction model isrich enough to be applied in other kind of architecture i.e.
with centralized control.
As future work, we are currently investigating
implementation issues and specifically the feasibility ofweb services composition implementation using
WS-SAGAS transaction model.

[References][1] H. Garcia-Molina, D. Gawlick, J. Klein, K. Kleissner,and K. Salem, Modeling long-running activities as nested
sagas. Data Engineering Bulletin, vol.14, no.1, pp. 14-18.
March.1991.
[2] A.k.Elmagarmid, ed., Database transaction models foradvanced applications, Morgan Kaufmann Publishers,
San Mateo, California, 1992.
[3] J.E.B. Moss, Nested transactions: an approach toreliable distributed computing, " MIT Press, Cambridge,
Massachusetts, 1985.
[4] Neila BEN LAKHAL, Takashi KOBAYASHI and
Haruo YOKOTA, Distributed architecture for reliable
execution of web services, Technical Report of IEICE,
DBWS2003 2B, DE2003-24, pp.97-102, 2003-DBS-131(17), pp.129-136, 2003.7.
[5] OGSA home page, http://www.globus.org/ogsa/

Neila BEN LAKHAL
She received a BS in computer science applied to
management from High Institute of Management of Tunis
Tunisia in 2000. She is currently a Master course student
in the Graduate School of Information Science andEngineering of Tokyo Institute of Technology. She has
been working on transaction processing and distributed
workflow systems failure recovery.

Takashi KOBAYASHIHe received a B.E. and M.E. in computer science from
Tokyo Institute of Technology in 1997 and 1999,
respectively. He is a research associate of Global Scientific
Information and Computing Center, Tokyo Institute ofTechnology. His research interests include software
patterns, software architecture and information retrieval.
He is a member of IPSJ and JSSST.

Haruo YOKOTA
He received the B.E., M.E., and Dr.Eng. degrees from
Tokyo Institute of Technology in 1980, 1982, and 1991,
respectively. He joined Fujitsu Ltd. in 1982, and was a
researcher at ICOT for the Japanese 5th Generation
Computer Project from 1982 to 1986, and at Fujitsu
Laboratories Ltd. from 1986 to 1992. From 1992 to 1998,
he was an Associate Professor in Japan Advanced
Institute of Science and Technology (JAIST). He iscurrently a Professor at Global Scientific Information andComputing Center in Tokyo Institute of Technology. His
research interests include general research area of dataengineering,
information
storagesystems,
anddependable computing. He is a chair of Technical Group of
Data Engineering in IEICE and a member of IPSJ, JSAI,
IEEE, IEEE-CS, ACM and ACM-SIGMOD.

日本データベース学会 Letters Vol.2, No.2