Scaling replica maintenance in intermittently synchronized mobile databases.
To avoid the high cost of continuous connectivity, a class of mobile applications employs replicas of shared data that are periodically updated. Updates to these replicas are typically performed on a client-by-client basis--that is, the server individually computes and transmits updates to each client--limiting scalability. By basing updates on replica groups (instead of clients), however, update generation complexity is no longer bound by client population size. Clients then download updates of pertinent groups. Proper group design reduces redundancies in server processing, disk usage and bandwidth usage, and dimininishes the tie between the complexity of updating replicas and the size of the client population. In this paper, we expand on previous work done on group design, include a detailed I/O cost model for update generation, and propose a heuristic-based greedy algorithm for group computation. Experimental results with an adapted commercial replication system demonstrate a significant increase in overall scalability over the client-centric approach.
INTRODUCTION
Intermittently Synchronized Database (ISDB) systems allow
mobile data sharing applications to reduce cost by forgoing
continuous connectivity. To allow sharing, a dedicated
update server maintains the primary copy (global database)
of all data held by mobile clients while each client maintains
its own replica of some subset of the global database
schema. The update server maintains the primary copy of
the global database by receiving updates from the clients
and distributing them on demand to the clients based on
knowledge of their subscriptions. (See Figure 1.) Typically,
the server generates update les for clients on an individual
basis: the server scans through a set of updates, and for
each client and update, decides if the client should receive
the update. In this way, each client receives a customized
update le containing only the relevant data. This technique
is simple and straightforward but requires the server to do
work in direct proportion to the number of clients, limiting
the scalability of the system and resulting in greater time to
maintain local replicas.
In this paper, we build on previous work that proposed organizing
updates into groups shared by clients [5]. Using this
approach, the server manages update processing for a limited
and controllable number of groups, irrespective of the
number of clients. Instead of receiving updates customized
for its specic needs, each client accesses the updates for
the groups containing data it needs. The group-based approach
results in better server scalability because the work
of the server is decoupled from the actual number of clients
maintained [5, 11]. For example, a salesperson may enter
her o-ce in the morning before visiting customers and load
sales data from the server onto her laptop. Throughout the
day, the salesperson updates her local copy of the sales data
regardless of the connectivity with the server. When conditions
permit it, a reliable connection can be established with
the server to synchronize local data using updates generated
for the proper groups. Connectivity options include conventional
wireless modems, high speed wireless LANs (e.g.,
or docking the mobile device wired base station.
Furthermore, her coworkers may concurrently update their
replicated data.
In short, we develop a detailed cost model for group design
and oer a remedy to a scalability problem natural to
ISDBs that share data. We then present extensive experimental
results demonstrating the improved e-ciency using
our design techniques. We begin in Section 2 by placing our
work in the context of related work. We dene the architecture
and an I/O-based cost model for evaluating a spe-
cic data grouping in Section 3. In Section 4, we propose a
heuristic set of operators for modifying data groupings and
a greedy algorithm to apply these operators. We also outline
how to handle changes in the system conguration. In
Section 5, we compare our approach to intuitive grouping
alternatives, and demonstrate that our grouping algorithm
provides signicantly greater scalability in client population
size. Finally, we summarize our observations and describe
future work in Section 6. Note that for the sake of brevity,
we do not include the proofs of theorems in this paper, and
present only a subset of our experimental results. For more
detail, the reader may refer to [12].
2. RELATED WORK
An ISDB is an instance of a distributed computing sys-
tem. Multiple databases independently operate on shared
data. The assumptions that clients are mobile and commonly
suer long periods of disconnection from the server,
however, make traditional concurrency control protocols in-
applicable. Traditional distributed database systems use the
two-phase-commit protocol to help ensure the ACID properties
of transactions [7]. This protocol is communication
intensive and is therefore impractical when clients can be
unreachable for long periods of time{e.g., if a mobile client
powers down in order to save energy.
In response, researchers have proposed replicating data
among multiple clients and allowing them to operate on
the replicas independently [1]. This allows quicker response
time, reduces the possibility of deadlock, reduces the need
for energy-consuming communication with the server, and
allows mobility resistant to network outages, with the down-side
of relaxing the ACID properties [3].
To aid such functionality, the architecture must include
a dedicated centralized server that collects updates, and resolves
con
icts as described in [2]. This server increases
the availability and reliability of shared data, but may suffer
performance problems because the amount of work the
server must do increases with the number of clients served.
The architecture and goal of the CODA intermittently
connected le system is similar to those of ISDBs. Researchers
of CODA predicted (but did not experience) the
possibility of a reintegration storm, which occurs when multiple
clients simultaneously try to synchronize their local
caches with the server [9]. This results in unmanageably
long reintegration times for each client. A similar project
called DBMate supports intermittently connected database
systems. Experiments with DBMate show that server design
can improve synchronization performance [8]. The work in
this paper generalizes these results.
Group design is similar to materialized view design for
large database systems. Both try to reorganize monolithic
sets of data in order to speed up response time for clients.
However, view design has slightly dierent goals and as-
sumptions. The utility of view design is measured by how
closely the resultant views cover the expected queries; the
main cost is the disk space consumed in storing the views
[4]. In group design for ISDBs, the utility of groups is measured
by how quickly they are generated, and the cost is
roughly how much extra data must be transmitted to the
clients. Furthermore, since views are assumed to contain
subsets of relational data and groups contain updates, they
can be manipulated in dierent ways. For these reasons,
algorithms for view design are inapplicable to group design.
3. MODEL
Standard ISDB architecture includes the database server,
update server, le server, network, and clients. The database
server stores the global database. The update server generates
sets of updates for the replicas stored on the clients.
These updates are made available to clients through a set of
le servers. Clients intermittently connect to the le server
via a network. The client is composed of a client update
agent, and a local DBMS. When the client downloads up-
dates, the client update agent processes them by applying
them to the replicas contained on the local DBMS. Data
ow from client to server is not discussed in this paper, but
the interested reader may refer to [10] for more details.
The global database is divided into publications or frag-
ments, which are horizontal partitions of the database. Each
client subscribes to a subset of fragments based on its data
needs. The server maintains multiple, possibly overlapping
datagroups of fragments, designed based on client subscrip-
tions. The DBMS records updates from clients in a log,
which is modied so that it also stores the scope [3]{the
which the update aects{of each update.
An update session is dened as the process during which
the update server scans the log for outstanding updates,
and for each datagroup, generates an update le (called the
update log) containing the updates that are in that data-
group's scope. The resultant update logs are then placed
on a le server for use by the clients. The frequency of up-date
sessions is application dependent and controlled by the
system administrator. A client downloads the update log(s)
that correspond to its local subscription. The client's up-date
server then processes and applies the contents of the
update log(s) to its local fragment replicas. In the basic approach
to update processing practiced by industry, which we
call client-centric, one datagroup is dened for each client
to exactly match its local subscription. In the proposed
data-centric approach [5], datagroups are created according
to how data are shared and the number of datagroups is
generally independent of the number of clients.
We consider the following two steps critical in synchronizing
a client: generating update les at the server and transmitting
them to the clients. We do not emphasize client-side
processing because the availability of powerful mobile computing
platforms (e.g., Pentium-class laptops) means that
client-side processing is not a performance bottleneck, especially
when the client is able to \install" updates while
being disconnected.
These two critical steps are tightly coupled. If an up-date
server can generate update logs more quickly, then they
are available for download sooner, and if update logs take
more time to generate, a client must wait longer to down-load
them. It is therefore reasonable to increase the cost of
one of these steps if the decrease in the other is greater.
Problem Statement: We are given a global database,
divided into a set of fragments, g. The proportion
of updates applied to F i during an update session
is estimated by a weight, W i . Fragment weights can be determined
by either using database statistics or as a function
of the volume of data a fragment denition spans (i.e., the
fragment's size) and the number of clients that subscribe to
it (i.e., the fragment's subscription level):
subscription level) of fragment i
(size  subscription level) of all fragments
The server stores a set of datagroups
generates an update log for each, containing
the updates to the group's fragments. The size of
each update log is a function of the sum of the weights of
its corresponding datagroup.
Each client, i, has a set of interests, C i where C i  F .
Each client subscribes to a set of datagroups such that the
groups to which the client subscribe contain a superset of the
fragments of interest to the client. Stated formally, if C is
the set of all C i , given a mapping from clients to datagroups,
(the power set of G), for each client i, [(i)
. This is the covering constraint.
Our goal is to generate a set of datagroups G and a mapping
that minimizes the total cost function (see Equation
below). With client-centric grouping,
jCj. The data-centric grouping
approach determines its grouping based on the aggregated
interests of the entire client population and the capabilities
of the system architecture. Figure 2 gives a simple example
of data-centric redesign in the case where the interests of
one client are a subset of those of another. Intuitively, if the
number of fragments in the database is xed, as the number
of clients increases, the absolute amount of overlap in
interests increases. This suggests that data-centric redesign
increases in usefulness with a growing client population.
3.1 Cost Model
Our cost model assumes that I/O time is the dominant
cost factor and is therefore a good approximation of the over-all
update processing cost of a particular grouping scheme.
Three server and network activities make up the total cost:
update mapping (mapping of updates to their respective
datagroups 1 ), update log storage (storage of all update logs
An update operation is one of three data manipulating
onto disk), and update log propagation (loading and transmission
of update logs). Total cost is therefore:
Total Cost = Update Mapping Cost
Update Storage Cost Update Propagation Cost (2)
The components of Equation 2 are explicitly modeled below.
The variables we use are shown in the following table
Variable Description (units, if appropriate)
CS server disk seek time (secs)
CL server disk latency time (secs)
CD CS +CL
CT server disk transmission rate (secs/byte)
rate between client k and server
VB buer size for each update log le (bytes)
VD average update operation record size (bytes)
VP average fragment denition record size (bytes)
VT average temporary table record size (bytes)
VG average datagroup denition record size
(bytes)
VS number of operations in the update le
total size of update le
M number of datagroups
N number of clients
Update (to datagroup) mapping cost is the time required
to map updates to datagroups. We assume that the
log of updates to be distributed and an update-to-fragment
mapping table (the publication information) are sequentially
read into memory (2CD +CT (VF )). The results of
the join are saved into a temporary le (CD
The temporary le and the fragment-to-datagroup mapping
table (the subscription information) are then read (2CD
joined in memory to produce
the nal result. Hence,
Update Mapping Cost
Update storage (to disk I/O) cost measures the time
required to store all the update logs onto disk at the server.
We assume that a main-memory buer is maintained for
each update log, and whenever a buer is lled, its contents
are written to disk. This happens until all update logs are
The left term in the parentheses
below indicates the time spent on disk latencies that are
experienced for each update log when the buer is lled,
whereas the right term indicates how much time is required
to store the actual data on disk. Recall that the weight of
fragment estimates the proportion of operations that
commands, namely INSERT, UPDATE and DELETE. Combinations
of these operations constitute the transactions contained
in update logs.
2 The term \record" in the table refers to the data structure
(e.g., row) containing the respective information
Salesman
Northeast
Manager
Salesman
Northeast
Manager
Data Data Data Data Data Data Data Data
North East South West North East South West
Database
Server
F
Definition
G
Mapping
F
Client
Population
CLIENT-CENTRIC GROUPING DATA-CENTRIC GROUPING
REDESIGN

Figure

2: Example of client-centric to data-centric redesign using aggregated interests.
are applied to that fragment.
Update Storage Cost
(Server to client) update propagation cost measures
the time required to load into memory and then transmit
the appropriate update logs to all clients, assuming unicast
communication between the server and each client. Each
log the client downloads is sequentially read, then joined in
memory, then transmitted over the network at the client's
bandwidth.
Update Propagation Cost
In the equation above, disk latencies are experienced while
reading each client k's update logs (CD j(k)j). For each
client k, the volume of data read and transmitted are the
same (VF
although the server's
disk rate is xed (CT ), the clients' transmission rates are independent
3.2 Some Potential Cost Reducing Alternative

For illustrative purposes, we now discuss certain extreme
datagroup design strategies. A single large datagroup
the amount of disk resources
used. However, all clients must then receive all updates
regardless of their particular interests. If transmission costs
are high, this is a very costly solution. At the other ex-
treme, one datagroup can be generated for each fragment
This is similar to the server-side organization
proposed in [8]. Note that if the number of fragments
is high, then managing all the datagroups becomes
costly. Another solution is to generate one datagroup per
client C). This is the client-centric solution
standard used by industry that, as shown in [5], results in
high levels of redundant work as the client population grows.
The alternative we propose lies somewhere in between these
solutions and is based on how the clients share data.
Another option is to ameliorate the system architecture
itself with multiple update servers, in which each can work
in parallel to generate the update logs for a subset of clients,
as described in [10]. Instead of precluding it, such architectural
solutions complement data-centric design. For exam-
ple, clients can be allocated to each update server based
on the potential eectiveness of the resultant data-centric
grouping. One way to do this is to cluster clients based on
interest a-nities as in [6]. However, because we assume a
single update server, such work is outside the scope of this
paper.
4. A HEURISTIC APPROACH TO GROUPING
Because of the complexity of the grouping problem (it can
be modeled as an NP complete mathematical programming
problem), we oer a heuristic algorithm. We start by introducing
three operators that perform grouping operations
on fragments. Each has dierent cost proles, and thus are
applicable in dierent situations. At the end of this section,
we introduce a means of greedily applying these operators.
For brevity, we do not include a formal cost analysis but one
can be found in [12].
Based on the cost equations introduced in Section 3.1,
certain conclusions can be drawn about ways of manipulating
the grouping in order to reduce update processing costs.
Namely, we can manipulate the number of datagroups, the
composition of datagroups, and the subscription of clients
to datagroups in order to change update processing costs.
Common ways of redesigning datagroups, although with different
side eects, include merging, splitting, and subtracting
overlapping datagroups [7]. Although similar operators
are used in materialized view design, these operators are
based on algorithms that, as we explained in Section 2, are
generally inapplicable here. We therefore dene our own
operators and give their denitions, side-eects, and applicability
below. See Figure 3.
4.1 Operators for Redesigning Datagroups
Merging two datagroups involves replacing them with
their union. Clients subscribing to at least one of the merged
datagroups instead subscribe to their union, preserving the
covering constraint (See Section 3). If there is overlap between
the merged datagroups, then storage cost is reduced
in proportion to the size of the overlap. If a client originally
subscribed to only one of the merged datagroups, the client
must receive super
uous updates for fragments contained in
the \other" merged datagroup, resulting in increased update
log transmission costs.
Applicability of Merge - Because this operator typically
increases the amount of data that must be transmitted to
a client, we do not expect this operator to be used much,
unless the network bandwidth is very high, or the degree of
overlap between two datagroups is very high.
Splitting involves nding two non-totally overlapping, but
partially intersecting datagroups, and splitting
to form a third datagroup. Subscribers to either
datagroup must also subscribe to the third datagroup. Splitting
reduces overlap in datagroups, but does not increase the
amount of data transmitted to the respective subscribers.
There is, however, overhead in terms of disk seeks and latencies
for each additional datagroup generated.
Applicability of Split - Splitting should increase in relevance
as the volume of updates increases or the degree of
overlap between two datagroups increases, because the time
saved in not rewriting large sets of updates osets the increase
in disk seek and scan times.
Subtracting two datagroups applies only if one is a sub-set
(either proper or not) of the other. The smaller of the
two is subtracted from the larger one, eliminating their over-
lap. If the datagroup subtracted from becomes empty (in
the case where the subset relationship is not proper), then
it is discarded. Subscribers to the larger datagroup must
also subscribe to the smaller one (if a smaller one exists);
overhead in terms of disk latencies is incurred by clients having
to subscribe to additional datagroups. The number of
datagroups is not increased by this operation, and savings
are proportional to the degree of overlap between the subtracted
datagroups. Subscribers to these datagroups do not
need to receive extra data.
Applicability of Subtract - This operator diers from the
other two, because of the subset restriction on the operands.
Nonetheless, this operator typically has fewer side eects: It
neither increases the amount of data sent to clients the way
merge does, nor the number of datagroups the way split
does.
Example: Consider two datagroups, A and B, that each
generate update logs of 10KB. If, due to the denitions of
A and B, these update logs always have a single byte dif-
ference, then it may make sense to merge A and B. This
saves the server some work by maintaining one fewer data-
group and not storing its corresponding update log. The
cost however, is that clients subscribing to one of A or B,
must download an additional byte. But at 19Kbps, the additional
byte adds less than a millisecond in transfer time.
Alternatively, splitting A and B forces the server to maintain
the denition of an additional datagroup and generate
an additional byte-sized update log, which, depending on
the server load, may not be cost eective.
On the other hand, if A and B both generate update logs
of 10KB, which only have 5KB in common, it may make
sense to split the datagroups. Although splitting in the
above case would force the server to maintain the denition
of an additional datagroup and gererate an additional byte-
sized update log, here it would save the server some storage
time (because of the magnitude of the overlap) without increasing
the volume of data sent to the client. The drawback
is that splitting forces the server to maintain an additional
datagroup. Savings in storage, however, increase in importance
as datagroups grow. If these two datagroups were
merged instead, then clients subscribing to one of A or B
would have to spend  2 seconds downloading super
uous
data in addition to the  4 seconds spent downloading pertinent
data at 19Kbps.
4.2 Greedy Heuristic
The application strategy proposed here pursues local cost
minima until no cost reduction can be made by applying
the above operators. The greedy algorithm starts with the
client-centric solution and applies all possible subtraction
operations on the set of datagroups until no cost-reduction
is possible with this operator. We then search for the most
cost-eective merge or split. If one exists, we perform it,
and repeat the cycle:
GREEDY HEURISTIC
while TRUE do
Perform all possible cost-reducing subtraction
operations
Let m be the most benecial merge and let s be
the most benecial split.
If either m or s results in a cost reduction, then
perform the one that reduces cost the most.
neither m nor s is performed, then quit.
od
Subtraction is given precedence because it typically has
the fewest side-eects in terms of cost penalties and reduces
the search space for the other two operators. Furthermore,
merge and split can increase the applicability of subtract.
4.3 Redesign
As time passes, an ISDB changes its conguration. New
clients may be periodically added to the ISDB, with a given
subscription. The problem is deciding the proper data-
groups to assign to them. This problem is similar to the NP -
hard set-covering problem. Moreover, the existing clients
may change their subscriptions or their type of connection
with the server may change. A client may move from one
location to another and change its subscription to match its
locale, or another client may acquire a faster, higher band-width
connection.
The problem of redesign therefore has two levels: redesign
only subscriptions (groups remain xed); redesign both the
groups as well as the subscriptions. We address these problems
heuristically. Such solutions are necessary because
the greedy heuristic described in this paper has complexity
We therefore oer techniques that reduce
the need of running it. These techniques and relevant
proofs are fully described in [12].
4.3.1 Addition of Clients
In this section, we roughly describe how to map data-
groups to the subscriptions of new clients. This problem is
similar to the NP -complete weighted set-covering problem,
A
A
A'
A
A'
merge split subtract

Figure

3: The Merge, Split, and Subtract Operators. The boxes represent datagroups. The dashed lines
indicate overlap.
and we solve the client-addition problem in a similar way.
To each subscription, we greedily map the datagroup that
has the best (lowest) cost-eectiveness. Cost-eectiveness
is the ratio of the size of the datagroup (size is dened in
Section and the total size of the fragments covered for the
rst time by the datagroup. This process is repeated until
the entire subscription is covered. We have a ratio bound
for the results of this algorithm:
Theorem 4.1. The solution achieved by the greedy algorithm
is within a factor of HN approximation of the minimal
cost cover, where
is the N th
harmonic number and N is the size of the subscription.
4.3.2 Rerunning the Redesign Algorithm
As time passes, the conguration of the ISDB changes
making a data-centric grouping less cost-eective. Examples
of changes include changing of client connectivity, client
subscriptions, or server speed. Since we can keep track of
these changes, recomputing current client-centric cost (Ccc )
is straight-forward using the cost model from Section 3. By
comparing this cost with the actual current cost of the current
data-centric grouping (Cdc ), an administrator can decide
to redesign the datagroups if the cost improvement o-
sets the estimated redesign time (Cr
This is a conservative rule of thumb for deciding the benet
of redesign and varies depending on the application.
5. EXPERIMENTS
5.1 Goals
The goal of our experiments is to show that data-centric
grouping of updates using our greedy heuristic (denoted by
dc), results in faster refresh times for the average client than
other, more intuitive methods. Refresh time includes the
time required for the server to generate an update log(s)
(including computation and storage) and transmit it to the
proper client. These costs correspond to the ones described
in Section 3. The other grouping methods we consider are
described in Table 1.
In our experimental design, the database is composed of
100 fragments. Each fragment i is assigned a value, p i (0
Each client subscribes to fragment
i with a probability p i . To assign values to each p i , we
consider two probability distributions: one highly skewed
(Zipan, with one uniform. This results in
the average client subscribing to 1% of the database. The
total volume of updates is a linear function of the number of
clients. They are allocated to each fragment in proportion
to that fragment's p i value. Each client is assumed to have
the same network bandwidth (C i
The client population and client bandwidth. Varying these
parameters over these values re
ects a wide range of appli-
cations, such as the OLTP-class mobile o-ce application
described in the beginning of this paper. We omit experiments
varying update volume for the sake of brevity. See

Table

2.
We show that as any of the experimental parameters in-
creases, the advantage of using dc increases over the other
techniques. For example, the dierence between dc and cc
increases with the number of clients. Performance gains generally
come from detecting and removing redundant update
processing (i.e., overlapping subscriptions), but as we show,
under some circumstances, can also come by ooading work
onto other components in the architecture.
5.2 Experimental Set-Up
We ran our experiment on an Ethernet LAN consisting
of Pentium II computers running Windows NT. Update services
are provided by Synchrologic iMobile on a 266MHz
PC with 64MB RAM. (Performance trends using alternative
ISDB middleware, such as those by Oracle, IBM or Sybase,
should be similar to those reported here.) The database
server is Sybase SQL Anywhere v.6, running on a 200MHz
PC with 128MB RAM. The database stores a universal relation
to which we apply updates that are distributed to the
clients.
For the data-centric experiments, extensions based on those
described in [5] have been incorporated into iMobile. One
of the consequences of these extensions is that an extra set
of meta-data must be sent to each client. The size of the
meta-data le has been empirically estimated as ( 24
where jGj is the number of datagroups generated. The meta-data
grows with the number of groups because increasing the
number of groups results in the need to store more mapping
information for them. This extra metadata increases the
refresh times of dc, og and op generally by adding transmission
time. This extra cost becomes insignicant however,
as workloads increase and does not aect the trends of the
results.
5.3 Experiment 1: Varying Client Population
The results for both data distributions are nearly identi-
cal. Method op is bad with low populations because it generates
update logs regardless of whether they are subscribed
to or not. But, as the population increases, the probability
that a datagroup is not subscribed to becomes low. Method
og makes sense when there are few clients, because it saves
Grouping Methods (notation) comments
data-centric (dc) groups generated with the greedy heuristic
client-centric (cc) employed in industry, creates a unique group for each client
one-giant-group (og) minimizes costs at the server by storing updates for all clients in a single group
one-per-fragment (op) minimizes network costs and eliminates some storage redundancy by generating
a single group for each fragment

Table

1: Grouping Methods
Parameter Description Values (control values in fg)
Number of clients 1, 5, 50, f100g, 200, 500, 1000
Workload (updates/client) f50g
Client bandwidth (bps) 19:2
Distribution of updates over fragments Zipf

Table

2: Parameter values for experiments.20601001401 5 50 100 200 500 1000
clients
refresh
time
og
op
cc
clients
refresh
time
og
op
cc
dc
A. Uniform Distribution B. Zipf Distribution

Figure

4: Per-Client Refresh Time (seconds) With Varying Client Population.51525354519200 57600 512000 1024000 10240000
bandwidth (bps)
refresh
time
og
op
cc
bandwidth (bps)
refresh
time
og
op
cc
dc
A. Uniform Distribution B. Zipf Distribution

Figure

5: Per-Client Refresh Time (seconds) With Varying Client Bandwidth.
the server some work. The amount of super
uous data sent
to each client grows, however, with the population, making
this grouping infeasible. Method cc breaks down with a high
population because of the increasing amount of redundant
work it must do with a growing population.
In these tests, dc, which uses the proposed greedy heuris-
tic, has consistently good performance, resulting in the lowest
or nearly the lowest refresh times over all populations.
Method dc outperforms op, because dc groups together fragments
that are often subscribed to together. Method dc
avoids the problems associated with og and cc by generating
many datagroups with little overlap, but not so many as
to compromise server performance. See Figure 4.
Please note that the total volume of data distributed is
not scaled up per client as the client population increases.
We keep the total volume of data constant in order to isolate
client-population eects. However, experimental results
given a greater total volume of data make the dc results even
more favorable with respect to the others.
5.4 Experiment 2: Varying Client Bandwidth
In practice, clients may choose among many connectivity
options, including wireless modem, conventional modem,
high-speed wireless LAN, or simply docking the portable device
at the o-ce LAN. We therefore study how these changing
bandwidths aect the eectiveness of the various grouping
methods.
Although og performs poorly when there is little band-
width, it gains the most as bandwidth increases. With og,
work at the server is already minimized, so more bandwidth
reduces the most harmful eects of shipping super
uous
data.
Method op has good performance as well, but fails to take
advantage of the increased bandwidth by generating fewer
groups in order to save the server some work. It therefore
ultimately performs worse than og.
With high bandwidth, cc has the worst performance of
all, because of the redundant work that must be done at the
server, regardless of network performance. This is an important
result, and indicates that, regardless of the capability of
the network, per-client ISDB refresh processing using cc has
a performance
oor.
Method dc does the best, by generating multiple disjoint
groups which conserve network resources when they
are poor, and generating fewer groups which conserve server
resources when the network is fast. See Figure 5.
6. CONCLUSION
In this paper, we dene a detailed model of ISDBs, describe
how this model inherently leads to performance problems
with client refresh, and oer a grouping solution. We
propose redesigning updates into groups based on the aggregated
interests of the entire client population (data-centric).
This allows clients to share groups intended for many clients.
To formulate a redesign technique we dene a detailed cost
dene operators that manipulate costs based on the
system conguration, and devise a way of applying them,
based on greedy heuristics.
We tested our greedy heuristic against the client-centric
approach, and two other intuitive solutions: a monolithic
group containing all updates and individuals groups for each
fragment. Overall, our heuristic outperforms all the others
in terms of refresh time because it greedily allocates resources
where they are needed{either to the server or the
network depending on the conguration of the ISDB. Fur-
thermore, the relative benet of data-centric grouping increases
with the client population, improving scalability.
Our work on ISDBs is ongoing. For example, we limited
client connectivity to unicast because this is currently the
dominant form of communication in practice. We are currently
exploring the use of multicast as a means of improving
network scalability.
7.

ACKNOWLEDGMENTS

The authors would like to acknowledge Ms. Mireille Jacobson
for her valuable editorial assistance.
8.



--R

Replication and consistency: Being lazy helps sometimes.
Replicating and allocation data in a distributed database system for workstations.
The dangers of replication and a solution.
Implementing data cubes e-ciently
Grouping techniques for update propagation in intermittently connected databases.
Vertical partitioning algorithms for database design.
Principles of Distributed Database Systems.
Data partitioning for disconnected client server databases.
Experience with disconnected operation in a mobile computing environment.

A framework for server data fragment grouping to improve scalability in intermittently synchronized databases.
Minimizing redundant work in lazily updated replicated databases.
--TR
Vertical partitioning algorithms for database design
The dangers of replication and a solution
Implementing data cubes efficiently
Replication and consistency
Principles of distributed database systems (2nd ed.)
Data partitioning for disconnected client server databases
Replicating and allocating data in a distributed database system for workstations
A framework for designing update objects to improve server scalability in intermittently synchronized databases
Grouping Techniques for Update Propagation in Intermittently Connected Databases

--CTR
Efficient synchronization for mobile XML data, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
distributed databases;mobile databases;intermittent synchronization