Gossip-based dynamic load balancing in a self-organized autonomous desktop grid

Abstract

This paper presents a decentralized scheduling algorithm for dynamic load balancing in a self-organized desktop Grid environment. The proposed desktop Grid system allows volunteer nodes to join or leave freely at runtime, whereas user tasks can be launched at any node and make best use of computing resources by transparent process migration. To achieve rapid aggregation of runtime load information, we design an efficient gossip-based protocol based on an unstructured peer-to-peer dynamic network. The decentralized scheduling algorithm allows each node to determine which tasks to be relocated autonomously for achieving load balancing. Our autonomous scheduling solution can avoid the reassignment conflict problem, where different local schedulers may decide to migrate their process(es) to the same target node, by a process selection method based on game theory. The simulation results demonstrate that our solution can excel the centralized greedy scheduling algorithm and can perform as well as a meta-heuristic algorithm, while retaining small migration overhead.