J. Cent. South Univ. Technol. (2008) 15: 545-551

DOI: 10.1007/s11771-008-0103-y

Scheduling transactions in mobile distributed real-time database systems

LEI Xiang-dong(À×Ïò¶«), ZHAO Yue-long(ÕÔÔ¾Áú), CHEN Song-qiao(³ÂËÉÇÇ), YUAN Xiao-li(Ô¬ÏþÀò)

(School of Information Science and Engineering, Central South University, Changsha 410083, China)

                                                                                                                                                                           

Abstract: A DMVOCC-MVDA (distributed multiversion optimistic concurrency control with multiversion dynamic adjustment) protocol was presented to process mobile distributed real-time transaction in mobile broadcast environments. At the mobile hosts, all transactions perform local pre-validation. The local pre-validation process is carried out against the committed transactions at the server in the last broadcast cycle. Transactions that survive in local pre-validation must be submitted to the server for local final validation. The new protocol eliminates conflicts between mobile read-only and mobile update transactions, and resolves data conflicts flexibly by using multiversion dynamic adjustment of serialization order to avoid unnecessary restarts of transactions. Mobile read-only transactions can be committed with no-blocking, and respond time of mobile read-only transactions is greatly shortened. The tolerance of mobile transactions of disconnections from the broadcast channel is increased. In global validation mobile distributed transactions have to do check to ensure distributed serializability in all participants. The simulation results show that the new concurrency control protocol proposed offers better performance than other protocols in terms of miss rate, restart rate, commit rate. Under high work load (think time is 1s) the miss rate of DMVOCC-MVDA is only 14.6%, is significantly lower than that of other protocols. The restart rate of DMVOCC-MVDA is only 32.3%, showing that DMVOCC-MVDA can effectively reduce the restart rate of mobile transactions. And the commit rate of DMVOCC-MVDA is up to 61.2%, which is obviously higher than that of other protocols.

Key words: mobile distributed real-time database systems; muliversion optimistic concurrency control; multiversion dynamic adjustment; pre-validation; multiversion data broadcast

                                                                                                                                                                              

1 Introduction

The communication bandwidth is asymmetric in mobile broadcast environment^[1-2]. The downstream (server to mobile host, MH) communication capacity is much greater than the upstream (MH to server) communication capacity. Since the bandwidth from MH to the server is very limited, each MH should minimize wireless communication to reduce the contention of the narrow bandwidth. Mobile read-only transactions should be committed with no-blocking^[3-6]. Data conflicts should be detected as soon as possible at the MHs to avoid any wastage of resources and to reduce the response time of mobile transactions. More schedules of transaction executions should be allowed to avoid unnecessary transaction aborts since the MHs may suffer from a long delay to realize any mobile transaction aborts and restarts of the failed mobile transactions. The tolerance of mobile transactions of disconnections from the broadcast channel should be increased. The concurrency control protocol should not involve the MHs to synchronize with each other and the server for data conflict detection^[7-8].

In mobile computing environments system, work loads are the most partly mobile read-only transactions that execute queries and analysis. But under single version scheduler mobile read-only transactions are frequently blocked by mobile update transactions^[9]. Multiversion mechanism can eliminate conflicts between read-only and update transactions, and increase the concurrency degree of transactions and the tolerance of mobile transactions of disconnections from the broadcast channel.

Multiversion concurrency control mechanism is of desirable property of which a read request never fails and does not need to wait. In typical database systems, reading is more frequent than writing. This advantage may be of major practical significance. Multiversion concurrency control mechanism eliminates the conflict between read-only transactions and update transactions. Therefore, read-only transactions can be committed with non-blocking.

In this work, DMVOCC-MVDA (distributed multiversion optimistic concurrency control with multiversion dynamic adjustment) protocol was proposed to process distributed real-time transaction in mobile broadcast environments. Transaction validation was performed at two levels: local validation and global validation. Local validation of transactions was carried out at two phases: local pre-validation and local final validation; local pre-validation was performed at MHs, and transactions that survive in local backward pre- validation must be submitted to the server for local final validation. Such an early data conflict detection feature can save processing and communication resources.

