Malika Boulkenafed
email: malika.boulkenafed@inria.fr

Valérie Issarny
email: valerie.issarny¡@inria.fr

AdHocFS: Sharing Files in WLANs

This paper presents the ADHOCFS file system for mobile users, which realizes transparent, adaptive file access according to the users' specific situations (e.g., device in use, network connectivity, etc). The paper concentrates more specifically on the support of ADHOCFS for collaborative file sharing within ad hoc groups of trusted nodes that are in the local communication of each other using the underlying ad hoc network, which has not been addressed in the past.

I. INTRODUCTION

A number of distributed systems deals with mobility (e.g., [START_REF] Kumar | Log-based directory resolution in the coda file system[END_REF], [START_REF] Satyanarayanan | Coda: A highly available file system for a distributed workstation environment[END_REF], [START_REF] Guy | Ficus: A very large scale reliable distributed file system[END_REF], [START_REF] Petersen | Flexible update propagation for weakly consistent replication[END_REF], [START_REF] Kubiatowicz | Oceanstore: An extremely wide-area storage system[END_REF], [START_REF] Mascolo | XMID-DLE: a data-sharing middleware for mobile computing[END_REF]). In these systems, data copies on a given mobile node are updated locally and are subsequently loosely synchronized with copies on either other mobile nodes (e.g., [START_REF] Guy | Ficus: A very large scale reliable distributed file system[END_REF], [START_REF] Petersen | Flexible update propagation for weakly consistent replication[END_REF], [START_REF] Yu | Design and evaluation of a continuous consistency model for replicated services[END_REF], [START_REF] Ekenstam | The bengal database replication system[END_REF]) or stationary servers (e.g., [START_REF] Satyanarayanan | Coda: A highly available file system for a distributed workstation environment[END_REF], [START_REF] Kumar | Log-based directory resolution in the coda file system[END_REF]) through propagation of updates, which is also referred to as optimistic replication. Copy synchronization is then handled through the provision of protocols for the management of conflict detection and resolution. Optimistic replication has proven successful for dealing with data access from wireless terminals, while accounting for network disconnection. However, this comes at a high cost in terms of communication and hence energy, due to the underlying scheme of update propagation. This is even more true in the case of collaborative work where updates are propagated to all nodes storing a copy of updated files.

In general, advances in WLANs and in service discovery protocols call for revising the handling of data sharing on mobile nodes. Specifically, nodes that are in the communication range of each other dynamically form a LAN system, which may be seen as a temporary wired LAN system. However, the resulting LAN system has the following intrinsic requirements that must be dealt with: resource saving and in particular energy saving for (unplugged) mobile nodes, adaptation according to the network's dynamics, and security. This paper introduces the ADHOCFS distributed file system that addresses the above requirements. ADHOCFS manages ad hoc groups, i.e., dynamic groups of trusted peers that are in the commu-nication range of each other, so as to further support secure collaborative sharing of files among the group's members. In addition, ad hoc group management is realized so as to minimize resource consumption, and in particular energy consumption on the mobile nodes.

The remainder is organized as follows. Section II provides an overview of ADHOCFS, discussing resolution of file access from any mobile terminal. Sections III to V detail the core functions of ADHOCFS that together serve realizing secure cooperative caching within ad hoc groups through support for security, ad hoc group management and coherency management. Section VI then assesses AD-HOCFS, evaluating response time of core functionalities through experiment. Finally, Section VII summarizes our contribution compared to related work.

II. ADHOCFS OVERVIEW

ADHOCFS is organized around a traditional file system hierarchy and the local file systems of the mobile terminals act as caches of the distributed file system. Then, file names are resolved into the various locations from which the files may be retrieved. For a given file, its locations include at least the address of the file's home server (see Fig. 1-[a]) and may further extend to both a local address should the file be cached on the terminal (see Fig. 1-[b]), and to terminals in the local communication range (see Fig. 1-[c]) that cache the file, as identified using the ADHOCFS location service. The location service serves identifying peer (mobile) terminals that are accessible by the given mobile terminal and with which files may safely be shared (see Fig. 1-[d]), i.e., terminals belonging to the embedding ad hoc group. Such an identification relies on a traditional service discovery protocol combined with service identification using security domains. Each security domain is uniquely identified through the address of the home server storing the file system appertained to the given domain (see Fig. 1-[e]). An example of security domain is the Web server (identified by its URL) hosting the information relating to a given project, which is used by the project's members to share data. Seamless access to files is then realized by making sure that at least the address of the user's file system stored on his home server The local file system of a mobile terminal is then updated as follows. When access to a file whose name resolves only into the file's home server, is requested, a connection is established using either the wireless LAN or wide-area wireless network, depending on the terminal location. The hierarchy of the local file system gets extended with the path that leads to the requested file (if missing) and the file is copied locally. In addition, upon discovery of peer terminals, the directory hierarchy of the terminals' local file systems are merged so that any file accessible in the local communication range gets identified 1 . Access to such a file from any of the mobile terminals then leads to copy the file locally -if not already cached.

In our context where the files get copied and updated in various locations as users move, it is crucial that each user always sees coherent data (i.e., at least the last version he accessed or, possibly, later versions that got subsequently modified by authorized users). It is further mandatory to integrate adequate cryptographic techniques within the system so that the user's data can only be accessed by authorized users. Such techniques have to be used upon access and transfer of data both in the local (see Fig. 1-[f]) and in the wide area (see Fig. 1-[g]). The next sections detail ADHOCFS support for meeting the above requirements, concentrating on collaborative file sharing within ad hoc groups, which lies in the following three core functionalities: (i) data security, which guarantees that files get accessed and replicated only from/on trusted (mobile) nodes; (ii) ad hoc group management that deals with the creation of ad hoc groups and their dynamics in terms of addition and removal of peer nodes; and (iii) coherency management within groups.

Access to files on the home server from mobile terminals is no longer discussed, as it is managed in a way similar to existing mobile systems. Briefly stated, secure file access from a mobile terminal to the file's home server is implemented via public key cryptography. Coherency management among distinct groups is further based on optimistic replication; file copies on mobile terminals are then reconciled with copies at the server upon synchronization with the server, using the same reconciliation scheme as the one discussed in Section V. Finally, it is considered that any mobile terminal regularly synchronizes with the files' home servers to which it is granted access to, using either infrastructure-based wireless networking or ad hoc networking, depending on the specific location of the terminal and servers.

III. SECURITY MANAGEMENT

Security is of crucial importance in our context since we are using both wireless LAN and global wireless networks. It is therefore mandatory to ensure end-to-end privacy and integrity of the user's data. However, as our platform aims at running on resource constrained terminals (e.g., wireless PDA), it is necessary to balance strong security enforcement with resource consumption, and in particular energy. ADHOCFS uses both asymmetric and symmetric cryptography. The former is used for securing communication links between any mobile terminal and a file server, and is not further detailed due to the paper focus on file sharing among mobile terminals. The latter is used for securing communication links between any two peer mobile terminals within an ad hoc group. Symmetric cryptography enables ensuring privacy of data between two terminals using a well-known algorithm and a shared secret, i.e., a secret key. Moreover, by using symmetric cryptography in conjunction with a cryptographically secure hash function, also called one way function, it is possible to ensure data integrity [START_REF] Menezes | Handbook of Applied Cryptography[END_REF].

In ADHOCFS, files of related interests are grouped into a security domain. A secret domain key is then associated with each domain, and it is shared by the domain's server and all the terminals whose users are granted access to this domain. More specifically, the secret key is regularly computed at the domain's server and securely propagated to trusted mobile terminals when they synchronize with the server. The domain key is used for both authentication and secure message exchanges among peer mobile terminals.

