6 Pervasive Mobile Transactions

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Pervasive computing is a user-centric distributed computing paradigm that allows users to transparently access their preferred services even while moving around. Furthermore, many pervasive applications (e.g., a fund transfer between two different banking systems) must be executed reliably. Pervasive transaction processing can be used to guarantee such transparent and reliable services for users.

In this chapter, Section 6.1 introduces the concept of pervasive transactions. Section 6.2 presents a pervasive transaction processing framework, followed by a context-aware pervasive transaction model in Section 6.3. Then we propose a context-adaptive dynamic transaction management algorithm in Section 6.4. Finally, Section 6.5 models and verifies the accuracy of the proposed transaction management algorithm using Petri nets.

6.1 Introduction to Pervasive Transactions

Owing to the high mobility of users, pervasive systems run in an extremely dynamic and heterogeneous environment, where various networked devices and communication protocols coexist, and network topology and bandwidth are dynamically mutative and frequent [1–5]. Therefore, open pervasive environments are prone to various failures from networks, devices, applications, and basic services of pervasive systems [3]. To facilitate use as much as possible, pervasive systems have to intelligently handle failures and hide complex recovery processes from users, providing transparent communication and computing services [1,3]. As a result, transaction management technology, which has been widely used to guarantee system consistency for a variety of distributed computing paradigms, is an important enabling technology for making user-centric pervasive computing a reality.

Context adaptation is an important characteristic that distinguishes pervasive systems from traditional distributed environments. Specifically, pervasive environments exhibit the following features:

■ High mobility. Pervasive systems provide mobile users with transparent online services. With the movement of a node, neighbors change continuously. As a result, a context-aware communication mechanism is an important feature of pervasive transaction processing.

■ Limited resources. Networked mobile devices have limited energy, computing capacity, and storage resources. Therefore, energy-efficient communication and computation are important considerations [6,7].

■ Uncertain fixed infrastructure. Traditional mobile transaction models rely on wired fixed networks. In pervasive environments, however, networks cover almost every area, and computing and service extend from fixed networks to various wireless networks. A fixed infrastructure, such as a base station, is not a requisite any more.

■ Heterogeneous and changing environments. Networks, data, and devices are different from each other in a pervasive environment. Various wireless networks with different communication protocols (e.g., Bluetooth, Wi-Fi) coexist with wired networks, while at the same time the network connection and bandwidth are extremely unstable.

These features require that pervasive transactions have to be aware of timeand space-changing context and therefore must adjust execution behaviors dynamically, as is shown in Figure 6.1. For example, let each hospital in a city scatter a few mobile medical assistants (MMA) equipped with mobile devices that keep on moving around the city to provide medical treatment assistance to potential patients. A traveler (Alice) is driving a car with a mobile device (MD), suddenly suffers from an acute illness, and urgently needs to find a hospital. First, Alice discovers and then requests the nearest MMA (T₁). The MMA checks its lightweight mobile database and reserves a sickbed that meets Alice’s requirements (T₂). If the MMA does not hold the corresponding data (e.g., a currently available sickbed) in the local database, it downloads the data from the central database on a fixed network or transfers the reservation request to the central database server (T₃). After a sickbed is successfully reserved, Alice queries the public traffic service to find the best route to that hospital (T₄). If Alice cannot find out any MMA within a given distance, she queries the Health Service Central Hospital for a sickbed reservation (T₅); although that hospital is far away, it can provide a variety of medical services.

Figure 6.1 A scenario of pervasive transactions.

Although there have been many transaction models proposed for traditional mobile systems [8–11], they focused on variable bandwidth, network disconnection, replication and synchronization, and hand off of mobile hosts (MHs). Clustering [12] (also called weak–strict) groups semantics-related databases within a cluster. Data are kept in two versions: a weak consistency (local consistency) version for weak transactions and a strict consistency (global consistency) version for strict transactions. Strict and weak transactions are executed when a MH is either strongly connected or weakly connected with fixed networks, respectively. Similar to clustering, two-tier replication [13] (also called base–tentative) maintains a master copy for base transactions and multiple replicated copies for tentative transactions. High Commit Mobile (HiCoMo) transactions [14] keep two kinds of tables: base tables for base transactions and aggregate tables for HiCoMo transactions. An Isolation Only Transaction (IOT) [15] also includes two kinds of transactions—for MH states that are connected and disconnected.