2 Commit processing

The traditional commit protocols, such as 2PC (two phase commit), 3PC (three phase commit), etc., may not perform satisfactorily in mobile broadcast environments mainly because of the limited resources, especially the communication capacity^[10]. Therefore, the 2PC commit protocols must be revised to be suitable for mobile distributed real-time database systems. The mobile distributed real-time transaction T is issued at a MH that is called home-MH (H-MH). Transaction T_co at the BS (base station) to which H-MH is attached is identified as the coordinator. If T issues read/write request and H-MH cannot process, then it creates a subtransaction T_i, and sends T_i to T_co. Upon the receipt of T_i from H-MH, T_co creates distributed real-time transaction control block for T_i which contains one entry, deadline of T_i, and coordinator¡¯s identity. In the case of coordinator change, a distributed real-time transaction control block is used to inform the new coordinator the status of T and commit set members. T_co distributes T_i to the relevant server. The server, after receiving T_i, distributes T_i to MH or fixed host(FH) which processes T_i. T_co waits for transaction processing results. During T_i processing, if T_i is aborted for any reason, the participant will send an aborted message to T_co before the deadline of T_i expires. At the end of T_i, the participant sends commit message to T_co. If the participant cannot complete its subtransaction for any reason, it will send an aborted message to the coordinator. T is committed when T_co receives all commit messages, and T_co sends commit massage to members of the commit set. If T_co receives neither a commit nor an aborted message within the deadline of T, T will be aborted, T_co sends abort message to members of the commit set.

When H-MH moves to another cell, the coordinator may always reside at the BS to which the H-MH is attached. The old coordinator transfers state information to the new coordinator. The coordinator informs all the participants about this change.

3 Transaction processing at MHs

3.1 Read/write request processing

Each transaction T_i is associated a timestamp, denoted by T_S(T_i). This timestamp is assigned before the transaction starts. For each data item x, a sequence of versions 1, x₂, ¡­, x_m> is associated. Each version x_k contains three data fields: the value of version x_k; W_TS(x_k), the largest timestamp which creates version x_k; R_TS(x_k), the largest timestamp of any transaction that successfully reads version x_k. During read phase, the scheme operates as follows. Suppose that transaction T_i issues a read(x) or write(x) operation. Let x_k denote the version of x whose write timestamp is the largest (less than or equal to T_S(T_i)). If transaction T_i issues a read(x), then the value returned is the version x_k. The reason is that a transaction reads the most recent version that comes before it in time. The version x_k is set to R_Set(T_i), where R_Set(T_i) denotes the set of data items read by T_i. If transaction T_i issues a write(x), and if T_S(T_i)£¼R_TS(x_k), the transaction T_i is restarted, otherwise a new version of x is created. The reason is that if T_i attempts to write a version that some other transactions would have read, the write is not allowed. The new version x_i is set to W_Set(T_i),  where W_Set(T_i) denotes the set of data item that have been written by T_i.

3.2 Multiversion dynamic adjustment

The restart of mobile transaction is high cost in mobile broadcast environment. The main purpose of multiversion dynamic adjustment of serialization order is to prevent unnecessary restarts, which occur when a transaction is restarted that could have been serialized successfully with respect to the validating transaction. Let r_i[x_j] represent the read operation of T_i for reading the version x_j of x, and w_i[x_i] denote write operation of T_i for writing version x_i of x. Furthermore, assume v_i and c_i denote the validation and commit of T_i, respectively. Consider the following three transactions T₁, T₂, and T₃, and their execution multiversion(MV) history fragment H:

H: r₁[x₀] r₂[x₀]w₁[x₁]r₃[y₀]r₂[y₀]w₃[y₃]w₁[y₁]v₁v₂c₁c₂

The MV history H is not serializable, therefore, both T₂ and T₃ are restarted in the validation of T₁. A careful examination of H shows that T₂ has only a write-read conflict on data item x. Thus, as long as the serialization order T₂¡úT₁ is set, T₂ does not need to restart. The restart of T₂ is referred to be an unnecessary restart. T₃ clearly needs to restart as it has both read-write and write-read conflicts with T₁. Since the number of read operations is much higher than that of write operations in mobile broadcast environments, a large fraction of data conflicts is of the read-write type, and a significant portion of them falls into this category.

