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.
Complete list of metadatas

https://hal.inria.fr/hal-00800412
Contributor : Grégory Mounié <>
Submitted on : Wednesday, March 13, 2013 - 4:21:35 PM
Last modification on : Saturday, July 27, 2019 - 1:15:12 AM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

325