On scheduling redundant requests with cancellation overheads
Reducing latency in distributed computing and data storage systems is gaining increasing importance. Several empirical works have reported on the efficacy of scheduling redundant requests in such systems. That is, one may reduce job latency by 1) scheduling the same job at more than one server and 2) waiting only until the fastest of them responds. Inspired by the empirically observed gains of such schemes, several theoretical models have been proposed to explain the power of using redundant requests. Although the proposed models in the literature provide useful insights such as when scheduling redundant requests can be beneficial, all these results rely heavily on a common assumption: all redundant requests of a job can be immediately cancelled as soon as one of them is completed.