Data Consistency in Intermittently Connected Distributed Systems.
AbstractMobile computing introduces a new form of distributed computation in which communication is most often intermittent, low-bandwidth, or expensive, thus providing only weak connectivity. In this paper, we present a replication scheme tailored for such environments. Bounded inconsistency is defined by allowing controlled deviation among copies located at weakly connected sites. A dual database interface is proposed that in addition to read and write operations with the usual semantics supports weak read and write operations. In contrast to the usual read and write operations that read consistent values and perform permanent updates, weak operations access only local and potentially inconsistent copies and perform updates that are only conditionally committed. Exploiting weak operations supports disconnected operation since mobile clients can employ them to continue to operate even while disconnected. The extended database interface coupled with bounded inconsistency offers a flexible mechanism for adapting replica consistency to the networking conditions by appropriately balancing the use of weak and normal operations. Adjusting the degree of divergence among copies provides additional support for adaptivity. We present transaction-oriented correctness criteria for the proposed schemes, introduce corresponding serializability-based methods, and outline protocols for their implementation. Then, some practical examples of their applicability are provided. The performance of the scheme is evaluated for a range of networking conditions and varying percentages of weak transactions by using an analytical model developed for this purpose.
Introduction
Advances in telecommunications and in the development of portable computers have provided for
wireless communications that permit users to actively participate in distributed computing even
while relocating from one support environment to another. The resulting distributed environment
is subject to restrictions imposed by the nature of the networking environment that provides
varying, intermittent and weak connectivity.
In particular, mobile clients encounter wide variations in connectivity ranging from high-
bandwidth, low latency communications through wired networks to total lack of connectivity
[7, 11, 23]. Between these two extremes, connectivity is frequently provided by wireless networks
characterized by low bandwidth, high latency or high cost. To overcome availability and latency
barriers, and reduce cost and power consumption mobile clients most often deliberately avoid use
of the network and thus operate switching between connected and disconnected modes of opera-
tion. To support such behavior, disconnected operation, that is the ability to operate disconnected,
is essential for mobile clients [11, 12, 26]. In addition to disconnected operation, operation that
exploits weak connectivity, that is connectivity provided by intermittent, low-bandwidth, or expensive
networks, is also desirable [18, 9]. Besides mobile computing, weak and intermittent
connectivity also applies to computing using portable laptops. In this paradigm, clients operate
disconnected most of the time, and connect occasionally through a wired telephone line or upon
returning back to their working environment.
Private or corporate databases will be stored at mobile as well as static hosts and mobile users
will query and update these databases over wired and wireless networks. These databases, for
reasons of reliability, performance, and cost will be distributed and replicated over many sites.
In this paper, we propose a replication schema that supports weak connectivity and disconnected
operation by balancing network availability against consistency guarantees.
In the proposed schema, data located at strongly connected sites are grouped together to form
clusters. Mutual consistency is required for copies located at the same cluster while degrees of
inconsistency are tolerated for copies at different clusters. The interface offered by the database
management system is enhanced with operations providing weaker consistency guarantees. Such
operations allow access to locally, i,e., in a cluster, available data. Weak reads access
bounded inconsistent copies and weak writes make conditional updates. The usual operations,
here called strict, are also supported. They offer access to consistent data and perform permanent
updates.
The schema supports disconnected operation since users can operate even when disconnected
by using only weak operations. In cases of weak connectivity, a balanced use of both weak
and strict operations provides for better bandwidth utilization, latency and cost. In cases of
strong connectivity, using only strict operations makes the schema reduce to the usual one-copy
semantics. Additional support for adaptability is possible by tuning the degree of inconsistency
among copies based on the networking conditions.
In a sense, weak operations offer a form of application-aware adaptation [19]. Application-aware
adaptation characterizes the design space between two extremes ways of providing adapt-
ability. At one extreme, adaptivity is entirely the responsibility of the application, that is there
is no system support or any standard way of providing adaptivity. At the other extreme, adaptivity
is subsumed by the system, here the database management system. Since, in general, the
system is not aware of the application semantics, it cannot provide a single adequate form of
adaptation. Weak and strict operations lie in an intermediate point between these two extremes,
serving as middleware between a database system and an application. They are tools offered
by the database system to applications. The application can at its discretion use weak or strict
transactions based on its semantics. The implementation, consistency control, and the underlying
transactional support is the job of the database management system.
The remainder of this paper is organized as follows. In Section 2, we introduce the replication
model along with an outline of a possible implementation that is based on distinguishing data
copies into core and quasi. In Sections 3 and 4, we define correctness criteria, prove corresponding
serializability-based theorems, and present protocols for maintaining weak consistency under the
concurrent execution of weak and strict transactions and for reconciling divergent copies, respec-
tively. Examples of how the schema can be used are outlined in Section 5. In Section 6, we develop
an analytical model to evaluate the performance of the schema and the interplay among its various
parameters. The model is used to demonstrate how the percentage of weak transactions can be
effectively tuned to attain the desired performance. The performance parameters considered are
the system throughput, the number of messages, and the response time. The study is performed
for a range of networking conditions, that is for different values of bandwidth and for varying
disconnection intervals. In Section 7, we provide an estimation of the reconciliation cost. This
estimation can be used for instance to determine an appropriate frequency for the reconciliation
events. In Section 8, we compare our work with related research and conclude in Section 9 by
summarizing.
2 The Consistency Model
To support autonomous operation during disconnections and improve performance, data are distributed
over mobile and stationary sites. Transactions are initiated at both mobile and stationary
hosts.
2.1 Data Correctness
As usually, a database state is defined as a mapping of every data item to a value of its domain.
Data are related by a number of restrictions called integrity constraints that express relationships
among their values. A database state is consistent if the integrity constraints are satisfied [20].
Consistency maintenance in traditional distributed environments relies on the assumption that all
sites are normally connected. This assumption, however, is no longer valid in mobile computing,
maximum number of updates per data item not reflected at all copies
range of acceptable values a data item can take
is the:
d
maximum number of transactions that operate on inconsistent data
maximum number of data items that have divergent copies
maximum number of divergent copies per data item

Table

