Fair scheduling of bag-of-tasks applications on large-scale platforms

• We present a scheduling model for fair resource sharing on large-scale platforms.
• It effectively aggregates information about application stretch.
• Task allocation is performed so that the maximum stretch is minimized.
• Our model is able to perform similar to a centralized implementation.
• The management overhead is bounded.

Users of distributed computing platforms want to obtain a fair share of the resources they use. With respect to the amount of computation, the most suitable measure of fairness is the stretch. It describes the slowdown that the applications suffer for being executed in a shared platform, in contrast to being executed alone. In this paper, we present a decentralized scheduling policy that minimizes the maximum stretch among user-submitted applications. With two reasonable assumptions, that can be deduced from existing system traces, we are able to minimize the stretch using only local information. In this way, we avoid a centralized design and provide scalability and fault tolerance. As a result, our policy performs just 11% worse than a centralized implementation, and largely outperforms other common policies. Additionally, it easily scales to hundreds of thousands of nodes. We presume that it can scale to millions with a minimal overhead. Finally, we also show that preemption is crucial to provide fairness in any case.