CSC 789 Assignment 7

Due date: Thursday, April 30, 2009

  1. Work through all the exercises in the Trackless Server Problem Tutorial, Lessons II through IV.
  2. (Easy.) Use trackless work functions to design a trackless online algorithm for the 2-server problem in M2,4, and prove that it is 2-competitive.
  3. Every deterministic trackless algorithm can be described using trackless work functions. Thus, LRU can be described using trackless work functions.
    1. The domain of a trackless work function for the 2-paging problem has three points. (If we adopt the rule that the two pages in a cache must be different, the domain of a black trackless work function has only two points, while the domain of a red trackless work function has at most three points.) This is quite different from the domain of an ordinary work function, which is infinite.
      You should be able to see this easily, since the 2-paging problem is the same as the 2-server problem in a uniform space.
    2. What is the domain of a trackless work function for the 3-paging problem? (Hint: if we assume that a cache never contains duplicate pages, the domain of a black trackless work function has four points, while the domain of a red trackless work function has at most seven points. It might be difficult to draw a nice figure like we can for the 2-server problem.)
    3. Describe LRU for the 3-paging problem in terms of trackless work functions.
  4. Work Exercise 12.1 in the trackless algorithms handout. postscript form pdf form