The technique of multiversion dynamically adjusting the serialization order eliminates these unnecessary restarts by adjusting serialization orders of transactions at validation. Let T_v and T_a be validating transaction and active transaction, respectively, there are possibly two types of conflicts between T_v and T_a in multiversion concurrency control mechanism.  There is not write-write conflict in multiversion mechanism because transactions write data items on different versions.

1) R_Set(T_v)¡ÉW_Set(T_a)¡Ù? (read-write conflict). This type of conflict can be resolved by adjusting the validation interval of T_a to induce the serialization order T_v¡úT_a, which signifies that the writes of T_a should not affect the reads of T_v.

2) W_Set(T_v)¡ÉR_Set(T_a)¡Ù?(write-read conflict). This type of conflict can be resolved by adjusting the validation interval of T_a to induce the serialization order T_a¡úT_v, which implies that the writes of T_v should not affect the read phase of T_a.

Each transaction T_i at MHs is allocated with a validation interval V(T_i)=[b_l, b_u], which is initialized [0, ¡Þ]. The V(T_i) reflects the dependencies of T_i on the committed transactions. If T_i (with V(T_i)=[b_li, b_ui]) is serialized before T_j (with V(T_j)=[b_lj, b_uj]), i.e. T_i¡úT_j, then the following relation must hold b_ui£¼b_lj. If a transaction¡¯s validation interval is empty, there is no possible way to serialize the transaction any more, then it must be restarted.

To reflect serialization relation between the mobile transactions and the committed transactions, when a read or write request is processed, V_bl(T_i) will be adjusted. Let x_k denote the version of x whose write timestamp is the largest (less than or equal to T_S(T_i)), if transaction T_i issues a read(x) and if data item x is located in the MH, then version x_k is read by T_i. V_bl(T_i) is adjusted to W_ST(x_k), that is, V(T_i)=V(T_i)¡É[W_TS(x_k), ¡Þ], and the version x_k is set to R_Set(T_i). If transaction T_i issues a write(x), data item x is located in the MH, and if T_S(T_i)£¼R_TS(x_k), the transaction T_i is restarted, otherwise a new version of x_i is created and the new version x_i will be stored into the private workspace of T_i. V_bl(T_i) is adjusted, that is, V(T_i)= V(T_i)¡É[W_TS(x_k),¡Þ]¡É[R_TS(x_k),¡Þ]. The new version x_i is set to be W_Set(T_i). If V(T_i) shuts out, T_i will be aborted.

3.3 Local pre-validation

At the beginning of every broadcast cycle, the server broadcasts the validation information of the committed transaction in the last broadcast cycle. The validation information of transactions consists of C_Set, A_Set, C_ReadSet and C_WriteSet, where C_Set is the set of transactions successfully validated at the server in the last broadcast cycle, A_Set is the set of transactions rejected at the server in the last broadcast cycle, C_ReadSet is the read set of the committed transactions, and C_WriteSet is the write set of the committed transactions. If a mobile transaction does not pass local pre-validation, then it has to be restarted. Let T_i and T_c denote mobile active transaction and committed transaction in the last broadcast cycle, respectively, then there are two types of data conflicts that can induce the serialization order between the active transaction T_i and the committed transaction T_c such that V_I(T_i) has to be adjusted. Then, the rules to resolve data conflicts are given as follows.

1) R_Set(T_i)¡ÉW_Set(T_c)¡Ù?. This type of conflict can be resolved by adjusting the validation interval of T_i to induce the serialization order T_i¡úT_c, which shows that the read of T_i should not affect the write of T_c. T_i precedes T_c in the serialization order. Therefore, the adjustment of V(T_i) should be V_bu(T_i)£¼T_S(T_c), that is, V(T_i)=V(T_i)¡É[0, T_S(T_c)]. C_WriteSet contains the data items that in the write set of the committed transactions. This rule can be described as follows: for each item x_k is in R_Set(T_i), if x_k is in C_WriteSet, V_bu(T_i) will be set to min({W_TS(x_k)|x_k in C_WritSet}). Data item x_k is marked valid, and is not required to be validated at the server. Because the write timestamps of data items created by transactions that are committed after current broadcast cycle are greater than all write timestamps of data items in C_WriteSet.

