CSC 789 Assignment 5

Due date: Thursday, March 19, 2009

Since this homework assignment is more than twice as difficult (and counts more than twice as much) as any previous assignment, I suggest you get started earlier than usual.
  1. Work Exercise 6.6, that is, prove that the Manhattan Plane is isometric to the plane with the l metric.
  2. Work Exercise 6.10. You may not assume the result of Exercise 6.9 unless you prove it.
  3. Let M={x,y,z} where d(x,y)=6, d(x,z)=7, and d(y,z)=9. Consider the 2-server problem on M, where the initial position of the servers is {x,y}.
    1. Suppose the request sequence is z x. If we use HARMONIC, what is the probability that we have a server at y after servicing that sequence?
    2. Suppose the request sequence is z x. If we use Random-Slack, what is the probability that we have a server at y after servicing that sequence?
    3. Suppose the request sequence is z x y x, and we use the work function algorithm. What is the optimum offline cost of servicing that sequence? If we use the work function algorithm, what are our moves, and what is our cost? Show the table of work function values (or offset function values) at each step.
    4. Suppose the request sequence is z x y x, and we use the tight span algorithm. What are our moves, and what is our cost? Show the positions of the servers and the virtual servers in the tight span of M at each step.
    5. Suppose that the request sequence is z x y x, and we use BALANCE_2, the Irani-Rubinfeld algorithm. What is our cost? Show the positions of the servers and the values of the needed variables at each step.
    6. Suppose that the request sequence is z x y x, and we use BALANCE_SLACK. What is our cost? Show the positions of the servers and the values of the needed variables at each step.
  4. Suppose someone had a proof that the k-server conjecture holds for Rn with the l metric, for every n. Prove that the k-server conjecture would be true.
  5. Work Exercises 9.1, 9.2, 9.3, and 9.4.
  6. Compute the competitiveness of EQUITABLE if k=3 and n=5, that is, there are a total of 5 pages in the universe in main memory. Your solution should show the graph with the offset functions and the distributions, the costs and the potentials.
    Hint: the anwer is H2 = 11/6.