Minimization of Communication Cost Through Caching in Mobile Environments.
AbstractUsers of mobile computers will soon have online access to a large number of databases via wireless networks. Because of limited bandwidth, wireless communication is more expensive than wire communication. In this paper, we present and analyze various static and dynamic data allocation methods. The objective is to optimize the communication cost between a mobile computer and the stationary computer that stores the online database. Analysis is performed in two cost models. One is connection (or time) based, as in cellular telephones, where the user is charged per minute of connection. The other is message based, as in packet radio networks, where the user is charged per message. Our analysis addresses both the average case and the worst case for determining the best allocation method.
Introduction
Users of mobile computers, such as palmtops, notebook computers and personal communication
systems, will soon have online access to a large number of databases via wireless networks. The
potential market for this activity is estimated to be billions of dollars annually, in access and
communication charges. For example, while on the road, passengers will access airline and other
carriers schedules, and weather information. Investors will access prices of financial instruments,
salespeople will access inventory data, callers will access location dependent data (e.g. where
is the nearest taxi-cab, see [10, 24]) and route-planning computers in cars will access traffic
information.
Because of limited bandwidth, wireless communication is more expensive than wire commu-
nication. For example, a cellular telephone call costs about $0.35 cents per minute. As another
example, RAM Mobile Data Corp. charges on average $0.08 per data message to or from the
mobile computer (the actual charge depends on the length of the message). It is clear that for
users that perform hundreds of accesses each day, wireless communication can become very ex-
pensive. Therefore, it is important that mobile computers access online databases in a way that
minimizes communication.
We assume that an online database is a collection of data items, where a data item is, for
example, a web-page or a file. Users access these data items by a unique id, such as a key, one at
a time. We minimize communication using an appropriate data-allocation scheme. For example,
if a user frequently reads a data-item x, and x is updated infrequently, then it is beneficial for
the user to allocate a copy of x to her/his mobile computer. In other words, the mobile user
subscribes to receive all the updates of x. This way the reads access the local copy, and do
not require communication. The infrequent updates are transmitted from the online database
to the mobile computer. In contrast, if the user reads x infrequently compared to the update
rate, then a copy of x should not be allocated to the mobile computer. Instead, access should be
on-demand; every read request should be sent to the stationary computer that stores the online
database.
Thus, one-copy and two-copies are the two possible allocation schemes of the data item x to
a mobile computer. In the first scheme, only the stationary computer has a copy of x, whereas in
the second scheme both, the stationary and the mobile computer have a copy of x. An allocation
method determines whether or not the allocation scheme changes over time. In a static allocation
method the allocation scheme does not change over time, whereas in a dynamic one it does. The
following is an example of a dynamic allocation method. The allocation scheme changes from
two-copies to one-copy as a result of a larger number of writes than reads in a window of four
minutes.
In mobile computing the geographical area is usually divided into cells, each of which has
a stationary controller. Our stationary computer should not be confused with the stationary
controller. The stationary computer is some node in the stationary network that is fixed for a
given data item, and it does not change when the mobile computer moves from cell to cell.
In this paper we analyze two static allocation methods, namely the one that uses the one-copy
scheme and the one that uses the two-copies scheme; and a family of dynamic data allocation
methods. These methods are suggested by the need to select the allocation scheme according to
the read/write ratio: if the reads are more frequent then the methods use the two-copies allocation
scheme, otherwise they use the one-copy scheme. The family consists of all the methods that
allocate and deallocate a copy of a data item to the mobile computer based on a sliding window of
k requests. For every read or update (we often refer to updates as writes) the latest k requests are
examined. If the number of reads is higher than the number of writes and the mobile computer
does not have a copy, then such a copy is allocated to the mobile computer; if the number of
writes is higher than the number of reads and the mobile computer does have a copy, then the
copy is deallocated. Thus, the allocation scheme is dynamically adjusted according to the relative
frequencies of reads and writes.
The algorithms in this family are distributed, and they are implemented by software residing
on both, the mobile and the stationary computers. The different algorithms in this family differ
on the size of the window, k.
Our analysis of the static and dynamic algorithms addresses both worst-case, and the expected
case for reads and writes that are Poisson-distributed. Furthermore, this analysis is done in two
cost models. The first is connection (or time) based, where the user is charged per minute of
cellular telephone connection. In this model, if the mobile computer reads the item from the
stationary database computer, then the read-request as well as the response are executed within
one connection of minimum length (say one minute). If writes are propagated to the mobile
computer, then this propagation is also executed within one minimum-length connection.
The second cost model is message based. In this model the user is charged per message,
and the exact charge depends on the length of the message. Therefore, in this model we distinguish
between data-messages that are longer, and control-messages that are shorter. Data-
messages carry the data-item, and control messages only carry control information, specifically
read-requests (from the mobile computer to the stationary computer) and delete-requests (the
delete-request is a message that deallocates the copy at the mobile computer). Thus a remote
read-request necessitates one control message, and the response necessitates a data message. A
write propagated to the mobile computer necessitates a data-message.
The rest of the paper is organized as follows. In the next section we present a summary
of the results of this paper. In section 3 we formally present the model, and in section 4 we
precisely present the sliding-window family of dynamic allocation algorithms. In section 5 we
develop the results in the connection cost model, and in section 6 we develop the results in the
message model. In section 7 we discuss some other dynamic allocation methods, and extensions
to handle read, write operations on multiple data items. In section 8 we compare our work to
relevant literature. In section 9 we discuss the conclusions of our analysis.
2 Summary of the results
We consider a single data item x and a single mobile computer, and we analyze the static
allocation methods ST 1 (mobile computer does not have a copy of x) and ST 2 (mobile computer
does have a copy of x), and the dynamic allocation methods SW k (sliding-window with windowsize
k).
We assume that reads at the mobile computer are issued according to the Poisson distribution
with the parameter - r , namely in each time unit the expected number of reads is - r . The writes
at the stationary computer are issued independently according to the Poisson distribution with
the parameter -w . Other requests are ignored in this paper since their cost is not affected by the
allocation scheme. We let ' denote -w
-r+-w .
Our analysis of each one of the algorithms uses three measures. The first, called expected
cost and denoted EXP , gives the expected cost of a read/write request in the case that ' is
known and fixed. The second, called average expected cost and denoted AV G, is important for
the case ' is unknown or it varies over time with equal probability of having any value between
0 and 1. It gives average the expected cost of a request over all possible values of '.
Our third measure is for the worst case, and it is based on the notion of competitiveness 1
(see [9, 18, 23, 29, 32]) of an on-line algorithm. Intuitively, a data allocation algorithm A is said
to be c-competitive if for any sequence s of read-write requests, the cost of A on s is at most c
times as much as the minimum cost, namely the cost incurred by an ideal offline algorithm that
knows the whole sequence of requests in advance (in contrast our algorithms are online, in the
sense that they service the current request without knowing the next request).
In the remainder of this section we summarize the results for each one of the two cost models
discussed in the introduction. These results will be interpreted and discussed at the intuitive
level in the conclusion section.
2.1 Summary of results in the connection model
In the connection model our results are as follows. For ST 1 the expected cost (i.e. expected
number of connections) per request is the expected number of connections
per request is '. For SW k the expected cost per request is '
ff k is the probability that the majority of k consecutive requests are reads (the formula for this
probability is in equation 5). Furthermore, we show that for any fixed k, SW k is not lower than
'g. Thus, if ' - 1, then the static allocation method ST 1 has the best expected cost
per request, and if ' - 1, then the static allocation method ST 2 has the best expected cost per
request.
Next consider the average expected cost. SW k has the best average (over the possible values
of ') expected cost per request. This cost is 1+ 1
, and it decreases as k increases, coming
within 6% of the optimum for In contrast, ST 1 and ST 2 , both have an average expected
cost of 1For the worst case, we show that ST 1 and ST 2 are not competitive, i.e., the ratio between their
performance and the performance of the optimal, perfect-knowledge algorithm is unbounded. In
contrast, we show that SW k is 1)-competitive, and this competitiveness factor is tight.
In summary, in the worst case the cost of the SW k family of allocation algorithms increases
as k increases, whereas the average expected cost decreases as k increases. The window size k
should be chosen to strike a balance between these two conflicting requirements. For example, k
may provide a reasonable compromise.
1 The traditional worst case complexity as a function of the size of the input is inappropriate since all the
algorithms discussed in this paper have the same complexity under this measure. For example, in the connection
model, for each algorithm there is a sequence of requests of size m on which the algorithm incurs cost m.
2.2 Summary of results in the message passing model
In this model our results are as follows. Let the cost of a data message be 1 and the cost of a
control message be !, where 0 - 1. For ST 1 , the expected cost per request is (1+!)
and for ST 2 the expected cost is '. For SW 1 , the expected cost is '
for derived the expected cost as a function of ! and ' as shown in equation
15 of section 6.3 2 . From these formulae of the expected costs, we conclude the following. If
, then ST 1 has the best expected cost; if ' ! 2\Delta!
, then ST 2 has the best expected
cost; otherwise, namely if 2\Delta!
, the SW 1 algorithm has the best expected cost. The
dominance graph of these three strategies is shown in the following figure 1. It indicates the
superior algorithm for each value of ' and !.

