|
Archive@NYU >
Stern School of Business >
IOMS: Information Systems Working Papers >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2451/14184
|
| Title: | The Two Headed Disk: Stochastic Dominance of the Greedy Policy |
| Authors: | Seshadri, Sridhar
Rotem, Doron |
| Keywords: | Two headed disk
Seek time
Stochastic optimality
Analysis of algorithms |
| Issue Date: | 1995 |
| Publisher: | Stern School of Business, New York University |
| Series/Report no.: | IS-97-26 |
| Abstract: | In his paper "Should the two-headed disk be greedy? - Yes, it
should" Hofri defined a "greedy policy" as follows.
Assuming that the range 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 distance for uniform request probabilities and
conjectured that it stochastically dominates every other policy.
Stochastic dominance is of practical importance in this context as it
guarantees that a policy that optimizes expected seek distance also
guarantees optimal seek time. The main result of this paper is a proof
of Hofri's conjecture. The paper contains two proofs, the first
establishes the conjecture, and the second shows that if the seek
distance is stochastically minimized under a repositioning policy, then
the policy must be Hofri's greedy policy and the request distribution
must be uniform. |
| URI: | http://hdl.handle.net/2451/14184 |
| Appears in Collections: | IOMS: Information Systems Working Papers
|
All items in Faculty Digital Archive are protected by copyright, with all rights reserved.
|