In mobile transaction coordination, the Moflex model [16] submits subtransactions to mobile transaction managers running in base stations, which then submits the subtransactions to databases. Each Moflex transaction is composed of a set of dependency relationships, handoff rules, and expected final states. Kangaroo transaction [17] deploys a data access agent (DAA) in each base station for mobile transaction management. Promotion [18] is a nested, long-lived transaction model where top transactions are executed on fixed hosts and subtransactions on MHs controlled by the compact. In pre-serialization [19], each base station runs a global transaction coordinator responsible for transaction coordination as well as disconnect and mobility management. TCOT [20] is a one-phase commit protocol for a transaction termination decision (e.g., commit, abort, etc.) in message-oriented systems. This protocol uses a time-out mechanism to reduce the impact of a slow and unreliable wireless link, where the time-out not only enforces the termination condition but also the entire execution duration as well. Lim and Hurson [21] proposed a hierarchical concurrency control algorithm—v-lock, which uses global locking tables to serialize global transactions and to detect and remove global deadlocks. The global locking tables are created with semantic information contained within the hierarchy. A data replication scheme, which caches queries and the associated data at the mobile unit as a complete object to alleviate the limited bandwidth and local autonomy restrictions, was also used in this research.

These existing mobile transaction models cannot be directly applied to mobile pervasive systems because of the following:

1. Insufficient support for the mobility. Traditional mobile transaction models are built on a client–server–proxy architecture [22], where fixed hosts are data sources and transaction servers. Therefore, these models only address the mobility of clients without considering the mobility of data servers. In pervasive environments, however, mobile devices interact with each other in a peer-to-peer way, and both the client and the server will be moving during transaction processing.

2. Little consideration of context awareness. Pervasive transaction management has to adapt to transaction context. Existing proposals have not solved such an issue.

6.2 Mobile Transaction Framework

Existing client–proxy–server-based mobile transaction models need base stations for communication and transaction management and fixed data servers for transaction execution. Therefore, they only address the mobility of clients. In pervasive environments, however, users and devices keep moving, so there are no fixed base stations. Instead, mobile devices can work as both clients and servers in a peer-to-peer way. As a result, traditional mobile transaction modes will face the following unavailable transaction service problem.

6.2.1 Unavailable Transaction Service

In traditional client–proxy–server-based mobile transaction systems, base stations in the fixed network are at the center and work as gateways among mobile clients as well as fixed servers and mobile transaction managers. An MH can communicate with a base station only when it is located within the corresponding cell. Specifically, the MH disconnects with any database server if the MH moves out of the range of any base station, causing the unavailable transaction service as illustrated in Figure 6.2.

The unavailable transaction service problem seriously restricts online pervasive services. But its online service is one of the most attractive scenes distinguishing pervasive computing from traditional mobile computing paradigm. So, a new transaction processing framework should be designed for pervasive transactions that enable MHs to communicate with each other anytime, anywhere.

6.2.2 Pervasive Transaction Processing Framework

To make the provision of pervasive transaction service anytime and anywhere a reality, we propose a new pervasive transaction processing framework, as shown in Figure 6.3. In this framework, neighboring mobile devices that use the same wireless communication protocols automatically connect with each other. In such a framework, there are two kinds of nodes: a mobile ubiquitous device without any database (MUD), such as a smart mobile phone, and a mobile ubiquitous device with database(s) (MUDD), such as a powerful laptop. Accordingly, MUDDs work not only as clients initiating mobile transactions but also as servers executing transactions while MUDs act only as clients.

Figure 6.2 Unavailable transaction service. MH: mobile host; BS: base station; FH: fixed host; R: ratio range of a mobile host.

Figure 6.3 A pervasive transaction processing framework.

The pervasive transaction processing framework is composed of three layers of networks: fixed network, wireless routing backbone network, and wireless mesh subnetwork. Each node forwards data for other neighboring nodes so that any two nodes can connect by multiple hops. In Figure 6.3, dashed and solid lines denote wireless and wired communications, respectively; thicker lines mean higher wireless bandwidths; “FH” denotes a fixed host connected with a fixed network; “MUD” and “MUDD” mean mobile ubiquitous devices without any database and with database(s), respectively; and “TMH” indicates a traditional MH without mesh functionalities. MUDs and MUDDs with identical communication protocols are interconnected into low-level wireless mesh networks automatically and dynamically.

A pervasive transaction can be initiated by any mobile device, with the following different execution models:

■ A pervasive transaction is entirely executed by MUDD(s), which occurs more often than the next two models.

■ A pervasive transaction is distributed between MUDD(s) and FHs.

■ A pervasive transaction is entirely executed by FHs.

6.3 Context-Aware Pervasive Transaction Model

Pervasive transaction processing must be aware of changing context. In this section, we will present a context model and then a context-aware transaction model because they are prerequisite to adaptive transaction management.

6.3.1 Context Model for Pervasive Transaction Processing