1: Divergence among copies.
since the distributed sites are only intermittently connected. Similar considerations also hold for
widely distributed systems and for computing using portable laptops. Thus, instead of requiring
maintenance of all integrity constraints we define units of consistency, called clusters.
Data items are partitioned into clusters Cl i based on their location, so that data in strongly
connected sites belong to the same cluster. In particular, data located at the same, neighbor,
or strongly connected sites belong to the same cluster, while data residing at remote or weakly
connected sites belong to separate clusters. As an example, let each mobile host be a cluster by
each own and all fixed hosts belong to the same cluster. Other configurations are also possible.
For instance, in a wide area distributed environment all hosts in nearby locations constitute one
cluster. We relax consistency as follows:
cluster state is consistent iff all intracluster integrity constraints hold. A database
state is bounded-consistent iff all cluster states are consistent and all intercluster integrity constraints
are bounded-consistent.
Bounding inconsistency for an integrity constraint depends on the type of the constraint.
In this paper, we focus on replication constraints, where all copies x i of the same data item x
have the same value. For replicated data, bounded inconsistency means mutual consistency of
all copies in the same cluster and bounded divergence [27, 1] among copies located at different
clusters. Bounded divergence is quantified by a positive integer d, called degree of divergence;
possible definitions of d are listed in Table 1. A replication constraint for x is then called d-
consistent. Data copies are occasionally reconciled to obtain a mutual consistent value. The
degree of divergence can be tuned based on the strength of connection among clusters, by keeping
the divergence small in instances of high bandwidth availability and allowing for greater deviation
in instances of low bandwidth availability.
2.2 The Extended Database Operation Interface
To increase availability and reduce network usage we allow direct access to locally, e.g., in a
cluster, available d-consistent copies by introducing weak read and weak write operations. We call
the standard read and write operations strict read and strict write operations. In particular, a
read operation on a data item x (WR[x]) reads a locally available value of x. A weak write
operation (WW [x]) writes locally available copies and becomes permanent after reconciliation. A
strict read operation (SR[x]) reads the value written by the last strict write operation. Finally, a
strict write operation (SW [x]) writes one or more copies of x and is permanent upon the end of
the issuing transaction.
Definition 2 A transaction (T ) is a partial order (OP , !), where OP is the set of weak (WR)
or strict read (SR) , weak (WW ) or strict write (SW operations
executed by the transaction, and ! represents their execution order. The partial order must specify
the order of conflicting data operations and contains exactly one abort or commit operation which
is the last in the order. Two weak (strict) data operations conflict if they access the same copy of
a data item and at least one of them is a weak (strict) write operation.
Two types of transactions are supported, weak and strict. Upon submission, each user trans-action
is decomposed into a number of weak and strict subtransactions units according to its
semantics and the degree of consistency required by the application. A weak transaction (WT )
is a transaction where OP does not include strict operations. A strict transaction (ST ) is a
transaction where OP does not include weak operations. Weak transactions access data copies
that belong to the same cluster and thus are local at that cluster. There are two commit events
associated with each weak transaction, a local commit in its associated cluster and an implicit
global commit at reconciliation. Local commitment is expressed by an explicit commit operation,
C. Updates made by locally committed weak transactions are visible only to weak transactions in
the same cluster. These updates become permanent and visible to strict transactions only after
reconciliation when local transactions become globally committed.
2.3 Realizing the Extended Database Interface
We divide copies into core and quasi. Core copies are copies that have up-to-date and permanent
values, while quasi copies are copies that have potentially obsolete values that are only conditionally
committed. All quasi copies at a cluster are mutually consistent and bounded-inconsistent
with respect to core copies. Core copies are mutually consistent. An efficient distribution of core
and quasi copies may be accomplished using appropriate algorithms for replica placement such
as those proposed in [10]. To process the operations of a transaction, the database management
system translates operations on data items into operations on copies of these data items. We
formalize this procedure by a translation function h.
Function h maps each read operation into a number of read operations on copies of x and
returns one value (e.g., the most up to date value) as the value read by the read operation. That
is, we assume that h when applied to a read operation returns one value rather than a set of
values. In particular, h maps each SR[x] operation into a number of read operations on core
copies of x and returns one from these values as the value read by the operation. Depending
on how each weak read operation is translated, we define two types of translation functions: a
best-effort translation function that maps each WR[x] operation into a number of read operations
on locally available core or quasi copies of x and returns the most up-to-date such value, and
a conservative translation function that maps each weak read into a number of read operations
core and quasi local copies.
Conservative
Variations
Eventual
Immediate
corresponding clusters.
Writes only core copies.
Reads only local quasi copies.
Variations
Writes core and quasi copies at the
Reads local copies, returns as the value read the most recent value.
Reads core copies, returns as the value read the most recent value.
Writes local quasi copies.
Strict Read (SR)
Strict Write (SW)
Weak Read (WR)
Weak Write (WW)

Table

2: Variations of the translation function.
only on locally available quasi copies and returns the most up-to-date such value. Based on
the time of propagation of updates of core copies to quasi, we define two types of translation
functions: an eventual translation function that maps a SW [x] into writes of only core copies
and an immediate translation function that updates as well the quasi copies at the corresponding
cluster. For an immediate h, conservative and best-effort have the same result. Each WW [x]
operation is translated by h into a number of write operations of local quasi copies of x. Table 2
summarizes the semantics of operations.
How many and which core or quasi copies are actually read or written when a database operation
is issued on a data item depends on the coherency algorithm used, e.g, quorum consensus,
ROWA, [3]. Without loss of generality, we assume that there is only one quasi copy per cluster.
This assumption can be easily lifted but with significant complication in notation. Since all quasi
copies in a cluster have the same value, this single copy can be regarded as their representative.
Immediate translation and consistency. To handle integrity constraints besides replication,
in the case of an immediate translation function h, h should be defined such that the integrity
constraints between quasi copies in the same cluster are not violated. The following example is
Example 1 For simplicity consider only one cluster. Assume two data items x and y, related by
the integrity constraint x consistent database state x
and y \Gamma4, where the subscripts c, and q denote core and quasi copies respectively.
Consider the transaction program:
then
If the above program is executed as a strict transaction SW (x) SR(y) C, we get the database state
\Gamma4, in which the integrity constraint between the quasi copies
of x and y is violated. 2
The problem arises from the fact that quasi copies are updated to the current value of the
core copy without taking into consideration integrity constraints among them. Similar problems
occur when refreshing individual copies of a cache [1]. Possible solutions include: (1) Each time
a quasi copy is updated as a result of a strict write, the quasi copies of all data related to it by
some integrity constraint are also updated either after or prior to the execution of the transaction.
This update is done following a reconciliation procedure for merging core and quasi copies (as
in Section 4). In the above example, the core and quasi copies of x and y should have been
reconciled prior to the execution of the transaction, producing for instance the database state
2. Then, the execution of the transaction would result in the
database state x which is consistent. (2) If a strict transaction
updates a quasi copy at a cluster, its read operations are also mapped into reads of quasi copies
at this cluster. In cases of incompatibilities, a reconciliation procedure is again initiated having a
similar result as above. (3) Updating quasi copies is postponed by deferring any updates of quasi
copies that result from writes of the corresponding core copies. A log of weak writes resulting
from strict writes is kept. In this scenario, the execution of the transaction results in the database
state x which is consistent. The first two approaches force
an immediate reconciliation among copies, while the third approach defers this reconciliation and
is preferable in cases of low connectivity among clusters.
3 Weak Connectivity Operation
In this section, we provide serializability-based criteria, graph-based tests and a locking protocol
for correct executions that exploit weak connectivity. We use the terms read and write to refer to
the operations on data copies. When is an operation, the subscript j denotes that o belongs to
transaction j, while the subscript on a data copy identifies the cluster. A complete intracluster
schedule, IAS, is an observation of an interleaved execution of transactions in a given cluster
configuration, that includes (locally) committed weak transactions and (globally) committed strict
transactions. Formally,
be a set of transactions. A
(complete) intracluster schedule, IAS, over T is a pair (OP, ! a ) in which ! a is a partial ordering
relation such that
1.
2. For each T i and all operations op k , op l in T i , if op k ! i op l , then every operation in h(op k )
is related by ! a to every operation in h(op l ).
3. All pairs of conflicting operations are related by ! a , where two operations conflict if they
access the same copy and one of them is a write operation.
4. For all read operations, read j [x i ] there is at least one write k [x i ] such that write k [x i
read
5. If SW j [x] ! a SR j [x] and read j
y written by T j for which there is a y i 2 Cl i , where x i is a quasi copy when h is conservative
and any, quasi or core, copy when h is best effort.
Condition 1 states that the transaction managers translate each operation on a data item into
appropriate operations on data copies. Condition 2 states that the intracluster schedule preserves
the ordering stipulated by each transaction and Condition 3 that it also records the execution
order of conflicting operations. Condition 4 states that a transaction cannot read a copy unless
it has been previously initialized. Condition 5 states that if a transaction writes a data item x
before it reads x, then it must write to the same copy of x that it subsequently reads. Finally,
Condition 6 indicates that for a strict transaction, if a write is translated to a write on a data
copy at a cluster Cl i then all other writes of this transaction that may be possibly read by a weak
transaction must also write the corresponding copies at cluster Cl i . This condition is necessary
for ensuring that weak transactions do not see partial results of a strict transaction.
A read operation on a data item x reads-x-from a transaction T i if it reads (i.e., returns as the
value read) a copy of x written by T i and no other transaction writes this copy in between. We
say that a transaction T i has the same reads-from relationship in schedule S 1 as in schedule S 2 ,
if for any data item x, if T i reads-x-from T j in S 1 then it reads-x-from T j in S 2 . Given a schedule
S, the projection of S on strict transactions is the schedule obtained from S by deleting all weak
operations, and the projection of S on a cluster Cl k is the schedule obtained from S by deleting
all operations that do not access Cl k . A schedule is one-copy serializable if it is (view) equivalent
to a serial one-copy schedule [3].
3.1 Correctness Criterion
A correct concurrent execution of weak and strict transactions must maintain d-consistency among
clusters and strict consistency inside each cluster.
Definition 4 (IAS Weak Correctness) An intracluster schedule S IAS is weakly correct iff
1. all transactions have a consistent view, i.e., all constraints that can be evaluated using the
data read are valid,
2. there is a one copy serial schedule S such that (a) it has the same set of strict transactions
and operations, (b) strict transactions have the same reads-from relationship as in S IAS ,
and (c) the set of final writes on core copies is the same as in S IAS .
3. it maintains the d-degree relationship among copies.
Next, we discuss how to enforce the first two conditions. Protocols for bounding the divergence
among copies are outlined at the end of this section. The following theorem, defines correctness
in terms of equivalence to serial executions.
Theorem 1 Given that d-consistency is maintained, an intracluster schedule S is weakly correct
if its projection on strict transactions is one-copy serializable and each of its projections on a
cluster is conflict-equivalent to a serial schedule.
Proof: The first condition of the definition of correctness is guaranteed for strict transactions
from the requirement of one-copy serializability, since strict transaction get the same view as in
a one-copy serial schedule and read only core copies. For weak transactions at a cluster, the
condition is provided from the requirement of serializability of the projection of the schedule on
this cluster given that the projection of each transaction at the cluster maintains consistency
when executed alone. Thus it suffices to prove that such projections maintain consistency. This
trivially holds for weak transactions since they are local at each cluster. The condition also holds
for strict transactions, since if a strict transaction maintains d-consistency, then its projection on
any cluster also maintains d-consistency, as a consequence of condition (6) of the definition of an
IAS schedule. Finally, one copy serializability of the projection of strict transactions suffices to
guarantee 2(b) and 2(c) since strict transactions read only core copies and weak transactions do
not write core copies respectively. 2
Note, that intercluster constraints other than replication constraints among quasi copies of data
items at different sites may be violated. Weak transactions however are unaffected by such
violations, since they read only local data. Although, the above correctness criterion suffices to
ensure that each weak transaction gets a consistent view, it does not suffice to ensure that weak
transactions at different clusters get the same view, even in the absence of intercluster constraints.
The following example is illustrative.
Example 2 Assume two clusters that have both quasi and core
copies of the corresponding data items, and the following two strict transactions ST
In addition, at cluster Cl 1 we have the weak
transaction , and at cluster Cl 2 the weak transactions WT
. For simplicity, we do not show the transaction that
initializes all data copies. We consider an immediate and best effort h.
The execution of the above transactions produces the weakly correct schedule
The projection of S on strict transactions is: which is
equivalent to the 1SR schedule:
The projection of S on serializable as
The projection on
as
Thus, weak correctness does not guarantee that there is a serial schedule equivalent to the
intracluster schedule as a whole, that is including all weak and strict transactions. The following
is a stronger correctness criterion that ensures that weak transactions get the same consistent
view. Obviously, strong correctness implies weak correctness.
Definition 5 (IAS Strong Correctness) An intracluster schedule S is strongly correct iff there
is a serial schedule S S such that
1. S S is conflict-equivalent with S, and
2. In S S , (a) strict transactions have the same reads-from relationship, and (b) the set of final
writes on core copies is the same as in a one copy serial schedule.
Lemma 1 An intracluster schedule S is strongly correct if it is conflict-equivalent to a serial
schedule S S and its projection on strict transactions is equivalent to a one-copy serial schedule
S 1C such that the order of transactions in S S is consistent with the order of transactions in S 1C .
Proof: We need to prove that in S 1C strict transactions have the same read-from and final
writes as in S S which is straightforward since strict transaction only read data produced by strict
transactions and core copies are written only by strict transactions. 2
Since weak transactions do not directly conflict with weak transactions at other clusters, the
following is an equivalent statement of the above lemma,
Corollary 1 An intracluster schedule S is strongly correct if its projection on strict transactions
is equivalent to a one-copy serial schedule S 1C , and each of its projections on a cluster Cl i is
conflict-equivalent to a serial schedule S S i such that the order of transactions in S S i is consistent
with the order of transactions in S 1C .
If weak IAS correctness is used as the correctness criterion, then the transaction managers
at each cluster must only synchronize projections on that cluster. Global control is required
only for synchronizing strict transactions. Therefore, no control messages are necessary between
transaction managers at different clusters for synchronizing weak transactions. The proposed
schema is flexible, in that any coherency control method that guarantees one-copy serializability
(e.g., quorum consensus, primary copy) can be used for synchronizing core copies. The schema
reduces to one-copy serializability when only strict transactions are used.
3.2 The Serialization Graph
To determine whether an IAS schedule is correct, a modified serialization graph is used, that we
call the intracluster serialization graph (IASG) of the IAS schedule. To construct the IASG, a
replicated data serialization graph (SG) is built to represent conflicts between strict transactions.
An SG [3] is a serialization graph augmented with additional edges to take into account the fact
that operations on different copies of the same data item may also cause conflicts. Acyclicity of
the SG implies one-copy serializability of the corresponding schedule. Then, the SG is augmented
with additional edges to represent conflicts between weak transactions in the same cluster and
conflicts between weak and strict transactions. We add an edge between two transactions
An edge is called a dependency edge if it represents the fact that a
transaction reads a value produced by another transaction, and a precedence edge if it represents
the fact that a transaction reads a value that was later changed by another transaction.
It is easy to see that in the IASG there are no edges between weak transactions at different
clusters, since weak transactions at different clusters read different copies of a data item. In
addition:
be a weak transaction at cluster Cl i and ST a strict transaction. The IASG
graph induced by an IAS may include only the following edges between them:
ffl a dependency edge from ST to WT i
ffl a precedence edge from WT i to ST
Proof: Straightforward from the conflict relation, since the only conflicts between weak and strict
transactions are due to strict writes and weak reads of the same copy of a data item. 2
Theorem 2 Let S IAS be an intracluster schedule. If S IAS has an acyclic IASG then S IAS is
strongly correct.
Proof: When a graph is acyclic then each of its subgraphs is acyclic thus SG is acyclic. Acyclicity
of the SG implies one-copy serializability of the strict transactions since strict transactions read
only values written by strict transactions. Let T 1 , T 2 , . , T n be all transactions in S IAS . Thus
are the nodes of the IASG. Since IASG is acyclic it can be topologically sorted. Let
, . , T i n be a topological sort of the edges in IASG, then by a straightforward application
of the serializability theorem [3] S IAS is conflict equivalent to the serial schedule S
, .
. This order is consistent with the partial order induced by a topological sorting of the SG,
let S 1C be the corresponding serial schedule. Thus the order of transactions in S S is consistent
with the order of transactions in S 1C . 2
3.3 Protocols
Serializability. We distinguish between coherency and concurrency control protocols. Coherency
control ensures that all copies of a data item have the same value, here we must maintain this
property globally for core and locally for quasi copies. Concurrency control ensures the main-
tanance of the other integrity constraints, here the intracluster constraints. For coherency control,
we assume a generic quorum-based schema [3]. Each strict transaction reads q r core copies and
writes q w core copies per strict read and write operation. The values of q r , and q w for a data item
WR WW SR SW
x
x
x
WR WW SR SW
x
x
x
WR WW SR SW
x
x
x
(a)
WR WW SR SW
x
x
x
(b)
x
x
(c)
x
x
(d)

Figure

1: Lock compatibility matrices. A X entry indicates that the lock modes are compatible.
(a) Eventual and conservative h. (b) Eventual and best effort. (c) Immediate and conservative.
(d) Immediate and best effort h.
x are such that q r +qw ? n d , where n d is the number of available core copies of x. For concurrency
control we use strict two phase locking where each transaction releases its locks upon commitment
[3]. Weak transactions release their locks upon local commitment and strict transactions upon
global commitment. There are four lock modes (WR, WW , SR, SW ) corresponding to the four
data operations. Before the execution of each operation, the corresponding lock is requested. A
lock is granted only if the data copy is not locked in an incompatible lock mode. Figure 1 depicts
the compatibility of locks for various types of translation functions and is presented to demonstrate
the interference between operations on items. Differences in compatibility stem from the
fact the operations access different kinds of copies. The basic overhead imposed by these protocols
on the performance of weak transactions is caused by other weak transactions at the same cluster.
This overhead is small since weak transactions do not access the slow network. Strict transactions
block a weak transaction only when they access the same quasi copies. This interference is limited
and can be controlled, e.g., by letting in cases of disconnections, strict transactions access only
core copies and weak only quasi.
Bounded inconsistency among copies. At each cluster, the degree for each data item expresses
the divergence of the local quasi copy from the value of the core copy. This difference may
result either from globally uncommitted weak writes or from updates of core copies that have not
yet been reported at the cluster. As a consequence, the degree may be bounded either by limiting
the number of weak writes pending commitment or by controlling the h function. In Table 3, we
outline ways of maintaining d-consistency for different ways of defining d.
4 A Consistency Restoration Schema
After the execution of a number of weak and strict transactions, all core copies of a data item
have the same value, while its quasi copies may have as many different values as the number of
clusters. In this section, we first provide criteria for characterizing the correctness of protocols for
reconciling the different values of copies and then describe such a protocol. The exact point of
reconciliation depends on the application requirements and the distributed system characteristics.
Appropriately bound the number of weak transactions at
the distribution of weak transactions at each cluster must be
that operate on inconsistent data
can take
copies of each data item
Bound the number of clusters that can have divergent quasi
per data item
the maximum number of data items that
so that a strict write modifies the quasi copies at each
disconnected clusters since there is no way of notifying them
cluster at least after d updates. This canot be ensured for
for remote updates.
Bound the number of data items that can have quasi copies.
item not reflected at all copies
the maximum number of updates per data
adjusted.
Allow only weak writes with values inside the acceptable range
When d is defined as: Applicable Method
each cluster. In the case of a dynamic cluster reconfiguration,
the maximum number of transactions
a range of acceptable values a data item
have divergent copies
the maximum number of divergent copies

Table

3: Maintaining bounded inconsistency.
Reconciliation may be forced to keep the inconsistency inside the required limits. Alternatively, it
may be initiated periodically or on demand upon the occurrence of specific events. For example,
values may be reconciled when the network connection is reestablished, for instance when a
palmtop is plugged-back to the stationary network or a mobile host enters a cell that provides
good connectivity.
4.1 Correctness Criterion
Approaches to reconciling copies vary from purely syntactic to purely semantic ones [5]. We adopt
a purely syntactic application-independent approach. Our correctness criterion is based on the
following principle: if a core copy is written, and a strict transaction has read it, the value of the
core copy is the value selected. Otherwise, the value of any quasi copy may be chosen. Some
transactions that wrote a value that was not selected may need to be undone/compensated
or redone. This may lead to roll-back of other weak transactions that have read values written
by this transaction. However, transaction roll-back is limited and never crosses the boundaries of
a cluster.
A (complete) intercluster schedule, IES, models execution after reconciliation, where global
transaction should become aware of local writes, i.e., local transaction become globally committed.
In the schedule, we must add additional conflicts between weak and strict operations.
Definition 6 (intercluster schedule) An intercluster schedule (IES) S IES based on an intracluster
schedule a ) is a pair (OP 0
1. OP 0
2. for any op i and op j ffl OP 0
and in addition:
3. for each pair of weak write WW i [x] and strict read SR j [x] operations either WW
4. for each pair of weak write WW i [x] and strict write SW j [x] operations either WW
We extend the reads-from relationship for strict transactions as follows. A strict read operation
on a data item x reads-x-from from a transaction T i in an IES schedule if it reads a copy of x
and T i has written this copy or a quasi copy of x and no other transaction wrote this or the quasi
copy in between.
We accept as many weak writes as possible without violating the one-copy serializability
of strict transactions. Specifically, a weak write is accepted only when it does not violate the
extended read-from relationship for strict transactions.
Definition 7 (IES Correctness) An intercluster schedule is correct iff
1. it is based on a correct IAS schedule S IAS , and
2. the reads-from relationship for strict transactions is the same with their reads-from relation
in the S IAS .
4.2 The Serialization Graph
To determine correct IES schedules we define a modified serialization graph that we call the
intercluster serialization graph (IESG). To construct the IESG, we augment the serialization
graph IASG of the underlying intracluster schedule. To force conflicts among weak and strict
transactions that read different copies of the same data item, we induce
ffl first, a write order as follows: if T i weak writes and T k strict writes any copy of an item x
then either T
ffl then, a strict read order as follows: if a strict transaction ST j reads-x-from ST i in S IAS and
a weak transaction WT follows ST i then we add an edge ST j !WT .
Theorem 3 Let S IES be an IES schedule based on an IAS schedule S IAS . If S IES has an acyclic
IESG then S IES is correct.
Proof: Clearly, if the IESG graph is acyclic, the corresponding graph for the IAS is acyclic
(since to get the IESG we only add edges to the IASG). We will show that if the graph is acyclic
then the read-from relation for strict transactions in the intercluster schedule S IES is the same
as in the underlying intracluster schedule S IAS . Assume that ST j reads-x-from ST i in S IAS .
Assume for the purposes of contradiction, that ST j reads-x-from a weak
transaction WT . Then WT writes x in S IES and since ST i also writes x either (a) ST
or (b) WT ! ST i . In case (a), from the definition of the IESG, we get ST j ! WT , which is
a contradiction since ST j reads-x-from WT . In case (b) WT ! ST i , that is WT precedes ST i
which precedes ST j , which again contradicts the assumption that ST j reads-x-from WT . 2
Until there are no cycles in the IESG
rollback a weak transaction WT in the cycle
unroll all exact transactions related with a dependency edge to WT
Per data item
If the final write is on a core copy
propagate this value to all quasi copies
else
choose a value of a quasi copy
propagate this value to all core and quasi copies

Table

4: The reconciliation steps.
4.3 Protocol
To get a correct schedule we need to break potential cycles in the IES graph. Since to construct
the IESG we start from an acyclic graph and add edges between a weak and a strict transaction,
there is always at least one weak transaction in each cycle. We rollback such weak transactions.
Undoing a transaction may result in cascading aborts, of transactions that have read the values
written by the transaction; that is, transactions that are related with a dependency edge to the
transaction undone. Since weak transactions write only quasi copies in a cluster, and since only
transactions in the same cluster can read these quasi copies we get the following lemma:
Only weak transactions in the same cluster read values written by weak transactions
in that cluster.
The above lemma ensures that only weak transactions in the same cluster are affected when
a weak transaction is aborted to resolve conflicts in an intercluster schedule. In practice, fewer
transactions ever need to be aborted. In particular, we need to abort only weak transactions whose
output depends on the exact values of the data items they read. We call these transactions exact.
Most weak transactions are not exact, since by definition, weak transactions are transactions that
read local d-consistent data. Thus, even if the value they read was produced by a transaction that
was later aborted, this value was inside an acceptable range of inconsistency and this is probably
sufficient to guarantee their correctness.
Detecting cycles in the IESG can be hard. The difficulties raise from the fact that between
transactions that wrote a data item an edge can have any direction, thus resulting in polygraphs
[20]. Polynomial tests for acyclicity are possible, if we made the assumption that transactions
read a data item before writing it. Then, to get the IES graph from the IAS graph we need only:
ffl induce a read order as follows: if a strict transaction ST reads an item that was written by
a weak transaction WT we add a precedence edge SR !WT

Table

4 outlines the reconciliation steps.
In the proposed hybrid schema, weak and strict transactions coexist. Weak transactions let users
process local data thus avoiding the overhead of long network accesses. Strict transactions need
access to the network to guarantee consistency of their updates. Weak reads provide users with
the choice of reading an approximately accurate value of a datum in particular in cases of total
or partial disconnections. This value is appropriate for a variety of applications that do not
require exact values. Such applications include gathering information for statistical purposes or
making high-level decisions and reasoning in expert systems that can tolerate bounded uncertainty
in input data. Weak writes allow users to update local data without confirming these updates
immediately. Update validation is delayed till clusters are connected. Delayed updates can be
performed during periods of low network activity to reduce demand on the peaks. Furthermore,
grouping together weak updates and transmitting them as a block rather than one at a time
can improve bandwidth usage. For example, a salesperson can locally update many data items,
till these updates are finally confirmed, when the machine is plugged back to the network at
the end of the day. However, since weak writes may not be finally accepted, they must be used
only when compensating transactions are available, or when the likelihood of conflicts is very
low. For example, users can employ weak transactions to update mostly private data and strict
transactions to update frequently used, heavily shared data.
The cluster configuration is dynamic. Clusters of data may be explicitly created or merged
upon a forthcoming disconnection or connection of the associated mobile client. To accommodate
migrating locality, a mobile host may move to a different cluster upon entering a new support
environment. Besides defining clusters based on the physical location of data, other definitions are
also possible. Clusters may be defined based on the semantics of data or applications. Information
about access patterns, for instance in the form of a user's profile that includes data describing
the user's typical behavior, may be utilized in determining clusters. Some examples follow.
Example 1: Cooperative Environment. Consider the case of users working on a common
project using mobile hosts. Groups are formed that consist of users who work on similar topics of
the project. Clusters correspond to data used by people in the same group who need to maintain
consistency among their interactions. We consider data that are most frequently accessed by a
group as data belonging to this group. At each group, the copies of data items belonging to the
group are core copies, while the copies of data items belonging to other groups are quasi. A data
item may belong to more than one group if more than one group frequently accesses it. In this
case, core copies of that data item exist in all such clusters. In each cluster, operations on items
that do not belong to the group are weak, while operations on data that belong to the group are
strict. Weak updates on a data item are accepted only when they do not conflict with updates
by the owners of that data item.
Example 2: Caching. Clustering can be used to model caching in a client/server architecture.
In such a setting, a mobile host acts as a client interacting with a server at a fixed host. Data
are cached at the client for performance and availability. The cached data are considered quasi
copies. The data at the fixed host are core copies. Transactions initiated by the server are always
strict. Transactions initiated by the client that invoke updates are always weak while read-only
client transactions can be strict if strict consistency is required. At reconciliation, weak writes
are accepted only if they do not conflict with strict transactions at the server. The frequency of
reconciliation depends on the user consistency requirements and on networking conditions.
Example 3: Location Data. In mobile computing, data representing the location of a mobile
user are fast-changing. Such data are frequently accessed to locate a host. Thus, location data
must be replicated at many sites to reduce the overhead of searching. Most of the location copies
should be considered quasi. Only a few core copies are always updated to reflect changes in
location.
6 Quantitative Evaluation of Weak Consistency
To quantify the improvement in performance attained by sacrificing strict consistency in weakly
connected environments and to understand the interplay among the various parameters, we have
developed an analytical model. The analysis follows an iteration-based methodology for coupling
standard hardware resource and data contention as in [35]. Data contention is the result of
concurrency and coherency control. Resources include the network and the processing units. We
generalize previous results to take into account (a) nonuniform access of data, that takes into
consideration hotspots and the changing locality, (b) weak and strict transaction types, and (c)
various forms of data access, as indicated by the compatibility matrix of Table 1. An innovative
feature of the analysis is the employment of a vacation system to model disconnections of the
wireless medium. The performance parameters under consideration are the system throughput,
the number of messages sent, and the response time of weak and strict transactions. The study
is performed for a range of networking conditions, that is for different values of bandwidth and
for varying disconnection intervals.
6.1 Performance Model
We assume a cluster configuration with n clusters and a Poisson arrival rate for both queries and
updates. Let - q and - u respectively be the average arrival rate of queries and updates on data
items initiated at each cluster. We assume fixed length transactions with N operations on data
items, of which are queries and N are updates. Thus
the transaction rate, i.e., the rate of transactions initiated at each cluster, is
Let c be the consistency factor of the application under consideration, that is c is the fraction
of the arrived operations that are strict. To model hotspots, we divide data at each cluster into hot
and cold data sets. Let D be the number of data items per cluster, D c of which are cold and D h
hot. To capture locality, we assume that a fraction o of transactions exhibit locality, that is they
access data from the hot set with probability h and data from the cold set with probability
The remaining transactions access hot and cold data uniformly. Due to mobility, a transaction
may move to a different cluster and the data it accesses may no longer belong to the hot data of
the new cluster. This can be modeled by letting diminish. Locality is taken advantage by the
replication schema, by assuming that the probability that a hot data has a core copy at a cluster
is l, and that a cold data has a core copy is l 0 , where normally, l l be the probability
that an operation at a cluster accesses a data item for which there is a core copy at the cluster,
For simplicity, we assume that there is one quasi copy of each data item at each cluster. Let
q r be the read and q w the write quorum, and N S the mean number of operations on data copies
per strict transaction. The transaction model consists of nL states, where nL is the random
variable of items accessed by the transaction and NL its mean. Without loss of generality, we
assume that NL is equal to the number of operations. The transaction has an initial setup phase,
state 0. Then, it progress to states in that order. If successful, at the end of state nL
the transaction enters into the commit phase at state nL+1 . The transaction response time r trans
can be expressed as
where nw is the number of lock waits during the run of the transaction, r w j is the waiting time for
the jth lock contention, r E is the sum of the execution times in states excluding lock
waiting times, r INLP is the execution time in state 0, and t commit is the commit time to reflect
the updates in the database.
Resource contention analysis
We model clusters as M/G/1 systems. The average service time for the various types of requests,
all exponentially distributed, can be determined from the following parameters: t q processing
time for a query on a data copy, t u time to install an update on a data copy, t b overhead time
to propagate an update or query to another cluster. In each M/G/1 server, all requests are
processed with the same priority on a first-come, first-served basis. Clusters are connected and
later reconnected. To capture disconnections, we model each connection among two clusters as
an M/M/1 system with vacations. A vacation system is a system in which the server becomes
unavailable for occasional intervals of time. If W is the available bandwidth between two clusters
and if we assume exponentially distributed packet lengths for messages with average size m then
the service rate s r is equal to W=m. Let t r be the network transmission time.
Number of Messages. The total number of messages transmitted per second amongst clusters is:
The first term corresponds to query traffic; the second to update traffic.
Execution Time. For simplicity, we ignore the communication overhead inside a cluster, assuming
either that each cluster consists of a single node or that the communication among the nodes inside
a cluster is relatively fast. Without taking into account data contention, the average response
time for a weak read on a data item is R w
and for a weak update R w
w is the average wait time at each cluster. Let b r be 0 if q
strict read on a data item R s
and for a strict write R s
+w). The computation of w is given in the Appendix.
Average Transmission Time. The average transmission time t r equals the service time plus the
at each network link, t . The arrival rate - r at each link is Poisson
with mean M=(n(n \Gamma 1)). The computation of w r is given in the Appendix.
Throughput. The transaction throughput, i.e., input rate, is bounded by: (a) the processing time
at each cluster, (since - E[x], where - is the arrival rate of all requests at each cluster and E[x]
is the mean service time) (b) the available bandwidth, (since - r - t r ), and (c) the disconnection
intervals, (since - r - E[v], where E[v] is the mean duration of a disconnection).
Data contention analysis
We assume an eventual and best effort h. In the following, op stands for one of WR, WW , SR,
SW . Using formula (A) the response time for strict and weak transactions is:
strict +N q P q R SR +N u P u R SW
where P op is the probability that a transaction contents for an op operation on a data copy, and
R op is the average time spent waiting to get an op lock given that lock contention occurs. P q and
P u are respectively the probability that at least one operation on a data copy per strict read or
conflicts. Specifically, P An outline of the
estimation of P op and R op is given in the Appendix. For a detailed description of the model see
[21].
6.2 Performance Evaluation
The following performance results show how the percentage of weak and strict transactions can be
effectively tuned based on the prevailing networking conditions such as the available bandwidth
and the duration of disconnections to attain the desired throughput and latency. Table 5 depicts
some realistic values for the input parameters. The bandwidth depends on the type of technology
used, for infrared a typical value is 1 Mbps, for packet radio 2 Mbps, and for cellular phone 9-14
Kbps [7].
Parameter Description Value
n number of clusters 5
- q query arrival rate 12 queries/sec
- u update arrival rate 3 updates/sec
c consistency factor ranges from 0 to 1
q r read quorum ranges from 1 to n
quorum ranges from 1 to n
local transactions accessing hot data ranges from 0 to 1
h probability that a local transaction access hot data ranges from 0 to 1
l probability a hot data has a core copy at a given cluster ranges from 0 to 1
l 0 probability a cold data has a core copy at a given cluster ranges from 0 to 1
t u processing time for an update 0.02 sec
processing time for a query 0.005 sec
propagation overhead 0.00007 sec
vacation interval ranges
available bandwidth ranges
average size of a message 512 bits
c number of cold data items per cluster 800
D h number of hot data items per cluster 200
average number of operations per transaction 10

Table

5: Input parameters.18220
c
Consistency factor
Maximum
allowable
input
rate
for
c
Maximum
allowable
input
rate
for
updates
Consistency factor

Figure

2: Maximum allowable input rate of updates for various values of the consistency factor.
(left) Limits imposed by the processing rate at each cluster (- E[x]). (right) Limits imposed
by bandwidth restrictions (- r - t r ).
c
Consistency factor
Maximum
allowable
rate
for
updates
c
Maximum
allowable
rate
for
updates
Consistency factor

Figure

3: Maximum allowable input rate for updates for various values of the consistency factor.
Limits imposed by disconnections and their duration (- r - E[v]).
System throughput. Figures 2(left), 2(right), and 3 show how the maximum transaction input,
or system throughput, is bounded by the processing time, the available bandwidth, and the
disconnection intervals respectively. We assume that queries are four times more common than
updates As shown in Figure 2(left), the allowable input rate when all transactions are
almost double the rate when all transactions are strict 1). This is the result
of the increase in the workload with c caused by the fact that strict operations on data items may
be translated into more than one operation on data copies. The percentage of weak transactions
can be effectively tuned to attain the desired throughput based on the networking conditions such
as the duration of disconnections and the available bandwidth. As indicated in Figure 2(right), to
get for instance, the same throughput with 200bps as with 1000bps and must lower the
consistency factor below 0.1. The duration of disconnections may vary from seconds when they
are caused by hand offs ([17]) to minutes for instance when they are voluntary. Figure 3 depicts
the effect of the duration of a disconnection on the system throughput for both short durations

