Asymptotic Load Balancing Algorithm for Many Task Scheduling

Cloud computing can enable the unraveling of new scientific breakthroughs. We will eventually arrive to compute overwhelmingly large sizes of information, larger than we ever thought about it. Better scheduling algorithms are the key to process Big Data. This paper presents a load balancing scheduling algorithm for Many Task Computing using the computational resources from Cloud, in order to process a huge number of tasks with a finite number of resources. As such, the algorithm can be also used for Big Data, because it scales easily for big applications if we put a load balancing algorithm on top of virtual machines. We impose an upper bound of one for the maximum nodes that can carry an arbitrary job without executing it and we show that this statement holds by simulating the algorithm in MTS2 (Many Task Scheduling Simulator). We also show that the algorithm’s overlay performs even better when there are multiple nodes and we discuss about choosing the best local scheduling policy for the working nodes.