@Article{kallahalla:buffer-management,
  author = {M. Kallahalla and P. J. Varman},
  title = {Analysis of simple randomized buffer management for parallel I/O},
  journal = {Information Processing Letters},
  year = {2004},
  month = {April},
  volume = {90},
  number = {1},
  pages = {47--52},
  institution = {Hewlett Packard Labs, 1501 Page Mill Rd, Palo Alto, CA 94304
  USA; Hewlett Packard Labs, Palo Alto, CA 94304 USA; Rice Univ, Dept ECE,
  Houston, TX 77005 USA},
  publisher = {Elsevier Science},
  copyright = {(c)2004 Institute for Scientific Information, Inc.},
  URL = {http://dx.doi.org/10.1016/j.ipl.2004.01.009},
  keywords = {parallel I/O, prefetching, data placement, caching, buffer
  management, analysis, algorithms, randomization, pario-bib},
  abstract = {Buffer management for a D-disk parallel I/O system is considered
  in the context of randomized placement of data on the disks. A simple
  prefetching and caching algorithm PHASE-LRU using bounded lookahead is
  described and analyzed. It is shown that PHASE-LRU performs an expected
  number of I/Os that is within a factor Theta(log D/log log D) of the number
  performed by an optimal off-line algorithm. In contrast, any deterministic
  buffer management algorithm with the same amount of lookahead must do at
  least Omega(rootD) times the number of I/Os of the optimal. (C) 2004 Elsevier
  B.V. All rights reserved.}
}