Scheduling and load balancing for distributed computing systems

This research comprehensively examines dynamic task scheduling for distributed systems, concentrating on shared, heterogeneous networks and systems where reliability and availability are critical factors. The problems we investigate are unique to distributed systems scheduling and require approaches such as load sharing and load balancing that differ from traditional uniprocessor scheduling concepts. The main areas of our contributions include: mathematical analysis of scheduling metrics and system models; development, simulation and performance evaluation of adaptive load balancing algorithms for distributed computing; and the implementation of experimental scheduling protocols on heterogeneous networked systems.; Specifically, this research leads to the proposal and evaluation of a new performance metric and a new workload index; derivation and experimental corroboration of an abstract model for fault-tolerant parallel systems; presentation and evaluation of a novel algorithm for adaptive load balancing; and the construction of an experimental framework for resource management studies into load distribution policies.; The new performance metric, system variation, is found to be an effective indicator of the degree of load imbalance in a system. The workload index we propose, residual load capacity, and its associated dynamic balancing strategy enhance system performance in a heterogeneous environment. The abstract model is shown to accurately predict the performance of our fault-tolerant resource manager for programs that may experience processor failures. Our new adaptive balancing algorithm outperforms classical dynamic algorithms when presented with heterogeneous arrival rates; it demonstrates considerable robustness and adaptability to changing system conditions. For all of these experiments, the resource management tool has proven to be a useful framework for the investigation of new scheduling metrics and strategies.