2) W_Set(T_i)¡ÉR_Set(T_c)¡Ù?. This type of conflict can be resolved by adjusting the validation interval of T_i to induce the serialization order T_c¡úT_i, which shows that the read of T_c should not affect the write of T_i. T_c precedes T_i in the serialization order. Therefore, the adjustment of V(T_i) should be V_bl(T_i)£¾T_S(T_c), that is, V(T_i)=V(T_i)¡É[T_S(T_c), ¡Þ]. C_ReadSet contains the data items that in the read set of the committed transactions. This rule is described as follows: for each item x_i is in W_Set(T_i), if x_j is in C_ReadSet, V_bl(T_i) will be set to max({R_TS(x_k)| x_k in C_ReadSet}).

The algorithm of local pre-validation is described as follows:

local_pre-validation(T_i) 

for each x_k ¡ÊR_Set(T_i) 

if(x_j ¡ÊC_WriteSet) 

V(T_i)=V(T_i)¡É[0,min({W_TS(x_j)| x_j¡ÊC_WriteSet})];

if(V(T_i)==[ ]) abort T_i;

}

}

for each x_i ¡ÊW_Set(T_i)  {

if(x_j¡ÊC_ReadSet)  {

V(T_i)=V(T_i)¡É[max({R_TS(x_j)| x_j¡ÊC_ReadSet}), ¡Þ];

if(V(T_i)==[ ]) abort T_i;

submit T_i to the server for local final validation;

A mobile read-only transaction at MH can be committed if it passes all the local pre-validation in course of execution. It is serialized after all transactions committed before beginning of the current broadcast cycle. A mobile update transaction has to be sent to server for local final validation because the mobile update transaction is serialized after all transaction committed before its validation phase and is serialized before all active transaction.

4 Transaction processing at server

MHs do not have a complete and up-to-date data. For instance, the information about the commit of some conflicting transactions that are submitted to the server after the start of the last broadcast cycle is not known to MHs. Then, all mobile transactions that pass local backward pre-validation at MHs have to be submitted to the server for local final validation. A mobile only-only transaction at the HM can be committed locally and does not need to be submitted to the server for local final validation if it passes all the local backward pre-validation. Data conflicts are detected by comparing the read set of validating mobile transaction and the write set of the committed transaction, since the committed transactions precede the validating transaction in the serialization order.

Suppose that transaction T_i and T_j create successfully version x_i and x_j of data item x, respectively.  A version order is defined as follows: x_i£¼£¼x_j£¼=£¾T_S(T_i)£¼T_S(T_j).

1) Let T_v be the validating transaction. For each data item x_k in R_Set(T_v), if x_k is not marked valid, and if there exists version x_k+1, x_k£¼£¼x_k+1, the adjustment of V(T_v) should be V_bu (T_v)£¼W_TS(x_k+1), that is, V(T_v)=V(T_v)¡É[0, W_TS(x_k+1)]. It is because new versinon x_k+1 is created after T_v reads version x_k. T_v should be serialized before the transaction that created version x_k+1.

2) Let T_v be the validating transaction. For each data item x_v in W_Set(T_v), the adjustment of V(T_v) should be  V_bl(T_v)>max(R_TS(x)). That is, set V(T_v)=V(T_v)¡É [max(R_TS(x)), ¡Þ]. It is because transactions committed may not read version x_v created by T_v. T_v should be serialized after all committed transactions that read data item x.

The algorithm of local final backward validation is described as follows:

