@InProceedings{armen:disk-model,
  author = {Chris Armen},
  title = {Bounds on the Separation of Two Parallel Disk Models},
  booktitle = {Proceedings of the Fourth Workshop on Input/Output in Parallel
  and Distributed Systems},
  year = {1996},
  month = {May},
  pages = {122--127},
  publisher = {ACM Press},
  address = {Philadelphia},
  keywords = {parallel I/O, theory, parallel I/O algorithm, pario-bib},
  abstract = {The single-disk, D-head model of parallel I/O was introduced by
  Agarwal and Vitter to analyze algorithms for problem instances that are too
  large to fit in primary memory. Subsequently Vitter and Shriver proposed a
  more realistic model in which the disk space is partitioned into D disks,
  with a single head per disk. To date, each problem for which there is a known
  optimal algorithm for both models has the same asymptotic bounds on both
  models. Therefore, it has been unknown whether the models are equivalent or
  whether the single-disk model is strictly more powerful. \par In this paper
  we provide evidence that the single-disk model is strictly more powerful. We
  prove a lower bound on any general simulation of the single-disk model on the
  multi-disk model and establish randomized and deterministic upper bounds. Let
  $N$ be the problem size and let $T$ be the number of parallel I/Os required
  by a program on the single-disk model. Then any simulation of this program on
  the multi-disk model will require $\Omega\left(T \frac{\log(N/D)}{\log
  \log(N/D)}\right)$ parallel I/Os. This lower bound holds even if replication
  is allowed in the multi-disk model. We also show an $O\left(\frac{\log
  D}{\log \log D}\right)$ randomized upper bound and an $O\left(\log D (\log
  \log D)^2\right)$ deterministic upper bound. These results exploit an
  interesting analogy between the disk models and the PRAM and DCM models of
  parallel computation.}
}