2. THE STATE TRANSITION MODEL
Let a state be defined by a vector containing the
age of the stashed copies for all clients of the
system. In particular, let U = (u[sub1], u[sub2],
..., u[subn]), where u[subi] is the age of the copy
stashed on client i is an element of D, and 0 less
than or equal to u[subi] < t[subi].
Now let U = {u[sub1], u[sub2], ..., u[subn]} and
V = {v[sub1], v[sub2], ..., v[subn]} be two valid
states. There then exists a transition from U to
V if state V is such that:
Multiple line equation(s) can not be represented
in ASCII text.
In expression (1), in the first case, the copy
for client i is t[subi] -1 time units old; then
it must be quickly replaced by a fresh copy. On
the other hand, if the copy has not yet reached
the age of t[subi] - 1 units it can either get one
unit older or be replaced by a new copy. This corresponds
to the second case of expression (1).
We now define the set of states Ns and the set
of transitions M that correspond, respectively,
to the vertices and edges of the state transition
graph G(N[subs], M). All edges are directed, and
the cost of a transition is given by the cost of
a "stashing tree" defined by the arrival
state. A stashing tree corresponds to a Steiner
tree linking the server and the clients that have
a new copy in the arrival state. Note that if all
the components of the arrival state vector are nonnull,
then the transition cost must be zero (all copies
are left to age one more version or one more instant
of time). Conversely, there must be at least one
client to be restashed on the arrival state for
the transition cost to be nonnull. To clarify these
concepts we invite the reader to examine a simple
network example presented in Figure 3 and its corresponding
state transition graph in Figure 4. In the latter,
the nodes represent the states (a particular state
i is E[subi]), whereas the directed links represent
the transitions. Let us pick two particular states
with nonnull transitions, E[sub5] and E[sub4]. The
cost of the transition from E[sub5] to E[sub4] is
5, which corresponds to the stashing tree cost for
state E[sub4]. This is the cost of the Steiner tree
to reach client d[sub2] in the network example shown
in Figure 3. We now examine the case of the transition
from E[sub5] to E[sub6]. State E[sub6] does not
involve the stashing of a new copy; therefore the
transition to that state has a cost of zero.
We have now defined the vertices, the transitions,
and the costs of the state transition graph. In
what follows it will be proved that this graph is
strongly connected. Therefore, for a finite interval
of time delta, finding the best stashing policy
is equivalent to finding the minimum cost path of
length delta in the state transition graph. When
a steady-state solution is desired, it has been
proved (Sanso and Soumis 1993) that such a solution
corresponds to a path made up of a transitory path
followed by the cycle of minimal mean cost. A polynomial
algorithm for finding the minimal mean cost cycle
can be found in Karp (1978).
Connectedness of the State Transition Graph
To prove that the state transition graph is strongly
connected we first need to formally define a "new"
state. We define a "new" state o as a
state in which all clients are restashed, that is,
o = (0, 0, ..., 0). This definition is used in the
following lemma.
Lemma 1. There always exists a path of length k
from state o to any state U is an element of N[subs],
U not equal to o such that k = max[subiis an element
ofD]{u[subi]}.
Proof. Let Q[sub1] be a subset of states such that
V is an element of Q[sub1] equivalence max[subiis
an element ofD]{v[subi]} = 1. Any state V is an
element of Q[sub1] can be reached from o in one
transition. Let Q[sub2] be a subset of states such
that W is an element of Q[sub2] equivalence max[subiis
an element ofD]{w[subi]} = 2. Any state W is an
element of Q[sub2] is one transition away from at
least one state in Q[sub1], and therefore two transitions
away from state o. Let Q[subk] be the set of states
so that
Multiple line equation(s) can not be represented
in ASCII text.
Then state U is an element of Q[subK] is one transition
away from at least one state in Q[subk-1] and, since
any state in Q[subk-1] is k - 1 transitions from
o, U is k transitions from o.
Theorem 1. The state transition graph G(N[subs],
M) is strongly connected.
Proof. For an oriented graph to be strongly connected
there must be a path between each pair of vertices.
We have proven, in Lemma 1, that any state can be
reached from state o. Conversely, state o can be
reached from any state, since clients can always
be restashed regardless of the age of their copies.
Therefore, it is always possible to reach any state
using a path through state o. Thus, a path exists
between any given pair of states.
Size of the State Transition Graph
Before providing insight into the number of states
and transitions in a graph, we need to introduce
the definition of class. Two states are said to
be in the same class if and only if they share the
same group of newly stashed clients. In other words,
states U and V belong to the same class k if and
only if
Multiple line equation(s) can not be represented
in ASCII text.
We associate two different types of sets with the
notion of class. OMEGA[sub] corresponds to the set
of states belonging to class k, whereas J[subk]
corresponds to the set of clients being stashed
for every state that belongs to OMEGA[subk]. To
illustrate these concepts in an example in Figure
3 we show a simple network, and in Figure 4 its
state transition graph.
In these examples we see four classes of states
with the following characteristics:
Multiple line equation(s) can not be represented
in ASCII text.
The reader can verify that there are two states,
E[sub2] and E[sub6], that can be reached without
new stashing and therefore belong to the same class,
and that the set of clients stashed for these states
is empty. In addition, there are two other states,
E[sub3] and E[sub5], for which only client 1 is
stashed; these two states form a class for which
the client set is made up of client 1. The other
classes in the example may be similarly described.
Theorem 2. The number of states |N[subs| equals
PI[subi epsilon D] t[subi], and the number of transitions
|M| is given by PI[subi epsilon D] (2t[subi] - 1).
Proof. Since a state is defined as a vector of
the ages of the copies stashed in every local device,
it is straightforward to see that the number of
states equals the product of all predicate requirements.
To track the number of transitions, we first establish
the number of transitions entering the states belonging
to a class. More formally, let T[subk](U) be the
number of transitions entering a state U belonging
to class k, that is, U is an element of OMEGA[subk],
and let |OMEGA[subk]| be the number of states belonging
to class k. Then the expression for T[subk](U) and
|OMEGA[subk]| is:
Multiple line equation(s) can not be represented
in ASCII text.
We remind the reader that D is the set of all clients
while J[subk] is the set of the clients that are
restashed for the states belonging to class k. Thus,
D - J[subk] represents those clients that are not
restashed.
Another measure of interest is the number of classes
in the network. Let K be the set of classes for
a given network. To find an expression for |K|,
the number of classes in K, we first partition the
set of clients D into two disjoint subsets D[sub1]
and D[sub2], where:
Multiple line equation(s) can not be represented
in ASCII text.
The number of classes is given by:
Multiple line equation(s) can not be represented
in ASCII text.
The total number of transitions |M| is given by
the sum over all classes of the number of states
belonging to a class by the number of transitions
entering each state:
Multiple line equation(s) can not be represented
in ASCII text.
Expression (6) can be simplified by successively
factoring terms t[sub1], t[sub1] - 1, ..., yielding:
Multiple line equation(s) can not be represented
in ASCII text.
