@Article{varman:bounds,
  author = {Peter J. Varman and Rakesh M. Verma},
  title = {Tight Bounds for prefetching and Buffer Management Algorithms for
  Parallel {I/O} Systems},
  journal = {IEEE Transactions on Parallel and Distributed Systems},
  year = {1999},
  month = {December},
  volume = {10},
  number = {12},
  pages = {1262--1275},
  URL = {http://ieeexplore.ieee.org/iel5/71/17782/00819948.pdf},
  keywords = {parallel I/O, prefetching, pario-bib},
  abstract = {The I/O performance of applications in multiple-disk systems can
  be improved by overlapping disk accesses. This requires the use of
  appropriate prefetching and buffer management algorithms that ensure the most
  useful blocks are accessed and retained in the buffer. In this paper, we
  answer several fundamental questions on prefetching and buffer management for
  distributed-buffer parallel I/O systems. First, we derive and prove the
  optimality of an algorithm, P-min, that minimizes the number of parallel
  I/Os. Second, we analyze P-con, an algorithm that always matches its
  replacement decisions with those of the well-known demand-paged MIN
  algorithm. We show that P-con can become fully sequential in the worst case.
  Third, we investigate the behavior of on-line algorithms for multiple-disk
  prefetching and buffer management. We define and analyze P-Iru, a parallel
  version of the traditional LRU buffer management algorithm. Unexpectedly, we
  find that the competitive ratio of P-Iru is independent of the number of
  disks. Finally, we present the practical performance of these algorithms on
  randomly generated reference strings. These results confirm the conclusions
  derived from the analysis on worst case inputs.}
}