THE 2-HEADED DISK - STOCHASTIC-DOMINANCE OF THE GREEDY POLICY

In his paper ''Should the two-headed disk be greedy? - Yes, it should' ' Hofri defined a ''greedy policy'' as follows. Assuming that the rang e of disk addresses is [0,1], a request at location x is served by the closest arm while the other arm jockeys to a new position, z, where z = (1/3)x or z = 2/3 + x/3 depending on whether x is larger or smaller than 1/2. Hofri proved that this policy minimizes the expected seek d istance for uniform request probabilities and conjectured that it stoc hastically dominates every other policy. Stochastic dominance is of pr actical importance in this context as it guarantees that a policy that optimizes expected seek distance also guarantees optimal seek time. T he main result of this paper is a proof of Hofri's conjecture. The pap er contains two proofs, the first establishes the conjecture, and the second shows that if the seek distance is stochastically minimized und er a repositioning policy, then the policy must be Hofri's greedy poli cy and the request distribution must be uniform.