Modern disk drives have the capability of reordering I/O requests in order to minimize the mechanical motion (and hence time) associated with servicing the requests. Assume that we are given a set of N I/O requests which are chosen in accordance with some reasonable distribution. One may naturally ask for:
In 1995 Andrews, Bender, and Zhang were able to make considerable progress on the first problem. They showed that in the idealized case in which the read/write disk head can instantaneously accelerate (decelerate) from (to) rest to (from) maximal speed, a polynomial time algorithm (reasonable running time) exists for finding the optimal ordering of requests. This is known as the linear seek function case. In the more general (realistic) case in which the disk head experiences real acceleration and deceleration they were able to show that the problem is NP complete (difficult to solve) but were also able to present an algorithm which orders the requests in such a way that the total service time is at most 50% larger than the optimum.
In our work we try to consider both problems at once. We show that for linear seek functions the distribution of the service time is essentially equivalent to that of the longest increasing subsequence of of points in a diamond (a square tilted by 45 degrees). Approximation to the first order for such problems is then obtained via work of Deuschel and Zeitouni on the size of maximal increasing subsequences for points generated by general distributions in the unit square. Second order information can likewise be obtained via the results of Baik, Deift and Johansson on the length of the maximal increasing subsequence and results of Johansson on the width of the maximal increasing subsequence. To describe the asymptotic behavior of the service time for more general seek functions we introduce a notion of generalized increasing subsequences. For such sequences, even the analog of Ulam's conjecture is currently unknown. We provide elementary order of magnitude estimates for the size of the maximal such sequence. Talagrand's isoperimetric inequalities still apply to generalized subsequences and we use the associated concentration of measure to show that the maximal sequence lies in the vicinity of the diagonal. This information is then exploited to establish for every epsilon > 0 a polynomial time algorithm which with probability approaching 1 (as N tends to infinity) provides an ordering whose associated service time is a multiplicative factor of at most 1 + epsilon from optimal.
The talk will present these developments and will assume no knowledge
of computer science jargon. At the end we will present some of the
remaining mathematical and algorithmic challenges, in particular we hope
to advertise the study of generalized increasing subsequences in view of
the very concrete motivation.