INTERGALACTIC CLIENT-SERVER PROGRAM (ICSP)
We assume that each C has a coordinator (CC) and each server has a coordinator SC; each CC communicates with the SC through message passing. Here the procedure call and procedure invocation are decoupled, and procedure invocation takes place through guards , binding, and internal operations.
A ICSP is a 5-tuple: (S, f(0) M, m(0),T), where S is a set of servers, M is a finite set of coordinators (CC) contained in the C, T is a finite set of external or global transactions on S, and m(0) and f(0) are the initial states of C and S, respectively. Each coordinator CC(i) in C(i) and CS(p) in S(p) are, respectively, characterised by pairs (V(i), Op(i)) and (V(p), Op(p)); here, V(i) [V(p)] is the set of all possible values (domain) for the C(i) [S(p)] and Op(i) [Op(p)] is the set of local operations that can be performed on that C(i) [S(p)]. Each operation Op(i) [Op(p)] is a partial function taking input values from the domain and outputting values from the domain V(i) [V(p)], thus changing the C(i) [S(p)] to a new state.
A global transaction (called an external transaction, or extran ) T(ip) is defined as a two-way transaction between the C(i) and its fixed hosts S(p); this consists of a message sent from C(i) to execute a desired transaction in S(p). C(i) has a behaviour specified by: Pre(T(ip)), G(i), F(i), Post(T(ip)), where Pre() and Post() are, respectively, the pre- and post-states that are active before and after the transaction T(ip). G(i) is a guard of C(i), and F(i) is the command function consisting of operations that map input values to output values in local domains (note that the operations used in G(i) and F(i) are assumed to be defined) and sending messages. S(p) has a behaviour specified by Pre(T(ip)), G(p), F(p), Post(T(ip)), where Pre() and Post() are, respectively, the pre- and post-states that are active before and after the transaction T(ip). G(p) is a guard of S(p), and F(p) is the command function consisting of operations that map input values to output values in local domains (note that the operations used in G(p) and F(p) are assumed to be defined) and sending messages.
The prearranged contract between S(p) and C(i) specifies what message C(i) can accept and what actions it can perform when it receives the message while in state Pre(T(ip)) to satisfy the postcondition Post(T(ip)).The extran T(ip) can trigger in S(p) numeric, symbolic, or database computations (heterogeneous computing) and leave C(i) and S(p) in a consistent state.
Each extran T(ip) triggers a set of computations in C(i) and in S(p). If the objects C(i) and S(p) are "made up" of subobjects, we may have to execute a local transaction within C(i) and in S(p) (called an internal transaction, or intran ). After executing the extran and intran, the system reaches a new state from the old state such that: New state = Old state - pre(T(ip) ) post(T(ip)), using the command set F(i) and F(p). The internal transactions in S(p) and C(i) retain the ACID properties: atomicity, consistency, isolation, and durability.
Concurrency and Serializability
In concurrent mobile-host programming, we need to consider how to speed up the system by permitting concurrent transactions between several Cs and the S. This would require the analysis as to how the respective internal and external transactions interfere with each other when they are applied. In order to execute the internal transactions concurrently they must satisfy the following conditions (Bacon, 1993):
The set of objects in each S(p) and in each C(i) accessed by any two different intrans are pairwise disjoint .
The set of local states in C(i) and S(p) used by two different intrans are pairwise disjoint. Condition 1 is well-known for those familiar with database transaction handling (Bacon, 1993; Krishnamurthy & Murthy, 1992; Nodine et al., 1995; Ozsu, 1994; Silva & Krause, 1997); Condition 2 corresponds to the mutual exclusion of processes in concurrent programming (Bacon; Thomas & Weedon, 1998). These aspects are taken care of by the coordinators CC(i) and SC(p).
Traditionally, we require that the following two conditions are to be satisfied for global serialization:
At each C and S, the local schedules are serializable. That is, the conflicting actions are performed in the order of their temporal precedence.
At each C and S, the serialization order of transactions dictated by every other C and S is not violated. That is, for each pair of conflicting actions among transactions p and q, an action of p precedes an action of q in any local schedule if and only if p precedes q in the total ordering of all transactions in all S and in all C.
The above two conditions require that two different C(i) and C(j) do not interfere in S(p) [we assume that two servers S(p) and S(q) do not interfere]. There are four ways in which such interference can take place; these are illustrated by examples from a flight reservation.
Enabling dependence (ED): C(i) and C(j) are called enable dependent (or dataflow dependent) through S(p) if the message from C(i) creates the required precondition in S(p) and results in a message to C(j) and creates the required precondition in C(j) to fire. ED is analogous to write-read (WR) conflict in database transaction processing.
Example 2: C(i) asks for a reservation earlier to take up the last seat in a plane. After reservation, the positive intent was expressed by S(p). Then C(i) cancels its reservation. Following that C(j) asks for a reservation. This results in S(p) providing a positive response. Thus C(i) enables C(j).
Inhibit dependence (ID): C(i) and C(j) are called inhibit dependent if the firing of C(i) does not create the required precondition in S(p) needed by C(j) and prevents it from executing any action.
Example: C(i) asks for a reservation earlier to take up the last seat in a plane; after reservation intent was expressed by S(p), C(i) confirms its reservation. Then C(j) asks for a reservation. This results in S(p) providing a negative response to C(j). Thus C(i) disables C(j).
Opposition dependence (OD): C(i) and C(j) are opposition dependent (also called data-output dependent) through S(p) if the order in which C(i) and C(j) enable S(p) and update S(p) produce different results in S(p); that is, the objects C(i) and C(j) perform conflicting operations on S(p) and are not interleavable. Hence, the local serializability in S(p) is not ensured if the actions are carried out in different order. OD is analogous to WW conflict in database transaction processing.
Example: C(i) asks for a reservation earlier to take up the last seat in a plane; after the reservation intent was expressed by S(p), C(j ) asks for a reservation and gets a negative response since all seats are filled. Then C(i) cancels its reservation. This results in S(p) ending up with a vacant seat. If, on the other hand, C(j) has contacted S(p) later, after C(i) has cancelled its reservation, then C(j) gets a positive response. Hence actions are not interleavable and the schedule is not conventionally serializable.
Data antidependence (AD): C(i) and C(j) are data antidependent through S(p) if C(i) enables S(p) and receives the data from S(p); subsequently, the firing of another object C(j) enables S(p) and results in updates of the same set of elements. AD is analogous to RW conflicts in database transaction processing and affects the global serializability.
Example: C(i) asks for a reservation earlier to take up the last seat in a plane; after reservation intent was expressed by S(p), the confirmation message did not arrive from C(i) within deadline. Meanwhile C(j) asks for a reservation and gets a positive response and C(j) confirms its seat. This results in C(i) ending up with an uncommitted dependency. Traditionally this is not a serializable schedule.
The extrans are called conflict-free if they do not have any of the above dependencies. However, in a mobile environment with many mobile hosts, the above conflicts are hard to resolve due to disconnection; hence, global serialization may be hard to achieve. Also, in a practical situation, global serialization may not be the right thing to expect, as explained below.
Relaxing Serializability Criteria
Most traditional databases use the serializability as the basic notion of correctness. Serializability requires that conflicting operations be executed in a strictly sequential way. However, in a situation involving cooperation, the transactions need to share data associated with the particular application. In such a case, serializability is not the only correctness criterion. In fact, global consistency cannot be achieved in many applications, and one has to use correctness criteria (called user -defined correctness criteria) or a contract that satisfy the needs of the individual members in a business community. In such cases the correctness can only be defined by a well- formed sentence in a suitable formal language defined by a grammar. In practice, many systems use the production rules or condition-event-action system in some form for this purpose, e.g., finite state grammars or scripts. Such systems are well-suited to describe a stereotyped control flow or protocol to describe operations allowable for each transaction and permissible ways of interleaving the operations of related cooperative transactions. In other words conflicts are resolved locally in a flexible way that suits a given user. Such a protocol resembles the intentionaction right-left turn signals used while driving cars on roads governed by the right-of-way rules!
Since tasks executing from different mobile hosts may interfere in an undesirable way, it is necessary to enforce a certain behaviour pattern among the members to prevent side effects. The members may themselves decide to enforce some protocol on the interaction between the members and objects to ensure consistency for each member in its own way. Also each member can set up its own method of undoing and recovery in isolation from other members to avoid interference and further failures.
In view of the above difficulties we must not attempt global serialization in a mobile environment, and concurrent computations should be restricted to only business processes such as reservations , purchases, and other processes that involve negotiation between sellers and many customers. In this case the seller does not permit direct concurrent actions on its database from outside except through its coordinator, which serializes the requests using its local time-stamp order. These aspects are illustrated by an example involving the intention -action protocol in the next section.