Paper Info
Title
Dynamic load balancing in distributed real-time systems (abstract)
Abstract
In this study, load balancing aspect of distributed real-time systems subject to dynamic changes is discussed. Real-time distributed systems, especially in applications such as automated/computerized factory environment, are often prone to load changes through out their long operational life period. Load changes in such systems may be deterministic as well as random.Three types of changes are possible. (1) the existing modules constituting such systems may complete their mission at a point in time and terminate. (2) some other modules may have lend themselves into existence triggered by a signal or a call from another module. (2) some modules may undergo significant increase or reductions in the volume of execution and/or communication requirements. These changes can upset the existing balance in load distribution over the system, thus prolong the tasks involved. The objective is thus to investigate near optimal heuristic solutions to handle the problem for n-module and m-processor applications.The optimal solution to the problem of load balancing is so far found NP-hard for more than 3 processors. A survey of studies in the field of load balancing has shown that heuristic methods can give near optimal or in some cases optimal results.In our study, the load requirements of a m-module and n-processor distributed system, where m can be greater than n, are decomposed into phases. Each phase is assumed to be relatively balanced. An incremental heuristic refinement algorithm is used to find near optimal solution within a single phase. The algorithm is being extended to cover multiphase case.The results of experiments on the incremental heuristic refinement algorithm have shown 60% optimal results over 313 different runs.Key words: Load balancing, distributed realtime system, graph theoretic, linear and nonlinear programming, NP-hard, incremental heuristic refinement algorithm.
Year
DOI
Venue
1990
10.1145/100348.100460
ACM Conference on Computer Science
Keywords
Field
DocType
optimal heuristic solution,near optimal,optimal result,load change,load balancing,load requirement,optimal solution,load distribution,cases optimal result,dynamic load balancing,incremental heuristic refinement algorithm,real-time system,distributed system,real time,load balance,nonlinear programming
Graph,Heuristic,Mathematical optimization,Computer science,Load balancing (computing),Single phase,Nonlinear programming,Real-time computing,Upset,Factory environment,Dynamic load balancing,Distributed computing
Conference
ISBN
Citations 
PageRank 
0-89791-348-5
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
M. Bozyigit1234.35
M. Melhi2131.13