Pervasive transaction context covers all the information relevant to individuals, networks, and devices within the activity space, specifically including the following dimensions:

■ Person: profile, preferences, and requirements of users

■ Wireless network: connectivity and performance of networks

■ Mobile device: computing and storage capacity of mobile devices

■ Location: longitude and latitude (or relative position) of mobile devices.

Table 6.1 Context Details of Pervasive Transactions

Entity	Attribute	Value
Person	Name	User name
	Sex	Male or female
	Age	Value of age
	Requirement	Requirement description
	Preference	Behavior preference
Wireless networks	Connectivity	Connected, disconnected
	Bandwidth	High, medium, low
	Delay	High, medium, low
	Lost_ratio	High, medium, low
	Cost	Expensive, cheap, free
	Stability	Good, medium, bad
Mobile devices	Available_battery	Full, half, low
	Available_data	Available, unavailable
	Computing_capacity	High, medium, low
	Available_memory	Full, half, low
	Available_cache	Full, half, low
	Security	Secure, open
Location	Location	Pairs of longitude and latitude

Table 6.1 lists context details of pervasive transactions; this is where some attributes may be described more accurately. For example, we can represent computing capacity by the main frequency of a mobile device and available memory by the size of available storage.

A context model is a formal representation of physical space, information space, and human activities. We abstract transaction context using entities, attributes, and relationships among entities and model the context using an entity–relationship diagram. The graphic context model for pervasive transactions is shown in Figure 6.4, where we only illustrate attributes of the entity, person. Attributes of other entities can be easily complemented in the same way as in Table 6.1. Some attributes (e.g., preference of a user) cannot be directly abstracted from entity profiles, and data mining–type technologies have to be used for this purpose. Entities are described through pairings of attributes and values.

6.3.2 Context-Aware Pervasive Transaction Model

A context-aware transaction model should be able to adjust behaviors dynamically in terms of changing transaction context. A context-aware pervasive transaction can be formally defined as follows.

Figure 6.4 Context model for pervasive transactions.

Definition 6.1

A pervasive transaction is a 7-tuple (T, CT, ECA, ECA_i, D, TS, FS), where:

■ T = {T_i | 1 ≤ i ≤ n} is the set of all subtransactions in a pervasive transaction.

■ CT = {CT_i | 1 ≤ i ≤ n} is the set of compensating transactions for all the subtransactions.

■ ECA = <ECA_i> is the list of ECA rules for all the subtransactions.

■ ECA_i = <E_i, C_i, A_i> is the list of 3-tuple with event, context, and action for the subtransaction T_i.

■ D is the set of interdependencies that specify relationships between T_i and T_j(T_i, T_j ∈ T).

■ TS = { S_i | 1 ≤ i ≤ n} is the set of states of all subtransactions.

■ FS is the set of acceptable final states.

The formula ECA = <ECA_i | 1 ≤ i ≤ n > is at the center of the context-aware pervasive transaction mode. ECA consists of a list of ECA rule descriptors, where ECA_i is a rule descriptor for a subtransaction T_i, and ECA_i has a higher priority than ECA_i+1. In particular, each ECA_i = <E_i, C_i, A_i> is also a list of 3-tuple (event, context, and corresponding action), describing multiple context-based execution policies for a subtransaction T_i, where

■ E_i = {E_ij} is the set of events that occur during the execution of T_i.

■ C_i = {C_ik} is the set of context associated with a subtransaction T_i. We take C_i as the conditions that executing T_i has to meet. C_i covers four dimensions: WN, MD, location, and person, described in Table 6.1.

■ A_i = {A_il} is the set of corresponding actions.

Table 6.2 Transaction State Description

Symbol	State	Description
I	Initiation	T_i does not start to execute
E	Executing	T_i is executing and has not committed
S	Committed	T_i has successfully committed
F	Failed	T_i has failed to commit and is rolled back to previous state
C	Compensating	Compensating transaction C_i has been executing

Figure 6.5 State conversion diagram of transactions. I, E, S, F, and C represent five states, Initiation, Executing, Committed, Failed, and Compensating, respectively.

D is the set of intradependencies between T_i and T_j (T_i, T_j ∈ T). We define two kinds of intradependencies: success dependency (≺_s) and failure dependency (≺_f). T_i≺_sT_j means that T_j cannot be executed until T_i successfully commits. T_i≺_fT_j denotes that T_j can start to execute only if T_i fails to commit or is compensated in the case that T_i has committed.