local_final_backward_validation(T_v)  {

for each x_k in R_Set(T_v)  {

if (x_k is not marked as valid)  {

if($x_k+1(x_k£¼£¼x_k+1)) V(T_v)=V(T_v)¡É[0, W_TS(x_k+1)];

if(V(T_v)==[ ])  {

abort T_v;

A_Set=A_Set¡È{ T_v};

for each x_v in W_Set(T_v)  {

V(T_v)=V(T_v) ¡É[max(R_TS(x)), ¡Þ];

if(V(T_v)==[ ])  {

abort T_v;

A_Set=A_Set¡È{ T_v};

5 Global validation

After local validation a global validation is needed for distributed serializability^[11]. Let V_H(T_v) denote the validation interval of T_v at the H-MH, and V_pi(T_v) the validating interval of T_v at the participant P_i for validating transaction T_v. Suppose that there are n participants. The validation interval of T_v is adjusted to be V(T_v)=V_H(T_v)¡ÉV_P1(T_v)¡ÉV_P2(T_v)¡É¡­¡ÉV_Pn(T_v). If the transaction validation interval is empty, T_v is aborted to ensure the distributed serializability; otherwise T_co commits T_v, and sends commit massage to all participants.

The algorithm of global validation is described as  follows:

global_validation (T_v)  {

V(T_v)=V_H(T_v);

for each V_Pi(T_v) at participant P_i

V(T_v)=V(T_v)¡ÉV_Pi(T_v);

if(V(T_v)==[ ]) abort T_v;

else  {

T_S(T_v)=V_lb(T_v)+ min(C_Time, V_lb(T_v)+¦¤);

//C_Time is current system time

//¦¤ is a sufficiently small value

for each x_k in R_Set(T_v)

if(T_S(T_v)>R_TS(x_k))  {

R_TS(x_k)=T_S(T_v);

C_ReadSet=C_ReaSet ¡È{x_k};

for each x_v in W_Set(T_v)  {

W_TS(x_k)=T_S(T_v);

write x_k into the database;

C_WriteSet=C_WriteSet ¡È{x_v};

C_Set=C_Set¡È{ T_v};

commit T_v ;

If a validating transaction is allowed to be committed, a final timestamp indicating its position in the serialization order is assigned to it. The final timestamp T_S(T_v) is equal to min(C_Time, V_bl(T_v)+¦¤), where C_Time is current system time, ¦¤ is a sufficiently small value. If a transaction is never adjusted, the final timestamp of T_v is current system time. The read and the write set of T_v are added into C_ReadSet and C_WriteSet accordingly. When the next broadcast cycle comes, the server will broadcast the validation information.

6 Correctness of DMVOCC- MVDA protocol

The correctness of the concurrency control protocol presented, DMVOCC-MVDA, is proved. That is, the DMVOCC-MVDA protocol ensures serializability. If the multiversion serialization graph of a set of transactions, MVSG(H), is acyclic, the schedule H is serializable^[12].

Lemma 1 Let T_i and T_j be two committed transactions in a local history (LH) produced by the DMVCC-MVDA. If there is an edge T¡úT_j in multiversion serialization graph MVSG(LH), then there exists T_S(T_i)£¼T_S(T_j).

Proof If there is an edge T_i¡úT_j in MVSG(LH), there must exist one or more conflicting operations with one of the following types on data item x. Let r_i[x_k] represent the read operation of T_i  for reading the version x_k of x, and w_i[x_i] denote T_i for writing the version x_i of x.

Case 1 r_i[x_k]¡úw_j[x_j]

1) T_i is committed before T_j reaches validation phase

For w_j[x_j], when T_j reaches the validation phase, the validation interval of T_j will be adjusted: V(T_j)=V(T_j)¡É [W_TS(x_k), ¡Þ]¡É[R_TS(x_k), ¡Þ], where x_k is the version of x whose write timestamp is the largest (less than or equal to T_S(T_j)). At server the adjustment of V(T_j) should be  V_bl(T_j)£¾max(R_TS(x)), that is, V(T_j)=V(T_j)¡É[max(R_TS(x)), ¡Þ]. This ensures that the final timestamp of T_j, T_S(T_j), which is obtained by adding a sufficiently small value to the lower bound of V(T_j), is greater than R_TS(x_k), which is equal to or greater than T_S(T_i). Thus, T_S(T_i)¡ÜR_TS(x_k)£¼T_S(T_j), i.e. T_S(T_i)£¼T_S(T_j).

2) T_j is committed before T_i reaches validation phase

For r_i[x_k], when T_i reaches the validation phase, , the validation interval of T_i will be adjusted: V(T_i)=V(T_i)¡É[0, W_TS(x_k)], where W_TS(x_k) is equal to T_S(T_j). At server if there exists version x_k+1 under x_k£¼£¼x_k+1, the adjustment of V(T_i) should be V_bu(T_i)£¼W_TS(x_k+1). That is, V(T_i)= V(T_i)¡É[0, W_TS(x_k+1)]. This ensures that T_S(T_i) is lesser than W_TS(x_k). Thus, T_S(T_i)£¼W_TS(x_k)=T_S(T_j), i.e. T_S(T_i)£¼T_S(T_j).

Case 2 w_i[x_i]¡úr_j[x_i]

This case will happen when T_i is committed before T_j reads x_i. When T_j reads x_i, the validation interval of T_j will be adjusted: V(T_j)=V(T_j)¡É[W_TS(x_i), ¡Þ], where W_TS(x_i) is equal to T_S(T_j). It ensures that T_S(T_j) is greater than W_TS(x_i). Thus, T_S(T_i)=W_TS(x_i)£¼T_S(T_j). Therefore T_S(T_i)£¼T_S(T_j).

Theorem 1 Every local history(LH) generated by the DMVOCC-MVDA protocol is serializable.

Proof Assume that in the MVSG(LH) generated by DMVOCC-MVDA protocol, there exists a cycle T₁¡úT₂¡úT₃¡ú¡­T_n¡úT₁. According to the results of Lemma 1, There exists

T_S(T₁)£¼T_S(T₂)£¼¡­£¼T_S(T_n)£¼T_S(T₁).

This results in an unresolvable contradiction. Thus, MVSG(LH) must be acyclic, implying that the schedule must be serializable.

Theorem 2 Every global history(GH) generated by the DMVOCC-MVDA protocol is serializable.

Proof Suppose that MVSG(GH) generated by DMVOCC-MVDA protocol contains a cycle T₁¡úT₂¡ú T₃¡ú¡­T_n¡úT₁, where n£¾1. For n=2, there probably exist the following two cases.

Case 1 Both transactions are local. Based on Theorem 1, there is T_S(T₁)£¼T_S(T₁), which is contradictory and therefore no cycle can exist.

Case 2 Both transactions are global. Because the proposed protocol executes global operations in both sites, thus the serialization graphs for both sites are identical. Therefore, by Theorem 1 this is T_S(T₁)£¼T_S(T₁). This is contradictory and therefore no cycle can exist.

Suppose that the Theorem 2 holds for n=i for i¡Ý2, it holds for n=i+1. By the induction hypothesis, the path T₁¡ú¡­¡úT_i implies that T_S(T₁)£¼T_S(T_i). By T_i¡úT_i+1 there are two possible cases to be considered.

Case 1 Both transactions T_i and T_i+1 are local transactions. Then by Lemma 1, there exists T_S(T₁)£¼T_S(T_i)£¼T_S(T_i+1)£¼T_S(T₁) at least one site. This is contradictory and therefore no cycle can exist.

Case 2 Both transactions T_i and T_i+1 are global. Then based on Lemma 1, there exists T_S(T₁)£¼£¼T_S(T_i)£¼T_S(T_i+1)£¼T_S(T₁) at least one site. This is contradictory and therefore no cycle can exits.

Therefore, no cycle can exist in MVSG(GH), and thus the DMVOCC-MVDA protocol produces only global serializable histories.

7 Performance evaluation

The simulation experiments study the performance of the proposed new concurrency control protocol (DMVOCC-MVDA), DTO-2PC (DTO combined with 2PC)^[7], and DHP-2PL^[1] in real-time broadcast environments. The major performance of these protocols is the miss rate. Other performance includes restart rate, commit rate^[13]. The simulation model consists of servers, MHs, fixed hosts(FHs), BSs and broadcast disks^[14-15]. The servers maintain and broadcast multiple versions for each data item to MHs periodically. Different data items may be broadcast at different rates. The data items of the broadcast are divided in the ranges of similar access probabilities. Each of these ranges is placed on a separate disk. Older versions of hot items are placed along with the current values of hot items on the fast disks, while versions of cold data are placed slow disks. Thus, in a broadcast cycle, hot data items are broadcast frequently, clod data items are broadcast less frequently.

At the beginning of every broadcast cycle, the server broadcasts validation information of the committed transactions in the last broadcast cycle. After the completion of a transaction, MH will generate another transaction after a think time. The deadline of a mobile transaction is assigned as (C_Time+S_Factor¡ÁP_{ExecutionTime}), where C_Time is the current system time,  S_Factor is the slack factor, and P_{ExecutionTime} is the predicted execution time and a function of transaction length. Table 1 lists the baseline setting for the simulation experiments. These parameters are chosen in order to create a scenario with high utilization and data contention. A mobile transaction is processed until it is committed. Once the transaction deadline is found missing, the transaction will be aborted.

Table 1 Parameters of simulation experiments

Fig.1 shows the miss rate of mobile transactions under different concurrency control mechanisms. It can be seen that DMVOCC-MVDA improves the systems performance in terms of miss rate. The miss rate of DMVOCC-MVDA is significantly lower than that of DTO-2PC. The DHP-2PL is relatively poor. When think time is 1 s, the miss rate of DMVOCC-MVDA is only 14.6%, while that of DHP-2PL reaches 48.2%. This is because multiversion mechanism removes the conflict between read-only transactions and update transactions in DMVOCC-MVDA. Transaction local pre-validation is performed at MH. Such an early data conflict detection feature can save processing and communication resources. Since DTO-2PC is single version protocol, mobile read-only transactions are frequently blocked by mobile update transactions, thus causing long response time of mobile transactions and miss rate of mobile transactions. In DHP-2PL the overhead for setting locks and detecting data conflicts in mobile environment can be very heavy due to the low bandwidth in mobile broadcast environments. The transaction may spend lots of time for waiting for data locks, and thus missing its deadline. Deadlock detect is too expensive in mobile broadcast environments. The MH requires continuous synchronization with servers for data locks.

Fig.1 Miss rate of mobile transactions vs think time

Fig.2 shows the restart of mobile transactions under different concurrency control mechanisms. It can be seen that DMVOCC-MVDA effectively reduces the restart rate of mobile transactions. When think time is 1 s, the restart rate of DMVOCC-MVDA is only 32.3%, while that of DHP-2PL reaches 105.3%. This is because multiversion mechanism removes the conflict between mobile read-only transactions and mobile update transactions. The technology of multiversion dynamic adjustment of serialization order can prevent unnecessary restarts of transaction. Therefore, the number of transaction restarts can be greatly reduced.

Fig.2 Restart rate of mobile transactions vs think time

Fig.3 shows the commit rate of mobile transactions under different concurrency control mechanisms. It can be seen that the commit rate of DMVOCC-MVDA is significantly higher than that of other protocols. When think time is 1 s, the miss rate of DMVOCC-MVDA reaches 61.2%, while that of DHP-2PL is only 41.3%. The major reason is that DMVOCC-MVDA significantly reduces the miss rate and restart of mobile transactions.

Fig.3 Commit rate of mobile transactions vs think time

8 Conclusions

1) The distributed real-time transaction processing in mobile broadcast environments are studied. Each MH should minimize wireless communication to reduce the contention of the narrow bandwidth in mobile broadcast environment. Mobile read-only transactions should be committed with no-blocking. Data conflicts should be detected as soon as possible at the MHs to avoid any wastage of resources and to reduce the response time of mobile transactions. More schedules of transaction executions should be allowed to avoid unnecessary transaction restarts.

2) DMVOCC-MVDA protocol is designed to process mobile distributed real-time transaction in mobile broadcast environments. At the MHs, all mobile transactions perform local pre-validation of transactions. The protocol can eliminate conflicts between mobile read-only and mobile update transactions, and resolve data conflicts flexibly using multiversion dynamic adjustment of serialization order to avoid unnecessary restarts of transactions. Mobile read-only transactions can be committed with no-blocking, and respond time of mobile read-only transactions is greatly reduced.

3) The simulation results show that the new concurrency control protocol proposed offers better performance in terms of miss rate, restart rate and commit rate.

References

[1] LAM K Y, KUO T W, TSANG W H. Concurrency control in mobile distributed real-time database systems [J]. Information Systems, 2000, 25(4): 261-286.

[2] LIAO Guo-qiong, LIU Yun-sheng, WANG Li-na. Concurrency control of real-time transactions with disconnections in mobile computing environment [C]// The 2003 International Conference on Computer Networks and Mobile Computing (ICCNMC03). Washington DC: IEEE Computer Society Press, 2003: 205-212.

[3] LEE S K, KITSUREGAWA M, HWANG C S. Efficient processing of wireless read-only transactions in data broadcast [C]// The 12th International Workshop on Research Issues in Data Engineering: Engineering E-Commerce/E-Business Systems RIDE-2EC. Washington DC: IEEE Computer Society Press, 2002: 101-111.

[4] LI Guo-hui, YANG Bing, CHEN Ji-xiong. Efficient optimistic concurrency control for mobile real-time transactions in a wireless data broadcast environment [C]// The 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA¡¯05). Washington, DC: IEEE Computer Society Press, 2005: 443-446.

[5] BRAVNER A, ALENCAR F S. A semantic-serializability based fully-distributed concurrency control mechanism for mobile multi-database systems [C]// The 16th International Workshop on Database and Expert Systems Applications (DEXA¡¯05). Washington DC:IEEE Computer Society Press, 2005: 1085-1089.

[6] LEI Xiang-dong, YUAN Xiao-li. Validation concurrency control protocol in parallel real-time database systems [J]. Journal of Central South University of Technology, 2002, 9(3): 198-201.

[7] LEE V C S, LAM K W, SON S H. On transaction processing with partial validation and timestamp ordering in mobile broadcast environments [J]. IEEE Transactions on Computers, 2002, 51(10): 1196-1211.

[8] LEE V C S, LAM K W, KUO T W. Efficient validation of mobile transactions in wireless environments [J]. The Journal of Systems and Software, 2004, 69(1): 183-193.

[9] LEI Xiang-dong, ZHAO Yue-long, YUAN Xiao-li. Transaction processing in mobile database systems [J]. Chinese Journal of Electronics, 2005, 14(3): 491-494.

[10] KUMAR V, PRABHU N, DUNHAM M H, SEYDIM A Y. TCOT¡ªA timeout-based mobile transaction commitment protocol [J]. IEEE Transactions on Computers, 2002, 51(10): 1212-1218.

[11] LINDSTR?M J. Performance of distributed optimistic concurrency control in real-time databases [C]// The 17th International Conference on Information Technology (CIT 04). Berlin Heidelberg: Springer-Verlage, 2004, 3356: 243-252.

[12] PARK C, PARK S, SON S H. Multiversion locking protocol with freezing for secure real-time database systems [J]. IEEE Transactions on Knowledge and Data Engineering, 2002, 5(14): 1141-1154.

[13] DATA A, SON S H. Limitations of priority cognizance in conflict resolution for firm real-time database systems [J]. IEEE Transaction on Computers, 2000, 49(5): 483-501.

[14] PITOURA E, CHRYSANTHIS P K. Multiversion data broadcast [J]. IEEE Transactions on Computers, 2002, 51(10): 1224-1230.

[15] GUOHONG C. Proactive power-aware cache management for mobile computing systems [J]. IEEE Transactions on Computers, 2002, 51(6): 608-621.

              

Foundation item: Project(20030533011) supported by the National Research Foundation for the Doctoral Program of Higher Education of China

Received date: 2007-12-15; Accepted date: 2008-03-09

Corresponding author: LEI Xiang-dong, Doctoral candidate; Tel:+86-13786153879; E-mail: leixiangdong@csu.edu.cn

(Edited by CHEN Wei-ping)