Wolfgang W. Bein / Lawrence L. Larmore: Trackless Servers: Lesson II

Trackless Servers: Lesson II. Trackless Work Functions.

The Trackless Server Problem. the trackless 2-server problem is defined to be the 2-server problem, where the algorithm is not only on-line, but may not keep track of any point in the M unless it has a server there. This means that, when request r_t is announced, and the algorithms has servers at r_{t-1} and s_{t-1}, it is told the distances r_{t-1}r_t and s_{t-1}r_t, and that is all. It may not ask what the distance is between r_t and r_j for some j < n-1, unless it so happens that s_{t-1} = r_j. The trackless k-server problem for any k is defined similarly. It is clear that the trackless server problem is at least as hard as the server problem. That is, if C_k is the competitiveness of the k-server problem and T_k is the competitiveness of the trackless k-server problem, then C_k <= T_k. The Trackless Work Function. Given a sequence of requests and our service of that sequence, it is possible, using dynamic programming, for us to calculate the adversary's cost, under the assumption that the adversary will make those choices which minimize its total cost. The trackless work function is simply a a function showing the partial calculations of that dynamic program at a particular step. Informal Definition. The trackless work function at step t is a real-valued function tau_t(x,y). The domain of tau_t is D_t, the set of ordered pairs (x,y) such that the triple {d_t,x,y} is P-permissible. (Recall that d_t is the distance between our two servers at time t.) The value tau_t(x,y) is the minimum cost that the adversary could have expended, up to and including step t, provided that pr = x and ps = y, where p is the position of the adversary's other server. Offset. To simplify calculations, we also offset trackless work functions, by subtracting a constant which makes the minimum value zero. Example. Assume that P is the property of having integer distances not greater than 2. (That is, a metric space is P if and only if, for any two distinct points p,q in M, pq is either 1 or 2.) The table on the left illustrates one example of a trackless work function for the 2-server problem on P metric spaces. In this example, d = 1, which means that D, the domain of tau, has cardinality 6. Why exactly 6?

Trackless Servers: Lesson II. Trackless Work Functions.

The Trackless Server Problem. the trackless 2-server problem is defined to be the 2-server problem, where the algorithm is not only on-line, but may not keep track of any point in the M unless it has a server there. This means that, when request r_t is announced, and the algorithms has servers at r_{t-1} and s_{t-1}, it is told the distances r_{t-1}r_t and s_{t-1}r_t, and that is all. It may not ask what the distance is between r_t and r_j for some j < n-1, unless it so happens that s_{t-1} = r_j. The trackless k-server problem for any k is defined similarly.

It is clear that the trackless server problem is at least as hard as the server problem. That is, if C_k is the competitiveness of the k-server problem and T_k is the competitiveness of the trackless k-server problem, then C_k <= T_k.

The Trackless Work Function. Given a sequence of requests and our service of that sequence, it is possible, using dynamic programming, for us to calculate the adversary's cost, under the assumption that the adversary will make those choices which minimize its total cost. The trackless work function is simply a a function showing the partial calculations of that dynamic program at a particular step.

Informal Definition. The trackless work function at step t is a real-valued function tau_t(x,y). The domain of tau_t is D_t, the set of ordered pairs (x,y) such that the triple {d_t,x,y} is P-permissible. (Recall that d_t is the distance between our two servers at time t.) The value tau_t(x,y) is the minimum cost that the adversary could have expended, up to and including step t, provided that pr = x and ps = y, where p is the position of the adversary's other server.

Offset. To simplify calculations, we also offset trackless work functions, by subtracting a constant which makes the minimum value zero.

Example. Assume that P is the property of having integer distances not greater than 2. (That is, a metric space is P if and only if, for any two distinct points p,q in M, pq is either 1 or 2.)

The table on the left illustrates one example of a trackless work function for the 2-server problem on P metric spaces. In this example, d = 1, which means that D, the domain of tau, has cardinality 6. Why exactly 6?

Back to Table of Contents

Closures of Metric Spaces.

Previous Lesson

Next Lesson

Theorem: The trackless work function contains all information that can be useful to a trackless on-line algorithm.
That is, if A_1 is any trackless on-line algorithm for the 2-server problem on P metric spaces, then there is another trackless on-line algorithm for the same problem, A_2, such that