TS = {S₁, S₂, …, S_n} is the set of states of all subtransactions in a pervasive transaction. S_i, the state of subtransaction T_i, is one of five possible states: I, E, F, S, and C (see Table 6.2). Each subtransaction starts with state “I” and ends with state “S” (T_i is successfully committed) or “F” (T_i is aborted). Figure 6.5 illustrates the state conversion of transactions.

FS is the set of acceptable final states. A pervasive transaction may have multiple proper final states acceptable to a user, probably with different priorities. For example, Alice first discovers the quickest qualified devices for the sickbed reservation and, after a failure, she will contact the Health Service Central Hospital to reserve a sickbed.

6.3.3 A Case of Pervasive Transactions

We model the medical treatment reservation scenario mentioned in Section 6.1 as a mobile pervasive transaction (T, CT, ECA, D, TS, FS). MD is a mobile device used by Alice; MMA is a mobile medical assistant that is equipped with mobile device(s) and keeps on moving around. According to Section 6.1, we have:

■ T = {T₁, T₂, T₃, T₄, T₅}. The global transaction T consists of five subtransactions. For the meaning of each subtransaction, please refer to the scenario in Section 6.1.

■ CT = {∅, CT₂, CT₃, ∅, CT₅}. CT₂, CT₃, and CT₅ are compensating transactions of T₂, T₃, and T₅, respectively. T₁ and T₄ do not need to be compensated.

■ D = {T₁≺_sT₂, T₂≺_sT₄, T₂≺_fT₃, T₃≺_sT₄, T₁≺_f T₅, T₅≺_sT₄}. The intradependency D specifies that T may be executed in one of three sequences: σ₁ = {T₁, T₂, T₄}, σ₂ = {T₁, T₃, T₄}, or σ₃ = {T₅, T₄}.

■ TS = {S₁, S₂, …, S₅}. S_i is the state of subtransaction T_i. The transaction initiator MD updates TS once a subtransaction is executed.

■ FS = {(S, S, -, S, -), (S, F, S, S, -), (F, -, -, S, S)}, where “S” and “F” stands for a successful commit and an abort of the corresponding subtransaction, respectively, while “-” means that the execution state of the subtransaction does not affect the decision.

ECA describes how to adapt the transaction context and thus is a central element of our pervasive transaction model. In this example, ECA consists of five rule descriptors (each for a subtransaction) such that ECA = <ECA₁, ECA₂, ECA₃, ECA₄, ECA₅>, where

■ ECA₁ = <<E₁, C₁₁, A₁₁>, <E₁, C₁₂, A₁₂>>. <E₁, C₁₁, A₁₁>, and <E₁, C₁₂, A₁₂> describe that MD successfully connects with and fails to discover the nearest MMA, where E₁ means Alice tries to discover the nearest MMA; C₁₁ means the network link and bandwidth among the MD and qualified MMAs are good enough for communication; and a discovered MMA is able to handle the transaction request; A₁₁ means the MD selects the MMA as a transaction participant, on behalf of Alice; C₁₂ means the network link or bandwidth between the MD and any MMA is not qualified for communication; and A₁₂ refers to when MD connects with the Health Service Central Hospital. Note that in that case, subtransaction T₁ has failed.

■ ECA₂ = <E₂, C₂, A₂>. The MMA checks its local database to reserve a sickbed meeting Alice’s requirements. If the data are locally available, T₂ can successfully commit. Otherwise, T₂ will fail.

■ ECA₃ = <<E₃₁, C₃₁, A₃₁>, <E₃₂, C₃₂, A₃₂>>. In a case where the MMA cannot find the needed data in its local database, it continues to handle the sickbed reservation. E₃₁ means subtransaction T₂ failed; C₃₁ means the MMA has enough computing and storage capacity; A₃₁ means the MMA downloads the needed data from the central database; E₃₂ means the MMA finds that it is not able to store the needed data; C₃₂ means the link between the MMA and the central database server is qualified; and A₃₂ refers to when the MMA transfers the sickbed reservation request to the central database server.

■ ECA₄ = <E₄, C₄, A₄>. After finishing the sickbed reservation, MD queries a public traffic information service to discover the best path to that hospital.

■ ECA₅ = <E₅, C₅, A₅>. MD requests the Health Service Central Hospital reserve a sickbed. We assume the central database server of the Health Service Central Hospital can handle transactional medical treatment requests all the time.

6.4 Dynamic Transaction Management

Due to changing pervasive context, pervasive transaction management has to adaptively adjust execution policies during transaction processing, which will be presented in this section.

6.4.1 Context-Aware Transaction Coordination Mechanism

A pervasive transaction is initiated by a mobile device (MD or MDD) called an initiator. Then, in a multiple-hop fashion, the initiator distributes subtransactions to neighboring MDDs or FHs, called executors. In wireless networks, data communication consumes more energy than application operations. The transaction management mechanism works via the following principles:

