Speaker: Joan Boyar
University of Southern Denmark
Title: Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
Access graphs, which have been used previously in connection with competitive analysis to model locality of reference in paging, are considered in connection with relative worst order analysis. In this model, not surprisingly, Flush-When-Full is shown to be strictly worse than both Least-Recently-Used (LRU) and First-In-First-Out (FIFO on (essentially) any access graph. However, LRU is shown to be strictly better than FIFO on paths and cycles, even though they are equivalent on cycles under competitive analysis. In addition, LRU and FIFO are shown to be incomparable on some families of graphs which grow with the length of the sequences.
This is joint work with Sushmita Gupta and Kim Skak Larsen.