Figure

and longer ones (Figure 3(right)). For long disconnections (Figure 3(right)), only
a very small percentage of strict transactions can be initiated at disconnected sites. To keep the
throughput comparable to that for shorter disconnections (Figure 3(left)) the consistency factor
must drop at around three orders of magnitude.
Communication cost. We estimate the communication cost by the number of messages sent.
The number of messages depends on the following parameters of the replication schema: (1)
the consistency factor c, (2) the data distribution l for hot and l 0 for cold data, (3) the locality
factor and (4) the quorums, q r and q w , of the coherency schema. We assume a ROWA schema
not otherwise stated. As shown in Figure 4(left) the number of messages
increases linearly with the consistency factor. As expected the number of messages decreases with
the percentage of transactions that access hot data, since then local copies are more frequently
available. To balance the increase in the communication cost caused by diminishing locality there
may be a need to appropriately decrease the consistency factor (Figure 4(middle)). The number of
Number
of
messages
Consistency factor (c)20601000
Number
of
messages
Locality (o)
Number
of
messages
Relication of hot copies (l)

Figure

4: Number of messages. (left) For various values of c. (middle) With locality. (right) For
different replication of hot core copies. Unless otherwise stated
and
Number
of
messages
Replication of cold core data (l1)50150250
Number
of
messages
Read quorum
equal rates
4 times more queries
4 times more updates

