Load Balancing in Distributed Systems

TLDR

Distributed computing systems consist of heterogeneous processors with varying performance and reliability. The study aims to develop an algorithm that optimally assigns program modules to heterogeneous processors to minimize execution time or cost. The authors model distributed programs as tasks with precedence, probabilistic branching, and concurrency, and use a Markov decision theory–based algorithm to compute optimal task‑to‑processor assignments. The resulting algorithm is general and applicable to systems with any number of processors.

Abstract

In a distributed computing system made up of different types of processors each processor in the system may have different performance and reliability characteristics. In order to take advantage of this diversity of processing power, a modular distributed program should have its modules assigned in such a way that the applicable system performance index, such as execution time or cost, is optimized. This paper describes an algorithm for making an optimal module to processor assignment for a given performance criteria. We first propose a computational model to characterize distributed programs, consisting of tasks and an operational precedence relationship. This model alows us to describe probabilistic branching as well as concurrent execution in a distributed program. The computational model along with a set of seven program descriptors completely specifies a model for dynamic execution of a program on a distributed system. The optimal task to processor assignment is found by an algorithm based on results in Markov decision theory. The algorithm given in this paper is completely general and applicable to N-processor systems.