Scheduling Different Types of Linear Workflows with Partial Computations in a Distributed System

In distributed systems, along with generic jobs which can run on any distributed processor, there exist also some local jobs which need to run in a subset of the distributed processors for data locality reasons. In such environments, it is particularly challenging to employ effective scheduling techniques in order to avoid long delays of local jobs due to generic jobs execution and to reach the required level of Quality of Service (QoS). To achieve this goal, imprecise computation of generic jobs is permitted under certain conditions. In this research all jobs, generic and local, have a linear workflow structure and they are processed in a cluster of distributed processors. Thus, jobs are linear workflows (LWs). Local LWs can run on a part of the processors only, while generic LWs jobs may run on any processor of the whole distributed system. Scheduling techniques based on imprecise computations are employed to the generic LWs. Extensive simulation experiments are carried out to evaluate their performance. The results demonstrate that the partial computation of generic LW jobs contribute beneficially to performance under different scenarios of percentage of local jobs and load conditions.