■ An initiator discovers the shortest and most qualified executors. By qualified, we mean the executors have enough computing and storage capacity and bandwidth among the initiator and the executors. Shortest means the executor has the least number of hops away from the initiator. The fewer the number of hops, the less energy is consumed for a unit of data transmission. Therefore, this approach reduces the energy consumption of energy-limited mobile devices while it improves the probability of a successful transaction commit at the same time.

■ An executor (MDD) actually performs application operations in the subtransaction. In general, a resource-limited MDD has a lightweight mobile database that holds partial data from the central databases running on the fixed host. If accessed data are available locally, the executor performs the subtransaction directly. Otherwise, the executor will download the accessed data from the central database or will transfer the subtransaction to the fixed central database server.

6.4.2 Coordination Algorithm for Pervasive Transactions

Let a global pervasive transaction T consists of n subtransactions such that T = {T₁, T₂, …, T_n}. The state of T is a set of states of all subtransactions such that TS = {S₁, S₂, …, S_n}, where S_i (i.e., the state of T_i) is one of five possible states: I, E, F, S, and C. TS is updated once a subtransaction is executed. Based on TS, states of global transactions can be divided into the following three types:

■ Acceptable state. TS reaches one of states acceptable by a user (i.e., TS ∈ FS).

■ Executing state. TS has not reached any acceptable state, and part of the subtransactions have not been executed such that TS ∉ FS ∧ ∃S_i = ‘I’.

■ Failed state. TS has not reached any acceptable state, but all subtransaction have been executed such that TS ∉ FS ∧ ∀S_i ≠ ‘I’.

MDDs have the ability to handle pervasive transactions. First, the transaction coordination mechanism discovers dynamically qualified devices such as transaction executors and then sends subtransactions to them. If data to be accessed during a subtransaction is locally available, the executor finishes application operations and performs the subtransaction locally. Otherwise, the executor will decide whether it downloads the data from its central database on a fixed host to a local database or transfers the subtransaction to the fixed host. From the system point of view, our transaction management involves an initiator and a set of mobile and/or fixed executors, where the initiator controls the pervasive transaction processing. Figure 6.6 illustrates the execution flow of the pervasive transaction coordination.

An initiator coordinates a pervasive transaction in the following steps:

1. Find (P_i, T_i): An initiator discovers a qualified neighboring node as a participant P_i to execute a subtransaction T_i. It is context-aware which subtransaction will be executed, based on event–context–action rule descriptors defined in pervasive transaction T.

Figure 6.6 Execution process of pervasive transactions.

2. Send (T_i, P_i): The initiator sends T_i to the participant P_i found in the first step.

3. Receive (R(T_i), P_i): The initiator waits for execution result R(T_i) from the P_i. R(T_i) is a SUCCESSFUL or a FAILED message, which means that P_i has successfully committed or failed to commit, respectively.

4. Global decision: Based on the T’ current state TS, the initiator makes a global decision:

■ Global commit. If T reaches the acceptable state, the initiator confirms all committed subtransactions by sending CONFIRM messages to them. At that time, the pervasive transaction T successfully commits.

■ Global abort. If T reaches the failed state, the initiator undoes the committed subtransactions, sending COMPENSATION messages to participants. In that case, T is aborted.

■ Continuous execution through selecting the next subtransaction. If T is still at the executing state, the initiator selects the next subtransaction T_j based on the R(T_i) and the intradependency D between T_j and T_i and then goes to step (1).

An executor actually performs the incoming subtransaction T_i under the control of the initiator in the following way:

1. Data verification. The executor checks the data that will be accessed during the execution of T_i in its local lightweight database. If there are no such data, the executor goes to step (3).

2. Subtransaction execution. If the accessed data are locally available, the executor performs T_i:

■ Executing application operations in T_i

■ Sending a SUCCESSFUL (or FAILED) message to the initiator when T_i is successfully committed (or fails to commit)

■ Executing a compensating transaction and recording a Failure in a log if it receives a CANCEL message

■ Recording a Success after it receives a CONFIRM message

3. Data or subtransaction transfer. In a case where the executor cannot find the data in its own local database, it needs to download the data from the central database server or transfer T_i to the central database server. The central database server refers to the main database of an organization, which holds all data needed by the organization’s activities and is connected with a fixed network. When the central database server receives a subtransaction, it executes the subtransaction using the policy described in step (2).

6.4.3 Participant Discovery

In pervasive environments, the centralized registry mechanism is impracticable for pervasive transactions due to the node mobility. Accordingly, before submitting a subtransaction, an initiator has to dynamically find a qualified (mobile) device that is able to provide the specific services (e.g., sickbed reservation) for the subtransaction as a participant.

