Asymptotic Analysis of Probabilistic Scheduling for Erasure-Coded Heterogeneous Systems

Rooji Jinan, Gaurav Gautam, Parimal Parag, Vaneet AggarwalSIGMETRICS Perform. Evaluation Rev 2023 · DOI · OpenReview

Abstract

We consider (k, k) fork-join scheduling on a large number (say, N) of parallel servers with two sets of heterogeneous rates. An incoming task is split into k sub-tasks and dispatched to k servers according to a probabilistic selection policy, with parameter ps being the selection probability of slower servers. Mean task completion time admits an integral form, and thus it is analytically intractable to compute ps that minimizes it. In this work, we provide an upper bound on the mean task completion time, and determine ps that minimizes this upper bound. Numerically, this choice has been shown to be near-optimal.
BibTeX
@article{jinan2023asymptotic,
  author = {Rooji Jinan and Gaurav Gautam and Parimal Parag and Vaneet Aggarwal},
  title = {{Asymptotic Analysis of Probabilistic Scheduling for Erasure-Coded Heterogeneous Systems}},
  journal = {SIGMETRICS Perform. Evaluation Rev.},
  year = {2023},
  doi = {10.1145/3595244.3595248},
}
Figure