Promoting Cooperation in Selfish Computational Grids

Abstract : In distributed computing, the recent paradigm shift from centrally-owned clusters to organizationally distributed computational grids introduces a number of new challenges in resource management and scheduling. In this work, we study the problem of Selfish Load Balancing which extends the well-known load balancing (LB) problem to scenarios in which each processor is concerned only with the performance of its local jobs. We propose a simple mathematical model for such systems and a novel function for computing the cost of the execution of foreign jobs. Then, we use the game-theoretic framework to analyze the model in order to compute the expected result of LB performed in a grid formed by two clusters. We show that, firstly, LB is a socially-optimal strategy, and secondly, for similarly loaded clusters, it is sufficient to collaborate during longer time periods in order to make LB the dominant strategy for each cluster. However, we show that if we allow clusters to make decisions depending on their current queue length, LB will never be performed. Then, we propose a LB algorithm which balances the load more equitably, even in the presence of overloaded clusters. Our algorithms do not use any external forms of compensation (such as money). The load is balanced only by considering the parameters of execution of jobs. This analysis is assessed experimentally by simulation, involving scenarios with multiple clusters and heterogeneous load.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2009, 199, pp.647-657. 〈10.1016/j.ejor.2007.06.067〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00800412
Contributeur : Grégory Mounié <>
Soumis le : mercredi 13 mars 2013 - 16:21:35
Dernière modification le : jeudi 11 janvier 2018 - 06:22:01

Lien texte intégral

Identifiants

Collections

Citation

Krzysztof Rzadca, Denis Trystram. Promoting Cooperation in Selfish Computational Grids. European Journal of Operational Research, Elsevier, 2009, 199, pp.647-657. 〈10.1016/j.ejor.2007.06.067〉. 〈hal-00800412〉

Partager

Métriques

Consultations de la notice

249