MDs are generally battery-powered so that power saving is one of the most important performance metrics. Generally speaking, the fewer the number of hops of message transmission in multiple-hop mesh networks, the lower the energy consumption of mobile devices. To reduce total energy consumption, the transaction initiator finds and selects participants based on two principles. The first one is to find a mobile device within the shortest distance. The second is to select the mobile device with the most remaining energy. We use the number of hops between the initiator and a participant to measure the distance. The initiator discovers a qualified participant for a subtransaction T_i through the following mechanism:

1. Participant query. An initiator broadcasts a query message REQ within the format shown in Figure 6.7a. “SD” is a service description, and only mobile devices that can provide the specified services respond to the REQ message; h is the number of hops between the source node S and a destination node D.

2. Forwarding and response. Upon receiving an REQ message, any mobile device

■ Appends itself to the path field and increases h field by 1.

■ Constructs and returns a response message RES along with the current device states, shown in Figure 6.7b, only if it can provide services specified in the SD field.

■ Otherwise, it further broadcasts the updated RES message if h is less than H_max. However, if h is equal to H_max, it drops the message. Note that any device ignores the messages received previously.

3. Participant selection. The initiator collects response messages within a given period of time, and then

■ Extracts the number of hops from the h field of each RES message, marking h(k).

■ Calculates the minimal number of hops $H_{\min} = \underset{for all RES}{Min} (h (k))$ $H_{\min} = \underset{for all RES}{Min} (h (k))$ .

Figure 6.7 Query and response messages for participant discovery: (a) query message, (b) response message and (c) path in the response message.

■ Selects a mobile device with H_min hops and qualified context (e.g., enough network bandwidth) as a participant. When many devices have the same H_min hops, if there is a fixed host with H_min hops, the fixed host will be selected as a participant; otherwise, the mobile device with the most remaining energy will be selected as a participant.

4. Default participant. In this case, the initiator has failed to find any qualified device within H_max hops. We assume that there be well-known fixed hosts to provide public services in a city. If there is no response, which means any mobile device within the range of H_max hops cannot execute T_i, the initiator selects a well-known fixed host eligible for execution of T_i.

6.5 Formal Transaction Verification

In this section, we model the aforementioned coordination algorithm through Petri nets and then validate the algorithm’s correctness using the Petri nets’ reachable tree analysis technology.

6.5.1 Petri Net with Selective Transition

A Petri net is an abstract and formal tool that can model systems’ events, conditions, and the relationships among them. The occurrence of these events may change the state of the system, causing some of the previous conditions to cease holding and other conditions to begin to hold [23]. A Petri net consists of two kinds of nodes: places and transitions, which are connected by directed arcs from a place to a transition (P × T) or from a transaction to a place (T × P). In a Petri net, places and transitions represent conditions and events, respectively. In this chapter, we introduce a selective transition concept to express the selective activity. Before the definition of selective transition, we assume a transition t has m output arcs such that O(t) = {O(t)⁽ⁱ⁾ | O(t)⁽ⁱ⁾ is one of the output arcs of t, 1 ≤ i ≤ m}.

Definition 6.2

A transition t is selective if (1) any output arc O(t)⁽ⁱ⁾ ∈ O(t) associates with a condition O(t)⁽ⁱ⁾.cond(i) and (2) when a firing occurs, only the output arc O(t)⁽ⁱ⁾ with O(t)⁽ⁱ⁾.cond(i) = true (1 ≤ i ≤ m) is fired.

A selective transition concept extends the modeling ability of Petri nets by introducing conditional firing for output arcs. For an activity graph with a conditional loop, shown in Figure 6.8a for example, we model such an activity sequence in a selective Petri net; see Figure 6.8b. When transition t₂ is fired, only the output arc O(t)⁽ⁱ⁾ with O(t)⁽ⁱ⁾.cond(i) = true is actually fired.

Based on the selective transition concept, we model the aforementioned coordination algorithm as the graphic Petri net (see Figure 6.9). In particular, transaction t₁ has two exclusively input arcs: p₁ × t₁ and p₇ × t₁, where a white circle means t₁ can be fired if and only if one of the input arcs has a token. Places and transitions are described in Table 6.3. Two selective transitions, t₃ and t₅, denote judging the state of global transaction T and the situation of subtransactions, respectively. More specifically:

Figure 6.8 (a) Conditional activity and (b) selective transition.

Figure 6.9 Petri net of the coordination algorithm.

■ O(t₃)⁽¹⁾.cond(1): T reaches one of the acceptable states.

