Non-Cooperative Scheduling of Multiple Bag-of-Task Applications

Arnaud Legrand 1, 2 Corinne Touati 1, 2
2 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Multiple applications that execute concurrently on heterogeneous platforms compete for CPU and network resources. In this paper we analyze the behavior of $K$ non-cooperative schedulers using the optimal strategy that maximize their efficiency while fairness is ensured at a system level ignoring applications characteristics. We limit our study to simple single-level master-worker platforms and to the case where each scheduler is in charge of a single application consisting of a large number of independent tasks. The tasks of a given application all have the same computation and communication requirements, but these requirements can vary from one application to another. In this context, we assume that each scheduler aims at maximizing its throughput. We give closed-form formula of the equilibrium reached by such a system and study its performance. We characterize the situations where this Nash equilibrium is optimal (in the Pareto sense) and show that even though no catastrophic situation (Braess-like paradox) can occur, such an equilibrium can be arbitrarily bad for any classical performance measure.
Liste complète des métadonnées

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00153577
Contributor : Corinne Touati <>
Submitted on : Monday, June 11, 2007 - 4:06:51 PM
Last modification on : Thursday, October 11, 2018 - 8:48:02 AM
Document(s) archivé(s) le : Thursday, April 8, 2010 - 7:34:12 PM

Files

infocom.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00153577, version 1
  • ARXIV : 0706.1614

Collections

Citation

Arnaud Legrand, Corinne Touati. Non-Cooperative Scheduling of Multiple Bag-of-Task Applications. INFOCOM, May 2007, Anchorage, Alaska. ⟨inria-00153577⟩

Share

Metrics

Record views

360

Files downloads

194