Figure

1: Superiority coverage in message model
Next we consider the average expected cost, and we obtain the following results. ST 1 has
an average expected cost of 1+!; ST 2 has an average expected cost of 1; SW 1 has an average
expected cost of 1+2\Delta!; and the average expected cost of SW k (for k 6= 1) is given by equation
of section 6.3, and it has a lower bound of 2+!. Then we conclude that, if ! - 0:4, then SW 1
has the best average expected cost; if ! ? 0:4, then the average expected cost decreases as the
window size k increases (see corollary 2 in section 6.3).
For the worst case we show that, as in the connection cost model, neither ST 1 nor ST 2 are
competitive. Similarly, we show that the sliding-window algorithm SW 1 is (1+2 \Delta !)-competitive,
and SW k (for k ? 1) is [(1
In summary, the trade-off between the average expected cost and the worst case is similar
to the connection model. Namely, a dynamic allocation algorithm is superior to the static ones,
with the worst case improving with a decreasing window size; whereas the average expected cost
decreases as the window size increases.
2 The SW 1 algorithm is not a special case of the SW k algorithms, as pointed out at the end of section 4
3 The Model
A mobile computer system consists of a mobile computer MC and a stationary computer SC that
stores the online database. We consider a data item x that is stored at the stationary computer
at all times. Reads and writes are issued at the mobile or stationary computers. Actually, the
reads and writes at the stationary computer may have originated at other computers, but the
origin is irrelevant in our model. Furthermore, we ignore the reads issued by the stationary
computer and the writes issued by the mobile computer, since the cost of each such request is
fixed (zero and one respectively), regardless of whether or not MC has a copy of the data item.
Thus, the relevant requests are writes that are issued by the stationary computer, and reads that
are issued by the mobile computer. A schedule is a finite sequence of relevant requests to the
data item x. For example, w; w is a schedule. When each request is issued, either the
MC has a copy of the data item, or it does not. For the purpose of analysis we assume that
the relevant requests are sequential. In practice they may occur concurrently, but then some
concurrency control mechanism will serialize them, therefore our analysis still holds. We assume
that messages between the stationary computer and each mobile computer are delivered in a
first-in-first-out order.
We consider the following two cost models. The first is called the connection model. In this
model, for each algorithm (static or dynamic) the cost of requests is as follows. If there does not
exist a copy of the data item at the MC when a read request is issued, then the read costs one
connection (since the data item must be sent from the SC). Otherwise the read costs zero. For
a write at the SC, if the MC has a copy of the data item, then the write costs one connection;
otherwise the write costs zero. The total cost of a schedule /, denoted by COST (/), is the sum
of the costs for all requests in /.
The second model is called the message cost model. In this model, we assume that a data
message cost is 1, and a control message cost is !. Since the length of a control message is not
higher than the length of a data message, 0 - 1. In this model the cost of requests is as
follows. For a read request, if there exists a copy at the MC, then the read does not require
communication; otherwise, it necessitates a control message (which forwards the request to the
SC) and a data message (which transfers the data to the MC) with a total cost of 1
For a write request, if the MC does not have a copy of the data item, then the write costs
Otherwise the write costs 1, !, or 1 !, depending on the algorithm and on the result of
the comparison of reads and writes executed by the MC in response to the write request. If the
write is propagated to the MC and the MC does not deallocate its copy in response, then the
cost is 1; if the MC deallocates its copy in response then the cost is accounts for the
deallocate request). Finally, as will be explained in the next section, SW 1 does not propagate
writes to the MC; it simply deallocates the copy at the MC at each write request. Then the cost
of the write is !.
We assume that the reads issued from the MC are Poisson distributed with parameter - r ,
and the writes issued from the SC are Poisson distributed with parameter -w . Denote -w
-w+-r
by '. Observe that, since the Poisson distribution is memoryless, at any point in time ' is the
probability that the next request is a write, and
-w+-r
is the probability that the next
request is a read.
Suppose that A is a data allocation algorithm, and - r and -w are the read and write distribution
parameters, respectively. We denote by EXPA (') the expected cost of a relevant request.
Suppose now that ' varies over time with equal probability of having any value between 0 and
1. Then we define the average expected cost per request, denoted AV GA , to be the mean value
of EXPA (') for ' ranging from 0 to 1, namely
Z 1EXPA (')d' (1)
The average expected cost should be interpreted as follows. Suppose that time is subdivided
into sufficiently large periods, where in the first period the reads and writes are distributed
with parameters - 1
r and - 1
w , and '
r
; in the second period the reads and writes are
distributed with parameters - 2
r and - 2
w , and '
etc. Suppose further that each ' i has
equal probability of having any value between 0 and 1 (i.e. the probability densisty function
of ' has value 1 everywhere between 0 and 1, and is 0 everywhere else). In other words, each
' i is a random number between 0 and 1. Then, when using the algorithm A, the expected
cost of a relevant request over all the periods of time is the integral denoted AV GA . In other
words, AV GA is the expected value of the expected cost. One can also argue that AV GA is the
appropriate objective cost function when ' is unknown and it has equal probability of having
any value between 0 and 1.
For the worst-case study, we take competitiveness as a measure of the performance of an on-line
data allocation algorithm. Formally, a c-competitive data allocation algorithm A is defined
as follows. Suppose that M is the perfect data allocation algorithm that has complete knowledge
of all the past and future requests. Data allocation algorithm A is c-competitive if there exist
two numbers c (- 1), and b (- 0), such that for any schedule /,
We call c the competitiveness factor of the algorithm A. A competitive algorithm bounds the
worst-case cost of the algorithm to be within a constant factor of the minimum cost.
We say an algorithm A is tightly c-competitive if A is c-competitive, and for any number
A is not d-competitive.
4 Sliding-window algorithms
The Sliding-Window(k) algorithm allocates and deallocates a copy of the data item x at the
mobile computer. It does so by examining a window of the latest relevant read and write
requests. The window is of size k, and for ease of analysis we assume that k is odd. Recall, the
reads are issued at the mobile computer, and the writes are issued at the stationary computer.
Observe that at any point in time, whether or not the mobile computer has a copy of x, either
the mobile computer or the stationary computer is aware of all the relevant requests. If the mobile
computer has a copy of x, then all the reads issued at the mobile computer are satisfied locally,
and all the writes issued at the stationary computer are propagated to the mobile computer; thus
the mobile computer receives all the relevant requests. Else, i.e. if the mobile computer does not
have a copy, then all reads issued at the mobile computer are sent to the stationary computer;
thus the stationary computer receives all the relevant requests.
Thus, either the mobile computer or the stationary computer (but not both) is in charge of
maintaining the window of k requests. The window is tracked as a sequence of k bits (e.g. 0
represents a read and 1 represents a write). At the receipt of any relevant request, the computer
in charge drops the last bit in the sequence and adds a bit representing the current operation.
Then it compares the number of reads and the number of writes in the window.
If the number of reads is bigger than the number of writes and there is a copy of x at the
mobile computer, then the SW k algorithm simply waits for the next operation. If the number
of reads is bigger than the number of writes and there is no copy at the mobile computer (i.e.
the stationary computer is in charge), then such a copy is allocated as follows. Observe that the
last request must have been a read. The stationary computer responds to the read request by
sending a copy of x to the mobile computer. The SW k algorithm piggybacks on this message (1)
an indication to save the copy in MC's local database, in which the SC also commits to propagate
further writes to the MC, and (2) the current window of requests. From this point onwards, the
MC is in charge.
If the number of writes is bigger than the number of reads and there is no copy of x at the
MC, then the SW k algorithm waits for the next request. If the number of writes is bigger than
the number of reads and there is a copy of x at the MC (i.e. the MC is in charge), then the
copy is deallocated as follows. The SW k algorithm sends to the SC (1) an indication that the SC
should not propagate further writes to the MC, and (2) the current window of requests. From
this point onwards the SC is in charge.
This concludes the description of the algorithm, and at this point we make two remarks. First,
when the window size is 1 and the MC has a copy of x, then a write at the SC will deallocate
the copy (since the window will consist of only this write). Therefore, instead of sending to the
MC a copy of x, the SC simply sends the delete-request that deallocates the copy at the MC.
Thus, SW 1 denotes the algorithm so optimized. Observe that SW 1 the classic write-invalidate
protocol.
5 Connection cost model
In this section we analyze the algorithms in the connection cost model. The section is divided
into 3 subsections. In the first subsection, we probabilistically study the static data allocation
algorithms, and in the second we study the family of sliding window algorithms. In each of
these subsections we derive the expected cost first, then the average expected cost, and then we
compare the algorithms based on these measures. Finally, in section 5.3 we analyze the worst
case performance of all the algorithms.
5.1 Probabilistic analysis of the static algorithms
For the ST 1 algorithm, a write request costs 0, and a read request cost 1 connection. For the
algorithm, every write costs 1, and every read costs 0. Hence, EXP ST 1
(') and EXP ST 2
are simply equal to the probabilities that a request is a read and a write, respectively. Thus,
Concerning the average expected cost, by equation 1 and equation 2 we obtain
and AV G ST 2
5.2 Probabilistic analysis of the SW k algorithms
In this section we derive the expected cost of the SW k algorithms, and we show that for each k
and for each ', the SW k algorithm has a higher expected cost than one of the static algorithms.
Then we derive the average expected cost of the SW k algorithms, and we show that for any k
the SW k algorithm has a lower average expected cost than both static algorithms. Also, we show
that the average expected cost of the SW k algorithms decreases when k increases.
Recall that we are assuming that the size of the window k (= 2 is an odd number.
At any point in time, the probability that there exists a copy at the MC (which we denote by
is the probability that the majority among the preceding k requests are reads, and this is
the same as the probability that the number of writes in the preceding k requests is less than or
equal to n, namely
Theorem 1 For every k and for every ', the expected cost of the SW k algorithm is
Proof: Let us consider a single request, q. When there is a copy at the MC, then the expected
cost of q is equal to the probability that q is a write operation, and it equals '. When there is no
copy at the MC, the expected cost of q is '. The expected cost of q is the probability that
there is a copy at the MC times the expected cost of q when there is a copy at the MC, plus the
probability that there is no copy at the MC times the expected cost of q when there is no copy
at the MC. Thus, we conclude the theorem. 2
The next theorem compares the expected costs of the SW k and the static algorithms.
Theorem 2 For every k and every ', EXP SW k
(')g
Proof: From equations 2, 5 it follows that EXP SW k
theorem follows due to the fact that the weighted average of two values is not smaller than the
minimum of the two values. 2
Now let us consider the average expected costs.
Theorem 3 For the sliding-window algorithm with window size k, SW k , the average expected
cost per request is
Z 1EXP SW k
Our derivation of equation 6 uses the following identity for positive integers a and b,
Z 1x a
Using equation 5, it is straightforward to show that
Using equation 4 and the identity given by equation 7 and after some algebraic simplifications,
it can be shown that Z 1ff k \Delta
and Z 1ff k
Substituting for
in equation 8, and after some simplification, we get the
result given by equation 6. 2
Corollary 1 The average expected cost of the SW k algorithms decreases when the window size
k increases, and AV G SW k
for any k - 1.
Proof: From theorem 3, it is easy to see that AV G SW k
decreases when k increases, and
1= 1. From equations 3 in section 5.1, we conclude the corollary.5.3 Worst case analysis in connection model
In this section we show that the static algorithms, ST 1 and ST 2 , are not competitive. Then
we show that the SW k algorithm is (k 1)-competitive. Therefore, our competitiveness study
suggests that for optimizing the worst case, one has to choose the sliding window algorithm with
a small window size k.
First, let's consider the two static strategies. For the ST 1 algorithm, we can pick a long
schedule which consists of only reads. Then the cost of the ST 1 algorithm is un-boundedly
higher than the cost of the optimal algorithm on this schedule (which is 0 if we keep a copy at
the MC). For the ST 2 algorithm, we can also pick a long schedule which consists of only writes.
Then the cost of the ST 2 algorithm on this schedule is also un-boundedly higher than the optimal
cost (which is 0 if we do not keep a copy at the MC). Therefore, the static algorithms, ST 1 and
are not competitive.
Theorem 4 The sliding-window algorithm SW k is tightly
We prove this by showing that for any schedule / of requests, COST SW k
is the number of read requests in / that occur immediately after a write
request. We will also exhibit a schedule / 0 for which COST SW k
Since it can be shown that the cost of an optimal off-line algorithm on a schedule / is N / , it
follows that SW k is tightly 1)-competitive. As before, we assume throughout the proof that
First we prove that COST SW k
1). Let / be a schedule consisting of
read and write requests. Let N / be the number of read requests in / that occur immediately after
a write request. We divide the schedule / into maximal blocks consisting of similar requests.
Formally, let r be the division of / into blocks such that the requests in any block
are all reads or they are all writes, and successive blocks have different requests.
It should be easy to see that the total number of read blocks in /, i.e. blocks that only
contain read requests, is less than or equal to (N / 1). Similarly, the total number of write
blocks in / is less than or equal to (N / 1). Now, we analyze the cost of read and write requests
separately. Consider any read block B i . It should be easy to see that only the first n+1 reads in
may each incur a connection. After the first n reads the window will definitely have more
reads than writes, and the algorithm will maintain two copies (consequently further reads in the
block do not cost any connections). Thus the cost of executing all the reads in B i is bounded
by (n 1). Hence the cost of all the reads in / is bounded above by (n 1). By a
similar argument, it can be shown that the cost of all the writes in a write block is bounded by
(n+ 1). As a consequence, the cost of all the writes in / is bounded by (n+ 1) \Delta (N
rearranging the terms, we
get COST SW k
To show that the above bound is tight, assume that initially there is a single copy of the
data item. Consider a schedule / 0 that starts with a block of read requests, ends with a block
of write requests, and in each block there are exactly k requests. It should be easy to see that
6 Message cost model
This section is divided into 4 subsections. In the first subsection we probabilistically analyze
the static algorithms, in the second we analyze SW 1 , and in the third we analyze the family of
sliding window algorithms SW k for k ? 1. 3 In each one of the first three subsections we study
the algorithm's expected cost first, then the average expected cost. We also study the relation
among the expected costs of all the static and dynamic algorithms; and the relation among the
average expected costs. In subsection 6.4, we study the worst case of all the algorithms.
Recall that in this model we assume that a data message cost is 1, and a control message
cost is !, where ! ranges from 0 to 1.
6.1 Probabilistic analysis of the static algorithms
For the ST 1 algorithm, the write does not require any communication, whereas the read costs
for the ST 2 algorithm, every write costs 1, the read costs 0. So,
3 As mentioned at the end of section 4, SW 1 is not simply SW k with 1. In this cost model this difference
in the algorithms results in a different analysis, thus the need for a separate subsection dedicated to the analysis
of SW 1 .
6.2 Probabilistic analysis of the SW 1 algorithm
First we derive the expected cost of a relevant request.
Theorem 5 The expected cost of the SW 1 algorithm is
Proof: For the SW 1 algorithm, a read that immediately follows a write costs
the control message that conveys the read request, and 1 for the data message); a write that
immediately follows a read costs an ! (the cost of a control message deallocating the copy at
the MC). No other relevant requests cost any communication. Therefore, the expected cost of a
request q is the expected cost of a read that immediately follows a write times the probability of
q being such a read, plus the expected cost of a write that immediately follows a read times the
probability of q being such a write, namely, EXP SW 1
In the next theorem we study the relation of the expected costs of three algorithms, i.e.,
('), and EXP SW 1
('). The results of this theorem is graphically illustrated
in

Figure

1.
Theorem 6 The expected costs EXP SW 1
('), and EXP ST 2
are related as follows,
depending on ' and !.
, then EXP ST 1
, then EXP SW 1
, then EXP ST 2
Proof: This is a straight-forward algebraic derivation, that uses equations 11, 13, and the fact
Now we are ready to consider the average expected cost.
Theorem 7 The average expected cost of the SW 1 algorithm is
and AV G SW 1
Proof: Equation 14 can be easily obtained from equation 13, based on the definition of the
average expected cost (equation 1). Since 0 - 1, we obtain 1+2\Delta!- 1- 1+!. From the
equations 12 in section 6.1, we conclude the theorem. 2
6.3 Probabilistic analysis of SW k
In this section we consider the SW k algorithms, for First, we derive the formula
of the expected cost for SW k . Then we show that for any k and for any ' the expected cost of
SW k is higher than the minimum of the expected costs of SW 1 , ST 1 , and ST 2 . Thus we conclude
that for a known fixed ', SW k is inferior to the other algorithms. Then we derive the formula
of the average expected cost for SW k . Then we show that SW k has the best average expected
cost for some k - 1, and we determine this optimal k as a function of !, the cost of a control
message.
Theorem 8 For every k ? 1, the expected cost of the SW k algorithm is
Consider a write request w. It costs a data message if there exists a copy at the MC
when the request is issued. The probability of having a copy at the MC is ff k . Additionally, if
the MC deallocates its copy as a result of this write, the write will necessitate a delete message
sent from the MC to the SC, It can be argued (and we omit the details) that this occurs if and
only if the sequence of k requests immediately preceding w, starts with a read and has exactly
writes. Therefore, the expected cost of w is
Now consider a read request r. It does not require communication if there is a copy at the
MC when the request is issued. Otherwise, it costs a control message for the request, and a data
message for the response. Thus, the expected cost of r is
Therefore, the expected cost of a request is the expected cost of a write times the probability
that the request is a write, plus the expected cost of a read times the probability that the request
is a read, namely, EXP SW k
A simple algebraic manipulation of the above expression leads to equation 15. 2
Theorem 9 For any ' and for any k ? 1, the expected cost of algorithm SW k is higher than
the expected cost of at least one of the algorithms SW 1 , ST 1 , and ST 2 . Namely, EXP SW k
(')g
In order to prove this theorem, we need the following three lemmas.
Lemma 1 For any k ? 1, if ' - 0:5, then EXP SW k
(').
Proof: From equations 11 and 15 we derive
decreases when k increases, and
From the definition of ff k (see equation 4), we can derive
are omitted). From this formula, we see that ff k+2 \Gamma ff k is
negative for all k - 1. Hence ff k decreases with k. As a consequence ff
for any k ? 1. 2
Lemma 3 For any k ? 1 and any ' ? 0:5,
, then EXP SW k
, then EXP SW k
(').
Proof: EXP SW k
equations 11 and 15) ff k
namely,
Base on the above inequality, it is easy to show that if
, then EXP SW k
Thus, we have proved the first claim of the lemma.
namely, EXP SW k
Based on the above inequality and lemma 2, it is easy to show that if ! -
, then EXP SW k
Proof of theorem 9: If ' - 0:5, then lemma 1 indicates that EXP SW k
(')g. The
theorem follows. 2
Now, let's consider the average expected cost of the SW k algorithms for k ? 1.
Theorem 10 For the SW k algorithm with window size k ? 1, the average expected cost is
Z 1EXP SW k
From the definition of ff k in section 5.2, equation 7 and equation 15, we can derive the
equation 16. The tedious intermediate derivation steps are omitted. 2
Corollary 2 For k ? 1, AV G SW k
decreases when k increases, and AV G SW k
This corollary is straight forward from equation 16. 2
In theorem 7 we have shown that the average expected cost of the SW 1 algorithm is better
(i.e. lower) than that of the static algorithm. In the following corollaries, we analyze when the
average expected cost of SW k (for k ? 1) is lower than the average expected cost of SW 1 based
on the two formulae 14 and 16. In corollary 3 below, we show that when ! - 0:4, the average
expected cost of SW k is always higher than that of SW 1 .
Corollary 3 If ! - 0:4, then AV G SW k
for any k ? 1.
Thus, by theorem 7 and corollary 2, we conclude this
corollary. 2
In the next corollary, we study the case where ! ? 0:4. We show that for a given ! ? 0:4,
there is some k 0 , such that if k - k 0 , then the average expected cost of SW k is lower than that
of SW 1 . The following figure illustrates the results of the corollaries 3 and 4. For example, if
only when k - 39, the SW k algorithm has a lower expected cost than that of
only when k - 7, the SW k algorithm has a lower expected cost than that
of SW 1 .
Corollary 4 If ! ? 0:4, then AV G SW k
for any k which satisfies
manipulation using equations 14 and 16. 2
6.4 Worst case in message model
In this section, we study the competitiveness of the algorithms ST 1 , ST 2 , and SW k for k - 1,
in the message cost model. The result for SW 1 is stated separately, since it is a special case
(see section 4). We conclude that the static algorithms are not competitive as is the case in the
connection model. Then we show that SW 1 is more competitive than SW k for k ? 1, and we
show that the competitiveness factor of the SW k algorithms deteriorates when k increases, thus
performs the best in the worst case.
As in the connection model, we can easily derive that the static algorithms are not competitive
in the message model.
Theorem 11 The algorithm SW 1 is tightly !)-competitive in the message cost model,
where !(! 1) is the ratio of control message cost to data message cost.
Similarly to the proof of theorem 4, we let N / be the number of reads in / that occur
immediately after a write, where / is an arbitrary schedule of requests. It is easy to see that
N / is the minimum cost to satisfy all the requests in /. Let r be the division of /
into blocks such that the requests in any block are all reads or they are all writes, and successive
blocks have different requests.
It should be easy to see that the total number of read blocks in / is less than or equal to
(N / +1), and a read block costs at most (1+!) since after the first read the mobile computer will
keep a copy of the data item. The total cost of reads is bounded by (N Similarly,
the total number of write blocks in / is less than or equal to (N / + 1), and a write block costs
only ! since the first write in the block will invalidate the copy at the MC. Thus, the total cost
of writes in / is bounded by (N
To show that the above bound is tight, assume that initially there is a single copy of the
data item. Consider a schedule / 0 that starts with a read request, ends with a write request,
and in each block there is exactly 1 request. It should be easy to see that COST SW k
Theorem 12 The algorithm SW k (for k ? 1) is tightly [(1 +!]-competitive in the
message cost model, where !(! 1) is the ratio of control message cost to data message cost.
Similarly to the proofs of theorems 4 and 11, we prove that for any schedule / of
requests, COST SW k
is the
number of read requests in / that occur immediately after a write request. We will also exhibit
a schedule / 0 for which COST SW k
is a constant.
Since it can be shown that the cost of an optimal off-line algorithm on / is N / , it follows that
SW k is tightly [(1 !]-competitive. As before, we assume throughout the proof
that
Let / be a schedule consisting of read and write requests. We prove that COST SW k
We divide the schedule / into maximal
blocks consisting of similar requests. Formally, let r be the division of / into blocks
such that the requests in any block are all reads or they are all writes, and successive blocks have
different requests.
It should be easy to see that the total number of read blocks in /, i.e. blocks that only
contain read requests, is less than or equal to (N / 1). Similarly, the total number of write
blocks in / is less than or equal to (N / 1). Now, we analyze the cost of read and write
requests separately. Consider any read block B i . It should be easy to see that only the first
may each cost (1 !). After the first n reads the window will definitely
have more reads than writes, and the algorithm will maintain two copies and further reads
in the block do not cost any communication. Thus the cost of executing all the reads in B i
is bounded by (n Hence the cost of all the reads in / is bounded above by
1). Now consider a . It is easy to see that B j will cost
at most (n data message, since after the first n the window will definitely have
more writes than reads and the copy at the MC will be deallocated, and this deallocation may
cost this block an additional control message. Thus, the cost of a write block is bounded by
(n+1+!). As a consequence, the cost of all the writes in / is bounded by (n+1+!) \Delta (N
Hence, COST SW k
rearranging the terms, we get COST SW k
To show that the above bound is tight, assume that initially there is a single copy of the
data item. Consider a schedule / 0 that starts with a block of read requests, ends with a block
of write requests, and in each block there are exactly k requests. It should be easy to see that
Extensions
In this section we discuss various extensions to the previous methods. In particular, in the first
subsection we show how to modify the static algorithms to make them competitive, and in the
second subsection we discuss extensions of the algorithm to optimize the case where multiple
data items can be read and written in a single operation.
7.1 Modifications to the Static Methods
We have presented two simple static methods that use the one-copy and two-copies schemes.
The static methods can be chosen if the value of ' is known in advance. For example, in the
connection model, the static method using a single copy at the stationary computer has the
best expected cost if ' ? 0:5. Similarly, the static method using the two-copy scheme has the
best expected cost when ' - 0:5. However, the static methods do not have a good worst case
behavior, i.e. they are not competitive. For example, a static method using a single copy will
incur a high cost on a sequence of requests consisting of only reads from the mobile computer.
This cost can be arbitrarily large, depending on the length of the sequence. Even though such a
sequence is highly improbable, it can occur with nonzero probability.
We can overcome this problem by simple modifications to the static methods, that actually
make them dynamic. For example, we can modify the one-copy static method as follows. It
will normally use the one-copy scheme until m consecutive reads occur; then it changes to the
two-copies scheme and uses this scheme until the next write. Then it reverts back to one-copy
scheme and repeats this process. We refer to this algorithm as T1m . It can be shown that T1m
1-competitive and that its expected cost is in the connection
model. Note that the second term is the additional expected cost over the static method (it can
be shown that for each ' ? 0:5 T1m has a lower expected cost than SWm and they are both
equally competitive). This is the price of competitiveness. Thus, if we know that ' ? 0:5 then
we can choose the T1m algorithm instead of ST 1 , for an appropriate value of m.
Similarly, we can modify the ST 2 algorithm to obtain the T2m algorithm that has almost the
same expected cost as ST 2 , and is (m
7.2 Multiple Data Items
In this paper we have addressed the problem of choosing an allocation method for a single data
items. These results can be extended to the case where multiple data items can be read and
written in a single operation.
We will sketch an algorithm that gives an optimal static allocation method, in the connection
model, for multiple data items, when the frequencies of operations on the data items are known
in advance. Assume that multiple data items can be remotely read in one connection; similarly
for the remote writes. We present the algorithm for the case when we have only two data items x
and y. This can be generalized to more than two data items. Also, we discuss how this approach
can be extended to the dynamic window based algorithms.
Assume that we have two data items x and y. We classify the read operations into three
classes. reads of x only, reads of y only, and reads that access both x and y. We assume that
these three different reads occur according to independent Poisson distributions with frequencies
respectively. We classify the writes similarly and assume that these writes occur
with frequencies -w;x ; -w;y and -w;  , respectively. It is to be noted that - denote the
frequencies of joint reads and writes respectively. Now, we have four possible allocation methods
for x and y: ST 1 (both x and y have only one copy), ST 2 ( both x and y have two copies), ST 1;2
has one copy and y has one copy) and ST 2;1 (x has two copies and y has only one). For each of
these allocation methods we can obtain the expected cost of a single operation using the above
frequencies, and then choose the one with the lowest expected cost. For example, the expected
cost for ST 1 is (- r;x and that of ST 1;2 is (- r;x
the sum of all the read and write frequencies. The above method can be generalized to any finite
set of data items. We need the frequencies of various joint operations on these data items.
To use the method given above we need to know the frequencies of various operations in
advance. If these frequencies are not known in advance, then we can use the window based
approach that dynamically calculates these frequencies. In this case, we need to keep track of
the number of operations of different kind (i.e. the joint/exclusive read/write operations for
multiple data items) in the window. From these numbers, we can calculate the frequencies of
these operations, compute their expected costs (similar to the static methods given in the previous
using these frequencies, and choose an appropriate future allocation method. To avoid
excessive overhead, this recomputation can be done periodically instead of after each operation.
Future work will address the performance analysis of this method.
8 Comparison with Relevant Literature
As far as we know this is the first paper to study the communication cost of static and dynamic
allocation in distributed systems using both, average case and worst case analysis. There are two
bodies of relevant work, each of which is discussed in one of the following two subsections. In the
first subsection we compare this paper with database literature on data allocation in distributed
systems. In the second subsection we compare this paper to literature on caching and distributed
virtual memory.
8.1 Data allocation in distributed systems
Data allocation in distributed systems is either static or dynamic. In [35] and [36], we considered
dynamic data allocation algorithms, and we analyzed them using the notion of convergence,
which is different than the measures used in this paper, namely expected case and worst case.
Additionally, the algorithms in those works are different than the ones discussed here. Further-
more, in [35] and [36] we did not consider static allocation algorithms, and we did not consider
the connection cost model.
Other dynamic data allocation algorithms were introduced in [22] and [23]. Both works
analyze dynamic data allocation in the worst case only. Actually, the SW 1 algorithm was first
analyzed in [23]. However, the model there requires a minimum of two copies in the system,
for availability purposes. Thus even for the worst case the results are different. In contrast, in
this paper we assume that availability constraints are handled exclusively within the stationary
system, independently of the mobile computers.
There has also been work addressing dynamic data allocation algorithms in [9]. This work also
addresses the worst case only. Additionally, the model there does not allow concurrent requests,
and it requires centralized decision making by a processor that is aware of all the requests in the
network. In contrast, our algorithms are distributed, and allow concurrent read-write requests.
Static allocation was studied in [37, 14]. These works address the following file-allocation
problem. They assume that the read-write pattern at each processor is known a priori or it
can be estimated, and they find the optimal static allocation scheme. However, works on the
file-allocation problem do not compare static and dynamic allocation, and they do not quantify
the cost penalty if the read-write pattern deviates from the estimate.
Many works on the data replication problem (such as [4, 6, 11, 13, 17, 21, 34]) and on file
systems (such as CODA [30, 33]) address solely the availability aspect, namely how to ensure
availability of a data item in the presence of failures. In contrast, in this paper we addressed the
communication cost issue.
The works done by Alonso and Ganguly in [5, 20] are also related to the present paper in
the sense that they also address the optimization issue for mobile computers. However, their
optimization objective is energy, whereas ours is communication.
The work on broadcast disks ([2]) also addresses peformance issues related to push/pull of
data in a mobile computing environment. However, this work assumes read-only data items and
it does not perform the type of analytical performance evaluation present in this paper.
8.2 Caching and virtual memory
In the computer architecture and operating systems literature there are studies of two subjects
related to dynamic data allocation, namely caching and distributed virtual memory (see [1, 3, 7,
However, there are several important differences between Caching and Distributed Virtual
Memory (CDVM) on one hand, and replicated data in distributed systems on the other. There-
fore, our results have not been obtained previously. First, many of the CDVM methods do
not focus on the communication cost alone, but consider the collection of factors that determine
performance; the complexity of the resulting problem dictates that their analysis is either experimental
or it uses simulation. In contrast, in this paper we assumed that since in mobile computing
wireless communication involves an immediate out-of-pocket expense, the optimization of wireless
communication is the sole caching objective; and we performed a thorough analytical cost
evaluation.
Second, in CDVM the size of the cache is assumed to be limited. Thus, the important issues
in CDVM literature are cache utilization, and the page replacement strategy (e.g. LRU, MRU,
etc.), namely which page to replace in the cache when the cache is full and a new page has to
be brought in. In other words, in contrast to replicated data in distributed systems, which may
reside on secondary and even tertiary storage, in CDVM a page may be deleted from the cache
as a results of limited storage. One may argue whether or not limited storage is a major issue in
distributed databases, however, in this paper we assumed that storage at the mobile computer
is abundant.
There have been some CDVM methods which consider communication cost as one of the
optimization criteria (e.g. TreadMarks [26]). However, they do not use dynamic allocation
schemes.
9 Conclusions
In this paper we have considered several data allocation algorithms for mobile computers. In
particular, we have considered the one-copy and the two-copies allocation schemes. We have
investigated static and dynamic allocation methods using the above schemes. In a static method
the allocation scheme remains unchanged throughout the execution. In a dynamic method the
allocation scheme changes dynamically based on a window consisting of the last k requests;
if in the window there are more reads at the mobile computer than writes at the stationary
computer, then we use the two-copy scheme, otherwise we use the one-copy scheme. We get
different dynamic methods for different values of k. For the dynamic method is simply the
classic write-invalidate protocol.
We have considered two cost models - the connection model and the message model. In the
connection model, the cost is measured in terms of the number of (wireless telephone) connec-
tions, where as in the message model the cost is measured in terms of the number of control and
data messages.
We have considered three different measures- expected cost, average expected cost, and the
worst case cost which uses the notion of competitiveness. Roughly speaking, an algorithm A
is said to be k-competitive if for every sequence s of read-write requests the cost of A on the
sequence s is at most k times the cost of an ideal off-line algorithm on s which knows s in advance.
An algorithm A is said to be competitive, if for some k ? 0, A is k-competitive. The expected
cost is the standard expected cost per request assuming fixed probabilistic distributions for reads
and writes. We believe that an allocation method should be chosen based on the expected cost
as well as the worst case cost. Specifically, we think that an allocation method should be chosen
to minimize the expected cost, provided that it has some bound on the worst case behavior.
Now we explain the difference between the expected cost and the average expected cost. We
have assumed that both, reads at the mobile computer and writes at the stationary computer,
occur according to independent Poisson distributions with frequencies - r and -w respectively.
When the values of - r and -w are known (more specifically, when the value of
-r+-w
is known), then an allocation method should be chosen based on the expected cost and the
competitiveness. However, when ' varies and it is equally likely to have any value between 0 and
1, then an allocation method should be chosen based on the average expected cost (in addition
to competitiveness). The average expected cost is the integral of the expected cost over ' from
0 to 1. An allocation method with a lower average expected cost will have a lower average cost
per request, in a sequence of requests in which the frequencies of reads and writes vary over
time. Furthermore, the average expected cost can also provide an insight and/or a measure for
selecting an allocation method in the case when ' is unknown, but it is equally likely to have
any value between 0 and 1 4 .
In the connection model, if ' is greater than 0:5, i.e., the read frequency is lower than the write
frequency, then the static allocation method using only one copy at the stationary computer has
4 If ' is not uniformly distributed, then the average expected cost should be defined as the integral of the
expected cost multiplied by the density function for '.
the best expected cost. Similarly, if ' is smaller than 0:5, then the static allocation method using
one copy at the stationary computer and one at the mobile computer has the best expected cost.
When - r and -w change over time (i.e. ' changes over time), then one of the dynamic
methods SW k for an appropriate value of k should be chosen. This is due to the fact that the
average expected cost of the SW k algorithms is lower than either one of the static methods. The
value of the window size k should be chosen to strike a balance between the average expected
cost (which decreases as k increases, see equation 6) and competitiveness (the SW k algorithm
1)-competitive, thus competitiveness becomes worse as k increases). For example, for
9 the sliding-window algorithm will have an average expected cost that is within 10% of
the optimum, and in the worst case will be at most 10 times worse than the optimum offline
algorithm.
In the message model, the static allocation methods are still not competitive; and the dynamic
allocation methods SW k are again competitive, although with a different competitiveness factor.
For a given ', the expected cost of one of the three methods ST 1 , ST 2 and SW 1 is lowest; the
particular one depends on the values of ' and ! (the ratio between the control message cost and
the data message cost). The lowest expected-cost algorithm as a function of ' and ! is given in
figure 1.
If ' is unknown or it varies over time, then one of the sliding window methods provides the
optimal average expected cost. The particular one depends on the value of !. If ! - 0:4 then
the SW 1 algorithm should be chosen as it has the least average expected cost; for other values
of !, the higher the value of k the lower the average expected cost of the SW k algorithm (see
figure 2). Again, the appropriate value of k should be chosen to strike a balance between average
expected cost and competitiveness.
The data allocation methods and the results of this paper pertain to applications where the
data items accessed by the various mobile computers are mostly disjoint, and the read requests
must be satisfied by the most-up-to-date version of the data item. For applications that do not
satisfy these assumptions, techniques that use data broadcasting and batching of updates may
be appropriate, and our results need to be extended. This is the subject of future work.

ACKNOWLEDGEMENT

We wish to thank the referees for their insightful comments.



--R

"An Evaluation of Cache Coherence Solutions in Shared-Bus Multiprocessors"
"Balancing Push and Pull for Data Broadcast"
"An Evaluation of Directory Schemes for Cache Coherence"
"Multidimensional Voting"
"Query Optimization for Energy Efficiency in Mobile Enviro- ments"
"The Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data"
"Adaptive Software Cache Management for Distributed Shared Memory Architectures"
shared memory based on type-specific memory coherence"
"Competitive Algorithms for Distributed Data Management"
"Replication and Mobility"
"The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data"
"Data Caching Tradeoffs in Client-Server BDMS Architectures"
"Distributed concurrency control performance: A study of algorithms, distribution and replication"

"A Characterization of Sharing in Parallel Programs and Its Application to Coherency Protocol Evaluation"
"Evaluating the Performance of Four Snooping Cache Coherency Protocols"
"Achieving Robustness in Distributed Database Systems"
"Competitive paging algorithms"
"Client data Caching: A foundation for high performance object database systems"
"Query Optimization in Mobile Enviroments"
"Weighted Voting for Replicated Data"
"A Competitive Dynamic Data Replication Algorithm"
"Dynamic Allocation in Distributed System and Mobile Com- puters"
"Querying in highly mobile distributed environments"
"Shared Virtual Memory on Loosely Coupled Multiprocessors"
"TreadMarks: Distributed Shared Memory on Standard Workstations and Operating Systems"
"Memory Coherence in Shared Virtual memory systems"
"Synchronization with Multiprocessor Caches"
"Competitive Snoopy Caching"
"Disconnected Operation in the Coda File System"
"Disk Cache Performance for Distributed Systems"
"Competitive algorithms for online problems"
"Coda: A Highly Available File System for a Distributed Workstation Environment"
"A Majority Consensus Approach to Concurrency Control for Multiple Copy Database"
"Distributed Algorithms for Dynamic Replication of Data"
"An Algorithm for Dynamic Data Distribution"
"The Multicast Policy and Its Relationship to Replicated Data Placement"
"Cache Consistency and Concurrency Control in a Client/Server DBMS Architecture"
--TR

--CTR
Sandeep K. S. Gupta , Pradip K. Srimani, Data management in wireless mobile environments, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
Wang , Ing-Ray Chen , Chih-Ping Chu , I-Ling Yen, Replicated Object Management with Periodic Maintenance in Mobile Wireless Systems, Wireless Personal Communications: An International Journal, v.28 n.1, p.17-33, January 2004
Ycel Saygin , zgr Ulusoy, Exploiting Data Mining Techniques for Broadcasting Data in Mobile Computing Environments, IEEE Transactions on Knowledge and Data Engineering, v.14 n.6, p.1387-1399, November 2002
James Jayaputera , David Taniar, Data retrieval for location-dependent queries in a multi-cell wireless environment, Mobile Information Systems, v.1 n.2, p.91-108, April 2005
Isabel Cruz , Ashfaq Khokhar , Bing Liu , Prasad Sistla , Ouri Wolfson , Clement Yu, Research activities in database management and information retrieval at University of Illinois at Chicago, ACM SIGMOD Record, v.31 n.3, September 2002
W. J. Lin , B. Veeravalli, A dynamic object allocation and replication algorithm for distributed systems with centralized control, International Journal of Computers and Applications, v.28 n.1, p.26-34, January 2006
Bharadwaj Veeravalli, Network Caching Strategies for a Shared Data Distribution for a Predefined Service Demand Sequence, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1487-1497, November
Bharadwaj Veeravalli, Network Caching Strategies for a Shared Data Distribution for a Predefined Service Demand Sequence, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1487-1497, November
Anurag Kahol , Sumit Khurana , Sandeep K.S. Gupta , Pradip K. Srimani, A Strategy to Manage Cache Consistency in a Disconnected Distributed Environment, IEEE Transactions on Parallel and Distributed Systems, v.12 n.7, p.686-700, July 2001
Xiao-Hui Lin , Yu-Kwong Kwok , Vincent K. N. Lau, A Quantitative Comparison of Ad Hoc Routing Protocols with and without Channel Adaptation, IEEE Transactions on Mobile Computing, v.4 n.2, p.111-128, March 2005
Sandeep K. S. Gupta , Goran Konjevod , Georgios Varsamopoulos, A theoretical study of optimization techniques used in registration area based location management: models and online algorithms, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
probabilistic analysis;mobile computing;communication cost;wireless communication;dynamic data allocation;caching