■ O(t₃)⁽²⁾.cond(2): T has not reached any acceptable state.

■ O(t₅)⁽¹⁾.cond(1): All subtransactions have been executed (i.e., ∀S_i = ‘S’ or ‘F’).

■ O(t₅)⁽²⁾.cond(2): Some subtransactions have not executed (i.e., ∃S_i = ‘I’).

6.5.2 Petri Net–Based Formal Verification

Petri nets can analyze systems’ behavioral properties, including reachability, boundedness, liveness, coverability, reversibility, persistence, and so on. For a bounded Petri net, these problems can be solved by the reachable tree [24]. Peterson [23] also pointed out that, in Petri nets, many questions often can be reduced to the reachable problem. In this subsection, we first construct the reachability of the Petri net and then validate the correctness of the coordination algorithm by the reachable tree analysis technology of Petri nets.

Table 6.3 Places and Transitions of Petri Net of the Coordination Algorithm

Elements	Description	Meaning
p₁	Active	A pervasive transaction T is initiated
p₂	Executing	T has been executing
p₃	Waiting	Initiator is receiving the R(T_i)
p₄	Committing	Initiator is committing globally
p₅	Success	T is successfully committed
p₆	Pending	T enters the pending state
p₇	Select subtransaction	Initiator selects the next subtransaction based on dependency
p₈	Compensating	Initiator is undoing subtransactions committed previously
p₉	Failure	T has been undone

t₁	Initiator discovers a participant P_i and sends T_i to P_i
t₂	Initiator updates the state of global transaction T
t₃	Initiator judges whether T reaches one of the acceptable states
t₄	T is committed globally
t₅	Initiator judges whether all subtransactions are executed
t₆	Subtransactions committed previously are undone by compensating transactions

Figure 6.10 illustrates a Petri net reachable tree for the coordination algorithm, which intuitively describes all the states from the initial state M₀ by the movement of tokens. In a reachable tree, a marking M is an assignment of tokens to each place. M is reachable from another marking M’ if M’ may be transformed to M through a sequence of firings. The set of all markings reachable from an initial marking M₀ in a Petri net (N, M₀) is marked by R(M₀).

The boundedness and liveness of Petri nets are often used as correctness criteria in protocol validation. This chapter discusses these two properties by analyzing a Petri net’s reachable tree. In a reachable tree, nodes denote M₀ and its successors; M₀ is the root, and leaf nodes correspond to the final state. A path from the M₀ to a leaf node means an execution sequence. The following theorems collaboratively prove the correctness of the coordination algorithm.

Figure 6.10 Reachable tree of Petri net of the coordination algorithm.

Theorem 6.1

The Petri net of the coordination algorithm is bounded.

Proof: A Petri net (N, M₀) is said to be k-bounded (or simply bounded) if the number of tokens in any one place does not exceed a finite number k for any marking reachable from M₀, that is, ∀m_i≤k for every place p_i in every marking M ∈ R(M₀) [24]. In the reachable tree of a Petri net, the number of tokens in each place is never more than 1. Therefore, the Petri net of the coordination algorithm is bounded, and the k is equal to 1.

For a bounded Petri net, its reachable tree contains all possible markings. Let MS be the marking set of the Petri net for the coordination algorithm. We have MS = R(M₀) = {M₀, M₁, M₂, M₃, M₄, M₅, M₆, M₇, M₈}; that is, any marking M in the Petri net of the coordination algorithm is reachable from M₀ such that M_i ∈ R(M₀) for any M_i ∈ MS. Therefore, there is no useless or dead state during the execution of a pervasive transaction.

Theorem 6.2

The Petri net of the coordination algorithm is L1-live.

Proof: A transition t is L1-live if t can be fired at least once in some firing sequences. Furthermore, a Petri net (N, M₀) is said to be L1-live if each transition in the net is L1-live [24]. By observing the reachable tree of Petri net of the coordination algorithm, we find that each marking is reachable and each transition can be fired at least once from M₀. Therefore, the Petri net of the coordination algorithm is L1-live.

Theorem 2 indicates that the coordination algorithm is deadlock-free as long as the firing starts with the initial marking M₀. According to Theorem 1 and Theorem 2, we can draw a conclusion: The transaction coordination algorithm is correct.

6.6 Evaluations

This section evaluates the performance of the coordination algorithm through a simulation system, as shown in Figure 6.11, where a coordinator and a participant execute the transaction coordination mechanism. During the pervasive transaction processing, the context-awareness module collects and monitors transaction context for dynamically adjusting transaction execution policies. Log service records necessary coordination and state information in order to recover systems from potential failures. A compensating transaction generator (CTG) automatically generates compensating transactions during the execution of pervasive transactions. A communication unit sends and receives messages. A local transaction manager (LTM), usually part of a local database, is responsible for ensuring the atomicity, consistency, isolation, and durability (ACID) properties of local subtransactions, while the coordinator manages a global pervasive transaction to achieve one of the acceptable states.

