The two headed disk: Stochastic dominance of the greedy policy

S. Seshadri, D. Rotem

Research output: Contribution to journalArticlepeer-review

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 2 = 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.

Original languageEnglish (US)
Pages (from-to)273-277
Number of pages5
JournalInformation Processing Letters
Volume57
Issue number5
DOIs
StatePublished - Mar 11 1996
Externally publishedYes

Keywords

  • Analysis of algorithms
  • Seek time
  • Stochastic optimality
  • Two headed disk

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'The two headed disk: Stochastic dominance of the greedy policy'. Together they form a unique fingerprint.

Cite this