Skip to Main content Skip to Navigation
New interface
Journal articles

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 metadata
Contributor : Grégory Mounié Connect in order to contact the contributor
Submitted on : Wednesday, March 13, 2013 - 4:21:35 PM
Last modification on : Tuesday, August 30, 2022 - 5:14:20 PM

Links full text



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



Record views