Comment on the Model:
The camera-ready version of this paper incorrectly asserts that Amazon S3 service latency can be "accurately" modeled via an exponential distribution. In fact, as shown in http://arxiv.org/abs/1307.8083 and http://arxiv.org/abs/1301.1294, an accurate model of the chunk downloading time of Amazon S3 is a constant delay plus an i.i.d. exponentially distributed random variable.
Under the assumption that the chunk downloading time is i.i.d. exponentially distributed, we have proven that a greedy scheduling policy is delay-optimal among all on-line scheduling policies for any arrival process of the file read requests. This does not imply that the greedy scheduling policy is delay-optimal for the Amazon S3 traces. The optimal scheduling policy under non i.i.d. exponential latency distributions (e.g., those from Amazon S3) remains open. The updated version of the paper that reflects these changes, and their implication on designing scheduling policies can be found at http://arxiv.org/abs/1404.6687.