Fair scheduling of bag-of-tasks applications using distributed Lagrangian optimization

Rémi Bertin 1, 2 Sascha Hunold 1 Arnaud Legrand 1, * Corinne Touati 1, 2
* Auteur correspondant
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Large scale distributed systems typically comprise hundreds to millions of entities (applications, users, companies, universities) that have only a partial view of resources (computers, communication links). How to fairly and efficiently share such resources between entities in a distributed way has thus become a critical question. Although not all applications are suitable for execution on large scale distributed computing platform, ideal are the Bag-of-Tasks (BoT) applications. Hence a large fraction of jobs in workloads imposed on Grids is made of sequential applications submitted in the form of BoTs. Up until now, mainly simple mechanisms have been used to ensure a fair sharing of resources among these applications. Although these mechanisms are proved to be efficient for CPU-bound applications, they are known to be ineffective in the presence of network-bound applications. A possible answer resorts to Lagrangian optimization and distributed gradient descent. Under certain conditions, the resource sharing problem can be formulated as a global optimization problem, which can be solved by a distributed self-stabilizing supply and demand algorithm. In the last decade, this technique has been applied to design various network protocols (variants of TCP, multi-path network protocols, wireless network protocols) and even distributed algorithms for smart grids. In this article, we explain how to use this technique for fairly scheduling concurrent BoT applications with arbitrary communication-to-computation ratio on a Grid. Yet, application heterogeneity raises severe convergence and stability issues that did not appear in the previous contexts and need to be addressed by non-trivial modifications. The effectiveness of our proposal is assessed through an extensive set of complex and realistic simulations.
Type de document :
Article dans une revue
Journal of Parallel and Distributed Computing, Elsevier, 2013, 〈10.1016/j.jpdc.2013.08.011〉
Liste complète des métadonnées

Littérature citée [48 références]  Voir  Masquer  Télécharger

Contributeur : Arnaud Legrand <>
Soumis le : dimanche 13 octobre 2013 - 15:38:28
Dernière modification le : mardi 15 octobre 2013 - 11:14:27
Document(s) archivé(s) le : vendredi 7 avril 2017 - 10:11:02


Fichiers produits par l'(les) auteur(s)





Rémi Bertin, Sascha Hunold, Arnaud Legrand, Corinne Touati. Fair scheduling of bag-of-tasks applications using distributed Lagrangian optimization. Journal of Parallel and Distributed Computing, Elsevier, 2013, 〈10.1016/j.jpdc.2013.08.011〉. 〈hal-00872473〉



Consultations de
la notice


Téléchargements du document