Figure

5: Number of messages. (left) For different replication of cold core copies. (right) For
different values of the read quorum. Unless otherwise stated
and
messages decreases when the replication factor of hot core copies increases (Figure 4(right)). The
decrease is more evident since most operations are queries and the coherency schema is ROWA,
thus for most operations no messages are sent. The decrease is more rapid when transactions
exhibit locality, that is when they access hot data more frequently. On the contrary, the number
of messages increases with the replication factor of cold core copies because of additional writes
caused by coherency control (Figure 5(left)). Finally, the relationship between the read quorum
and the number of messages depends on the relative number of queries and updates (Figure
5(right)).
Transaction response time. The response time for weak and strict transactions for various
values of c is depicted in Figure 6. The larger values of response times are for 200bps bandwidth,
while faster response times are the result of higher network availability set at 2Mbps. The values
for the other input parameters are as indicated in Table 5. The additional parameters are set as
follows: (1) the locality parameters are 0:9, (2) the data replication parameters
are l the disconnection parameters are and the vacation intervals are
exponentially distributed with sec, to model disconnection intervals that correspond
to short involuntary disconnections such as those caused by hand offs [17], (4) the coherency
Response
time
(in
secs)
Consistency factor c
strict - 200bps
strict 2Mbps

Figure

Comparison of the response times for weak and strict transactions for various values of
the consistency factor.
Consistency
Time
(sec)
Response time
Processing time
Lock wait
Consistency factor0.050.150.25Time
(sec)
Response time
Processing time
Lock wait

