Analysis of a General Mass Storage System
Don Coppersmith, D. Stott Parker, C. K. Wong · SIAM Journal on Computing · 1982
A model of a general mass storage system is presented and its performance analyzed. The system is composed of a square two-dimensional grid of storage cells over which a single read/write head moves freely. The head can contain at most some fixed number b of cell contents. Algorithms for realizing an arbitrary permutation of the memory contents are presented for all ranges of b, particularly the important case $b = 1$; in each case the algorithms’ performances are explicitly characterized. Open problems, especially regarding the development of good heuristics, are then discussed.