@InProceedings{kallahalla:read-once,
  author = {Mahesh Kallahalla and Peter J. Varman},
  title = {Optimal Read-Once Parallel Disk Scheduling},
  booktitle = {Proceedings of the Sixth Workshop on Input/Output in Parallel
  and Distributed Systems},
  year = {1999},
  month = {May},
  pages = {68--77},
  publisher = {ACM Press},
  address = {Atlanta, GA},
  URL = {http://vibes.cs.uiuc.edu/IOPADS/Accepted/Kallahalla.ps},
  keywords = {disk scheduling, parallel I/O, pario-bib},
  abstract = {We present an optimal algorithm, L-OPT, for prefetching and I/O
  scheduling in parallel I/O systems using a read-once model of block
  reference. The algorithm uses knowledge of the next L block references,
  L-block lookahead, to schedule I/Os in an on-line manner. It uses a dynamic
  priority assignment scheme to decide when blocks should be prefetched, so as
  to minimize the total number of I/Os. The parallel disk model of an I/O
  system is used to study the performance of L-OPT. We show that L-OPT is
  comparable to the best on-line algorithm with the same amount of lookahead;
  the ratio of the length of its schedule to the length of the optimal schedule
  is within a constant factor of the best possible. Specifically, we show that
  the competitive ratio of L-OPT is $\Omega(\sqrt{MD/L})$ which matches the
  lower bound on the competitive ratio of any prefetching algorithm with
  L-block lookahead. In addition we show that when the lookahead consists of
  the entire reference string, L-OPT performs the minimum possible number of
  I/Os; hence L-OPT is the optimal off-line algorithm. Finally, using synthetic
  traces we empirically study the performance characteristics of L-OPT.}
}