The use of the domain key enables minimizing the computation cost associated with cryptography. However, the security enforced by ADHOCFS is dependent upon the avoidance of the domain key forgery, which requires regular revocation of the key. Protection against forgery of the domain key on the terminal itself is enforced by storing the key encrypted on the terminal, and by decrypting it using the user's password (e.g., using a PAM module in Linux) 2 . An alternative solution to the setting of the group key would have been to integrate a protocol for key agreement within dynamic collaborative groups (e.g., [START_REF] Kim | Simple and fault-tolerant key agreement for dynamic collaborative groups[END_REF]). However, such protocols are costly, both in terms of computation and communication costs. This is why we have preferred to undertake a simpler solution in a first step. Finally, access control to files relies on the access control of the underlying local file system, given that file owners do not change.

Regarding the encryption of files transferred from one mobile node to another, the file blocks are encrypted and decrypted independently of the others (see Fig. 2-[a]). However, to protect against attacks that would replace blocks within messages, the header of each such message includes a secure checksum (using MD5) of the transferred file blocks (see Fig. 2-[c]). In addition, we use a nonce to ensure that any message received in reply to a request is indeed the reply. Using per-block encryption allows the decryption of blocks upon actual access, instead of decryption at the time the blocks are received. In the same way, a block that is decrypted will be encrypted only if a request for the block (e.g., request for a file copy from a peer mobile terminal) is received. In this way, the computation cost associated with cryptography is minimized, and hence energy consumption due to security management is reduced. Note that reduced energy consumption based on on-demand decryption is obtained due to the fact that transferred files are encrypted using the domain key (see Fig. 2-[b]). If the files were encrypted using a temporary secret key that would be set up upon the establishment of a connection between any two peer mobile terminals, then Fig. 3. Merging groups upon every subsequent transmission of a file, the file would have to be decrypted (using the secret key shared with the terminal from which the file was obtained) -if not already done-and then encrypted (using the secret key shared with the requesting terminal).

IV. AD HOC GROUP MANAGEMENT