After t steps, A_2 remembers nothing about the past except for the trackless work function.

If C_1 and C_2 are the competitivenesses of A_1 and A_2, respectively, then C_2 <= C_1.
Proof.
The diagram is contained within a square where rows and columns are labeled 0, 1, ... N, where N is the maximum permitted distance in M. As previously stated, N = 2 in this example. The domain D is the set of ordered pairs corresponding to the cells that are a light color (white, yellow, green, or red). The value of d is 1 in this example, so there are six light-colored cells.
There is a natural metric on D. Let M be the actual P metric space, and let r and s be the locations of our servers in M. Let P be the function from M to D defined as follows: for any point q in M, define P(q) = (rq,sq). If M is a universal P metric space, then P is onto D. Since we cannot know how large M is, we will always assume that M is universal, since that is the worst case.
The metric on D is defined as follows. If (x,y) and (x',y') are points in D, then the distance from (x,y) to (x',y') is the minimum possible value of the distance qq', where q and q' are chosen to be points in M such that P(q) = (x,y) and P(q') = (x',y').
Exercise 2.2: Find the distance between (2,0) and (1,1) in D. Answer.
We might ask now what will happen if we relax the property P .
Exercise 2.2: If P is Distance Bounded by N, that is, the distances between two points could be any positive real number, but not greater than N, what will D be? Answer.
Exercise 2.3: Prove that the trackless work function is 1-Lipschitz on D, that is, tau(x,y) - tau(x',y') is less than or equal to the distance from (x,y) to (x',y'). Proof.
Exercise 2.4: What is D, if P is Unrestricted? Answer.
We have two servers in this metric space. One of them is at r, the point that was last requested, and the other is at some other point, which we call s.
Each light background cell in the matrix (usually white background, but also including red, green, or yellow background) represents a set of points in M. If the cell is blank (and has dark background), that set is necessarily empty.
If the coordinates of a cell are (x,y), that means that the cell represents all points in M which are distance x from r and distance y from s.
Exercise 2.5: What is the distance between our servers, in the example illustrated? Answer
In the diagram, the cell colored yellow has coordinates (0,1) and represents just one point, namely r. The cell colored green has coordinates (0,1) and represents just one point, namely s. The cell with coordinates (2,1) represents the set of all points of M that have distance 2 from r and 1 from s. The cell with coordinates (0,2) is empty, because no point in M could have distance 0 from r and 2 from s, because this would violate the triangle inequality. This representation is the mapping P from M to the D, the set of cells of the diagram.
We assume that M is universal . This means that, given any finite set of points in M, say x_1, ... x_k, and given any finite set of possible distances d_1, ... d_k (recall that this means that each d_i must be a non-negative integer not greater than N), then M contains a point y which has distance d_i from each x_i, unless there is a simple proof involving the triangle inequality that shows that no such y exists. That means, y exists if and only if, for each i and each j:
|d_i-d_j| < d_ij < d_i+d_j where d_ij is the distance from x_i to x_j.
Restricting our attention only to universal spaces does not affect the analysis of the general trackless server problem. Further discussion of universal spaces.
Exercise 2.6. Is it true that the trackless workfunction on a cell is the minimum value of the workfunction over all points in M which map to that cell? Answer
In our calculations, we need a standard naming system for trackless work functions. The name of the one illustrated in the table is 2.1.100011. The first numeral is the N, the maximum permitted distance. The second is d, the distance from r to s. The other six numerals are the values of the trackless workfunction in canonical order, defined by the following ordering on cell positions (x,y):
1. If max(a,b) < max(c,d), then (a,b) < (c,d).
2. Otherwise, if a < c, then (a,b) < (c,d).
3. Otherwise, if d < b, then (a,b) < (c,d). (Yes, it's backwards!)
For example, the canonical order of the cells in the diagram above is:
(0,1) < (1,1) < (1,0) < (1,2) < (2,2) < (2,1)



Theorem: The trackless work function contains all information that can be useful to a trackless on-line algorithm. That is, if A_1 is any trackless on-line algorithm for the 2-server problem on P metric spaces, then there is another trackless on-line algorithm for the same problem, A_2, such that After t steps, A_2 remembers nothing about the past except for the trackless work function. If C_1 and C_2 are the competitivenesses of A_1 and A_2, respectively, then C_2 <= C_1. Proof. The diagram is contained within a square where rows and columns are labeled 0, 1, ... N, where N is the maximum permitted distance in M. As previously stated, N = 2 in this example. The domain D is the set of ordered pairs corresponding to the cells that are a light color (white, yellow, green, or red). The value of d is 1 in this example, so there are six light-colored cells. There is a natural metric on D. Let M be the actual P metric space, and let r and s be the locations of our servers in M. Let P be the function from M to D defined as follows: for any point q in M, define P(q) = (rq,sq). If M is a universal P metric space, then P is onto D. Since we cannot know how large M is, we will always assume that M is universal, since that is the worst case. The metric on D is defined as follows. If (x,y) and (x',y') are points in D, then the distance from (x,y) to (x',y') is the minimum possible value of the distance qq', where q and q' are chosen to be points in M such that P(q) = (x,y) and P(q') = (x',y'). Exercise 2.2: Find the distance between (2,0) and (1,1) in D. Answer. We might ask now what will happen if we relax the property P . Exercise 2.2: If P is Distance Bounded by N, that is, the distances between two points could be any positive real number, but not greater than N, what will D be? Answer. Exercise 2.3: Prove that the trackless work function is 1-Lipschitz on D, that is, tau(x,y) - tau(x',y') is less than or equal to the distance from (x,y) to (x',y'). Proof. Exercise 2.4: What is D, if P is Unrestricted? Answer. We have two servers in this metric space. One of them is at r, the point that was last requested, and the other is at some other point, which we call s. Each light background cell in the matrix (usually white background, but also including red, green, or yellow background) represents a set of points in M. If the cell is blank (and has dark background), that set is necessarily empty. If the coordinates of a cell are (x,y), that means that the cell represents all points in M which are distance x from r and distance y from s. Exercise 2.5: What is the distance between our servers, in the example illustrated? Answer In the diagram, the cell colored yellow has coordinates (0,1) and represents just one point, namely r. The cell colored green has coordinates (0,1) and represents just one point, namely s. The cell with coordinates (2,1) represents the set of all points of M that have distance 2 from r and 1 from s. The cell with coordinates (0,2) is empty, because no point in M could have distance 0 from r and 2 from s, because this would violate the triangle inequality. This representation is the mapping P from M to the D, the set of cells of the diagram. We assume that M is universal . This means that, given any finite set of points in M, say x_1, ... x_k, and given any finite set of possible distances d_1, ... d_k (recall that this means that each d_i must be a non-negative integer not greater than N), then M contains a point y which has distance d_i from each x_i, unless there is a simple proof involving the triangle inequality that shows that no such y exists. That means, y exists if and only if, for each i and each j: \|d_i-d_j\| < d_ij < d_i+d_j where d_ij is the distance from x_i to x_j. Restricting our attention only to universal spaces does not affect the analysis of the general trackless server problem. Further discussion of universal spaces. Exercise 2.6. Is it true that the trackless workfunction on a cell is the minimum value of the workfunction over all points in M which map to that cell? Answer In our calculations, we need a standard naming system for trackless work functions. The name of the one illustrated in the table is 2.1.100011. The first numeral is the N, the maximum permitted distance. The second is d, the distance from r to s. The other six numerals are the values of the trackless workfunction in canonical order, defined by the following ordering on cell positions (x,y): 1. If max(a,b) < max(c,d), then (a,b) < (c,d). 2. Otherwise, if a < c, then (a,b) < (c,d). 3. Otherwise, if d < b, then (a,b) < (c,d). (Yes, it's backwards!) For example, the canonical order of the cells in the diagram above is: (0,1) < (1,1) < (1,0) < (1,2) < (2,2) < (2,1)

This is the diagram of a trackless work function. It contains all the information that any trackless 2-server algorithm can use at any given time. This particular diagram illustrates Trackless Workfunction 2.1.100011
dist
to
s 2
0 1

1 1 0 1

0
0

0 1 2

dist to r

This is the diagram of a trackless work function. It contains all the information that any trackless 2-server algorithm can use at any given time. This particular diagram illustrates Trackless Workfunction 2.1.100011
dist to s	2		0	1
1	1	0	1
0		0
	0	1	2
dist to r

Next Lesson