Fault Tolerant PLBGSA: Precedence Level Based Genetic Scheduling Algorithm for P2P Grid

Due to monetary limitation, small organizations cannot afford high end supercomputers to solve highly complex tasks. P2P (peer to peer) grid computing is being used nowadays to break complex task into subtasks in order to solve them on different grid resources. Workflows are used to represent these complex tasks. Finishing such complex task in a P2P grid requires scheduling subtasks of workflow in an optimized manner. Several factors play their part in scheduling decisions. The genetic algorithm is very useful in scheduling DAG (directed acyclic graph) based task. Benefit of a genetic algorithm is that it takes into consideration multiple criteria while scheduling. In this paper, we have proposed a precedence level based genetic algorithm (PLBGSA), which yields schedules for workflows in a decentralized fashion. PLBGSA is compared with existing genetic algorithm based scheduling techniques. Fault tolerance is a desirable trait of a P2P grid scheduling algorithm due to the untrustworthy nature of grid resources. PLBGSA handles faults efficiently. 1. Introduction As the complexity of computational problems is increasing continuously, efficient use of computational resources becomes vital. Complex tasks are causing bottlenecks in performance throughout the technical arena. Organizations around the world use high-end computational devices, servers, and supercomputers to handle complex tasks. However, all organizations are not able to purchase such devices because of budget constraints. Grid computing has come up as a crusader to solve a highly complex task [1, 2]. Grid utilizes existing heterogeneous computational devices spread across multiple geographical locations [3]. This unification of computational resources yields manifold increase in computational capabilities. Initially central scheduler based scheduling algorithms were used by researchers to solve complex problems [4]. These techniques were effective in scheduling [5] complex task; however, they have many limitations, like the fact that failure of central scheduler causes collapse of the entire grid [6]. Limited capabilities of the central scheduler give way to scalability issues. Policies vary from company to company and political issues also caused the existence of central scheduler problematic [6]. Metascheduler deals with limitations of central scheduler to some extent [7]. In metascheduling, all clusters have their personal scheduler. DAG based tasks [8] are scheduled over the most capable cluster. Problem with global task scheduling arises when no cluster is capable of executing complex