Figure

7: (Left) Response time distribution for strict transactions. (right) Response time distribution
for weak transactions.
control schema is ROWA. The latency of weak transactions is about 50 times greater than that
of strict transactions. However, there is a trade-off involved in using weak transactions, since
updates may be aborted later. The time to propagate updates during reconciliation is not
counted. As c increases the response time for both weak and strict transactions increase since
more conflicts occur. The increase is more dramatic for smaller values of bandwidth. Figure 7(left)
and (right) show the response time distribution for strict and weak transactions respectively for
2Mbps bandwidth. For strict transactions, the most important overhead is network transmission.
All times increase as c increases. For weak transactions, the increase in the response time is the
result of longer waits for acquiring locks, since weak transactions that want to read up-to-date
data conflict with strict transactions that write them.
7 Reconciliation Cost
We provide an estimation of the cost of restoring consistency in terms of the number of weak
transactions that need to be rolled back. We focus on conflicts among strict and weak transactions
for which we have outlined a reconciliation protocol and do not consider conflicts among weak
transactions at different clusters. A similar analysis is applicable to this case also.
A weak transaction is rolled back if its writes conflict with a read of a strict transaction
that follows it in the IASG. Let P 1 be the probability that a weak transaction WT writes a
data item read by a strict transaction ST and P 2 be the probability that ST follows WT in the
serialization graph. Then the probability is the probability that a weak transaction is
rolled back. Assume that reconciliation occurs after N r transactions r of which are strict
are weak. For simplicity we assume uniform access distribution. Although it
is reasonable to assume that granule access requests from different transactions are independent,
independence cannot hold within a transaction if a transaction's granule accesses are distinct.
However, if the probability of accessing any particular granule is small, e.g., when the number
of granules is large and the access distribution is uniform, this approximation should be very
accurate. Then
Let p KL be the probability that in the IASG there is an edge from a given transaction of
type K to a given transaction of type L. Let p 0
be the probability that in the IASG
with m strict and m 0 weak transactions there is an edge from a given transaction of type K to
any transaction of type L. The formulas for p KL and p 0
are given in the Appendix.
be the probability that there is an acyclic path of length i, i.e., a path with
distinct nodes, from a given weak transaction to a given strict transaction in a IASG with m
strict and m 0 weak transactions. Then
The values of p(k; k can be computed from the following recursive relations:
where the first term is the probability of a path whose first edge is between weak transactions,
the second of a path whose first edge is between a weak and a strict transaction and includes at
least one more weak transaction and the last of a path whose first edge is between a weak and
a strict transaction and does not include any other weak transactions. Thus the actual number
of weak transaction that need to be undone or compensated because their writes cannot become
Probability
of
abort
(times
Consistency factor c
trans
trans
trans
trans
Probability
of
abort
(times
Number of transactions

Figure

8: Probability of abort for 3000 data items.0.010.030.050.07
Probability
of
abort
(times
Consistency factor c
1000 items
2000 items
3000 items
4000 items
5000 items0.010.030.050.07
1000 1500 2000 2500 3000 3500 4000 4500 5000
Probability
of
abort
(times
Number of data items

Figure

9: Probability of abort for
permanent is N We also need to roll back all exact weak transactions that read a
value written by a transaction aborted. Let e be the percentage of weak transactions that are
exact, then N roll

Figure

8(left) depicts the probability that a weak transaction cannot be accepted because
of a conflict with a strict transaction for reconciliation events occurring after varying number
of transactions and for different values of the consistency factor. Figure 9(left) shows the same
probability for varying database sizes. More accurate estimations can be achieved for specific
applications for which the access patterns of the transactions are known. These results can be
used to determine an appropriate reconciliation point, to balance the frequency of reconciliations
and the number of weak transactions that may be aborted. For instance, for a given c = 0:5, to
keep the probability below a threshold of say 0.00003, reconciliation events must take place as
often as every 85 transactions (Figure 8(right)).
8 Related Work
One-copy serializability [3] hides from the user the fact that there can be multiple copies of a
data item and ensures strict consistency. Whereas one-copy serializability may be an acceptable
criterion for strict transactions, it is too restrictive for applications that tolerate bounded inconsistency
and causes unbearable overheads in cases of weak connectivity. The weak transaction
model described in this paper was first introduced in [24] while preliminary performance results
were presented in [22].
Network Partitioning. The partitioning of a database into clusters resembles the network partition
problem [5], where site or link failures fragment a network of database sites into isolated
subnetworks called partitions. Clustering is conceptually different than partitioning in that it
is electively done to increase performance. Whereas all partitions are isolated, clusters may be
weakly connected. Clients may operate as physically disconnected even while remaining physically
connected. Strategies for network partition face similar competing goals of availability and
correctness. These strategies range from optimistic, where any transaction is allowed to be executed
in any partition, to pessimistic, where transactions in a partition are restricted by making
worst-case assumptions about what transactions at other partitions are doing. Our model offers a
hybrid approach. Strict transactions may be performed only if one-copy serializability is ensured
(in a pessimistic manner). Weak transactions may be performed locally (in an optimistic manner).
To merge updates performed by weak transactions we adopt a purely syntactic approach.
Read-only Transactions. Read-only transactions do not modify the database state, thus their
execution cannot lead to inconsistent database states. In our framework read-only transactions
with weaker consistency requirements are considered a special case of weak transactions.
In [8] two requirements for read-only transactions were introduced: consistency and currency
requirements. Consistency requirements specify the degree of consistency needed by a read-only
transaction. In this framework, a read-only transaction may have: (a) no consistency require-
ments; (b) weak consistency requirements if it requires a consistent view (that is, if all consistency
constraints that can be fully evaluated with the data read by the transaction must be true); or (c)
strong consistency requirements if the schedule of all update transactions together with all other
strong consistency queries must be consistent. While in our model strict read-only transactions
always have strong consistency requirements, weak read-only transactions can be tailored to have
any of the above degrees based on the criterion used for IAS correctness. Weak read-only transactions
may have no consistency requirement if they are ignored from the IAS schedule, weak
consistency if they are part of a weakly correct IAS schedule, and strong consistency if they are
part of a strongly correct schedule. The currency requirements specify what update transactions
should be reflected by the data read. In terms of currency requirements, strict read-only transactions
read the most-up-to-date data item available (i.e. committed). Weak read-only transactions
may read older versions of data, depending on the definition of the d-degree.
Epsilon-serializability (ESR) [25] allows temporary and bounded inconsistencies in copies to
be seen by queries during the period among the asynchronous updates of the various copies of a
data item. Read-only transactions in this framework are similar to weak read-only transactions
with no consistency requirements. ESR bounds inconsistency directly by bounding the number
of updates. In [34] a generalization of ESR was proposed for high-level type specific operations
on abstract data types. In contrast, our approach deals with low-level read and write operations.
In an N-ignorant system, a transaction need not see the results of at most N prior transactions
that it would have seen if the execution had been serial [13]. Strict transactions are 0-ignorant
and weak transactions are 0-ignorant of other weak transactions at the same cluster. Weak
transactions are ignorant of strict and weak transactions at other clusters. The techniques of
supporting N-ignorance can be incorporating in the proposed model to define d as the ignorance
factor N of weak transactions.
Mobile Database Systems. The effect of mobility on replication schemas is discussed in [2].
The need for the management of cached copies to be tuned according to the available bandwidth
and the currency requirements of the applications is stressed. In this respect, d-degree consistency
and weak transactions realize both of the above requirements. The restrictive nature of one-copy
serializability for mobile applications is also pointed out in [14] and a more relaxed criterion is
proposed. This criterion although sufficient for aggregate data is not appropriate for general
applications and distinguishable data. Furthermore, the criterion does not support any form of
adaptability to the current network conditions.
The Bayou system [6, 31] is a platform of replicated highly available, variable-consistency,
mobile databases on which to build collaborative applications. A read-any/write-any weakly-consistent
replication schema is employed. Each Bayou database has one distinguished server,
the primary, which is responsible for committing writes. The other secondary servers tentatively
accept writes and propagate them towards the primary. Each server maintains two views of
the database: a copy that only reflects committed data and another full copy that also reflects
tentative writes currently known to the server. Applications may choose between committed
and tentative data. Tentative data are similar to our quasi data, and committed data similar
to core data. Correctness is defined in terms of session, rather than on serializability as in the
proposed model. A session is an abstraction for the sequence of read and writes of an application.
Four types of guarantees can be requested per session: (a) read your writes, (b) monotonic
reads (successive reads reflect a non-decreasing set of writes), (c) writes follow read (writes are
propagated after reads on which they depend), and (d) monotonic writes (writes are propagated
after writes that logically precede them). To reconcile copies, Bayou adopts an application based
approach as opposed to the syntactic based procedure used here. The detection mechanism is
based on dependency checks, and the per-write conflict resolution method is based on client-
provided merge procedures [32].
Mobile File Systems. Coda [12] treats disconnections as network partitions and follows an
optimistic strategy. An elaborate reconciliation algorithm is used for merging file updates after the
sites are connected to the fixed network. No degrees of consistency are defined and no transaction
support is provided. [15, 16] extend Coda with a new transaction service called isolation-only
transactions (IOT). IOTs are sequences of file accesses that unlike traditional transactions have
only the isolation property. IOTs do not guarantee failure atomicity and only conditionally
guarantee permanence. IOTs are similar to weak transactions.
Methods for refining consistency semantics of cached files to allow a mobile client to select
a mode appropriate for the current networking conditions are discussed in [9], The proposed
techniques are delayed writes, optimistic replication and failing instead of fetching data in cases
of cache misses.
The idea of using different kinds of operations to access data is also adopted in [28, 29],
where a weak read operation was added to a file service interface. The semantics of operations
are different in that no weak write is provided and since there is no transaction support, the
correctness criterion is not based on one-copy serializability.
9

Summary

To overcome bandwidth, cost, and latency barriers, clients of mobile information systems switch
between connected and disconnected modes of operation. In this paper, we propose a replication
schema appropriate for such operation. Data located at strongly connected sites are grouped in
clusters. Bounded inconsistency is defined by requiring mutual consistency among copies located
at the same cluster and controlled deviation among copies at different clusters. The database
interface is extended with weak operations. Weak operations query local, potentially inconsistent
copies and perform tentative updates. The usual operations, called strict in this framework in
contradistinction to weak, are also supported. Strict operations access consistent data and perform
permanent updates. Disconnected operation is supported by using only weak operations. To
accommodate weak connectivity, a mobile client selects an appropriate combination of weak and
strict transactions based on the consistency requirements of its applications and on the prevailing
networking conditions. Adjusting the degree of divergence provides an additional support for
adaptability.
The idea of providing weak operations can be applied to other type of constraints besides
replication. Such constraints can be vertical and horizontal partitions or arithmetic constraints
[27]. Another way of defining the semantics of weak operations is by exploiting the semantics of
data. In [33], data are fragmented and later merged based on their object semantics.



--R

Data Caching Issues in an Information Retrieval System.
Replicated Data Management in Mobile Environments: Anything New Under the Sun?
Concurrency Control and Recovery in Database Systems.
Data Networks.
Consistency in Partitioned Networks.
The Bayou Architecture: Support for Data Sharing Among Mobile Users.
The Challenges of Mobile Computing.

Communication and Consistency in Mobile File Systems.
Data Replication for Mobile Computers.
Mobile Computing: Challenges in Data Management.
Disconnected Operation in the Coda File System.
Bounded Ingnorance: A Technique for Increasing Concurrency in a Replicated System.
Protocols for Maintaining Inventory Databases and User Profiles in Mobile Sales Applications.

Improving Data Consistency in Mobile Computing Using Isolation-Only Transactions
Cellular Essentials for Wireless Data Transmission.
Exploiting Weak Connectivity for Mobile File Access.
A Programming Interface for Application-Aware Adaptation in Mobile Computing
The Theory of Database Concurrency Control.
Transaction Management in Mobile Heterogeneous Environments.
A Replication Schema to Support Weak Connectivity in Mobile Information Systems.
Building Information Systems for Mobile Environments.
Maintaining Consistency of Data in Mobile Distributed Environments.
Replica Control in Distributed Systems: An Asynchronous Approach.
Experience with Disconnected Operation in a Mobile Computing Environment.
Management of Interdependent Data: Specifying Dependency and Consistency Requirements.
Service Interface and Replica Management Algorithm for Mobile File System Clients.
An Efficient Variable-Consistency Replicated File Service
Queueing Analysis
Session Guarantees for Weakly Consistent Replicated Data.
Managing Update Conflicts in Bayou
Supporting Semantics-Based Transaction Processing in Mobile Database Applications
Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems.
On the Analytical Modeling of Database Concurrency Control.
--TR

--CTR
Luis Veiga , Paulo Ferreira, PoliPer: policies for mobile and pervasive environments, Proceedings of the 3rd workshop on Adaptive and reflective middleware, p.238-243, October 19-19, 2004, Toronto, Ontario, Canada
Paolo Bellavista , Antonio Corradi , Rebecca Montanari , Cesare Stefanelli, Dynamic Binding in Mobile Applications: A Middleware Approach, IEEE Internet Computing, v.7 n.2, p.34-42, March
Joanne Holliday , Divyakant Agrawal , Amr El Abbadi, Disconnection modes for mobile databases, Wireless Networks, v.8 n.4, p.391-402, July 2002
Victor C. S. Lee , Kwok-Wa Lam , Sang H. Son , Eddie Y. M. Chan, On Transaction Processing with Partial Validation and Timestamp Ordering in Mobile Broadcast Environments, IEEE Transactions on Computers, v.51 n.10, p.1196-1211, October 2002
Wen-Chih Peng , Ming-Syan Chen, Design and Performance Studies of an Adaptive Cache Retrieval Scheme in a Mobile Computing Environment, IEEE Transactions on Mobile Computing, v.4 n.1, p.29-40, January 2005
Nadia Nouali , Anne Doucet , Habiba Drias, A two-phase commit protocol for mobile wireless environment, Proceedings of the sixteenth Australasian database conference, p.135-143, January 01, 2005, Newcastle, Australia
Guy Bernard , Jalel Ben-othman , Luc Bouganim , Grme Canals , Sophie Chabridon , Bruno Defude , Jean Ferri , Stphane Ganarski , Rachid Guerraoui , Pascal Molli , Philippe Pucheral , Claudia Roncancio , Patricia Serrano-Alvarado , Patrick Valduriez, Mobile databases: a selection of open issues and research directions, ACM SIGMOD Record, v.33 n.2, June 2004
Wanlei Zhou , Li Wang , Weijia Jia, An analysis of update ordering in distributed replication systems, Future Generation Computer Systems, v.20 n.4, p.565-590, May 2004
Paolo Bellavista , Antonio Corradi , Rebecca Montanari , Cesare Stefanelli, A mobile computing middleware for location- and context-aware internet data services, ACM Transactions on Internet Technology (TOIT), v.6 n.4, p.356-380, November 2006
Patricia Serrano-Alvarado , Claudia Roncancio , Michel Adiba, A Survey of Mobile Transactions, Distributed and Parallel Databases, v.16 n.2, p.193-230, September 2004
Srikumar Venugopal , Rajkumar Buyya , Kotagiri Ramamohanarao, A taxonomy of Data Grids for distributed data sharing, management, and processing, ACM Computing Surveys (CSUR), v.38 n.1, p.3-es, 2006
concurrency control;mobile computing;replication;disconnected operation;adaptability;consistency;transaction management