6.6.1 Experiment Environment

In the simulation system, there were 100 mobile devices that simulate MDDs and 10 fixed hosts; 20 mobile devices (i.e., executors) provide sickbed reservation service, and other 20 mobile devices (also executors) are able to handle public traffic queries. Fixed hosts support either sickbed reservations or public traffic queries. Any mobile device can issue global pervasive transactions, but only the executor is able to perform subtransactions initiated from other devices.

Figure 6.11 Architecture of the pervasive transaction system: (a) initiator and (b) executor.

We simulated the mobility of nodes by changing link states among them, and furthermore, we let the wireless links disconnect in the probability DisconnectProb. In addition, we modeled system load in the number of concurrent pervasive transactions (simplified NumMobiTran). Pervasive transactions were randomly initiated and concurrently executed in the system. Each of them consisted of two subtransactions.

During the transaction processing, CATran dynamically discovers a qualified participant for a subtransaction T_i and can select the next subtransaction T_j substitutable for T_i if T_i was aborted. In the medical treatment reservation described in Section 6.1, for example, the coordinator will request the subtransaction T₅ after T₁ fails. By comparison, NonCATran dispatches subtransactions to well-known devices that provide the corresponding services so that a NonCATran transaction is aborted if the network link between an initiator and an executor is unqualified.

6.6.2 Results and Evaluation

High mobility and frequent network disconnection significantly decrease the probability of successful commits. As a result, the failed ratio (FR) is an important criterion for measuring the effectiveness and performance of a transaction management mechanism. FR refers to the fraction of failed transactions. It can be formulated as FR = (FN ÷ TN) × 100%, where FN is the number of failed transactions and TN is the total number of transactions in the system within a given period of time.

■ System load. In this experiment, the number of concurrent pervasive transactions is varied from 100 to 500, where link disconnection probability is fixed such that DisconnectProb = 0.1. The performance results obtained for the two kinds of transactions, CATran and NonCATran, are shown in Figure 6.12. From this figure, we can see that the FR of the system upgrades for both strategies as the transaction load increases and, for all ranges of the transaction load, CATran performs better than NonCATran. This is because CATran selects a qualified mobile device with qualified context and is also able to execute substitutable subtransaction(s) if the previous request failed. By comparison, NonCATran sends a transaction request directly, without context awareness. The reason for the increase in the FR with both execution strategies is that a greater load on the physical resources caused more heavy data conflicts.

■ Link states. When a link disconnects or does not have enough bandwidth, nodes connected with the link can no longer communicate with each other. Therefore, for both CATran and NonCATran transactions, link states have significant impact on the FR. In this experiment, the DisconnectProb is varied from 0.1 to 0.7 in increments of 0.1. The performance results are shown in Figure 6.13, where the number of concurrent pervasive transactions in the system was fixed such that NumMobiTran = 50. As disconnection probability of wireless links increases, the performance of the system worsens with both execution strategies, CATran and NonCATran. The reason is that, with the increment of failure probability of links, more subtransactions cannot be sent to targeted nodes. However, the relative performance of CATran and NonCATran is not affected by the probability of wireless link failure because CATran transactions discover and select qualified devices before transaction processing.

Figure 6.12 Failed ratio versus the number of concurrent pervasive transactions.

Figure 6.13 Failed ratio versus the disconnection probability of wireless links.

Figure 6.14 Failed ratio versus the number of interaction operations in a pervasive transaction.

■ Interaction operations. Interaction operations refer to the requests initiated by a mobile device during the execution of a transaction. In this experiment, the number of interaction operations in pervasive transactions is varied from 1 to 7 in increments of 1 to evaluate the impact of interaction operations. Performance results obtained are illustrated in Figure 6.14, where NumInteration means the number of interaction operations in a pervasive transaction. As the degree of interaction operations was increased, the performance of CATran gets only a little bit worse because the CATran transactions select qualified participants. By comparison, a steeper degradation in performance was observed in NonCATran strategy as the number of interaction operations increased. The reason is that NonCATran transactions are directly dispatched to a well-known device without selection so that failure probability of these transactions accumulated because of more interactions among an initiator and executors through unstable wireless connections.

Table of Contents for 6 Pervasive Mobile Transactions

Create new playlist

Sign In

Sign Up

Table of Contents for
6 Pervasive Mobile Transactions