Ad hoc group management in ADHOCFS builds upon an existing service discovery protocol, i.e., the IETF Service Location Protocol (SLP) [START_REF] Guttman | Service location protocol, version 2[END_REF]. We use the configuration of SLP that does not rely on a directory agent for service discovery. In ADHOCFS, SLP serves locating peer mobile nodes, i.e., nodes in the communication range of the WLAN that have access to common security domains. Every mobile node acts as a Service Agent that handles lookup queries for peer nodes of ADHOCFS. Upon initialization, each terminal registers itself for each security domain of ADHOCFS it has access to, using the following format (i.e., SLP's Universal Resource Locator -URL-format): service:AdHocFS://IP address:port number /domain 3 .

Periodically, every mobile terminal looks for peer terminals by issuing, as a User Agent, the following service request: service:AdHocFS. Every mobile terminal in the local range sends back as many messages as security domains it belongs to; each message carries the URL associated with the given security domain, which embeds the terminal's IP address, port number, domain and unique identifier (UID). Using received URLs, terminals are able to join the ad hoc groups they belong to.

Consider first that all peer nodes are isolated (see Fig. 3-[a]), which is known through the group variable that has the value nil on every peer. Then, the embedding ad hoc group is created by one of the peers, called leader, that is the node that has the smallest UID. The leader concurrently interacts with all its peers as follows: it first establishes a secure connection with the peer, it then requests the peer for its local directory hierarchy that it will merge with its own. The request additionally embeds the list of group members. The leader finally broadcasts the directory hierarchy of the ad hoc group to all the peers and cooperative caching within the group may proceed. In addition, all the peers but the leaders concurrently establish secure connections with all their peers that have a larger UID than theirs. On every peer, the value of the group variable is now equal to the list of peers, and the leader variable is equal to the UID of the leader. Note that for the case where a node is isolated and hence the single member of a group, the value of the leader variable is the UID of the node.

Dynamics of the group is handled by periodically looking for peers. For a given period, the leader becomes the peer with the next higher UID than the value of leader. The leader then checks the value of group with the list of nodes returned by SLP. If these two values differ, the ad hoc group must integrate the (potential) new comers (which may themselves be part of a distinct ad hoc group), and discard the (potential) nodes that left. Addition of members is handled by merging groups as follows, considering that an isolated node forms a singleton group (see Fig. 3-[b]). In the reply to SLP requests for the discovery of peer nodes, the node embeds its local value of group and leader. Then, the leader of the new group becomes the node that has the smallest UID among all the leaders if all the merged groups have more than one member. If some groups are singleton, the leader is taken from the largest groups. The new leader then performs a merge protocol similar to the above one with all the leaders of the merged groups. All the leaders of merged groups then forward the updated directory hierarchy 4 to the peers that were led by them, together with the new value of group and leader, leading nodes to concurrently establish missing connections with peer nodes (see Fig. 3-[c]) and to form the new group (see Fig. 3-[d]). Leaving nodes are straightforward to handle; the leader broadcasts the new value of group to peer nodes. Note that the case of leader removal is handled by changing the leader on each period. Hence, in the worst case, a newly formed group stabilizes in at most two periods after the change occurrence.

The main cost of ad hoc group management lies in message exchanges for discovering peers and then merging groups. The overall cost is further proportional to the period that is set for managing the group's dynamics. The period is initially set to a given value and is then dynamically adapted according to the past behavior of the embedding group (which may be the node itself in the case of singleton group), using statistical modal class [START_REF] Degroot | Probability and Statistics[END_REF].

Peers interact through the WLAN that may be in either the infrastructure-base mode if a base station is nearby or the ad hoc mode in the absence of base station. ADHOCFS does not impose any specific networking mode and it is currently up to the users to set the preferred mode of operation, assuming that nodes in the local communication range of each other select the same networking mode. Note that ongoing work in the area of mobile networking will further allow for the transparent setting of the most adequate networking mode according to the environment [START_REF] Agha | VCB: an efficient resource sharing scheme for cellular mobile systems[END_REF]. In the specific case of ad hoc networking, it should be accounted for the fact that groups may only be partially connected if the network protocol does not support ad hoc routing among nodes. In this case, two groups merge only if all their members can communicate, which is identified by comparing the lists of peer nodes obtained through the slptool function of SLP.

V. COHERENCY MANAGEMENT

Existing network file systems aimed at mobile nodes implement optimistic replication so as to enable file access in disconnected mode. However, in the case of file sharing within an ad hoc group, file copies cached on peers may be strongly synchronized so as to prevent the occurrence of conflicting updates while in the group (apart from those created due to concurrent file updates before joining the group) and hence better support collaborative work groups. This further leads to minimize the communication cost (and hence energy cost) of update propagation since the complexity of update propagation among peer nodes under optimistic replication is in O(N) for every concurrent update, with ¡ being the number of peers, while it can be significantly reduced under conservative replication as detailed hereafter. In other words, base techniques that have been proven successful in wired LANs are of direct relevance for coherency management within ad hoc groups. Hence, ADHOCFS implements optimistic replication over nodes that belong to distinct groups, and conservative replication over peer nodes 5 . The following details our conservative coherency protocol within ad hoc groups.

Our coherency management protocol is based on a exclusive writer protocol within an ad hoc group. Using read/write locking within a group, all write operations are exclusive within the group while read operations are shared. However, local files can be manipulated (read/write) independently within disjoint groups, provided that data are synchronized when integrating a group 6 . A peer can be in five modes regarding a given data file: Fresh, the peer holds a fresh data copy after synchronizing with the reference copy; Read, the peer can read the data; UpdateRead, the peer is allowed to read the data but has to update its copy first; ReadWrite, the peer can read and write the data; and Invalid, the peer has no access to the data. With this protocol, either a peer modifies data in the ReadWrite state and all the other peers are in the Invalid state; or all the peers are in the Read or UpdateRead state. This protocol ensures that all reads access the most recent file version within the group. This guarantees data coherency within a group, given that data are reconciliated upon their first access. Within a group, concurrent and diverging file copies are detected using the CCL (Coherency Control List), which is attached to each file. The CCL logs in a data structure how and when the given file copy was modified since it was copied from its home server. An example of CCL is given in Figure 4. The CCL comprises the timestamp value of the reference copy, i.e., the copy stored on the file's home server 7 , at the time it was copied/synchronized with, and the log of subsequent updates on the local copy (see Fig. 4-[a]). The log is the list of all successive data holders, as seen by this specific data file copy (see Fig. 4-[b]). Data holders give the set of peers belonging to the same ad hoc group and locally caching the data. Every time the group members composition is modified, through addition or deletion of a peer, and upon update, a new item is added to the list, which contains the new set of group members storing the data (see Fig. 4-[c]). This enables tracking the dynamics of the ad hoc group due to peers mobility, and to distinguish updates within different ad hoc groups in order to enhance conflict detection. If a disconnected peer updates its local copy of the data, a new item is added to its local list, which contains only its UID. For every group composition, the list of modified file blocks is maintained (see Fig. 4-[d]).

Given local CCLs, a mobile node is able to determine whether its local file copies are coherent and/or can be reconciled with the file copies stored on peer nodes of the embedding ad hoc group 8 . When a node joins the ad hoc group, its directory hierarchy and the group's one are merged (see ¡ IV). The merging is further realized so that the a priori latest version (i.e., greatest timestamp and largest update list) of a given file copy is assigned the ReadWrite mode while others are assigned the Invalid mode if none of the file copies are being accessed. The same scheme applies if either the only copy that is being accessed is the latest version or all the copies being accessed may be reconciled. On the other hand, if diverging copies are being accessed, exceptions are signaled to all the applications that are accessing the file, leading to application-specific conflict resolution. In general, at the time of group merging, diverging copies are detected and are made known to users by associating a tag to local file copies that have diverged, which appears upon browsing.

File updates within the group are then lazily propagated from the latest writer as follows. If the file is requested for write access by another node, then the node acquires the ReadWrite lock and gets the list of updates. If the file is requested for read access the node acquires the Read lock and gets the list of updates. However, all the other nodes caching a copy of the file acquire only the UpdateRead lock. Note that the sent list of updates may not be sufficient to reconcile -if possible-the local copy since copies are not synchronized as nodes enter an ad hoc group. Hence, upon actual access, missing updates are possibly requested to the latest writer for reconciliation. In the case where the latest writer of a given file leaves the group, the protocol guarantees that the copy that will be accessed is the latest version present in the group. Lazy update propagation follows from our concern of minimizing energy consumption and hence computation and communication.

VI. EXPERIMENT

A first prototype of ADHOCFS has been implemented in Objective Caml 3 9 . The ADHOCFS prototype builds upon the Extended 2 FS (Ext2) local file system, the Blowfish symmetric encryption algorithm [START_REF] Schneier | Description of a new variable-length key, 64-bit block cipher (blowfish)[END_REF] using 128 bits keys, and the OpenSLP10 implementation of SLP. Mobile terminals of the platform are laptops with a 500 MHz Pentium III CPU, 256 KB of cache, 200 MB of RAM and a 10 GB hard disk running under Linux operating system. The wireless LAN is IEEE 802.11b in the ad hoc mode (Lucent 11Mb WaveLAN PC Card).

Figure 5 gives the time taken for creating a group, leaving and joining a group, which are linear with the group size. The main cost of group creation lies in detecting trusted peers and sending the directory hierarchies by group leader so as to compute the directory hierarchy of the overall group, which is mandatory to allow peers belonging to the group to have a global view of shared data and to enable collaborative sharing.

Table I gives the time taken to locally access a coherent data file in the write mode when the peer is in the Read state. This time is constant for a given group size: it corresponds to the cost of getting the token and notifying the peers to set their state to Invalid. Thus, messages sent to realize the coherent access are only control messages, and do not contain any updates. Note that the cost of additional peers in terms of response time is only of about 0.005 sec. Table I further shows the associated cost in terms of energy consumption, based on the formulas given in [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF]. Note that energy consumption is highly dependent upon the size of the group since non destination peers consume energy when messages are being sent under the ad hoc mode. Figure 6 gives the time taken to access a coherent data file when the peer is in the UpdateRead state, which corresponds to the cost of update propagation. Using our coherency protocol, getting locally access to a coherent data depends on the update size, while group size affects slightly the performance of our protocol. However, the energy consumption depends on both the group size and (based on equations from [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF]), where is the ad hoc group size and ( ) 1 3 the update size. Figure 7 gives the time taken to access a coherent data file when the peer C is in the Invalid state, after successive write operations performed by different peers. This time corresponds to the cost of getting the token and the updates, which are lazily propagated. More precisely, the peer C requesting for file access knows only the identity of the first writer D (i.e., the peer that set C to the Invalid state), and thus sends its request to D . However, D is not the actual token owner (last writer); it thus forwards C 's request to the peer that it considers as being the token owner (i.e., the peer that set D to the Invalid state). The process is then repeated until the request reaches the actual token owner (the last writer), which replies with the updates and the appropriate meta-data. Compared to the results shown in Figure 6, the cost of propagating the request among successive writers amounts to the cost of propagating an update from one peer to another.

Figure 8 gives the cost of getting a copy of a data file for writing when the peer does not cache it locally, while the peers caching the file within the ad hoc group, are in the Read/UpdateRead state. The resulting cost is linearly dependent on the file size. Similarly, the cost of opening a data file in the writing/reading mode increases linearly with update size. Hence, using our coherency protocol, getting locally access to a coherent file depends on the updates size, while group size affects only very slightly the performance of our protocol in terms of response time.

The above results show that the overhead introduced by the core functions of ADHOCFS is kept to a minimum, since response times offered by ADHOCFS remain comparable to the exchange of a data file between two nodes through the WLAN. To further show the benefits of lazy update propagation within ad hoc groups in terms of response time and energy consumption, we compare it to a version of our coherency protocol where updates are propagated whenever they occurs as realized by optimistic replication protocols supporting collaborative, peer-to-peer file sharing. We consider an ad hoc group of four peers, all caching the data, and being in the Read state. We further consider four successive write operations by different peers, each leading to an update size of 640 Kbytes. Under our protocol, the times taken to write access a coherent data file from the first write to the fourth one are respectively equal to: 0.019 sec, 1.20 sec, 1.22 sec, and 1.27 sec (see Figure 7). On the other hand, when the updates are propagated whenever they occur, the time taken to write access a coherent data file is the same for all four write operations in the above scenario, and is equal to 3.639 sec, which leads to 7218 mW of extra energy consumption. Thus, lazy update propagation allows for better response time but also for a lower communication cost, and hence lower energy consumption.

VII. CONCLUSION

In ADHOCFS, the file systems of mobile terminals act as local caches, and mobile terminals that have access to common files and are able to communicate through the wireless LAN, cooperate to form an ad hoc distributed file system. Core components of ADHOCFS lies in:

A naming service that resolves file names into the various locations from which files may be retrieved (i.e., at least the address of the file's home server, local copy if cached, peer terminals in the communication range that stores a file copy). A location service, which enables setting up ad hoc groups of trusted mobile terminals that are connected using the wireless LAN. In addition, secure links are established between peer nodes so as to guarantee data integrity and privacy, while minimizing the computation cost and hence energy consumption associated with cryptography.

A coherency management service that reconciles copies cached on mobile terminals that belong to the same group and enables collaborative file sharing among peer nodes.

We have presented an evaluation of ADHOCFS in terms of response times offered by the current ADHOCFS prototype. Results show that the response time of ADHOCFS operations remain comparable to the time taken for exchanging a file over the WLAN.

There has been a large amount of work on supporting access to shared files on mobile terminals. Early work in the area has been concentrating on enabling access to local files, independent of network connectivity. Hence, most proposals have been oriented towards ensuring availability of a local copy so as to cope with temporary disconnection. Relevant work in the area includes solutions to file prefetching (e.g., [START_REF] Kuenning | Automated hoarding for mobile computers[END_REF]) and to optimistic replication (e.g., [START_REF] Satyanarayanan | Coda: A highly available file system for a distributed workstation environment[END_REF], [START_REF] Guy | Ficus: A very large scale reliable distributed file system[END_REF], [START_REF] Kumar | Log-based directory resolution in the coda file system[END_REF], [START_REF] Joseph | Rover: A toolkit for mobile information access[END_REF], [START_REF] Petersen | Flexible update propagation for weakly consistent replication[END_REF], [START_REF] Yu | Design and evaluation of a continuous consistency model for replicated services[END_REF], [START_REF] Ekenstam | The bengal database replication system[END_REF], [START_REF] Mascolo | XMID-DLE: a data-sharing middleware for mobile computing[END_REF]). ADHOCFS does not currently include any support for managing the local cache according to future accesses, and in particular support for prefetching. This is part of our future work, which will benefit from existing solutions such as the one of [START_REF] Kuenning | Automated hoarding for mobile computers[END_REF]. On the other hand, ADHOCFS resembles and benefits from past work on optimistic replication since we have adopted a log-based solution for update propagation, which has been proven successful in this area. ADHOCFS further uses a conventional log-based optimistic coherency management for reconciliating copies that have been accessed within distinct ad hoc groups. It is further part of our future work to enhance support for automatic reconciliation based on latest research results (e.g., [START_REF] Kermarrec | The IceCube approach to the reconciliation of divergent replicas[END_REF]). However, ADHOCFS differs from the aforementioned references by accounting for the specifics of today's WLANs that allows creating dynamic networks of mobile nodes when they are in the local communication range of each other. Such dynamic networks may then be exploited for supporting collaborative group works. ADHOCFS offers such a capability through the management of dynamic, ad hoc groups of trusted mobile terminals, among which files may safely be shared. This has further led us to use a conservative replication scheme within ad hoc groups as it is more suited to collaborative applications, and further allows reducing the communication and energy cost associated with coherency management.

An ad hoc group of ADHOCFS realizes cooperative sharing of nomadic data, which has been an active area of research over the last few years given the increasing interest for supporting pervasive computing. Work in the area that is the closest to our concern relates to enabling data caching in various locations, and subsequently retrieving them in another location. However, existing proposals concentrate on leaving data on untrusted, stationary local storage servers (e.g., [START_REF] Kubiatowicz | Oceanstore: An extremely wide-area storage system[END_REF], [START_REF] Castro | Locating application data across service discovery domains[END_REF]), and are thus complementary to ours since we are addressing collaborative caching among trusted mobile nodes.

Among enhancements of ADHOCFS that we are working on, we are going to further elaborate synchronization with the files' home servers so as to both minimize the occurrence of diverging copies, and regularly revoke the domain key used within groups to securely share files. We are further interested in improving the quality of service of ADHOCFS, regarding in particular availability, examining more specifically replication of cached files within a group to ensure availability of the files' latest version despite the groups' dynamics. Exploitation of ad hoc networking raises the issue of further exploiting ad hoc routing protocols to allow accessing files stored on a terminal that is reachable in a number of hops. We have not integrated such a facility in ADHOCFS due to our focus on collaborative work where we consider that the communication range of WLANs like IEEE 802.11 allows for sufficient coverage of collaborative work groups. However, ad hoc routing protocols may conveniently be exploited to access a file that is not available in a group in the absence of a base station, which prevents accessing the file's home server. A base solution to this issue is presented in [START_REF] Sailhan | Energy-aware web caching for mobile terminals[END_REF] for the specific case of Web data, which can be easily adapted to the context of ADHOCFS. Finally, we are going to experiment the use of ADHOCFS with various types of mobile terminals (e.g., iPAQ), which is quite direct given the availability of Linux for embedded platforms.

Fig. 1 .

 1 Fig. 1. File access in AdHocFS

Fig. 2 .

 2 Fig. 2. File encryption

Fig. 4 .

 4 Fig. 4. Coherency Control List

Fig. 5 .Fig. 6 .

 56 Fig. 5. Time taken for group creation

Fig. 7 .Fig. 8 .

 78 Fig. 7. From Invalid to ReadWrite state after successive writes

TABLE I FROM

 I READ TO READWRITE STATE

				Group size (peers)	2		3		4	5	6	7	8	9	10
				Time (sec)		0.00949	0.01281	0.01982	0.02129	0.02645	0.02977	0.03493	0.03825	0.04341
				Energy (mW.sec)	1.58		2.91		5.4	6.67	9.08	11.87	15	18. 51	22.38
		1.6
									Group Creation
							One peer leaves the group
							One peer joins the group
		1.4
		1.2
		1
	Time (sec)	0.8
		0.6
		0.4
		0.2
		0
		1	2	3	4	5	6	7	8	9	10
					Group Size (peers)

Note that the file data is not merged.

Proceedings of the Second IEEE International Symposium on Network Computing and Applications (NCA'03)

Authorized licensed use limited to: UR Rocquencourt. Downloaded on June 23, 2009 at 11:15 from IEEE Xplore. Restrictions apply.

Note that this could alternatively be realized using a smartcard, for mobile terminals equipped with a smartcard device driver.Group leaderGroup member (slave)[c] [d] [a][b]

Mobile terminals that do not want to cooperate (e.g., for the sake of energy saving) de-register for the security domains they belong to.Proceedings of the Second IEEE International Symposium on Network Computing and Applications (NCA'03)

This update is the difference with the previous value of the hierarchy.

Note that the granularity of coherency management is left upon the users who choose the most effective decomposition of their shared data into files. Taking for instance the case of document editing, the document may be structured into a number of files according to the degree of concurrency updates that is targeted.

Note that a user who is being involved in a group can still choose to read his local file copy, which may possibly not be up to date, while waiting for acquiring a lock for accessing the shared file.

If a file is created locally on a peer, the corresponding timestamp has a special value (NIL) to indicate that this file has no reference copy yet.

Basically, two copies can be reconciled if the CCL associated to one is a sub-list of the CCL associated with the other.

caml.inria.fr

openslp.org Proceedings of the Second IEEE International Symposium on Network Computing and Applications (NCA'03)

ACKNOWLEDGMENT

The authors would like to acknowledge the contribution of David Mentré, Anis Ben-Arbia, and Animesh Pathak to the design and the implementation of the ad hoc group management protocol and the coherency management protocol. This Project has been partially funded by ITEA VIVIAN Project (ITEA 99040).


F Tartanoglu

V Issarny

A Romanovsky
email: alexander.romanovsky@newcastle.ac.uk

N Levy

Coordinated Forward Error Recovery for Composite Web Services

This paper proposes a solution based on forward error recovery, oriented towards providing dependability of composite Web services. While exploiting their possible support for fault tolerance (e.g., transactional support at the level of each service), the proposed solution has no impact on the autonomy of the individual Web services, Our solution lies in system structuring in terms of co-operative atomic actions that have a well-defined behaviour, both in the absence and in the presence of service failures. More specifically, we define the notion of Web Service Composition Action (WSCA), based on the Coordinated Atomic Action concept, which allows structuring composite Web services in terms of dependable actions. Fault tolerance can then be obtained as an emergent property of the aggregation of several potentially non-dependable services. We further introduce a framework enabling the development of composite Web services based on WSCAs, consisting of an XML-based language for the specification of WSCAs.

Introduction

Systems that build upon the Web services architecture are expected to become a major class of wide-area open distributed systems in the near future. The Web services architecture targets the development of applications based on XML-based standards, hence easing the development of distributed systems through the dynamic integration of applications distributed over the Internet, irrespective of their underlying platforms. However, the provision of effective support for the dependable integration of Web services is still an open issue, which has led to tremendous research effort over the last few years, in both industry and academia (e.g., [START_REF] Benatallah | Patterns and Skeletons for Parallel and Distributed Computing[END_REF][START_REF] Casati | Developing e-services for composing e-services[END_REF][START_REF]Business Process Execution Language for Web Services (BPEL4WS) 1.0[END_REF][START_REF] Mikalsen | Transactional attitudes: Reliable composition of autonomous Web services[END_REF][START_REF]Business Transaction Protocol (BTP)[END_REF][START_REF] Yang | Web component: A substrate for Web service reuse and composition[END_REF]).

Composition of Web services

Although the definition of the overall Web services architecture is still incomplete, the base standards have already emerged from the W3C 1 , which define a core middleware for Web services, partly building upon results from object-based and component-based middleware technologies. These standards relate to the specification of Web services and a supporting interaction protocol. SOAP (Simple Object Access Protocol) defines a lightweight protocol for information exchange that sets the rules of how to encode data in XML as well as the SOAP mapping to an Internet transport protocol (e.g., HTTP) [START_REF] W3c | Simple Object Access Protocol (SOAP) 1.1, W3C Note[END_REF]. Specification of Web service interfaces relies on the WSDL (Web Services Description Language) [START_REF]W3C. Web Services Description Language (WSDL) 1.1, W3C Note[END_REF] declarative language that is used to specify: (i) the service's abstract interface that describes the messages exchanged with the service, and (ii) the concrete binding information that contains specific protocoldependent details including the network end-point address of the service. Complementary to the above core middleware for the integration of Web services is UDDI (Universal Description, Discovery and Integration); this specifies a registry for dynamically locating and advertising Web services [START_REF]Universal Description, Discovery and Integration (UDDI), Version 3 Specification[END_REF].

Composing Web services relates to dealing with the assembly of existing services so as to deliver a new service out of them, given the corresponding published interfaces (see Figure 1). Integration of Web services is then realized according to the specification of the overall process composing the Web services. The process specifying the composition must actually not solely define the functional behaviour of the process in terms of interactions with the composed services, but also the process's non-functional properties, possibly exploiting middleware-related services. Various non-functional properties (e.g., availability, extendibility, reliability, openness, performance, security, scalability) should be accounted for in the context of Web services. However, enforcing dependability of composite Web services is one of the most challenging issues due to the concern for supporting business processes, combined with the fact that the composition process deals with the assembly of loosely-coupled autonomous components.

Web

WSDL

Composite

Dependability of composite Web services

In general, Web services run on heterogeneous platforms, and are autonomous components with different characteristics (e.g., transactional supports, concurrency policies, access rights). Moreover, Web services can use different transport protocols (e.g., HTTP, SMTP) and interacting with them requires dealing with limitations of the Internet, which is not a reliable media [START_REF] Kalyanakrishnan | Reliability of internet hosts: a case study from the end user's perspective[END_REF]. In addition, availability is a major issue in addressing dependability in Web service applications. Web services may be unavailable for an unknown reason and for an unknown amount of time. Moreover, the overall network status and server loads may cause extensively long delays on responses from Web service servers.

Composite Web services have high dependability requirements that call for dedicated fault tolerance mechanisms due to both the specifics of the Web services architecture and limitations of the Internet. The autonomy of component Web services raises challenging issues in specifying composition processes and in particular behaviour of composite services in the presence of faults. These faults include but are not limited to (i) faults occurring at the level of the Web services, which may be notified by error messages, (ii) faults at the underlying platform (e.g., hardware faults, timeouts), and (iii) faults due to online upgrades of component services and/or of their interfaces. These specifics of Web services require special care in the design of supporting fault tolerance mechanisms, which is the focus of our paper.

Contributions

This paper introduces a solution based on forward error recovery, for making composite Web services fault tolerant. The proposed solution has no impact on the autonomy of the individual Web Services, while exploiting their possible support for fault tolerance (e.g., transaction support at the level of each service). We define the notion of Web Service Composition Action (WSCA), which allows structuring composite Web services in terms of coordinated atomic actions that have a well-defined behaviour, both in the absence and in the presence of service failures. We then introduce an XML-based language for the specification of WSCAs. The language is used to define fault tolerant composite Web services and provides the application logic.

Section 2 presents proposed fault tolerance mechanisms for composite Web services, identifying limitations of mechanisms based on backward error recovery. This leads us to introduce Web Services Composition Actions (WSCA) for structuring the composition of Web services into fault tolerant functional units in Section 3. The associated development process and deployment of composite Web services is described in Section 4. Section 4.2 then defines the XML-based WSCA Language (WSCAL) to be used for specifying Web services composition based on WSCA, which may further be exploited for the automatic generation of the implementation of composite services. Finally, Section 5 summarises our contribution, and discusses our current and future work.

Fault tolerance mechanisms for Web services

The choice of fault tolerance techniques to be exploited for the development of dependable systems depends very much on the fault assumptions and on the system's characteristics and requirements (Section 2.1). Developing fault tolerant mechanisms for composite Web services has been an active area of research over the last couple of years (see [START_REF] Tartanoglu | Dependability in the Web Service Architecture[END_REF] for a survey). Existing proposals mainly exploit backward error recovery, and more specifically, transactions (Section 2.2). However, the autonomy of Web services and the Web latency have led to exploit more flexible transactional models and forward error recovery techniques (Section 2.3).

Backward versus forward error recovery

There are two main classes of error recovery [START_REF] Lee | Fault Tolerance Principles and Practice, volume 3 of Dependable Computing and Fault-Tolerant Systems[END_REF]: backward (based on rolling system components back to the previous correct state) and forward error recovery (which involves transforming the system components into any correct state). The former uses either diversely-implemented software or simple retry; the latter is usually applicationspecific and relies on an exception handling mechanism [START_REF] Cristian | Dependability of Resilient Computers, chapter Exception Handling[END_REF].

It is a widely-accepted fact that the most beneficial way of applying fault tolerance is by associating its measures with system structuring units as this decreases system complexity and makes it easier for developers to apply fault tolerance [START_REF] Randell | Recursive structured distributed computing systems[END_REF]. Structuring units applied for both building distributed systems and providing their fault tolerance are wellknown: they are distributed transactions and atomic actions (also referred to as conversations). Distributed transactions [START_REF] Gray | Transaction Processing: Concepts and Techniques[END_REF] use backward error recovery as the main fault tolerance measure in order to satisfy completely or partially the ACID (atomicity, consistency, isolation, durability) properties. Atomic actions [START_REF] Campbell | Error recovery in asynchronous systems[END_REF] allow programmers to apply both backward and forward error recovery. The latter relies on coordinated handling of action exceptions that involves all action participants. Backward error recovery has a limited applicability, and in spite of all its advantages, modern systems are increasingly relying on forward error recovery, which uses appropriate exception handling techniques as a means [START_REF] Cristian | Dependability of Resilient Computers, chapter Exception Handling[END_REF]. Examples of such applications are complex systems involving human beings, COTS components, external devices, several organizations, movement of goods, operations on the environment, real-time systems that do not have time to go back. Integrated Web services clearly falls into this category.

Backward error recovery for the Web

Transactions have been proven successful in enforcing fault tolerance in closed distributed systems and are extensively exploited for the implementation of primitive (noncomposite) Web services. However, transactions are not suited for making the composition of Web services fault tolerant in general, for at least two reasons. First, the management of transactions that are distributed over Web services requires cooperation among the transactional supports of individual Web services, which may not be compliant with each other and may not be willing to do so given their intrinsic autonomy and the fact that they span different administrative domains. Second, locking resources until the termination of the embedding transaction is in general not appropriate for Web services, still due to their autonomy, and also to the fact that they potentially have a large number of concurrent clients that will not stand extensive delays.

Enhanced transactional models have been considered to alleviate the latter shortcoming. In particular, the split model (also referred to as open-nested transactions) where transactions may split into a number of concurrent subtransactions that can commit independently allows reducing the latency due to locking. Typically, sub-transactions are matched to the transactions already supported by Web services (e.g., transactional booking offered by a service).

Hence, transactions over composite services do not increase the access latency as offered by the individual services. Enforcing the atomicity property over a transaction that has been split into a number of sub-transactions then requires using compensation over committed sub-transactions in the case of transaction abortion. However, to support this, Web services should provide compensating operations for all the operations they offer. Such an issue is in particular addressed by the BPEL4WS [START_REF]Business Process Execution Language for Web Services (BPEL4WS) 1.0[END_REF] and WSCI [START_REF] W3c | Web Service Choreography Interface (WSCI) 1.0, W3C Note[END_REF] languages for specifying services, which allow defining compensating operations associated with the services' operations. It is worth noting that using compensation for aborting distributed transactions must extend to all the participating Web services (i.e., cascading compensation by analogy with cascading abort). Such a concern is addressed in [START_REF] Mikalsen | Transactional attitudes: Reliable composition of autonomous Web services[END_REF]. This paper introduces a middleware whose API may be exploited by clients of a composite service for specifying and executing a (open-nested) transaction over a set of Web services whose termination is dictated by the outcomes of the transactional operations invoked on the individual services.

In addition to client-side solutions to the coordination of distributed open-nested transactions, work is undertaken in the area of distributed transaction protocols supporting the deployment of transactions over the Web, while not imposing long-lived locks over Web resources. These include BTP (Business Transaction Protocol) [START_REF]Business Transaction Protocol (BTP)[END_REF] and WS-Transaction [START_REF]Web Services Transaction (WS-Transaction)[END_REF]. The BTP protocol introduces the notion of cohesion, which allows non-ACID transactions to be defined by not requiring successful termination of all the transaction's participants for committing.

WS-Transaction defines a specialization of WS-Coordination [START_REF]BEA and IBM. Web Services Coordination (WS-Coordination)[END_REF], which is an extensible framework for specifying distributed protocols that coordinate the execution of Web services, and that can be used in conjunction with BPEL4WS. The business activity protocol defined in WS-Transaction specifically serves coordinating the execution of open-nested transactions over a set of business processes.

Forward error recovery for the Web

In addition to backward error recovery, forward error recovery, using exception handling mechanisms, is extensively exploited in the specification of composite Web services in order to handle error occurrences. For instance, in BPEL4WS [START_REF]Business Process Execution Language for Web Services (BPEL4WS) 1.0[END_REF], exception handlers (referred to as fault handlers) can be associated to a (possibly nested) activity so that when an error occurs inside an activity, its execution terminates, and the corresponding exception handler is executed. However, when an activity is defined as a concurrent process and at least one embedded activity signals an exception, all the embedded activities are terminated as soon as one signaled exception is caught, and only the handler for this specific exception is executed. Hence, error recovery actually accounts for a single exception and thus cannot ensure recovery of a correct state. The only case where correct state recovery may be ensured is when the effect of all the aborted activities are rolled back to a previous state, which may not be supported in general in the context of Web services, as discussed in the previous section. The shortcoming of BPEL4WS actually applies to all XML-based languages for Web services composition that integrate support for specifying concurrent activities and exception handling.

Web service composition actions

Our solution to the above shortcoming of forward error recovery approaches for composite Web services is based on the notion of coordinated atomic actions that provides a sound basis for dealing with concurrent exceptions (Section 3.1). However, the notion requires to be adapted to cope with the fault model (Section 3.2) and the specifics of Web services, leading to introduce WSCA (Section 3.3). Illustration of using WSCA is further illustrated using the classical travel agency case study (Section 3.4).

Coordinated atomic actions

The Coordinated Atomic Action (or CA action) concept [START_REF] Xu | Fault tolerance in concurrent objectoriented software through coordinated error recovery[END_REF] is a unified scheme for coordinating complex concurrent activities and supporting error recovery between multiple interacting components. It provides a conceptual framework for dealing with different kinds of concurrency and achieving fault tolerance by extending and integrating two complementary concepts -atomic actions and ACID transactions. Atomic actions are used to control cooperative concurrency and to implement coordinated error recovery whilst ACID transactions are used to maintain the consistency of shared resources. A CA action is designed as a set of participants cooperating inside it and a set of resources accessed by them (see Figure 2). In the course of the action, participants can access external resources that have ACID properties. Action participants either reach the end of the action and produce a normal outcome and commit transactions on external resources or, if one or more exceptions are raised, all the participants are involved in their coordinated handling. If several exceptions have been raised concurrently, they are resolved using a resolution tree imposing a partial order on all action exceptions, and all the participants handle the resolved exception [START_REF] Campbell | Error recovery in asynchronous systems[END_REF]. If this handling is successful, the action completes normally, but if handling is not possible then an exception is propagated and responsibility for recovery is passed to the caller of the action, while transactions on all external resources are aborted. A formal specification of CA actions can be found in [START_REF] Tartanoglu | Formalizing Dependability Mechanisms in B: From Specification to Development Support[END_REF].

Fault model of Web services

The CA action concept for tolerating faults is based on exception handling. It requires the detection of faults, and the mapping of these faults to anticipated exceptions for which handlers are to be defined. Several kinds of errors can occur during the execution of a composite Web service and can be detected at the composition level. These faults relate to: (i) system faults like crashes, timeouts or network errors that can be detected by specialized monitors that generate exceptions at the application level, and (ii) application-level faults. The latter includes a broad range of errors like system exceptions, programmed exceptions, exceptions propagated from other participants, fault messages that are received from SOAP calls and transport level faults (e.g., HTTP errors). Note that the semantics of exceptions is application-dependant. For instance, a timeout does not necessarily mean that a remote system has crashed, and an application-specific handler must be provided to handle this kind of error.

Adapting CA actions for the Web

CA actions provide a base structuring mechanism for developing fault tolerant composite Web services: a CA action specifies the collaborative realization of a given function by composed services, and Web services correspond to external resources. However, as raised previously, ACID properties over external resources are not suited in the case of Web services. We therefore introduce the notion of Web Service Composition Action (WSCA) that adapts CA actions to the specifics of Web services. WSCAs mainly differ from CA actions in relaxing the transactional requirements over external resources, which are not suitable for wide-area open systems.

WSCA participants specify interactions with composed Web services, stating the role of each Web service in the composition. Each Web service is viewed as an external resource. However, unlike the base CA action model, interactions do not have to be transactional. The interactions adhere to the semantics of the Web service operations that are invoked. An interaction may then be transactional if the given operation that is called is. However, transactions do not span multiple interactions.

Every WSCA participant further specifies actions to be undertaken when the Web services with which it interacts signal an exception, which may be either handled locally to the participant (system-level exceptions or programmed exceptions signaled by Web services operations that do not need to be cooperatively handled at the WSCA level) or be propagated to the level of the embedding WSCA. The latter then leads to co-operative exception handling according to the exceptional specification of the WSCA. When Web services offer compensating operations, the resulting forward recovery may realize a relaxed form of atomicity. If operations are compensated, the action itself will be atomic in the sense that it will restore its initial state, assuming that the compensating operations succeed. However, the external actions that accessed the service in an intermediate state might have invalidated values.

Compared to solutions that primarily rely on transactional supports for composite Web services, ours mainly differs in that it exploits forward error recovery at the composition level, while enabling exploitation of transactional supports offered by individual Web services, -if any. For many applications, the strict requirement for transactionality can indeed be substitued by the optional mechanisms offered by the underlying services. These concern services offering compensating operations. Hence, the underlying protocol for interaction among Web services remains the one of the Web services architecture (i.e., SOAP) and does not need to be complemented with a distributed transaction protocol. Similarly to our solution, the one of [START_REF] Mikalsen | Transactional attitudes: Reliable composition of autonomous Web services[END_REF] does not require any new protocol to support distributed opennested transactions. An open-nested transaction is declared on the client side by grouping transactions of the individual Web services, through call to a dedicated function of the middleware running on the client. The transaction then gets aborted by the middleware using compensation operations offered by the individual Web services, according to conditions set by the client over the outcomes of the grouped transactions. Our solution is then more general since we allow forward error recovery involving several Web services to be specified at the composition level, enabling in particular to integrate non-transactional Web services while still supporting dependability of the composite service. Fault tolerance can then be obtained as an emergent property of the aggregation of some potentially non-dependable services, based on the detection of faults and their mapping to application-dependant exceptions.

WSCA example: the travel agency

For illustration of WSCA, we consider joint booking of accommodation and flights using separate hotel and flight Web services. Then, the composite Web service's operation is specified using WSCAs as follows. The top-level TravelAgent WSCA comprises the User and the Travel participants; the former interacts with the user while the latter achieves joint booking according to the user's request through call to the WSCA that composes the Flight and the Hotel participants. A diagrammatic specification of the aforementioned WSCAs is shown in Figure 3. In the TravelAgent WSCA, the User participant requests the Travel participant to book a flight ticket and a hotel room for the duration of the given stay. This leads the Travel participant to invoke the JointBooking WSCA that composes the Hotel Web service and the Flight Web service. The participants of the JointBooking WSCA respectively requests for a hotel room and a flight ticket, given the travel itinerary and dates provided by the user. Each request is subdivided into reservation for the given period and subsequent booking if the reservation succeeds. If both the Hotel and the Flight participants raise the unavailable exception, then concurrent exception resolution applies, leading the JointBooking WSCA to signal an exception to the Travel participant of the TravelAgent WSCA, where the exception gets handled in a cooperation with the User denoted by the greyed box in the figure (e.g., the user is requested to give alternative dates). In the case where either the reservation or the booking of one of the participants fails, the participant raises an exception (unavailableHotel in the example) that is cooperatively handled at the level of the JointBooking WSCA. If one participant has already confirmed a reservation, the booking that has succeeded is cancelled and an un-available exception is signaled to the calling TravelAgent WSCA for recovery with user intervention (see Figure 3). Note that if the handling fails and the cancellation is not possible, the exception that is signaled is a failure exception sent to the calling WSCA with sufficient information about failed operations for later recovery.

Building WSCA-based composite services

Given the notion of WSCA, composite Web services are built by specifying their operations as WSCAs. The Web services that are composed are further declared in an abstract way to enable more flexible integration of different Web service instances through dynamic binding.

Composition process

The development process of a WSCA-based composite service comprises the definitions of: (i) the required abstract interfaces of the composed Web services that are to be integrated, and (ii) the composition process that gives the binding information as well as the WSCAs' standard and exceptional behaviours.

Required interfaces of components services to be integrated are declared. The abstract interface of any such service is given in terms of WSDL (limited to the abstract part), which defines the messages exchanged with the Web service. The service interface is further enriched with the characterization of the service's transactional behaviour if offered, in a way similar to existing solutions in the area (e.g., [START_REF] Mikalsen | Transactional attitudes: Reliable composition of autonomous Web services[END_REF], [START_REF] W3c | Web Service Choreography Interface (WSCI) 1.0, W3C Note[END_REF]).

The composition process of WSCA-based composite services is expressed as an independent XML document, which specifies the service instances to be integrated together with provided WSCAs, as detailed in Section 4.2. The Web service instance associated to a given composed service may be either statically set or dynamically retrieved according to the service's abstract specification. The only requirement that is demanded from the Web service instances is the conformance of their interfaces with the declared required interfaces. In the most general case, the conformance is verified by syntactically checking WSDL documents of Web services. To provide availability, we allow a participant to be bound to a set of Web service instances implementing the service's specification. WSCAs define the operations provided by the composite Web service. The definition of a WSCA specifies the behaviour of the WSCA's participants including the exception handlers that are executed when an exception occurs.

The WSCA-based composite services are deployed as Web services on top of a base Web service middleware (see Figure 4). Services that provide some WSCA composite services, are referenced in a UDDI Web services reg-istry for client use. Given base middleware for Web services, supporting the deployment of WSCA-based composite Web services requires in addition, a local runtime support for running WSCAs. The runtime support should include mechanisms for WSCA creation, synchronization of participants, exception detection and propagation, and dynamic binding of Web services.

Specifying composite services

This section introduces an XML-based language for the specification of WSCA-based composite Web services, which defines the graph of interactions among Web services. The actual implementation of the service composition may then be decoupled from the specification of the composition process, leaving under the responsibility of the developer to check that his/her implementation conforms to the service's specification. Alternatively, the implementation may be generated from the specification.

The specification of a composite Web service is given by the WSCAL (Web Service Composition Action Language) XML-based language which includes declarations of the service instances and the behaviour of the supported operations:

<WSCAL name=nmtoken> <services> Detailed below </services> <WSCA operation=nmtoken exceptionTree=anyURI>* Detailed below </WSCA> </WSCAL>

Service instances

The service instances are given through the services element that refers to the corresponding abstract interfaces of composed Web services: <services> <service name=qname>* <definition hrefSchema=anyURI /> <staticService instance=anyURI />* | <dynamicService onCall=boolean multiple=boolean />? </service> </services> Each service may be statically bound to a specific service instance (defined by the staticService element) and/or dynamically bound to an instance matching the abstract definition of the service interface that is given by the corresponding definition attribute (defined by the dynamicService element). In the former case, concrete binding information is provided through the WSDL document associated with the service's instance. In the latter case, a matching service instance is located at runtime using a location service such as a UDDI service. Dynamic binding of participants with associated Web services may take place either upon first invocation of the service's WSCAs or upon instantiation of the composite Web service, according to the value of the on-Call Boolean attribute of the given participant. Finally, we allow each service to be bound to a set of instances matching the specification of the associated service rather than a single instance for the sake of availability; this is specified using the multiple Boolean attribute in the DynamicService element and by stating as many instances as required with the staticService element. Then, a unique Web service that is available is chosen for the whole WSCA at the first invocation of the corresponding service. Note that if the Web service becomes unavailable, an exception is raised and another Web service can be chosen if it is explicitly specifed in the corresponding handler.

A sample of the services element for the TravelAgent composite service is given below, which directly follows from the informal presentation of Section 3.4. The service in particular offers the JointBooking WSCA that coordinates booking over the Hotel and Flight Web services, for which instances are dynamically retrieved upon invocation of the WSCA.

WSCA behaviour

The behaviour of the operations offered by the composite service is defined by the WSCA element: In the above, the operation attribute gives the name of the operation being specified and the exceptionTree attribute gives the XML document of the corresponding exception resolution tree. The exception tree is used to resolve the exceptions that are concurrently raised within WSCAs into a single exception, in a way similar to CA actions. Then, a sequence of participant elements are declared, each specifying:

<WSCA
The services with which the WSCA participant interacts through the bind element that gives the name of the services among those defined by the service elements in the embedding services element.

Parts of the messages associated with the WSCA that are relevant to the specific participant, which is defined using the input, output and fault elements. The fault elements define the exceptions that may be raised by the participants, which require cooperative exception handling and get composed with the exceptions concurrently raised by peer participants using the exception tree.

The local state of the specific participant through the state element that defines the local variables.

The behaviour of the specific participant using the behavior element. The participant behaviour subdivides into the participant's standard and exceptional behaviour (as defined by the standard and coordinat-edHandler elements). Each such behaviour is defined as a process using classical statements, including in particular interaction with the Web service instance(s) associated with the participant, message exchanges with peer participants and exception handling.

WSCAL statements for specifying participants' behaviour are quite similar to the ones introduced by XMLbased languages for the specification of composite services. We more specifically base the definition of WSCAL on the CSP language [START_REF] Hoare | Communicating Sequential Processes[END_REF] for the base statements, providing a sound basis towards formal reasoning about WSCAL specifications. We thus detail here only some base statements of interests regarding WSCAs. The call statement allows specifying (synchronous) operation calls where the invoked operation may be either local to the embedding composite Web service or provided by the Web services to which the participant is bound (which may be a WSCA if the service is itself composite). The return statement is the dual statement allowing specifying the message to be returned as partial result of the embedded operations, which is to be merged with the results returned by peer participants. The send statement allows specifying the sending of a message to a peer participant whose dual reception may be expressed using either the blocking wait or the non-blocking onInput statement. Finally, the raise statement allows signaling an exception whose handling is specified using the traditional try statement for defining exception handling scopes:

Coordinated exception handling

The specifics of WSCAL comes from structuring the operations provided by composite Web services as WSCAs that coordinate the execution of composed Web services operations with respect to failure occurrences, in particular introducing the specification of coordinated exception handling.

For each participant, the fault elements define the exceptions that may be raised and require cooperative exception handling. In addition, a default exception handler is defined for exceptions that are not declared. When a participant raises an exception, it is first handled locally by a local handler, defined using the localHandler element, while other participants continue their execution normally without being interrupted. If the local handler fails, or if such a handler is not defined, the participant ultimately raises the exception, which is propagated to all participants, leading to coordinated exception handling, defined using the corresponding coordinatedHandler element. Participants synchronize for execution of the coordinated exception handlers. That means in particular that if a participant is engaged in a remote call, all participants wait for the termination of this call. In the case where several participants raise exceptions which are concurrently propagated, then the exceptions are resolved using the document defined in the exceptionTree attribute, which imposes a partial order on all exceptions, and all participants handle this unique exception. The exception is then handled cooperatively by participants that can coordinate their execution in the same way as in the standard behavior, i.e., by message passing, and they can invoke external WSCAs if needed. The corresponding exception resolution algorithm can be found in [START_REF] Xu | Concurrent exception handling and resolution in distributed object systems[END_REF].

The WSCA that executes a coordinated exception handler terminates with one of the following outcomes [START_REF] Xu | Fault tolerance in concurrent objectoriented software through coordinated error recovery[END_REF]:

Exceptional outcome: All external operations on Web services and nested WSCAs are performed successfully (e.g., all transactions are validated). An exception is signaled to the upper level.

Abort outcome:

The WSCA has aborted and all external operations are aborted or compensated according to the transactional behavior of the accessed Web services as specified in the service interface. An abort exception is signaled to the upper level:

Failure outcome: The handling has failed and external operations cannot be aborted or compensated. This can be due to a failure in performing the cancellation operation or if such an operation is not defined. Responsibility for recovery is passed to the caller of the action. A failure exception is signaled to the upper level with information about failed operations:

Adopting the concept of coordinated exception handling of CA actions allows dealing with different types of faults in a disciplined way inside atomic units and partial results of nested actions to be reported to the higher level action, keeping error propagation under control.

The travel agency example

A sample of the participant element specifying the Hotel participants behaviour is given below. An example entry of the exception tree document is:

Conclusion

Web services are expected to become a major class of systems of systems in the near future. This paper has introduced our work towards supporting the development of dependable systems of systems in the context of the Web service architecture. Our approach primarily lies in the WS-CAL XML-based language for the abstract specification of the fault tolerant composition of Web services, which builds upon the CA actions concept for enforcing dependability.

We are currently implementing a base middleware support for WSCAs. The middleware includes the generation of composite Web services from WSCAL specification and a service for locating Web services. We are further working on the formal specification of WSCAL for enabling rigorous reasoning about the behavior of composite Web services regarding both the correctness of the composition and offered dependability properties. The specification of composite Web services using WSCAL allows carrying out a number of analyses with respect to the correctness and the dependable behavior of composite services. Except classical static type checking, the correctness of the composite service may be checked statically with respect to the usage of individual services. In addition, the same specification can be used for implementing executable assertions to check the composite service behaviour online. Reasoning about the dependable behaviour of composite Web services lies in the precise characterization of the dependability properties that hold over the states of the individual Web services after the execution of WSCAs. We are in particular interested in the specification of properties relating to the relaxed form of atomicity that is introduced by the exploitation of opennested transactions within WSCA.

As discussed in Section 2, there is extensive research work that is ongoing towards supporting the development of fault tolerant composite Web services, relying on the XMLbased abstract specification of Web services and of their composition, and on the transactional supports for composite Web services. Our contribution primarily comes from relying on forward error recovery instead of backward error recovery for specifying the behavior of composite Web services in the presence of failures. Forward error recovery is further specified in terms of co-operative actions, building upon the CA actions concept. Our analysis shows that this approach is more effective in dealing with faults at the level of composite Web services.

Figure 1 .

 1 Figure 1. Web services and their composition

Figure 2 .

 2 Figure 2. Coordinated atomic actions

Figure 3 .

 3 Figure 3. WSCA for composing Web services

  Figure 4. WSCA deployment

  <services> <service name=''UserBrowser''> <definition hrefSchema=''http://ta.com/TAUser.req''/> <staticService instance=''http://ta.com/Client.wsdl''/> </service> <service name=''FlightService''> <definition hrefSchema=''http://ta.com/Flight.req''/> <dynamicService onCall=true multiple=true /> </service> <service name=''HotelService''> <definition hrefSchema=''http://ta.com/Hotel.req''/> <dynamicService onCall=true multiple=true /> </service> </services>

  <resolve name=''unavailable''> <exception name=''unavailableHotel''/> <exception name=''unavailableFlight''/> </resolve> <resolve name=''unavailable''> <exception name=''unavailableHotel''/> <exception name=''cancelled''/> </resolve> Flight participants behavior is not detailed as it is similar to the Hotel participant. Coordinated booking is achieved as discussed in Section 3.4, exploiting in particular open-nested transactions of participating Web

World Wide Web Consortium, http://www.w3.org Proceedings of the

22nd International Symposium on Reliable Distributed Systems (SRDS'03)

Proceedings of the 22nd International Symposium on Reliable Distributed Systems (SRDS'03)

Proceedings of the 22nd International Symposium on Reliable Distributed Systems (SRDS'03) 1060-9857/03 $17.00 © 2003 IEEE

Acknowledgments

We would like to thank Marie-Claude Gaudel and Brian Randell for their helpful comments and discussions. We also thank Andras Pataricza for useful feedback about the paper. This research is partially supported by the European IST DSoS (Dependable Systems of Systems) project (IST-1999-11585) http://www.newcastle.research.ec.org/dsos/.

services. The two participants of the JointBooking WSCA have similar behaviour. The participant first invokes the reserve operation of the Web service to which it is bound and then books the proposed selection -if any-through call to book. Otherwise, the unavailable exception is raised by the reservation operation, leading to retry an alternative reservation, and ultimately propagating the unavailableHotel exception for cooperative handling at the level of the WSCA. Finally, cooperative handling of unavailableHotel by the WSCA amounts to canceling the performed booking by the peer participant -if any.